4 ms·

SIMD works fine with arrays of structures. It's sometimes awkward for people to phrase algorithms in terms of SIMD over arrays of structs, but that's often a pr

SIMD works fine with arrays of structures. It's sometimes awkward for people to phrase algorithms in terms of SIMD over arrays of structs, but that's often a problem imposed by poor programming language design, not a fundamental problem with SIMD itself.

immibis 2y ago
Rather, it's a fundamental problem with arrays of structs.
CoastalCoder 2y ago
Could you elaborate on this? I'd think that a fundamental problem is memory I/O bandwidth, and (depending on cache policy) poor cache hit ratios.
- jeltz 2y ago
  I assume they are talking about scatter/gather load and store. But even using those I assume performance typically will be worse due to cache misses.
  - CoastalCoder 2y ago
    I thought (maybe wrongly) that even with s/g load and store, the memory transactions will still be in units of contiguous addresses, sized according to the width of the memory bus. Is that not the case?
- alexhutcheson 2y ago
  If you are accessing elements in memory with a constant stride[1], then hardware prefetchers[2] do a surprisingly good job at “reading ahead” and avoiding cache misses. A typical example would be: you have an array of objects of constant size, and you’re reading a double field from a constant offset within each object. The hardware prefetcher will “recognize” this access pattern and prefetch that offset every sizeof(obj) bytes. The major downsides (vs. a struct-of-arrays design with full spatial locality) are: 1. Every prefetch pulls a full cache line, but the cache line will include data you don’t need. In this example, every cache line might have 64 bytes of data, but you only needed the one double field (8 bytes) - the rest is not useful. If you were iterating over an array of doubles you could have pulled 8 double fields in a single cache line. 2. Specific performance is hardware-dependent, so it’s hard to guarantee performance on e.g. low-end cores, short loops, or unusually long strides. [1] https://en.wikipedia.org/wiki/Stride_of_an_array https://en.wikipedia.org/wiki/Stride_of_an_array [2] https://en.wikipedia.org/wiki/Cache_prefetching https://en.wikipedia.org/wiki/Cache_prefetching
- eigenspace 2y ago
  > I'd think that a fundamental problem is memory I/O bandwidth, and (depending on cache policy) poor cache hit ratios. You seem to be assuming that a vectorized loop over an array of structs only ever uses one element from the struct and ignores the rest. In that case, then yes, you will get some bandwidth problems, but modern hardware prefetchers are so good that a vectorized loop that only looks at each Nth byte or whatever is actually much faster than one might think. I'll also note that the serial (non-SIMD) case also suffers here, but often not quite so badly as the SIMD case suffers. However, there's lots of cases where you want the whole struct. E.g. complex numbers are typically a struct of two real numbers, and SIMD arithmetic on vectors of structs of complex numbers is able to work just fine with the full theoretical SIMD performance improvement.
  - CoastalCoder 2y ago
    > You seem to be assuming that a vectorized loop over an array of structs only ever uses one element from the struct and ignores the rest. That is the worst case scenario of my concern with memory bandwidth. More generally, I'd imagine that any good roofline analysis would need to consider this data-layout issue. > but modern hardware prefetchers are so good that a vectorized loop that only looks at each Nth byte or whatever is actually much faster than one might think. I believe you. I wasn't really thinking about how efficiently the processor can pull the correct bytes into the register lanes. I was just focusing on the fundamental memory <--> CPU xfer part of the process. TL;DR: I'm trying to get better at using roofline analysis in my optimization efforts.
neonsunset 2y ago
This. Modern SIMD extensions have gathers and scatters to specifically work with these kinds of memory layout. For example, ARM64 NEON has interleaving loads and stores in the form of LD2/3/4 and respective ST* counterparts. https://documentation-service.arm.com/static/6530e5163f12c06bc0f740ef https://documentation-service.arm.com/static/6530e5163f12c06... (PDF)
- xoranth 2y ago
  Sure, but how well do they perform compared to vector loads? Do they get converted to vector load + shuffle uops, and therefore require a specific layout anyway? Last time I tried using gathers on AVX2, performance was comparable to doing scalar loads.
  - neonsunset 2y ago
    They are pretty good: https://dougallj.github.io/applecpu/measurements/firestorm/LD4_multi_16B.html https://dougallj.github.io/applecpu/measurements/firestorm/L... Gathers on AVX2 used to be problematic, but assume it shouldn't be the case today especially if the lane-crossing is minimal? (if you do know, please share!)
    - TinkersW 2y ago
      Gather is still terrible, the only core that handles it well is the Intel's P core. AMD issues 40+ micro ops in AVX2(80 in AVX512), and the Intel E core is much worse. When using SIMD you must either use SoA or AoSoA for optimal performance. You can sometimes use AoS if you have a special hand coded swizzle loader for the format.
      - LegionMammal978 2y ago
        Do you know of any resources on such swizzle loaders? I've toyed around with hand-coding x86 SIMD myself, and getting everything horizontally in the right place is always a pain.

