5 ms·

I wonder how well a simple C for loop with -O3 and maybe -march would do here. From my brief forays into reading (mostly AARCH64) assembly, it looks like C com

I wonder how well a simple C for loop with -O3 and maybe -march would do here. From my brief forays into reading (mostly AARCH64) assembly, it looks like C compilers can detect these kinds of patterns now and just convert them all to SIMD by themselves, with no work from the programmer. Even at -O2, converting an index-based loop into one based on start and end pointers is not unusual. Go doesn't seem to do this, the assembly output by the Go compiler looks much closer to the actual code than what you get from C. Rust iterators would also be fun to benchmark here, they're supposed to be as fast as plain old loops, and they're probably optimized to omit bounds checks entirely.

mratsim 3y ago
It depends. You need 2~3 accumulators to saturate instruction-level parallelism with a parallel sum reduction. But the compiler won't do it because it only creates those when the operation is associative, i.e. (a+b)+c = a+(b+c), which is true for integers but not for floats. There is an escape hatch in -ffast-math. I have extensive benches on this here: https://github.com/mratsim/laser/blob/master/benchmarks%2Ffp_reduction_latency%2Freduction_bench.nim#L336 https://github.com/mratsim/laser/blob/master/benchmarks%2Ffp...
- menaerus 3y ago
  In my experience, compilers rarely know how to make use of ILP even in some for what you would expect to be the "simple" cases. Handwriting the SIMD, at least in my case, almost always proved to be several times faster than the auto-vectorized code generated by the compiler.
  - mratsim 3y ago
    They do reorder instructions. I think the SIMD part has more to do with loop analysis than ILP. It's quite telling that there is a #pragma omp simd to hint to a compiler to rewrite the loop. Now I wonder what's the state of polyhedral compilers. It's been many years. And given the AI, LLMs hype they could really shine.
    - menaerus 3y ago
      > I think the SIMD part has more to do with loop analysis than ILP. If you know how to rewrite the algorithm in such a way so that it makes close-to-ideal utilization of CPU ports through your SIMD then it is practically impossible to beat it. And I haven't seen a compiler (GCC, clang) doing such a thing or at least not in the instances I had written. I've measured substantial improvements from such and similar utilization of CPU-level microarchitectural details. So perhaps I don't think it's the loop analysis only but I do think it's practically an impossible task for the compiler. Perhaps with the AI ...
- lifthrasiir 3y ago
  You don't necessarily need `-ffast-math` if you are willing to tweak your code a bit, since you can just introduce accumulators by yourself. Such optimizer-friendly code is not hard to write if you know basic principles.
  - mratsim 3y ago
    That's what I'm saying though. Either youbdo the accumulators yourself, or you need a compiler escape hatch.
    - lifthrasiir 3y ago
      I mean, you don't need SIMD to put accumulators.
      - mratsim 3y ago
        The compiler escape hatch is -ffast-math
steveklabnik 3y ago
> Rust iterators would also be fun to benchmark here I started to write this out, and then thought "you know what given how common this is, I bet I could even just google it" and thought that would be more interesting, as it makes it feel more "real world." The first result I got is what I would have written: https://stackoverflow.com/a/30422958/24817 https://stackoverflow.com/a/30422958/24817 Here's a godbolt with three different outputs: one at -O, one at -O3, and one at -03 and -march=native https://godbolt.org/z/6xf9M1cf3 https://godbolt.org/z/6xf9M1cf3 Eyeballing it comments: Looks like 2 and 3 both provide extremely similar if not identical output. Adding the native flag ends up generating slightly different codegen, I am not at the level to be able to simply look at that and know how meaningful the difference is. It does appear to have eliminated the bounds check entirely, and it's using xmm registers. I am pleasantly surprised at this output because zip in particular can sometimes hinder optimizations, but rustc did a great job here. ---------------------- For fun, I figured "why not also try as direct of the original Go as possible." The only trick here is that Rust doesn't really do the c-style for loop the way Go does, so I tried to translate what I saw as the spirit of the example: compare the two lengths and use the minimum for the loop length. Here it is: https://godbolt.org/z/cTcddc8Gs https://godbolt.org/z/cTcddc8Gs ... literally the same. I am very surprised at this outcome. It makes me wonder if LLVM has some sort of idiom recognition for dot product specifically. EDIT: looks like it does not currently, see the comment at line 28 and 29: https://llvm.org/doxygen/LoopIdiomRecognize_8cpp_source.html https://llvm.org/doxygen/LoopIdiomRecognize_8cpp_source.html
- camel-cdr 3y ago
  Those aren't vectorized at all, just unrolled. vmulss/vaddss just multiply/add the single-precision floating-point in the vector register. With clang you get basically the same codegen, although it uses fused multiply adds. The problem is that you need to enable -ffast-math, otherwise the compiler can't change the order of floating point operations, and thus not vectorize. With clang that works wonderfully and it gives us a lovely four times unrolled AVX2 fused multiply add loop, but enabling it in rust doesn't seem to work: https://godbolt.org/z/G4Enf59Kb https://godbolt.org/z/G4Enf59Kb Edit: from what I can tell this is still an open issue??? https://github.com/rust-lang/rust/issues/21690 https://github.com/rust-lang/rust/issues/21690 Edit: relevant SO post: https://stackoverflow.com/questions/76055058/why-cant-the-rust-compiler-auto-vectorize-this-fp-dot-product-implementation https://stackoverflow.com/questions/76055058/why-cant-the-ru... Apparently you need to use `#![feature(core_intrinsics)]`, `std::intrinsics::fadd_fast` and `std::intrinsics::fmul_fast`.

