5 ms·

It’s such a ridiculous situation we’re in. Just about every consumer CPU of the past 20 years packs an extra order of magnitude or two of punch for data process

It’s such a ridiculous situation we’re in. Just about every consumer CPU of the past 20 years packs an extra order of magnitude or two of punch for data processing workloads, but to not let it go to waste you have to resort to writing your inner loops using low-level nonportable intrinsics that are just a step above assembly. Or pray that the gods of autovectorization are on your side.

MangoToupe 1y ago
Well, yea. You need to describe your data flow in a way the CPU can take advantage of it. Compilers aren't magic.
- Sharlin 1y ago
  That’s like saying that you have to describe your data flow in terms of gotos because the CPU doesn’t understand for loops and compilers aren’t magic. I don’t mean that autovectorization should just work (tm), I just mean that reasonable portable SIMD abstractions should not be this hard.
  - Earw0rm 1y ago
    There's different ways of approaching it which have different performance consequences. Which is why accelerated libraries are common, but if you want accelerated primitives, you kinda have to roll your own.
  - tomsmeding 1y ago
    > I just mean that reasonable portable SIMD abstractions should not be this hard. Morally, no, it really ought to not be this hard, we need this. Practically, it really is hard, because SIMD instruction sets in CPUs are a mess. X86 and ARM have completely different sets of things that they have instructions for, and even within the X86 family, even within a particular product class, things are inconsistent: - On normal words, one has lzcnt (leading-zero count) and tzcnt (trailing-zero count), but on SIMD vectors there is only lzcnt. And you get lzcnt only on AVX512, the latest-and-greatest in X86. - You have horizontal adds (adding adjacent cells in a vector) for 16-bit ints, 32-bit ints, floats and doubles, and saturating horizontal add for 16-bit ints. https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=hadd&techs=AVX_ALL https://www.intel.com/content/www/us/en/docs/intrinsics-guid... Where are horizontal adds for 8-bit or 64-bit ints, or any other saturating instructions? - Since AVX-512 filled up a bunch of gaps in the instruction set, you have absolute value instructions on 8, 16, 32 and 64 bit ints in 128, 256 and 512 bit vectors. But absolute value on floats only exists on 512-bit vectors. These are just the ones that I could find now, there is more. With this kind of inconsistency, any portable SIMD abstraction will be difficult to efficiently compile for the majority of CPUs, negating part of the advantage.
    - dzaima 1y ago
      If by that absolute value thing you mean _mm512_abs_pd, that's a pseudoinstruction for 'and'ing via a mask that zeroes out the top bit, which can be done equally as well on 128/256-bit vectors, just without an intrinsic for some arbitrary reason. But yeah the gaps are super annoying. Some of my personal picks: - There's only 8- and 16-bit integer saturating add/subtract, even on AVX-512 - No 8-bit shifts anywhere either; AVX2 only has 32- and 64-bit dynamic shifts (and ≥16-bit constant shifts; no 64-bit arithmetic shift right though!), AVX-512 adds dynamic 16-bit shifts, still no 8-bit shifts (though with some GFNI magic you can emulate constant 8-bit shifts) - Narrowing integer types pre-AVX-512 is rather annoying, taking multiple instructions. And even though AVX-512 has instructions for narrowing vectors, you're actually better off using multiple-table-input permute instructions and narrowing multiple vectors at the same time. - Multiplies on x86 are extremely funky (there's a 16-bit high half instr, but no other width; a 32×32→64-bit instr, but no other doubling width instr; proper 32-bit multiply is only from AVX2, proper 64-bit only in AVX-512). ARM NEON doesn't have 64-bit multiplication. - Extracting a single bit from each element (movemask/movmsk) exists for 8-/32-/64-bit elements, but not 16-bit on x86 pre-AVX512; ARM NEON has none of those, requiring quite long instruction sequences to do so (and you quite benefit from unrolling and packing multiple vectors together, or even doing structure loads to do some of the rearranging) - No 64-bit int min/max nor 16-bit element top-bit dynamic blend pre-AVX512
      - janwas 1y ago
        I know dzaima is aware, but for all the other posters who might not be, our Highway library provides all these missing instructions, via emulation if required. I do not understand why folks are still making do with direct use of intrinsics or compiler builtins. Having a library centralize workarounds (such an an MSAN compiler change which hit us last week) seems like an obvious win.
    - exDM69 1y ago
      > Practically, it really is hard, because SIMD instruction sets in CPUs are a mess. X86 and ARM have completely different sets of things that they have instructions for Not disagreeing it's a mess, but there's also quite a big common subset containing all the basic arithmetic ops and some specialized ones rsqrt, rcp, dot product, etc. These should be easier to use without having to write the code for each instruction set. And they are with C vector extensions or Rust std::simd. Some of the inconsistencies you mention are less of a problem in portable simd, taking Rust for example: - lzcnt and tzcnt: std::simd::SimdInt has both leading_zeros and trailing_zeros (also leading/trailing_ones) for every integer size and vector width. - horizontal adds: notably missing from std::simd (gotta use intrinsics if you want it), but there is reduce_sum (although it compiles to add and swizzle). Curiously LLVM does not compile `x + simd_swizzle!(x, [1, 0, 3, 2])` into haddps - absolute values for iBxN and fBxN out of the box. Also these have fallback code (which is mostly reasonable, but not always) when your target CPU doesn't have the instruction. You'll need to enable the features you want at compile time (-C target-features=+avx2). > With this kind of inconsistency, any portable SIMD abstraction will be difficult to efficiently compile for the majority of CPUs, negating part of the advantage. I agree it negates a part of the advantage. But only a part, and for that you have zero cost fallback to intrinsics. And in my projects that part has been tiny compared to the overall amount of SIMD code I've written. For basic arithmetic ops it's a huge win to have to write the code only once, and use normal math operations (+, -, *, /) instead of memorizing the per-CPU intrinsics for two (or more) CPU vendors.
