5 ms·

It is crazy sometimes how you try to program something the best you ever could with classical C++, and then someone comes along and makes a version using SIMD t

It is crazy sometimes how you try to program something the best you ever could with classical C++, and then someone comes along and makes a version using SIMD that is over 10x faster (but less portable code). I really wish compilers were better at auto vectorization. And some support added for annotations in the language to locally allow reordering some operations, ...

deleted 3y ago
[deleted]
janwas 3y ago
This happens regularly in my experience :) Also, when using a SIMD wrapper library, it can actually be quite portable in practice.
kolbe 3y ago
There are unfortunately a lot of serial guarantees that are unavoidable even if compilers could optimize perfectly. For example: 'for(double v: vec) sum+=v' Floating point addition is not associative, so summing each value in order is not the same as summing every 8th element, then summing the remainder, which is how SIMD handles it. So even though this is an obvious optimization for compilers, they will prioritize the serial guarantee over the optimization unless you tell it to relax that particular guarantee. It's a mess and I agree with janwas: use a library (and in particular: use Google Highway) or something like Intel's ISPC when your hot path needs this.
- Aardwolf 3y ago
  Hence my suggestion for language support. Add some language syntax where you can say: "add these doubles, order doesn't matter", which allows the compiler to use SIMD
  - kolbe 3y ago
    -ffast-math if you want to push the onus on the compiler. Problem is you need to enforce that requirement on all user compilations, and I don't know what for MSVC. In-language would be nice.
    - Aardwolf 3y ago
      -ffast-math is global though and can break other libraries. I mean local, vectorization compatible but portable syntax, without actually writing it (let compiler do the work)
      - kolbe 3y ago
        Totally fair. I'm with you.
      - eesmith 3y ago
        According to https://stackoverflow.com/questions/40699071/can-i-make-my-compiler-use-fast-math-on-a-per-function-basis https://stackoverflow.com/questions/40699071/can-i-make-my-c... you annotate it with: __attribute__((optimize("-ffast-math"))) I tried it with: double sum1(double arr[128]) { double tot = 0.0; for (int i=0; i<128; i++) { tot += arr[i]; } return tot; } __attribute__((optimize("-ffast-math"))) double sum2(double arr[128]) { double tot = 0.0; for (int i=0; i<128; i++) { tot += arr[i]; } return tot; } The Compiler Explorer (gcc 13.2, --std=c++20 -march=native -O3) generates two different bodies for those: sum1(double*): lea rax, [rdi+1024] vxorpd xmm0, xmm0, xmm0 .L2: vaddsd xmm0, xmm0, QWORD PTR [rdi] add rdi, 32 vaddsd xmm0, xmm0, QWORD PTR [rdi-24] vaddsd xmm0, xmm0, QWORD PTR [rdi-16] vaddsd xmm0, xmm0, QWORD PTR [rdi-8] cmp rax, rdi jne .L2 ret sum2(double*): lea rax, [rdi+1024] vxorpd xmm0, xmm0, xmm0 .L6: vaddpd ymm0, ymm0, YMMWORD PTR [rdi] add rdi, 32 cmp rax, rdi jne .L6 vextractf64x2 xmm1, ymm0, 0x1 vaddpd xmm1, xmm1, xmm0 vunpckhpd xmm0, xmm1, xmm1 vaddpd xmm0, xmm0, xmm1 vzeroupper ret It is still compiler-specific and non-portable, but at least it is not global.
        gpderetta 3y ago
        I'm guilty of having used it, but form the doc: " The optimize attribute should be used for debugging purposes only. It is not suitable in production code." It can be very unreliable.
gumby 3y ago
> It is crazy sometimes how you try to program something the best you ever could with classical C++, and then someone comes along and makes a version using SIMD that is over 10x faster (but less portable code). But that’s one of the points of a systems programming language (of which C++ is one) — it tries to be portably as efficient as possible but makes it easy to do target-specific programming when required. > I really wish compilers were better at auto vectorization FORTRAN compilers sure are, since aliasing is not allowed. C++ is kneecapped by following C’s memory model.
- pklausler 3y ago
  Fortran compilers can assume that (many) dummy arguments to a particular procedure reference do not alias each other, true. But there are many other ways in which aliasing can happen in a conforming Fortran program.
