3 ms·

Haskell performs a very cool optimization called "stream fusion" to deal with a whole class of traversal optimization problems; stream fusion removes intermedia

Haskell performs a very cool optimization called "stream fusion" to deal with a whole class of traversal optimization problems; stream fusion removes intermediate list results completely, and bundles a bunch of things that look like maps/reduces/filters into a single operation. Your example doesn't quite hit it, but a similar bit of code like: for (int i = 0; i < N; i++) a[i] = 2 * b[i]; for (int i = 0; i < N; i++) c[i] = 2 * a[i] + b[i]; t = 0; for (int i = 0; i < N; i++) if (b[i] % 2 == 0) t += c[i]; Would be rewritten to the equivalent of: t = 0; for (int i = 0; i < N; i++) if (b[i] % 2 == 0) t += 5 * b[i]; Lots more info on the GHC optimizations page: https://wiki.haskell.org/GHC_optimisations#Fusion https://wiki.haskell.org/GHC_optimisations#Fusion

Symmetry 9y ago
Yes, stream fusion is super nifty. But can Haskell alter the size of the chunks it's sending through the stream? There was a recent HN thread about how GNU 'yes' is so fast thanks to buffering. Obviously too large a buffer would blow out the cache and stream fusion avoids that but a moderate amount of buffering so that you're neither working array by array nor element by element but cachable chunk by cachable chunk should be a happy middle. And with Haskell lists reduce pointer chasing as well.
- haldean 9y ago
  I think that the issue you're describing about `yes` was around building a buffer and issuing one big write() syscall instead of a bunch of small ones. I'm not sure about the actual implementation of the IO monad, and whether or not it coalesces call to write(), but it would definitely be possible. Also, idiomatic Haskell would make large writes, because usually (at least in my experience) you create a large string/Text representing your output, and then putStrLn or print it all at once. In regards to assembling the stream: when the list is actually materialized, I assume it's done one element at a time, but the LLVM backend that GHC uses might be doing some loop unrolling, but I'm not sure. Stream fusion doesn't require that all of the streams be the same type, though! Elements at different points in the stream can have wildly different sizes. For example, this would be fused: sum . map length . map double $ ["hello", "Symmetry"] where double x = concat [x x] That will never materialize a list of Strings, even though at two points in the stream you had a stream of strings.
  - hydraz 9y ago
    GHC doesn't actually perform stream fusion. Not by default, anyway: The default (by that I mean "ships with base", not that it's baked into the compiler) is something weaker, called build/foldr fusion, described by this rule: foldr z f (build g) = g f z Foldr is the usual catamorphism for the inductive list type, and build is an "abstracted constructor", of sorts: build :: (forall b. (a -> b -> b) -> b -> b) -> [a] build f = f (:) [] Note that build's argument is rank-2 polymorphic, and also the same as foldr's type.

Symmetry 9y ago

Yes, stream fusion is super nifty. But can Haskell alter the size of the chunks it's sending through the stream? There was a recent HN thread about how GNU 'yes' is so fast thanks to buffering. Obviously too large a buffer would blow out the cache and stream fusion avoids that but a moderate amount of buffering so that you're neither working array by array nor element by element but cachable chunk by cachable chunk should be a happy middle. And with Haskell lists reduce pointer chasing as well.

haldean 9y ago
I think that the issue you're describing about `yes` was around building a buffer and issuing one big write() syscall instead of a bunch of small ones. I'm not sure about the actual implementation of the IO monad, and whether or not it coalesces call to write(), but it would definitely be possible. Also, idiomatic Haskell would make large writes, because usually (at least in my experience) you create a large string/Text representing your output, and then putStrLn or print it all at once. In regards to assembling the stream: when the list is actually materialized, I assume it's done one element at a time, but the LLVM backend that GHC uses might be doing some loop unrolling, but I'm not sure. Stream fusion doesn't require that all of the streams be the same type, though! Elements at different points in the stream can have wildly different sizes. For example, this would be fused: sum . map length . map double $ ["hello", "Symmetry"] where double x = concat [x x] That will never materialize a list of Strings, even though at two points in the stream you had a stream of strings.
- hydraz 9y ago
  GHC doesn't actually perform stream fusion. Not by default, anyway: The default (by that I mean "ships with base", not that it's baked into the compiler) is something weaker, called build/foldr fusion, described by this rule: foldr z f (build g) = g f z Foldr is the usual catamorphism for the inductive list type, and build is an "abstracted constructor", of sorts: build :: (forall b. (a -> b -> b) -> b -> b) -> [a] build f = f (:) [] Note that build's argument is rank-2 polymorphic, and also the same as foldr's type.