Walter Bright:
There are several optimizations that D/DMD is not performing
on those ranges and
higher order functions. The Haskell compiler GHC optimized
that stuff using
purity, library defined "rewrite rules", stream
fusion/deforestation and more.
DMD does nothing of this, or very little. I think so far
Walter has shown no
interest in this.
I don't really know what you're talking about.
Then maybe you have missed the last two times I have discussed
such topics in D.learn. They are optimizations done by compilers
of functional languages, in particular the GHC compiler of the
lazy functional language Haskell.
The optimizations performed thanks to purity and immutability are
needed by GHC because in Haskell you use Higher Order Functions
(HOFs), and generally you use functions as first class immutable
values, so if you don't inline a lot, your Haskell program will
be slow as a snail.
The "rewrite rules" is a feature of the GHC compiler. It allows
the library writers to define rules that in most (or many) cases
are advantageous and lead to better optimization. As example one
of such rules swap map and filter, putting the filter before the
map, because this is more efficient. Haskell allows you to
perform such swapping because (nearly) everything it does is pure
and immutable.
Some examples and explanations on the GHC rewrite rules:
http://www.haskell.org/ghc/docs/7.0.1/html/users_guide/rewrite-rules.html
http://www.haskell.org/haskellwiki/GHC/Using_rules
http://www.haskell.org/haskellwiki/Playing_by_the_rules
Stream fusion, or more generally deforestation is another
optimization done by GHC, it's needed because it's a functional
language that uses lists all the time, and such optimization are
helped by Haskell default lazyness (deforestation is possible in
an eager language too, but it's a bit less easy to do, they say).
If you perform a map and then a filter and then another HOF you
are traversing lists all the time, and this is slow. Haskell
default strings currently are lists of chars, so you have to
optimize string operations well. To generate fast binaries GHC
"fuses" similar lazy streams, and avoids creating all the
intermediate lists.
With this optimization recently GHC has shown to generate good
enough vectorized SSE-aware binaries that are faster than naive C
code optimized by the vectorizing stages of the GCC optimizer,
and beaten only by very vector-intrinsics-heavy handwritten C
code:
http://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/haskell-beats-C.pdf
But that's not a paper to start reading about such topics,
because that's a late paper on the topic.
More on the topic:
http://www.randomhacks.net/articles/2007/02/10/map-fusion-and-haskell-performance
On the topic there are both easy to understand and harder to
understand papers. So you have to choose.
Bye,
bearophile
