3 ms·

Something I've always wondered about Haskell is whether there is, in practice, rope for the compiler to optimize things away from the theoretical underlying imp

Something I've always wondered about Haskell is whether there is, in practice, rope for the compiler to optimize things away from the theoretical underlying implementation. For instance a C compiler is free to turn for (int i = 0; i < N; i++) { a[i] = 2*b[i]; } for (int i = 0; i < N; i++) { c[i] = 2*d[i]; } into for (int i = 0; i < N; i+=2) { a[i] = 2*b[i]; a[i+1] = 2*b[i+1]; c[i] = 2*d[i]; c[i+1] = 2*d[i+1]; } It seems like GHC ought to similarly be able to turn some foo :: [Int] -> [Int] into foo :: [(Int, Int)] -> [(Int, Int)] under the covers for a similar speedup as long as it can, as with the C compiler, handle the case of an odd length with a bit of extra code. There are limits to how much you can restructure a list that's exported outside the compilation unit (my Haskell knowledge is fuzzy here so that's probably not the right terminology). And if the list is being re-stitched in odd ways it might be a bad idea. But as far as I can tell it ought to be doable and useful in most common cases. Of course maybe it's already doing this in those cases where it can prove that it works and that's why Haskell performance generally is good but fragile.

haldean 9y ago
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.

haldean 9y ago

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.