4 ms·

The main thing seems to be that we don't have general purpouse languages in common use that fit SIMD auovectorization in semantics, without carefully "code to t

The main thing seems to be that we don't have general purpouse languages in common use that fit SIMD auovectorization in semantics, without carefully "code to the compiler" portable assembly mindset. Even after 25 years of x86 SIMD support in hardware. It's just not been an aim even in more recent-ish languages like Rust, Swift, Go etc. Partly because of the unworkably hard task of targeting fragmented, undebuggable, proprietary driver/OS programming interfaces from POV of portable languages.

cmrdporcupine 4y ago
Exactly. But also he inadvertently actually touches on this in the post. Talking about people using hash tables and so on. I think if people had the right guidance from language and libraries and from education, they would choose array-based patterns more often. They're often in fact simpler to write. But many languages and common practices push people in a highly incremental piece by piece approach. I'd argue we're basically taught to think in terms of loops, from our earliest days of programming. We could just as easily be taught to think of things in terms of bulk arrays. The win in programming this way is extremely high. I was very disappointed to find the SIMD story in Rust so underdeveloped. Yes, people are not running weather forecasting on their home computers. But they're playing video, synthesizing audio, doing speech recognition, etc. all the time. And more of this ever day. And if there's any chance of rescuing the uses of ML from a hellish privacy violating landscape worth of a Butlerian Jihad... it would by making sure most of this type of computation was done locally on-device. Guess APL has the last laugh.
- acdha 4y ago
  > Yes, people are not running weather forecasting on their home computers. But they're playing video, synthesizing audio, doing speech recognition, etc. all the time. And more of this ever day. > > And if there's any chance of rescuing the uses of ML from a hellish privacy violating landscape worth of a Butlerian Jihad... it would by making sure most of this type of computation was done locally on-device. I think SIMD support is useful too but most of the examples you gave are things which are handled on-device now using dedicated hardware. Video playback has been hardware accelerated for ages, ML acceleration is multiple hardware generations in, etc.
  - adgjlsfhk1 4y ago
    Video playback only has dedicated hardware for the formats that exist when your CPU was made. A cpu with AVX-512 will do a lot better on AV1 decode/encode than one without until someone actually makes a cpu with hardware for it. Funnily enough, the best ML acceleration hardware on CPUs is AVX-512. For small neural nets, a well tuned CPU implementation will do way better than GPUs.
    - acdha 4y ago
      I'm not saying that there's no value in it, but rather that while you're right that it can produce a fair improvement over a traditional CPU implementation things like video are not the best examples because they're _so_ common that they get dedicated hardware which is usually considerably faster / more power-efficient so there's a narrow window for a couple of years where that SIMD implementation is most valuable. ML is similar – many people are running these apps now but, for example, many millions of them are running Apple ML models on Apple hardware with acceleration features so again, while SIMD is unquestionably useful, I'm not surprised that the average working programmer doesn't feel a huge need to dive in rather than using something like a library which will pick from multiple backends.
  - cmrdporcupine 4y ago
    This is not the case for synthesizing audio. Vectorization with GPU is essentially still useless there due to memory latency considerations, at least when I was looking at this most recently. EDIT: there was a period in the late 90s/early 00s when dedicated DSPs were a useful but costly add-on to digital audio PC systems. SIMD moving into the CPU put an end to that.
    - acdha 4y ago
      Thanks - I said “most” because there are definitely plenty of cases like that, but I think there’s an interesting phenomenon where SIMD is useful for its flexibility and low latency but we’re seeing faster cycles adding hardware support for the highest-value acceleration targets than we used to.
- bsder 4y ago
  > Exactly. But also he inadvertently actually touches on this in the post. Talking about people using hash tables and so on. I think if people had the right guidance from language and libraries and from education, they would choose array-based patterns more often. They're often in fact simpler to write. A) The vast majority of programmers have zero idea about any of this. They want a key-value store and have no idea about the underlying implmentation. And that's okay. You can write an awful lot of useful software without understanding Big-O notation. B) Pointer chasing has been dogshit on modern architectures for quite a while, and most people have no idea. Look at all the shit Rust gets for being annoying to implement linked lists which are a garbage data structure on modern CPUs. C) Array-of-struct to struct-of-array type transformations are just starting to get some traction in languages. Entity component systems are common in games but haven't really moved outside of that arena. These are the kind of things that vectorization can go to town on but haven't yet moved to mainstream programming. D) Most of this stuff is contained inside libraries anyway. So, only a few people really need to care about this.
  - cmrdporcupine 4y ago
    Thing is that hashmap usage goes beyond data manipulation / key-value store uses. People use it to construct semi-structured network data models, track counts by indices, etc. Because there's an assumption that the O(1) of a hashtable always beats the O(N) of a linear search. Except that that's really not always the case anymore on a modern arch, with things properly vectorized, etc. When what we should have is libraries that provide high level relational/datalog style manipulation of in-memory datasets, and you describe what you want to do and the system decides how. Personal beef. Think of the average "leetcode" question. It almost always boils down to an iterative pass over some sequence of data, manipulating in place. C-style strings or arrays of numbers, etc. If you tried to answer the question with "I'd use std::sort and then std::blah and so on, on some vectors" they'd show you the door because want you to show clever you are at managing for loop indices and off-by one problems and swapping data between two arrays in a nested loop, etc. So we're actually gating people on this kind of thing. And imho it's doing us a disservice. The code is not as readable. And it doesn't necessarily perform well. It's often a 1988 C programmer's idea of what good code is that is used as the entry bar.