- mort96 1y ago
  But why do you need to describe that data flow using non-portable assembly?
- nwallin 1y ago
  this turned into a larger rant than I wanted it to be. But I need to let it out every now and then. Feel free tos kip it. IMHO programming languages are, for the most part, designed such that a compiler's job is easy if you want to compile to scalar code, but damned near impossible if you want it to compile to vectorized code. So I have a point type, right? 'struct point3f { float x,y,z; };'. Easy peasy lemon squeezy. I add a bunch of member functions for normal stuff like addition, scalar multiplication, dot/cross product, etc. I write a triangle type: 'struct triangle { point3f a,b,c; };'. I write a bunch of functions for geometry stuff, intersections with rays, normals, etc. Then I make an array of triangles. I have an origin point and a look ray. I want to iterate over each triangle and figure out which triangles intersect my origin/ray. Now I'm stuck. This is a perfect use case for vectorization, I can trivially get 4x/8x/16x speedup with SSE/AVX/AVX512, but the compiler can't do it. The data's in the wrong layout. It's in the correct layout for scalar code, but the wrong format for vector code. If you want to write vector code, your data has to be in a struct of arrays (SoA) layout. There ought to exist a programming language that will, by default, automagically convert everything to SoA layout, unless you flag your array as AoS or your class as non-SoA-able. And ranged for loops are, by default, unsequenced. This will make autovectorization an order of magnitude easier, and will enable vectorization on complicated stuff that might be fiendishly difficult to vectorize, even by hand. This isn't trivial, and it can't simply be tacked on to a language later on. SIMD needs to be a day-0 priority. Everything else needs to be in support of that. Until then, until this happens, we will either be leaving 60% of our CPU's silicon idle 99% of the time, or scrubs like me will continue to write SIMD intrinsic laden code with lots of manual bullshit to do what the compiler/language design should be doing for me for free. Rant over. Thank you for coming to my TED talk.
  - gr4vityWall 1y ago
    Have you checked Odin out? I think it has what you want. https://odin-lang.org/docs/overview/#soa-struct-arrays https://odin-lang.org/docs/overview/#soa-struct-arrays
