7 ms·

Iterators and Streams in Rust and Haskell

167 points by psibi 9y ago

pklausler 9y ago
> But look again: C is taking 87 nanoseconds, while Rust and Haskell both take about 175 microseconds. It turns out that GCC it able to optimize this into a downward-counting loop, which drastically improves the performance. We can do similar things in Rust and Haskell to get down to nanosecond-level performance, but that's not our goal today. I do have to say: well done GCC. Downward-counting or not, it is simply impossible for GCC to generate code that executes all 1,000,000 iterations of the loop in 87ns. That would be 87 femtoseconds per iteration, on average. More likely, GCC figured out how to collapse the entire loop into a closed-form expression that is a function of the loop length.
- gpderetta 9y ago
  I.e. benchmarking is hard.
  - e12e 9y ago
    Being able to tell that a loop is gone shouldn't be too hard with a diff of the assembler output with optimizations on and off - at least for fairly trivial code.
- kccqzy 9y ago
  I don't think so. https://godbolt.org/g/GBZgER https://godbolt.org/g/GBZgER
  - nemetroid 9y ago
    Perhaps the entire call of the function was replaced by a constant, then.
    - mastax 9y ago
      Yep: https://godbolt.org/g/LCUah9 https://godbolt.org/g/LCUah9 calls_cheating(): movl $60, %eax ret
      - gizmo686 9y ago
        No. The "constant" is only provided at runtime from Haskell through its FFI. GCC has no opportunity to optimize that.
- gizmo686 9y ago
  I just tested this on my machine (gcc 5.4.0). At -O2, gcc produced normal looking assembly code. At -O3, gcc produced a monstrosity [0] that I don't feel like fully deciphering. However, from a brief glance, it does not appear to have created a closed form solution. Instead, it contains a single loop: .L4: addl $1, %edx paddd %xmm1, %xmm0 paddd %xmm2, %xmm1 cmpl %edx, %eax ja .L4 which seems to be using a SIMD instruction (paddd[1]) that adds does 4 32-bit integer additions in parallel. After this loop, it does some "housekeeping" (read, something I don't understand) before proceeding to an unwound version of the last iterations of the loop: leal 4(%rdx), %ecx addl %edx, %eax cmpl %ecx, %edi jl .L2 addl %ecx, %eax leal 8(%rdx), %ecx cmpl %ecx, %edi ... jl .L2 addl %ecx, %eax leal 28(%rdx), %ecx cmpl %ecx, %edi jl .L2 addl %ecx, %eax addl $32, %edx leal (%rax,%rdx), %ecx cmpl %edx, %edi cmovge %ecx, %eax ret Where .L2 is just: .L2: rep ret I assume that this is just some form of return, but the documentation I could find [2] seems to suggest that rep is a prefix for string operations, which doesn't make sense. [0]https://pastebin.com/raw/Y55gQG7p https://pastebin.com/raw/Y55gQG7p [1] http://x86.renejeschke.de/html/file_module_x86_id_226.html http://x86.renejeschke.de/html/file_module_x86_id_226.html [2] https://c9x.me/x86/html/file_module_x86_id_279.html https://c9x.me/x86/html/file_module_x86_id_279.html
  - gpderetta 9y ago
    the rep in rep ret is ignored, is just used for alignment; the 'housekeeping' code is to handle non-multiple of 8 loop counts. Still, unless I'm missing something, the code should be executing 8 adds per clock[2]; at 4ghz, that still above 1us for 500k adds. GCC doesn't seem to be able to fold the loop given a constant expression, unless the function is explicitly declared constexpr; in which case it will complain about the accumulator overflowing, but gcc doesn't seem to be taking advantage of it. Clang does not vectorize the loop but will replace it with a constant given a constant parameter. Bottom line, I'm not sure what's going on with the article's measurements. [2] potentially 12 for skylake or even 24 with avx.
  - implr 9y ago
    If you pass -march=skylake it will get even more monstrous, with AVX: https://godbolt.org/g/v7iKF3 https://godbolt.org/g/v7iKF3
- pcwalton 9y ago
  Another possibility is that GCC discovered that the loop had no side effects in the benchmark harness and eliminated it. This is a very common thing that happens in microbenchmarks.
  - gizmo686 9y ago
    The c code defines a function that returns the sum computed in the loop. This function is than run using Haskell's FFI. GCC has no way of knowing there is no side effects, because other code might link to it and use the result of the function. GHC, in concept, does know that there are no side effects, but that would apply to all of the functions being tested. Further, since it is using a benchmarking library, I assume the authors of said library were aware of the issue, and wrote it in such a way as to force evalutation of the function. https://gist.github.com/snoyberg/9b1c77b595c4adf90880213fc49f2a21#file-main-hs https://gist.github.com/snoyberg/9b1c77b595c4adf90880213fc49...