mratsim 3y ago

It depends. You need 2~3 accumulators to saturate instruction-level parallelism with a parallel sum reduction. But the compiler won't do it because it only creates those when the operation is associative, i.e. (a+b)+c = a+(b+c), which is true for integers but not for floats. There is an escape hatch in -ffast-math. I have extensive benches on this here: https://github.com/mratsim/laser/blob/master/benchmarks%2Ffp_reduction_latency%2Freduction_bench.nim#L336 https://github.com/mratsim/laser/blob/master/benchmarks%2Ffp...

menaerus 3y ago
In my experience, compilers rarely know how to make use of ILP even in some for what you would expect to be the "simple" cases. Handwriting the SIMD, at least in my case, almost always proved to be several times faster than the auto-vectorized code generated by the compiler.
- mratsim 3y ago
  They do reorder instructions. I think the SIMD part has more to do with loop analysis than ILP. It's quite telling that there is a #pragma omp simd to hint to a compiler to rewrite the loop. Now I wonder what's the state of polyhedral compilers. It's been many years. And given the AI, LLMs hype they could really shine.
  - menaerus 3y ago
    > I think the SIMD part has more to do with loop analysis than ILP. If you know how to rewrite the algorithm in such a way so that it makes close-to-ideal utilization of CPU ports through your SIMD then it is practically impossible to beat it. And I haven't seen a compiler (GCC, clang) doing such a thing or at least not in the instances I had written. I've measured substantial improvements from such and similar utilization of CPU-level microarchitectural details. So perhaps I don't think it's the loop analysis only but I do think it's practically an impossible task for the compiler. Perhaps with the AI ...
lifthrasiir 3y ago
You don't necessarily need `-ffast-math` if you are willing to tweak your code a bit, since you can just introduce accumulators by yourself. Such optimizer-friendly code is not hard to write if you know basic principles.
- mratsim 3y ago
  That's what I'm saying though. Either youbdo the accumulators yourself, or you need a compiler escape hatch.
  - lifthrasiir 3y ago
    I mean, you don't need SIMD to put accumulators.
    - mratsim 3y ago
      The compiler escape hatch is -ffast-math

steveklabnik 3y ago

> Rust iterators would also be fun to benchmark here I started to write this out, and then thought "you know what given how common this is, I bet I could even just google it" and thought that would be more interesting, as it makes it feel more "real world." The first result I got is what I would have written: https://stackoverflow.com/a/30422958/24817 https://stackoverflow.com/a/30422958/24817 Here's a godbolt with three different outputs: one at -O, one at -O3, and one at -03 and -march=native https://godbolt.org/z/6xf9M1cf3 https://godbolt.org/z/6xf9M1cf3 Eyeballing it comments: Looks like 2 and 3 both provide extremely similar if not identical output. Adding the native flag ends up generating slightly different codegen, I am not at the level to be able to simply look at that and know how meaningful the difference is. It does appear to have eliminated the bounds check entirely, and it's using xmm registers. I am pleasantly surprised at this output because zip in particular can sometimes hinder optimizations, but rustc did a great job here. ---------------------- For fun, I figured "why not also try as direct of the original Go as possible." The only trick here is that Rust doesn't really do the c-style for loop the way Go does, so I tried to translate what I saw as the spirit of the example: compare the two lengths and use the minimum for the loop length. Here it is: https://godbolt.org/z/cTcddc8Gs https://godbolt.org/z/cTcddc8Gs ... literally the same. I am very surprised at this outcome. It makes me wonder if LLVM has some sort of idiom recognition for dot product specifically. EDIT: looks like it does not currently, see the comment at line 28 and 29: https://llvm.org/doxygen/LoopIdiomRecognize_8cpp_source.html https://llvm.org/doxygen/LoopIdiomRecognize_8cpp_source.html

camel-cdr 3y ago
Those aren't vectorized at all, just unrolled. vmulss/vaddss just multiply/add the single-precision floating-point in the vector register. With clang you get basically the same codegen, although it uses fused multiply adds. The problem is that you need to enable -ffast-math, otherwise the compiler can't change the order of floating point operations, and thus not vectorize. With clang that works wonderfully and it gives us a lovely four times unrolled AVX2 fused multiply add loop, but enabling it in rust doesn't seem to work: https://godbolt.org/z/G4Enf59Kb https://godbolt.org/z/G4Enf59Kb Edit: from what I can tell this is still an open issue??? https://github.com/rust-lang/rust/issues/21690 https://github.com/rust-lang/rust/issues/21690 Edit: relevant SO post: https://stackoverflow.com/questions/76055058/why-cant-the-rust-compiler-auto-vectorize-this-fp-dot-product-implementation https://stackoverflow.com/questions/76055058/why-cant-the-ru... Apparently you need to use `#![feature(core_intrinsics)]`, `std::intrinsics::fadd_fast` and `std::intrinsics::fmul_fast`.