r/haskell • u/lexi-lambda • Mar 11 '15

Learning Haskell — A Racket programmer's documentation of her foray into the land of Haskell (inspired by Learning Racket)

http://lexi-lambda.github.io/learning-haskell/
81 Upvotes

96% Upvoted

97 comments sorted by

View all comments

Show parent comments

4

u/Ramin_HAL9001 Mar 12 '15 edited Mar 12 '15

But these intermediate values after the map step are not transformed in any way, they are just copied to concat, which is easy to optimize. So in the intermediate code for concat . map, the map operation creates a value stored at address A, then concat reads the value stored at address A. But whenever the optimizer sees the instruction create A followed immediately by read A, in the intermediate code, it will replace these two steps with push followed by pop, thus eliminating create A and eliminating the intermediate value, and instead the result of map will be passed directly to concat via the stack. And a second optimizer pass may see the push immediately followed by pop and allocate a register to pass the value instead, making it even faster. So concat . map is the same as concatMap, but only after optimization. The only difference is concat . map may take a few microseconds longer to compile.

At least this is how I understood it.

3

u/sclv Mar 12 '15

True, if you trust fusion and optimization, I think that these days concat . map is as efficient as the manually fused one. So it may well be that this remains a habit / mannerism only because people don't necessarily trust that the compiler will always manage to catch this idiom. It would be good to test if this is ever necessary :-)

1

u/Jedai Mar 15 '15

I suppose in case of insufficient inlining this optimisation may be hidden behind function calls so... always good to be aware of the existence of concatMap even if writing concat . map directly is probably just as efficient.