- adrianratnapala 9y ago
  I assume the 87 nanoseconds means the average per loop iteration, not all 1,000,000 iterations.
  - red75prime 9y ago
    It's unlikely. The entire loop should have taken 0.87 seconds then. That's a bit too much for several million operations, which don't seem to require memory access.
    - pklausler 9y ago
      0.087, but that still seems high.
iainmerrick 9y ago
I feel like the author has felt obliged to include the full results, which is noble, but it's mostly obscuring the interesting results. What does it matter if the "cheating" versions are faster, since they're doing something completely different? (OK, in principle it could be the same with an unrealistically magical optimizer.) Seems to me the key point is that a bunch of high-level constructs in both Rust and Haskell are very nearly as fast as a tight loop in C. That's great! The versions that are much slower don't seem very surprising, as they involve boxing the ints. (Edit to add: OK, reading more closely, I guess 'Haskell iterator 5' is interesting to dig into.)
- ozataman 9y ago
  No idea why people reacting here so far got fixated on the "cheating" versions - it's clear to me they were included mainly to set a maximal speed baseline/benchmark and are not the main point of the article.
  - iainmerrick 9y ago
    Well, the article starts with them and the chart starts with them! But the whole article would be better off without them.
  - runeks 9y ago
    I find the "cheating" versions peculiar because I don't see the purpose of it. What's the point, and in what way is it cheating? It's just a different algorithm, and doesn't add any useful information to the subject at hand.
    - chriswarbo 9y ago
      Numerical operations in a loop are often subject to aggressive optimisation by C compilers, which makes them tricky to use in benchmarks: are we measuring the intended loop, or has the work been optimised away? Often comparisons are made of "Blub vs C", where the C result is an order of magnitude smaller, and it's not clear if that's because C is fast or whether it's been optimised away. Including an "optimised away" version lets us know when this has happened: the "non-cheating" benchmarks take much longer than the "cheating" ones, so we can assume they've not been optimised away. I assume the author only went into detail about them because they're independently interesting, regardless of the main topic of the post.
runeks 9y ago
I find it really interesting that the idiomatic Haskell implementations (basically math) are the best-performing, while the Rust-like Haskell implementation (using an IORef) is orders of magnitude slower. This is exactly what I want: describe the logic of the operation, and leave the compiler to optimize for the hardware (in this case a CPU which mutates registers). The Rust implementation makes assumptions about the underlying hardware (has registers we can mutate), and is only about 15% faster than the Haskell implementation which makes no such assumptions. In essence, this is why I love Haskell, and choose it over Rust: it allows me to write my application logic directly, without having to think about it in terms of mutation, and have the generated code be pretty fast. If GHC becomes well-optimized enough it can render Rust obsolete, since "no runtime overhead" becomes pretty meaningless if it's actually slower than Haskell (e.g. using LinearTypes, which removes need for GC). Rust can't render Haskell obsolete, however, since Haskell's goal is basically allowing you to write logic directly, using types as propositions and values as proofs. So Haskell's goal is a qualitative one (execute logic) while Rust's is a quantitative one (performance/no runtime overhead), which results in Haskell being able to take the place of Rust if GHC gains sufficiently in performance.
- pjmlp 9y ago
  Not having issues with using a GC language is also a huge win. I can grasp Haskell without major issues, follow C++14 and C++17 meta-programming tricks, yet I still don't understand quite well how to deal with the borrow checker on Rust. Still haven't given up on it, but it shows the learning curve is a bit high, or then it is me that cannot wrap my head around it.
  - runeks 9y ago
    I'm not that familiar with Rust but, as far as I can see, it makes sense to say that Rust's borrow checker is an interface to a O(1) garbage collector (as fast as no GC at all), that the programmer has to implement at compile-time for all values. All the borrow checker-code is compiled into a no-runtime-overhead garbage collector, that is embedded into the resulting generated code. In the world of Haskell, the -> arrow embeds a GC (with runtime overhead) into the genrated code. A similar interface to Rust's borrow checker in Haskell (no runtime overhead) would be the ⊸ arrow from LinearTypes (in a future where GHC's GC is able to take advantage of this). It looks, to me, like the arrow (⊸) notation is a lot simpler inteface to a no-runtime-overhead garbage collector -- or the absense of a traditional GC, in other words -- than Rust's borrow checker. But I'm looking forward to seeing how it plays out (it will probably take years before it becomes reality).