- secondcoming 3y ago
  It's not just aliasing. gcc is quite bad at autovectorising in general, clang is much better. Here's a trivial algorithm that gcc borks over because 'bool' is used instead of 'int', even fixing that the codegen isn't great: https://godbolt.org/z/hf7szo78E https://godbolt.org/z/hf7szo78E
  - harry8 3y ago
    Really good example. It also sucks that you have no way of knowing at build time whether autovectorisation succeeded. Even if you have it working initially it can silently break and you don't know where. So using clang, you're careful and you check the generated code and everything is great, then later it isn't and you have to go hunting to find out why.
- Aardwolf 3y ago
  But why is C++ refusing to add "restrict" to its spec? C has restrict in its spec, C++ has not. Of course compilers inherit restrict from C, but it's not super portable due to C++ not officially supporting it. But why?!
dragontamer 3y ago
You could just use CUDA, which is C++ designed for GPUs, the ultimate SIMD machine of today. Or ROCm (basically CUDA but for AMD). I always was a fan of Microsoft's C++AMP though. I thought that was easiest to get into. Too bad it never stuck though.
- touisteur 3y ago
  DPC++/SYCL might be more interesting in this area (GPU code looking like evolved C++). ISPC is an interesting take on 'building a vector DSL which can easily be integrated in a C++ build-chain'. Though calling GPUs SIMD nowadays is kind of reductive, since you also have to contain with a very constrained memory hierarchy, and you don't write or think your code as SIMD much but more. Also they don't give access to most bit-tricks, and the rigmarole of shuffles one would expect from a SIMD processor.
  - dragontamer 3y ago
    > Though calling GPUs SIMD nowadays is kind of reductive, since you also have to contain with a very constrained memory hierarchy, and you don't write or think your code as SIMD much but more. Also they don't give access to most bit-tricks, Oh rly? * Popcnt is defined in ROCm and CUDA. * Shifts, XORs, AND, OR, NOT are all defined in GPUs. * You can actually do AES and a lot of other bit-level twiddling in GPU space very efficiently. (aka: see any mining software for highly-efficient bit-twiddling). Yeah, not as many tricks (ex: pext / pdep) as a CPU. But popcnt is the "big" one. GPUs also have bit-reverse instructions (which reduces the need for LS1B instructions like CPUs because you can do LS1B tricks on "both ends" by just bit-reversing). But honestly, GPUs are so parallel and Register-space is so plentiful that you can probably just build whatever you want out of AND/OR/NOT/XOR instructions alone. And since GPUs have single-cycle "popcnt", any symmetric bit-twiddling function can be built off of popcnt within a few cycles. > and the rigmarole of shuffles one would expect from a SIMD processor. Abuse of __shared__ memory and the full crossbar of a GPU-core means that you can arbitrarily shuffle data through __shared__ memory in like 5 clock ticks (well... in certain ways... if you do it wrong it'd take many clock ticks). GPUs are actually far superior to AVX512 in this front. NVidia's shfl.bfly instruction can implement FFTs, even-odd sorting, bitonic sorts, and more as high-speed communications. AMD has similar instructions: https://gpuopen.com/learn/amd-gcn-assembly-cross-lane-operations/ https://gpuopen.com/learn/amd-gcn-assembly-cross-lane-operat... Trust me on this case: GPU data-movement is far, far, far superior to CPU data-movement. Intel does NOT have the bpermute or permute instructions like a GPU does. Meanwhile, both AMD and NVidia GPUs have bpermute / permute for both gather-and-scatter-like operation / distribution of data across lanes. AMD/NVidia also have guarantees upon the speed of broadcasts across __shared__ memory. And butterfly-shuffles can theoretically implement any arbitrary shuffle you want in log2(SIMD-Width) steps, so we have incredible amounts of tools in GPU space that CPU-programmers have no idea about.
cmovq 3y ago
Good SIMD code requires careful consideration of how your data is laid out in memory. This makes auto vectorization really difficult since the compiler can’t fix your data for you outside of very local contexts

deleted 3y ago

[deleted]

janwas 3y ago

This happens regularly in my experience :) Also, when using a SIMD wrapper library, it can actually be quite portable in practice.