candrewlee14 4y ago
Check out Zig’s `Vector` type. I don’t think I’ve seen SIMD built as elegantly into any other systems language.
- anonymoushn 4y ago
  I use Zig every day and I consider Zig's vector type and SIMD support a good stepping stone to the destination of just writing the intrinsics. Competing efforts including std::simd or Highway are either unusable because they don't expose pshufb or more difficult to use than the tools they are abstracting away.
  - janwas 4y ago
    Author of Highway here :) PSHUFB is TableLookupBytes, or TableLookupBytesOr0 if you want its 0x80 -> 0 semantics. Can you help me understand why Highway might be more difficult to use? That would be very surprising if we are writing a largish application (few thousand lines of vector code) and have to rewrite our code for 3+ different sets of intrinsics.
    - anonymoushn 4y ago
      If I have some time I'll try porting a small parser I wrote the other day to Highway. I expect to gain a lot of bitcasts to change the element type, a lot of angle brackets, and a lot of compile time. It looks like there isn't a way to ask for permute4x64, so I will maybe replace my permute4x64 with SwapAdjacentBlocks, shuffle, and blendv, which will probably cost a register or two and some cycles. I don't think there are necessarily problems with the design of Highway given its constraints and goals. I would just personally find it easier for most of the SIMD code I've written (this tends to be mostly parsers and serializers) to write several implementations targeting AVX2, AVX-512, NEON, and maybe SSE3.
      - janwas 4y ago
        Thanks for your feedback! I'd be happy to advise on the port, feel free to open an issue if you'd like to discuss. I suppose there is a tradeoff between zero type safety + less typing, vs more BitCast verbosity but catching bugs such as arithmetic vs logical shifts, or zero extension when we wanted signed. Would be interesting if you see a difference in compile time. On x86 much of the cost is likely parsing immintrin.h (*mmintrin are about 500 KiB on MSVC). Re-#including your own source code doesn't seem like it would be worse than parsing actually distinct source files. Many of the Highway swizzle ops are fixed pattern; several use permute4x64 internally. Can you share the indices you'd like? If there is a use case, we are happy to add an op for that. It is impressive you are willing (and able) to write and maintain code for 4 ISAs. Still, wouldn't it be nice to have also SVE for Graviton3, SVE2 on new Arm9 mobile/server CPUs, and perhaps RISC-V V in future?

cmrdporcupine 4y ago

Exactly. But also he inadvertently actually touches on this in the post. Talking about people using hash tables and so on. I think if people had the right guidance from language and libraries and from education, they would choose array-based patterns more often. They're often in fact simpler to write. But many languages and common practices push people in a highly incremental piece by piece approach. I'd argue we're basically taught to think in terms of loops, from our earliest days of programming. We could just as easily be taught to think of things in terms of bulk arrays. The win in programming this way is extremely high. I was very disappointed to find the SIMD story in Rust so underdeveloped. Yes, people are not running weather forecasting on their home computers. But they're playing video, synthesizing audio, doing speech recognition, etc. all the time. And more of this ever day. And if there's any chance of rescuing the uses of ML from a hellish privacy violating landscape worth of a Butlerian Jihad... it would by making sure most of this type of computation was done locally on-device. Guess APL has the last laugh.

acdha 4y ago
> Yes, people are not running weather forecasting on their home computers. But they're playing video, synthesizing audio, doing speech recognition, etc. all the time. And more of this ever day. > > And if there's any chance of rescuing the uses of ML from a hellish privacy violating landscape worth of a Butlerian Jihad... it would by making sure most of this type of computation was done locally on-device. I think SIMD support is useful too but most of the examples you gave are things which are handled on-device now using dedicated hardware. Video playback has been hardware accelerated for ages, ML acceleration is multiple hardware generations in, etc.
- adgjlsfhk1 4y ago
  Video playback only has dedicated hardware for the formats that exist when your CPU was made. A cpu with AVX-512 will do a lot better on AV1 decode/encode than one without until someone actually makes a cpu with hardware for it. Funnily enough, the best ML acceleration hardware on CPUs is AVX-512. For small neural nets, a well tuned CPU implementation will do way better than GPUs.
  - acdha 4y ago
    I'm not saying that there's no value in it, but rather that while you're right that it can produce a fair improvement over a traditional CPU implementation things like video are not the best examples because they're _so_ common that they get dedicated hardware which is usually considerably faster / more power-efficient so there's a narrow window for a couple of years where that SIMD implementation is most valuable. ML is similar – many people are running these apps now but, for example, many millions of them are running Apple ML models on Apple hardware with acceleration features so again, while SIMD is unquestionably useful, I'm not surprised that the average working programmer doesn't feel a huge need to dive in rather than using something like a library which will pick from multiple backends.