167 points by psibi 9y ago

> But look again: C is taking 87 nanoseconds, while Rust and Haskell both take about 175 microseconds. It turns out that GCC it able to optimize this into a downward-counting loop, which drastically improves the performance. We can do similar things in Rust and Haskell to get down to nanosecond-level performance, but that's not our goal today. I do have to say: well done GCC. Downward-counting or not, it is simply impossible for GCC to generate code that executes all 1,000,000 iterations of the loop in 87ns. That would be 87 femtoseconds per iteration, on average. More likely, GCC figured out how to collapse the entire loop into a closed-form expression that is a function of the loop length.

gpderetta 9y ago
I.e. benchmarking is hard.
- e12e 9y ago
  Being able to tell that a loop is gone shouldn't be too hard with a diff of the assembler output with optimizations on and off - at least for fairly trivial code.
kccqzy 9y ago
I don't think so. https://godbolt.org/g/GBZgER https://godbolt.org/g/GBZgER
- nemetroid 9y ago
  Perhaps the entire call of the function was replaced by a constant, then.
  - mastax 9y ago
    Yep: https://godbolt.org/g/LCUah9 https://godbolt.org/g/LCUah9 calls_cheating(): movl $60, %eax ret
    - gizmo686 9y ago
      No. The "constant" is only provided at runtime from Haskell through its FFI. GCC has no opportunity to optimize that.
gizmo686 9y ago
I just tested this on my machine (gcc 5.4.0). At -O2, gcc produced normal looking assembly code. At -O3, gcc produced a monstrosity [0] that I don't feel like fully deciphering. However, from a brief glance, it does not appear to have created a closed form solution. Instead, it contains a single loop: .L4: addl $1, %edx paddd %xmm1, %xmm0 paddd %xmm2, %xmm1 cmpl %edx, %eax ja .L4 which seems to be using a SIMD instruction (paddd[1]) that adds does 4 32-bit integer additions in parallel. After this loop, it does some "housekeeping" (read, something I don't understand) before proceeding to an unwound version of the last iterations of the loop: leal 4(%rdx), %ecx addl %edx, %eax cmpl %ecx, %edi jl .L2 addl %ecx, %eax leal 8(%rdx), %ecx cmpl %ecx, %edi ... jl .L2 addl %ecx, %eax leal 28(%rdx), %ecx cmpl %ecx, %edi jl .L2 addl %ecx, %eax addl $32, %edx leal (%rax,%rdx), %ecx cmpl %edx, %edi cmovge %ecx, %eax ret Where .L2 is just: .L2: rep ret I assume that this is just some form of return, but the documentation I could find [2] seems to suggest that rep is a prefix for string operations, which doesn't make sense. [0]https://pastebin.com/raw/Y55gQG7p https://pastebin.com/raw/Y55gQG7p [1] http://x86.renejeschke.de/html/file_module_x86_id_226.html http://x86.renejeschke.de/html/file_module_x86_id_226.html [2] https://c9x.me/x86/html/file_module_x86_id_279.html https://c9x.me/x86/html/file_module_x86_id_279.html
- gpderetta 9y ago
  the rep in rep ret is ignored, is just used for alignment; the 'housekeeping' code is to handle non-multiple of 8 loop counts. Still, unless I'm missing something, the code should be executing 8 adds per clock[2]; at 4ghz, that still above 1us for 500k adds. GCC doesn't seem to be able to fold the loop given a constant expression, unless the function is explicitly declared constexpr; in which case it will complain about the accumulator overflowing, but gcc doesn't seem to be taking advantage of it. Clang does not vectorize the loop but will replace it with a constant given a constant parameter. Bottom line, I'm not sure what's going on with the article's measurements. [2] potentially 12 for skylake or even 24 with avx.
- implr 9y ago
  If you pass -march=skylake it will get even more monstrous, with AVX: https://godbolt.org/g/v7iKF3 https://godbolt.org/g/v7iKF3
pcwalton 9y ago
Another possibility is that GCC discovered that the loop had no side effects in the benchmark harness and eliminated it. This is a very common thing that happens in microbenchmarks.
- gizmo686 9y ago
  The c code defines a function that returns the sum computed in the loop. This function is than run using Haskell's FFI. GCC has no way of knowing there is no side effects, because other code might link to it and use the result of the function. GHC, in concept, does know that there are no side effects, but that would apply to all of the functions being tested. Further, since it is using a benchmarking library, I assume the authors of said library were aware of the issue, and wrote it in such a way as to force evalutation of the function. https://gist.github.com/snoyberg/9b1c77b595c4adf90880213fc49f2a21#file-main-hs https://gist.github.com/snoyberg/9b1c77b595c4adf90880213fc49...