kolbe 3y ago

There are unfortunately a lot of serial guarantees that are unavoidable even if compilers could optimize perfectly. For example: 'for(double v: vec) sum+=v' Floating point addition is not associative, so summing each value in order is not the same as summing every 8th element, then summing the remainder, which is how SIMD handles it. So even though this is an obvious optimization for compilers, they will prioritize the serial guarantee over the optimization unless you tell it to relax that particular guarantee. It's a mess and I agree with janwas: use a library (and in particular: use Google Highway) or something like Intel's ISPC when your hot path needs this.

Aardwolf 3y ago
Hence my suggestion for language support. Add some language syntax where you can say: "add these doubles, order doesn't matter", which allows the compiler to use SIMD
- kolbe 3y ago
  -ffast-math if you want to push the onus on the compiler. Problem is you need to enforce that requirement on all user compilations, and I don't know what for MSVC. In-language would be nice.
  - Aardwolf 3y ago
    -ffast-math is global though and can break other libraries. I mean local, vectorization compatible but portable syntax, without actually writing it (let compiler do the work)
    - kolbe 3y ago
      Totally fair. I'm with you.
    - eesmith 3y ago
      According to https://stackoverflow.com/questions/40699071/can-i-make-my-compiler-use-fast-math-on-a-per-function-basis https://stackoverflow.com/questions/40699071/can-i-make-my-c... you annotate it with: __attribute__((optimize("-ffast-math"))) I tried it with: double sum1(double arr[128]) { double tot = 0.0; for (int i=0; i<128; i++) { tot += arr[i]; } return tot; } __attribute__((optimize("-ffast-math"))) double sum2(double arr[128]) { double tot = 0.0; for (int i=0; i<128; i++) { tot += arr[i]; } return tot; } The Compiler Explorer (gcc 13.2, --std=c++20 -march=native -O3) generates two different bodies for those: sum1(double*): lea rax, [rdi+1024] vxorpd xmm0, xmm0, xmm0 .L2: vaddsd xmm0, xmm0, QWORD PTR [rdi] add rdi, 32 vaddsd xmm0, xmm0, QWORD PTR [rdi-24] vaddsd xmm0, xmm0, QWORD PTR [rdi-16] vaddsd xmm0, xmm0, QWORD PTR [rdi-8] cmp rax, rdi jne .L2 ret sum2(double*): lea rax, [rdi+1024] vxorpd xmm0, xmm0, xmm0 .L6: vaddpd ymm0, ymm0, YMMWORD PTR [rdi] add rdi, 32 cmp rax, rdi jne .L6 vextractf64x2 xmm1, ymm0, 0x1 vaddpd xmm1, xmm1, xmm0 vunpckhpd xmm0, xmm1, xmm1 vaddpd xmm0, xmm0, xmm1 vzeroupper ret It is still compiler-specific and non-portable, but at least it is not global.
      - gpderetta 3y ago
        I'm guilty of having used it, but form the doc: " The optimize attribute should be used for debugging purposes only. It is not suitable in production code." It can be very unreliable.

gumby 3y ago

> It is crazy sometimes how you try to program something the best you ever could with classical C++, and then someone comes along and makes a version using SIMD that is over 10x faster (but less portable code). But that’s one of the points of a systems programming language (of which C++ is one) — it tries to be portably as efficient as possible but makes it easy to do target-specific programming when required. > I really wish compilers were better at auto vectorization FORTRAN compilers sure are, since aliasing is not allowed. C++ is kneecapped by following C’s memory model.

