Thoughts on laziness (long)

[Richard Carlsson]

On Mon, 23 Oct 2000 matthias@REDACTED wrote:

>  > They should perform better in native code compared to ETS than
>  > under the BEAM emulator, but in general the complexity of the
>  > algorithms would remain the same.
> 
> I remember reading that the 'Mercury' people hoped to be able to
> perform complexity reducing source->source transforms. Does HIPE do
> that, or does the potential (I read "in general" to mean "there are
> some cases where we can do better". That may have been reading too
> much into what you wrote.) come from 'striking it lucky' when doing
> (local) optimisations on object code?

What I meant by that slightly opaque remark was that there are a number of
things we want to do in HiPE that are not being done today, such as type
analysis (in order to remove some runtime type tests), function inlining
and other optimizations on high-level intermediate code (Core Erlang),
using multiple return values instead of building intermediate heap objects
("{X, Y, Z} = foo(...), bar(X, Y, Z)"), and even partial evaluation.
However, these things all give linear speedup (no matter how lucky you
get). There *exist* some transformations which can give superlinear
speedup (i.e., changing the complexity), but typically, these are
difficult to control (you don't want your compiler to give unexpected code
size explosions) and are not necessarily useful for typical programs. They
are interesting, but are not a priority for us right now.

	/Richard Carlsson


Richard Carlsson (richardc@REDACTED)   (This space intentionally left blank.)
E-mail: Richard.Carlsson@REDACTED	WWW: http://www.csd.uu.se/~richardc/