immibis 2y ago

Rather, it's a fundamental problem with arrays of structs.

CoastalCoder 2y ago

Could you elaborate on this? I'd think that a fundamental problem is memory I/O bandwidth, and (depending on cache policy) poor cache hit ratios.

jeltz 2y ago
I assume they are talking about scatter/gather load and store. But even using those I assume performance typically will be worse due to cache misses.
- CoastalCoder 2y ago
  I thought (maybe wrongly) that even with s/g load and store, the memory transactions will still be in units of contiguous addresses, sized according to the width of the memory bus. Is that not the case?
alexhutcheson 2y ago
If you are accessing elements in memory with a constant stride[1], then hardware prefetchers[2] do a surprisingly good job at “reading ahead” and avoiding cache misses. A typical example would be: you have an array of objects of constant size, and you’re reading a double field from a constant offset within each object. The hardware prefetcher will “recognize” this access pattern and prefetch that offset every sizeof(obj) bytes. The major downsides (vs. a struct-of-arrays design with full spatial locality) are: 1. Every prefetch pulls a full cache line, but the cache line will include data you don’t need. In this example, every cache line might have 64 bytes of data, but you only needed the one double field (8 bytes) - the rest is not useful. If you were iterating over an array of doubles you could have pulled 8 double fields in a single cache line. 2. Specific performance is hardware-dependent, so it’s hard to guarantee performance on e.g. low-end cores, short loops, or unusually long strides. [1] https://en.wikipedia.org/wiki/Stride_of_an_array https://en.wikipedia.org/wiki/Stride_of_an_array [2] https://en.wikipedia.org/wiki/Cache_prefetching https://en.wikipedia.org/wiki/Cache_prefetching
eigenspace 2y ago
> I'd think that a fundamental problem is memory I/O bandwidth, and (depending on cache policy) poor cache hit ratios. You seem to be assuming that a vectorized loop over an array of structs only ever uses one element from the struct and ignores the rest. In that case, then yes, you will get some bandwidth problems, but modern hardware prefetchers are so good that a vectorized loop that only looks at each Nth byte or whatever is actually much faster than one might think. I'll also note that the serial (non-SIMD) case also suffers here, but often not quite so badly as the SIMD case suffers. However, there's lots of cases where you want the whole struct. E.g. complex numbers are typically a struct of two real numbers, and SIMD arithmetic on vectors of structs of complex numbers is able to work just fine with the full theoretical SIMD performance improvement.
- CoastalCoder 2y ago
  > You seem to be assuming that a vectorized loop over an array of structs only ever uses one element from the struct and ignores the rest. That is the worst case scenario of my concern with memory bandwidth. More generally, I'd imagine that any good roofline analysis would need to consider this data-layout issue. > but modern hardware prefetchers are so good that a vectorized loop that only looks at each Nth byte or whatever is actually much faster than one might think. I believe you. I wasn't really thinking about how efficiently the processor can pull the correct bytes into the register lanes. I was just focusing on the fundamental memory <--> CPU xfer part of the process. TL;DR: I'm trying to get better at using roofline analysis in my optimization efforts.

neonsunset 2y ago

This. Modern SIMD extensions have gathers and scatters to specifically work with these kinds of memory layout. For example, ARM64 NEON has interleaving loads and stores in the form of LD2/3/4 and respective ST* counterparts. https://documentation-service.arm.com/static/6530e5163f12c06bc0f740ef https://documentation-service.arm.com/static/6530e5163f12c06... (PDF)

xoranth 2y ago
Sure, but how well do they perform compared to vector loads? Do they get converted to vector load + shuffle uops, and therefore require a specific layout anyway? Last time I tried using gathers on AVX2, performance was comparable to doing scalar loads.
- neonsunset 2y ago
  They are pretty good: https://dougallj.github.io/applecpu/measurements/firestorm/LD4_multi_16B.html https://dougallj.github.io/applecpu/measurements/firestorm/L... Gathers on AVX2 used to be problematic, but assume it shouldn't be the case today especially if the lane-crossing is minimal? (if you do know, please share!)
  - TinkersW 2y ago
    Gather is still terrible, the only core that handles it well is the Intel's P core. AMD issues 40+ micro ops in AVX2(80 in AVX512), and the Intel E core is much worse. When using SIMD you must either use SoA or AoSoA for optimal performance. You can sometimes use AoS if you have a special hand coded swizzle loader for the format.
    - LegionMammal978 2y ago
      Do you know of any resources on such swizzle loaders? I've toyed around with hand-coding x86 SIMD myself, and getting everything horizontally in the right place is always a pain.