More on "Component Programming"

[bearophile]

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