jltsiren 1y ago
Adding parallelism is much easier on the hardware side than the software side. We've kind of figured out the easy cases, such as independent tasks with limited interactions with each other, and made them practical for the average developer. But nobody understands the harder cases (such as SIMD) well enough to create useful abstractions that don't constrain hardware development too much.
- smallmancontrov 1y ago
  Except for GPU manufacturers, who figured out the right way to do it 20 years ago. 20 years ago, it was extremely obvious to anyone who had to write forward/backward compatible parallelism that the-thing-nvidia-calls-SIMT was the correct approach. I thought CPU hardware manufacturers and language/compiler writers were so excessively stubborn that it would take them a decade to catch up. I was wrong. 20 years on, they still refuse to copy what works.
  - dzaima 1y ago
    That's because the things GPUs do just isn't what CPUs do. GPUs don't have to deal with ad-hoc 10..100-char strings. They don't have to deal with 20-iteration loops with necessarily-serial dependencies between invocations of the small loops. They don't have to deal with parallelizing mutable hashmap probing operations. Indeed what GPUs do is good for what GPUs do. But we have a tool for doing things that GPUs do well - it's called, uhh, what's it, uhh... oh yeah, GPUs. Copying that into CPUs is somewhere between just completely unnecessary, and directly harmful to things that CPUs are actually supposed to be used for. The GPU approach has pretty big downsides for anything other than the most embarassingly-parallel code on very massive inputs; namely, anything non-trivial (sorting, prefix sum) will typically require log(n) iterations, and somewhere between twice as much, and O(n*log(n)) memory access (and even summing requires stupid things like using memory for an accumulator instead of being able to just use vector registers), compared to the CPU SIMD approach of doing a single pass with some shuffles. GPUs handle this via trading off memory latency for more bandwidth, but any CPU that did that would immediately go right in the thrash because that'd utterly kill scalar code performance.
the__alchemist 1y ago
Evidence point towards the autovectorization gods being dead, false, or too weak. I hear, but don't believe their prophets.

MangoToupe 1y ago

Well, yea. You need to describe your data flow in a way the CPU can take advantage of it. Compilers aren't magic.

Sharlin 1y ago
That’s like saying that you have to describe your data flow in terms of gotos because the CPU doesn’t understand for loops and compilers aren’t magic. I don’t mean that autovectorization should just work (tm), I just mean that reasonable portable SIMD abstractions should not be this hard.
- Earw0rm 1y ago
  There's different ways of approaching it which have different performance consequences. Which is why accelerated libraries are common, but if you want accelerated primitives, you kinda have to roll your own.