adrianratnapala 9y ago
I assume the 87 nanoseconds means the average per loop iteration, not all 1,000,000 iterations.
- red75prime 9y ago
  It's unlikely. The entire loop should have taken 0.87 seconds then. That's a bit too much for several million operations, which don't seem to require memory access.
  - pklausler 9y ago
    0.087, but that still seems high.

iainmerrick 9y ago

I feel like the author has felt obliged to include the full results, which is noble, but it's mostly obscuring the interesting results. What does it matter if the "cheating" versions are faster, since they're doing something completely different? (OK, in principle it could be the same with an unrealistically magical optimizer.) Seems to me the key point is that a bunch of high-level constructs in both Rust and Haskell are very nearly as fast as a tight loop in C. That's great! The versions that are much slower don't seem very surprising, as they involve boxing the ints. (Edit to add: OK, reading more closely, I guess 'Haskell iterator 5' is interesting to dig into.)

ozataman 9y ago
No idea why people reacting here so far got fixated on the "cheating" versions - it's clear to me they were included mainly to set a maximal speed baseline/benchmark and are not the main point of the article.
- iainmerrick 9y ago
  Well, the article starts with them and the chart starts with them! But the whole article would be better off without them.
- runeks 9y ago
  I find the "cheating" versions peculiar because I don't see the purpose of it. What's the point, and in what way is it cheating? It's just a different algorithm, and doesn't add any useful information to the subject at hand.
  - chriswarbo 9y ago
    Numerical operations in a loop are often subject to aggressive optimisation by C compilers, which makes them tricky to use in benchmarks: are we measuring the intended loop, or has the work been optimised away? Often comparisons are made of "Blub vs C", where the C result is an order of magnitude smaller, and it's not clear if that's because C is fast or whether it's been optimised away. Including an "optimised away" version lets us know when this has happened: the "non-cheating" benchmarks take much longer than the "cheating" ones, so we can assume they've not been optimised away. I assume the author only went into detail about them because they're independently interesting, regardless of the main topic of the post.

runeks 9y ago

I find it really interesting that the idiomatic Haskell implementations (basically math) are the best-performing, while the Rust-like Haskell implementation (using an IORef) is orders of magnitude slower. This is exactly what I want: describe the logic of the operation, and leave the compiler to optimize for the hardware (in this case a CPU which mutates registers). The Rust implementation makes assumptions about the underlying hardware (has registers we can mutate), and is only about 15% faster than the Haskell implementation which makes no such assumptions. In essence, this is why I love Haskell, and choose it over Rust: it allows me to write my application logic directly, without having to think about it in terms of mutation, and have the generated code be pretty fast. If GHC becomes well-optimized enough it can render Rust obsolete, since "no runtime overhead" becomes pretty meaningless if it's actually slower than Haskell (e.g. using LinearTypes, which removes need for GC). Rust can't render Haskell obsolete, however, since Haskell's goal is basically allowing you to write logic directly, using types as propositions and values as proofs. So Haskell's goal is a qualitative one (execute logic) while Rust's is a quantitative one (performance/no runtime overhead), which results in Haskell being able to take the place of Rust if GHC gains sufficiently in performance.

pjmlp 9y ago
Not having issues with using a GC language is also a huge win. I can grasp Haskell without major issues, follow C++14 and C++17 meta-programming tricks, yet I still don't understand quite well how to deal with the borrow checker on Rust. Still haven't given up on it, but it shows the learning curve is a bit high, or then it is me that cannot wrap my head around it.
- runeks 9y ago
  I'm not that familiar with Rust but, as far as I can see, it makes sense to say that Rust's borrow checker is an interface to a O(1) garbage collector (as fast as no GC at all), that the programmer has to implement at compile-time for all values. All the borrow checker-code is compiled into a no-runtime-overhead garbage collector, that is embedded into the resulting generated code. In the world of Haskell, the -> arrow embeds a GC (with runtime overhead) into the genrated code. A similar interface to Rust's borrow checker in Haskell (no runtime overhead) would be the ⊸ arrow from LinearTypes (in a future where GHC's GC is able to take advantage of this). It looks, to me, like the arrow (⊸) notation is a lot simpler inteface to a no-runtime-overhead garbage collector -- or the absense of a traditional GC, in other words -- than Rust's borrow checker. But I'm looking forward to seeing how it plays out (it will probably take years before it becomes reality).