5 ms·

If we are speaking of C code, it's not quite so bad as it looks to have somewhat fat structs across multiple arrays, since you can fit 64 bytes in a cache line

If we are speaking of C code, it's not quite so bad as it looks to have somewhat fat structs across multiple arrays, since you can fit 64 bytes in a cache line on contemporary desktop CPUs, and that sets your real max-unit-size; the CPU is actively trying to keep the line hot and it does so (in the average case) by speculating that you're going to fetch the next index of the array. Since you have multiple cache lines, you can keep multiple arrays hot at the same time, it's just a matter of keeping it easy to predict fetching behavior by using simple loops that don't jump around...which leads to the pattern parent suggests, of cascading messages or buffers in groups of same type so that you get a few big iterations out of the way, and then a much smaller number of indirected accesses.

volta83 5y ago
If you loose vectorization, you might be loosing a 4x, 8x, 16, ... 32x perf difference by organizing your data in such a way that memory operations and data manipulation can't be vectorized.
- moldavi 5y ago
  When you say vectorize, are you referring to loop unrolling? Or SIMD or something?
  - simiones 5y ago
    I have never heard vectorization to refer to anything other than SIMD. Loop unrolling is usually only a useful technique to enable SIMD, as far as I know (at least on modern processors, where branch prediction has greatly decreased the cost of jump instructions).
    - jhgb 5y ago
      > as far as I know (at least on modern processors, where branch prediction has greatly decreased the cost of jump instructions). What about ILP? Can't that benefit from an unrolled loop in some cases? For example if there's a fairly long dependency chain but you might still be able to go through two loop bodies at once instead.
      - tsimionescu 5y ago
        I don't know for sure at all, but I don't think it's impossible that speculative execution could also achieve the same at the processor level.
        jhgb 5y ago
        I don't see how this has anything to do with speculation? In most cases where you care about this you don't have to speculate if all the loop iterations are needed. For example in matrix multiplication all of those iterations will be needed.
        tsimionescu 5y ago
        What I'm thinking is that the processor has an instruction stream that looks like this: loop: instr_1 instr_2 ... instr_n jcond loop Now, assuming the loop is not unrolled, it would need to speculate that `jcond loop` will jump to be able to execute 2 copies of instr_1 in parallel - I'm saying that it may be able to do that, though I am by no means sure.
        jhgb 5y ago
        Oh, I see what you mean -- I was talking (and thinking) about the unrolled version so it didn't make sense how speculation could help there. But I imagine that typically the kind of long chains that you might want to do in parallel in a single basic block are perhaps something that wouldn't get executed that far after a branch, if the only purpose is to not waste time after a branch misprediction. Plus from what I understand you'd still be wasting execution units here, just not by idling them but rather by speculating the "I'm done" branch repeatedly. EDIT: I just found that the idea that I had in my head actually exists and is called "modulo scheduling".
- lasagnaphil 5y ago
  But you usually can't achieve vectorization by just simply changing your data layout, the compiler's auto-vectorization features usually doesn't work that well. SOA or AOSOA layout for vectorization only becomes important when you begin to explicitly write SIMD code in intrinsics or pure assembly. And explicitly writing in SIMD is quite a hard feat in itself: it's okay when you're accelerating small, simple, and isolated algorithms in hot-code paths, but when you're doing much more complex calculations the time you need to invest in it to make it work goes out of hand pretty quickly.
  - volta83 5y ago
    > But you usually can't achieve vectorization by just simply changing your data layout, the compiler's auto-vectorization features usually doesn't work that well. Please don't build a straw man. You (or the compiler) can't achieve vectorization if you have the wrong data layout. Period. How easy / hard is for you or the compiler to vectorize something depends on the application. It can "just work", it might require a one line `pragma simd`, it might require you to use portable `std::simd` types by hands, or use SIMD intrinsics, or write assembly manually. But none of these are options if you have the wrong data layout.

volta83 5y ago

If you loose vectorization, you might be loosing a 4x, 8x, 16, ... 32x perf difference by organizing your data in such a way that memory operations and data manipulation can't be vectorized.

moldavi 5y ago
When you say vectorize, are you referring to loop unrolling? Or SIMD or something?
- simiones 5y ago
  I have never heard vectorization to refer to anything other than SIMD. Loop unrolling is usually only a useful technique to enable SIMD, as far as I know (at least on modern processors, where branch prediction has greatly decreased the cost of jump instructions).
  - jhgb 5y ago
    > as far as I know (at least on modern processors, where branch prediction has greatly decreased the cost of jump instructions). What about ILP? Can't that benefit from an unrolled loop in some cases? For example if there's a fairly long dependency chain but you might still be able to go through two loop bodies at once instead.
    - tsimionescu 5y ago
      I don't know for sure at all, but I don't think it's impossible that speculative execution could also achieve the same at the processor level.
      - jhgb 5y ago
        I don't see how this has anything to do with speculation? In most cases where you care about this you don't have to speculate if all the loop iterations are needed. For example in matrix multiplication all of those iterations will be needed.
        tsimionescu 5y ago
        What I'm thinking is that the processor has an instruction stream that looks like this: loop: instr_1 instr_2 ... instr_n jcond loop Now, assuming the loop is not unrolled, it would need to speculate that `jcond loop` will jump to be able to execute 2 copies of instr_1 in parallel - I'm saying that it may be able to do that, though I am by no means sure.
        jhgb 5y ago
        Oh, I see what you mean -- I was talking (and thinking) about the unrolled version so it didn't make sense how speculation could help there. But I imagine that typically the kind of long chains that you might want to do in parallel in a single basic block are perhaps something that wouldn't get executed that far after a branch, if the only purpose is to not waste time after a branch misprediction. Plus from what I understand you'd still be wasting execution units here, just not by idling them but rather by speculating the "I'm done" branch repeatedly. EDIT: I just found that the idea that I had in my head actually exists and is called "modulo scheduling".
lasagnaphil 5y ago
But you usually can't achieve vectorization by just simply changing your data layout, the compiler's auto-vectorization features usually doesn't work that well. SOA or AOSOA layout for vectorization only becomes important when you begin to explicitly write SIMD code in intrinsics or pure assembly. And explicitly writing in SIMD is quite a hard feat in itself: it's okay when you're accelerating small, simple, and isolated algorithms in hot-code paths, but when you're doing much more complex calculations the time you need to invest in it to make it work goes out of hand pretty quickly.
- volta83 5y ago
  > But you usually can't achieve vectorization by just simply changing your data layout, the compiler's auto-vectorization features usually doesn't work that well. Please don't build a straw man. You (or the compiler) can't achieve vectorization if you have the wrong data layout. Period. How easy / hard is for you or the compiler to vectorize something depends on the application. It can "just work", it might require a one line `pragma simd`, it might require you to use portable `std::simd` types by hands, or use SIMD intrinsics, or write assembly manually. But none of these are options if you have the wrong data layout.