- tomsmeding 1y ago
  > I just mean that reasonable portable SIMD abstractions should not be this hard. Morally, no, it really ought to not be this hard, we need this. Practically, it really is hard, because SIMD instruction sets in CPUs are a mess. X86 and ARM have completely different sets of things that they have instructions for, and even within the X86 family, even within a particular product class, things are inconsistent: - On normal words, one has lzcnt (leading-zero count) and tzcnt (trailing-zero count), but on SIMD vectors there is only lzcnt. And you get lzcnt only on AVX512, the latest-and-greatest in X86. - You have horizontal adds (adding adjacent cells in a vector) for 16-bit ints, 32-bit ints, floats and doubles, and saturating horizontal add for 16-bit ints. https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=hadd&techs=AVX_ALL https://www.intel.com/content/www/us/en/docs/intrinsics-guid... Where are horizontal adds for 8-bit or 64-bit ints, or any other saturating instructions? - Since AVX-512 filled up a bunch of gaps in the instruction set, you have absolute value instructions on 8, 16, 32 and 64 bit ints in 128, 256 and 512 bit vectors. But absolute value on floats only exists on 512-bit vectors. These are just the ones that I could find now, there is more. With this kind of inconsistency, any portable SIMD abstraction will be difficult to efficiently compile for the majority of CPUs, negating part of the advantage.
  - dzaima 1y ago
    If by that absolute value thing you mean _mm512_abs_pd, that's a pseudoinstruction for 'and'ing via a mask that zeroes out the top bit, which can be done equally as well on 128/256-bit vectors, just without an intrinsic for some arbitrary reason. But yeah the gaps are super annoying. Some of my personal picks: - There's only 8- and 16-bit integer saturating add/subtract, even on AVX-512 - No 8-bit shifts anywhere either; AVX2 only has 32- and 64-bit dynamic shifts (and ≥16-bit constant shifts; no 64-bit arithmetic shift right though!), AVX-512 adds dynamic 16-bit shifts, still no 8-bit shifts (though with some GFNI magic you can emulate constant 8-bit shifts) - Narrowing integer types pre-AVX-512 is rather annoying, taking multiple instructions. And even though AVX-512 has instructions for narrowing vectors, you're actually better off using multiple-table-input permute instructions and narrowing multiple vectors at the same time. - Multiplies on x86 are extremely funky (there's a 16-bit high half instr, but no other width; a 32×32→64-bit instr, but no other doubling width instr; proper 32-bit multiply is only from AVX2, proper 64-bit only in AVX-512). ARM NEON doesn't have 64-bit multiplication. - Extracting a single bit from each element (movemask/movmsk) exists for 8-/32-/64-bit elements, but not 16-bit on x86 pre-AVX512; ARM NEON has none of those, requiring quite long instruction sequences to do so (and you quite benefit from unrolling and packing multiple vectors together, or even doing structure loads to do some of the rearranging) - No 64-bit int min/max nor 16-bit element top-bit dynamic blend pre-AVX512
    - janwas 1y ago
      I know dzaima is aware, but for all the other posters who might not be, our Highway library provides all these missing instructions, via emulation if required. I do not understand why folks are still making do with direct use of intrinsics or compiler builtins. Having a library centralize workarounds (such an an MSAN compiler change which hit us last week) seems like an obvious win.
  - exDM69 1y ago
    > Practically, it really is hard, because SIMD instruction sets in CPUs are a mess. X86 and ARM have completely different sets of things that they have instructions for Not disagreeing it's a mess, but there's also quite a big common subset containing all the basic arithmetic ops and some specialized ones rsqrt, rcp, dot product, etc. These should be easier to use without having to write the code for each instruction set. And they are with C vector extensions or Rust std::simd. Some of the inconsistencies you mention are less of a problem in portable simd, taking Rust for example: - lzcnt and tzcnt: std::simd::SimdInt has both leading_zeros and trailing_zeros (also leading/trailing_ones) for every integer size and vector width. - horizontal adds: notably missing from std::simd (gotta use intrinsics if you want it), but there is reduce_sum (although it compiles to add and swizzle). Curiously LLVM does not compile `x + simd_swizzle!(x, [1, 0, 3, 2])` into haddps - absolute values for iBxN and fBxN out of the box. Also these have fallback code (which is mostly reasonable, but not always) when your target CPU doesn't have the instruction. You'll need to enable the features you want at compile time (-C target-features=+avx2). > With this kind of inconsistency, any portable SIMD abstraction will be difficult to efficiently compile for the majority of CPUs, negating part of the advantage. I agree it negates a part of the advantage. But only a part, and for that you have zero cost fallback to intrinsics. And in my projects that part has been tiny compared to the overall amount of SIMD code I've written. For basic arithmetic ops it's a huge win to have to write the code only once, and use normal math operations (+, -, *, /) instead of memorizing the per-CPU intrinsics for two (or more) CPU vendors.