- cmrdporcupine 4y ago
  This is not the case for synthesizing audio. Vectorization with GPU is essentially still useless there due to memory latency considerations, at least when I was looking at this most recently. EDIT: there was a period in the late 90s/early 00s when dedicated DSPs were a useful but costly add-on to digital audio PC systems. SIMD moving into the CPU put an end to that.
  - acdha 4y ago
    Thanks - I said “most” because there are definitely plenty of cases like that, but I think there’s an interesting phenomenon where SIMD is useful for its flexibility and low latency but we’re seeing faster cycles adding hardware support for the highest-value acceleration targets than we used to.
bsder 4y ago
> Exactly. But also he inadvertently actually touches on this in the post. Talking about people using hash tables and so on. I think if people had the right guidance from language and libraries and from education, they would choose array-based patterns more often. They're often in fact simpler to write. A) The vast majority of programmers have zero idea about any of this. They want a key-value store and have no idea about the underlying implmentation. And that's okay. You can write an awful lot of useful software without understanding Big-O notation. B) Pointer chasing has been dogshit on modern architectures for quite a while, and most people have no idea. Look at all the shit Rust gets for being annoying to implement linked lists which are a garbage data structure on modern CPUs. C) Array-of-struct to struct-of-array type transformations are just starting to get some traction in languages. Entity component systems are common in games but haven't really moved outside of that arena. These are the kind of things that vectorization can go to town on but haven't yet moved to mainstream programming. D) Most of this stuff is contained inside libraries anyway. So, only a few people really need to care about this.
- cmrdporcupine 4y ago
  Thing is that hashmap usage goes beyond data manipulation / key-value store uses. People use it to construct semi-structured network data models, track counts by indices, etc. Because there's an assumption that the O(1) of a hashtable always beats the O(N) of a linear search. Except that that's really not always the case anymore on a modern arch, with things properly vectorized, etc. When what we should have is libraries that provide high level relational/datalog style manipulation of in-memory datasets, and you describe what you want to do and the system decides how. Personal beef. Think of the average "leetcode" question. It almost always boils down to an iterative pass over some sequence of data, manipulating in place. C-style strings or arrays of numbers, etc. If you tried to answer the question with "I'd use std::sort and then std::blah and so on, on some vectors" they'd show you the door because want you to show clever you are at managing for loop indices and off-by one problems and swapping data between two arrays in a nested loop, etc. So we're actually gating people on this kind of thing. And imho it's doing us a disservice. The code is not as readable. And it doesn't necessarily perform well. It's often a 1988 C programmer's idea of what good code is that is used as the entry bar.

candrewlee14 4y ago

Check out Zig’s `Vector` type. I don’t think I’ve seen SIMD built as elegantly into any other systems language.

anonymoushn 4y ago
I use Zig every day and I consider Zig's vector type and SIMD support a good stepping stone to the destination of just writing the intrinsics. Competing efforts including std::simd or Highway are either unusable because they don't expose pshufb or more difficult to use than the tools they are abstracting away.
- janwas 4y ago
  Author of Highway here :) PSHUFB is TableLookupBytes, or TableLookupBytesOr0 if you want its 0x80 -> 0 semantics. Can you help me understand why Highway might be more difficult to use? That would be very surprising if we are writing a largish application (few thousand lines of vector code) and have to rewrite our code for 3+ different sets of intrinsics.
  - anonymoushn 4y ago
    If I have some time I'll try porting a small parser I wrote the other day to Highway. I expect to gain a lot of bitcasts to change the element type, a lot of angle brackets, and a lot of compile time. It looks like there isn't a way to ask for permute4x64, so I will maybe replace my permute4x64 with SwapAdjacentBlocks, shuffle, and blendv, which will probably cost a register or two and some cycles. I don't think there are necessarily problems with the design of Highway given its constraints and goals. I would just personally find it easier for most of the SIMD code I've written (this tends to be mostly parsers and serializers) to write several implementations targeting AVX2, AVX-512, NEON, and maybe SSE3.
    - janwas 4y ago
      Thanks for your feedback! I'd be happy to advise on the port, feel free to open an issue if you'd like to discuss. I suppose there is a tradeoff between zero type safety + less typing, vs more BitCast verbosity but catching bugs such as arithmetic vs logical shifts, or zero extension when we wanted signed. Would be interesting if you see a difference in compile time. On x86 much of the cost is likely parsing immintrin.h (*mmintrin are about 500 KiB on MSVC). Re-#including your own source code doesn't seem like it would be worse than parsing actually distinct source files. Many of the Highway swizzle ops are fixed pattern; several use permute4x64 internally. Can you share the indices you'd like? If there is a use case, we are happy to add an op for that. It is impressive you are willing (and able) to write and maintain code for 4 ISAs. Still, wouldn't it be nice to have also SVE for Graviton3, SVE2 on new Arm9 mobile/server CPUs, and perhaps RISC-V V in future?