pklausler 3y ago
Fortran compilers can assume that (many) dummy arguments to a particular procedure reference do not alias each other, true. But there are many other ways in which aliasing can happen in a conforming Fortran program.
secondcoming 3y ago
It's not just aliasing. gcc is quite bad at autovectorising in general, clang is much better. Here's a trivial algorithm that gcc borks over because 'bool' is used instead of 'int', even fixing that the codegen isn't great: https://godbolt.org/z/hf7szo78E https://godbolt.org/z/hf7szo78E
- harry8 3y ago
  Really good example. It also sucks that you have no way of knowing at build time whether autovectorisation succeeded. Even if you have it working initially it can silently break and you don't know where. So using clang, you're careful and you check the generated code and everything is great, then later it isn't and you have to go hunting to find out why.
Aardwolf 3y ago
But why is C++ refusing to add "restrict" to its spec? C has restrict in its spec, C++ has not. Of course compilers inherit restrict from C, but it's not super portable due to C++ not officially supporting it. But why?!

dragontamer 3y ago

You could just use CUDA, which is C++ designed for GPUs, the ultimate SIMD machine of today. Or ROCm (basically CUDA but for AMD). I always was a fan of Microsoft's C++AMP though. I thought that was easiest to get into. Too bad it never stuck though.

touisteur 3y ago
DPC++/SYCL might be more interesting in this area (GPU code looking like evolved C++). ISPC is an interesting take on 'building a vector DSL which can easily be integrated in a C++ build-chain'. Though calling GPUs SIMD nowadays is kind of reductive, since you also have to contain with a very constrained memory hierarchy, and you don't write or think your code as SIMD much but more. Also they don't give access to most bit-tricks, and the rigmarole of shuffles one would expect from a SIMD processor.
- dragontamer 3y ago
  > Though calling GPUs SIMD nowadays is kind of reductive, since you also have to contain with a very constrained memory hierarchy, and you don't write or think your code as SIMD much but more. Also they don't give access to most bit-tricks, Oh rly? * Popcnt is defined in ROCm and CUDA. * Shifts, XORs, AND, OR, NOT are all defined in GPUs. * You can actually do AES and a lot of other bit-level twiddling in GPU space very efficiently. (aka: see any mining software for highly-efficient bit-twiddling). Yeah, not as many tricks (ex: pext / pdep) as a CPU. But popcnt is the "big" one. GPUs also have bit-reverse instructions (which reduces the need for LS1B instructions like CPUs because you can do LS1B tricks on "both ends" by just bit-reversing). But honestly, GPUs are so parallel and Register-space is so plentiful that you can probably just build whatever you want out of AND/OR/NOT/XOR instructions alone. And since GPUs have single-cycle "popcnt", any symmetric bit-twiddling function can be built off of popcnt within a few cycles. > and the rigmarole of shuffles one would expect from a SIMD processor. Abuse of __shared__ memory and the full crossbar of a GPU-core means that you can arbitrarily shuffle data through __shared__ memory in like 5 clock ticks (well... in certain ways... if you do it wrong it'd take many clock ticks). GPUs are actually far superior to AVX512 in this front. NVidia's shfl.bfly instruction can implement FFTs, even-odd sorting, bitonic sorts, and more as high-speed communications. AMD has similar instructions: https://gpuopen.com/learn/amd-gcn-assembly-cross-lane-operations/ https://gpuopen.com/learn/amd-gcn-assembly-cross-lane-operat... Trust me on this case: GPU data-movement is far, far, far superior to CPU data-movement. Intel does NOT have the bpermute or permute instructions like a GPU does. Meanwhile, both AMD and NVidia GPUs have bpermute / permute for both gather-and-scatter-like operation / distribution of data across lanes. AMD/NVidia also have guarantees upon the speed of broadcasts across __shared__ memory. And butterfly-shuffles can theoretically implement any arbitrary shuffle you want in log2(SIMD-Width) steps, so we have incredible amounts of tools in GPU space that CPU-programmers have no idea about.

cmovq 3y ago

Good SIMD code requires careful consideration of how your data is laid out in memory. This makes auto vectorization really difficult since the compiler can’t fix your data for you outside of very local contexts