mort96 1y ago
But why do you need to describe that data flow using non-portable assembly?
nwallin 1y ago
this turned into a larger rant than I wanted it to be. But I need to let it out every now and then. Feel free tos kip it. IMHO programming languages are, for the most part, designed such that a compiler's job is easy if you want to compile to scalar code, but damned near impossible if you want it to compile to vectorized code. So I have a point type, right? 'struct point3f { float x,y,z; };'. Easy peasy lemon squeezy. I add a bunch of member functions for normal stuff like addition, scalar multiplication, dot/cross product, etc. I write a triangle type: 'struct triangle { point3f a,b,c; };'. I write a bunch of functions for geometry stuff, intersections with rays, normals, etc. Then I make an array of triangles. I have an origin point and a look ray. I want to iterate over each triangle and figure out which triangles intersect my origin/ray. Now I'm stuck. This is a perfect use case for vectorization, I can trivially get 4x/8x/16x speedup with SSE/AVX/AVX512, but the compiler can't do it. The data's in the wrong layout. It's in the correct layout for scalar code, but the wrong format for vector code. If you want to write vector code, your data has to be in a struct of arrays (SoA) layout. There ought to exist a programming language that will, by default, automagically convert everything to SoA layout, unless you flag your array as AoS or your class as non-SoA-able. And ranged for loops are, by default, unsequenced. This will make autovectorization an order of magnitude easier, and will enable vectorization on complicated stuff that might be fiendishly difficult to vectorize, even by hand. This isn't trivial, and it can't simply be tacked on to a language later on. SIMD needs to be a day-0 priority. Everything else needs to be in support of that. Until then, until this happens, we will either be leaving 60% of our CPU's silicon idle 99% of the time, or scrubs like me will continue to write SIMD intrinsic laden code with lots of manual bullshit to do what the compiler/language design should be doing for me for free. Rant over. Thank you for coming to my TED talk.
- gr4vityWall 1y ago
  Have you checked Odin out? I think it has what you want. https://odin-lang.org/docs/overview/#soa-struct-arrays https://odin-lang.org/docs/overview/#soa-struct-arrays

jltsiren 1y ago

Adding parallelism is much easier on the hardware side than the software side. We've kind of figured out the easy cases, such as independent tasks with limited interactions with each other, and made them practical for the average developer. But nobody understands the harder cases (such as SIMD) well enough to create useful abstractions that don't constrain hardware development too much.

smallmancontrov 1y ago
Except for GPU manufacturers, who figured out the right way to do it 20 years ago. 20 years ago, it was extremely obvious to anyone who had to write forward/backward compatible parallelism that the-thing-nvidia-calls-SIMT was the correct approach. I thought CPU hardware manufacturers and language/compiler writers were so excessively stubborn that it would take them a decade to catch up. I was wrong. 20 years on, they still refuse to copy what works.
- dzaima 1y ago
  That's because the things GPUs do just isn't what CPUs do. GPUs don't have to deal with ad-hoc 10..100-char strings. They don't have to deal with 20-iteration loops with necessarily-serial dependencies between invocations of the small loops. They don't have to deal with parallelizing mutable hashmap probing operations. Indeed what GPUs do is good for what GPUs do. But we have a tool for doing things that GPUs do well - it's called, uhh, what's it, uhh... oh yeah, GPUs. Copying that into CPUs is somewhere between just completely unnecessary, and directly harmful to things that CPUs are actually supposed to be used for. The GPU approach has pretty big downsides for anything other than the most embarassingly-parallel code on very massive inputs; namely, anything non-trivial (sorting, prefix sum) will typically require log(n) iterations, and somewhere between twice as much, and O(n*log(n)) memory access (and even summing requires stupid things like using memory for an accumulator instead of being able to just use vector registers), compared to the CPU SIMD approach of doing a single pass with some shuffles. GPUs handle this via trading off memory latency for more bandwidth, but any CPU that did that would immediately go right in the thrash because that'd utterly kill scalar code performance.

the__alchemist 1y ago

Evidence point towards the autovectorization gods being dead, false, or too weak. I hear, but don't believe their prophets.