3 ms·

Quadrupling code performance with a "useless" if

112 points by birdculture 3mo ago

anematode 3mo ago
Brilliant! Hadn't seen this technique before.
anirudhak47 3mo ago
latency optimization is a skill. I liked how you went till CSE pass. I myself wrote several passes to go to lowest latency possible
akoboldfrying 3mo ago
This is really surprising! I've never considered the possibility that using an equality test to skip a write that would be a no-op could break a dependency and thus lead to higher perf overall if the "equal" outcome occurs often enough. This might be applicable in many situations where you "edit" some data in-place, but most of the time there are few or no changes.
anthonj 3mo ago
I think this call for something similar to "__builtin_expect" or linux' likely()/unlikely(). Not very clean, but better than inserting obscure optimisations in the source.
- gblargg 3mo ago
  Assuming compilers are smart enough to insert an unnecessary branch to break the dependency.
  - vitally3643 3mo ago
    That's what the hints are for. Expect/likely/unlikely are the programmer informing the compiler what it should expect and how it should optimize
- purplesyringa 3mo ago
  That would be great, if only it worked as intended! From the perspective of an optimizing compiler, `a == b ? a : b` is worse than `b` regardless of the probability you assign to `a == b`. ETA: someone on Lobsters (https://lobste.rs/s/1an425/quadrupling_code_performance_with#c_4clhdw https://lobste.rs/s/1an425/quadrupling_code_performance_with...) noticed that `[[unlikely]]` actually works on LLVM (not on GCC, and with worse codegen on LLVM, but it's still good to know) -- updated the post.
- MaxBarraclough 3mo ago
  I was wondering the same thing. Also, could profile-guided optimisation help here?
mcv 3mo ago
Interesting. I thought modern CPU optimisation required avoiding branches, but here adding the branch allows the branch pediction to parallelise what it otherwise couldn't.
- zipy124 3mo ago
  It does and the key here is that adding the if is akin to avoiding a branch, since getting data then doing something with it is a hidden branch if you already have the data. All this code does is formalise the hidden branch so that it can be avoided when possible.
  - summarybot 3mo ago
    That's pretty cool. Is there something obcluding the compiler from noticing this parallelization opportunity without the new `if` ? My understanding is the assignment and the evaluation are somehow coupled in this case based on the essay, but I could use an explanation.
    - purplesyringa 3mo ago
      The optimization in the post is only advantageous if `next_j[i][j] == j` holds often enough. Without prior knowledge, the compiler can't know if it's going to improve performance, and the worst losses are greater than the best wins (branch misprediction is very expensive), so it decides not to interfere.
  - nextaccountic 3mo ago
    > since getting data then doing something with it is a hidden branch if you already have the data You mean that the naive, simpler code, despite not having an if, has a "branch" on the microarchitectural state? (which is like.. if we have this already in cache, do something. if not, do something else) // Find the optimal encoding for each symbol. // Chunk boundaries are located where encodings change. uint8_t encoding[n_symbols]; uint8_t j = 0; // always start with encoding 0 for simplicity for (int i = 0; i < n_symbols; i++) { j = next_j[i][j]; encoding[i] = j; }
throawayonthe 3mo ago
lobsters comment points out [[unlikely]] works here for clang https://clang.godbolt.org/z/r4xYWfPfe https://clang.godbolt.org/z/r4xYWfPfe edit: oh the article also mentions it now :)
6510 3mo ago
my js brain keeps thinking encoding[i] = next_j[i][j];
pillmillipedes 3mo ago
wow, what an interesting optimization! how would you even figure out that that if is what's needed to make it faster?
- purplesyringa 3mo ago
  I knew the loop was latency-bound and I couldn't easily decrease the latency, so I knew I had to somehow avoid the dependency chain at all. I remembered that CPUs predict some properties of memory accesses (e.g. they might predict that a store and then a load from different addresses likely don't intersect), but not addresses, so I thought about another way to force it to predict `j` well. Branch prediction turned out to be the simplest way to do so. Actually, since then I've found out that I could reduce latency by replacing a load on the critical chain with a vector shuffle instruction (`pshufb`, takes just 1 cycle on x86). Ironically, if I realized that sooner, I probably wouldn't have tried to use branch prediction at all!
nonadhocproblem 3mo ago
I've also been working on a compressor recently, and the same general idea (letting the compiler know that a data dependency occurs very infrequently, and it should therefore assume none exists to exploit ILP) has allowed me to speed up my decompression by a lot: https://github.com/welcome-to-the-sunny-side/misa77/blob/777f329b30653162ee0ba66fb42d838618d1b030/src/decompress_impl.h#L55-L56 https://github.com/welcome-to-the-sunny-side/misa77/blob/777...
patrulek 3mo ago
You can utilize MLP (memory-level parallelism) and reduce memory latency by reading whole 8 bytes of next_j at every iteration. Just do something like `uint64_t packed_next_j = *(uint64_t*)(&next_j[i])` and then just shift right to find proper j. This way you remove dependency on previous iteration. Did you tried that?
- purplesyringa 3mo ago
  The right-shift is the problem. You need to shift right by `j * 8`, which itself requires a shift to compute (`j << 3`), so you have two shifts on the critical path, resulting in a latency of 2 cycles. It's better than a load, but it's still noticeable.
  - patrulek 3mo ago
    2 cycles vs ~5 cycles is still nice improvement plus its more deterministic (but not that fast in optimistic case; better in pessimistic case) than `if` appraoch and probably easier to "invent" and reason about. Definitely not that cool as your `if` solution though :)
- OptionOfT 3mo ago
  Don't you need the previous iteration to find out how much you need to shift right?
  - patrulek 3mo ago
    Yes you need, but the initial problem here were sequential loads from L1 into registers.
exmadscientist 3mo ago
A huge part of the problem here is that you're playing with the 8-bit registers. They work, but they're like travelling the back roads: the CPU designers put all their effort into the big highway next door, and not so much into keeping the back roads clear. They're infamous for random weird stalls and such. I wouldn't be surprised at all if there's dependency chain tracking weirdness using them. If you can change the type on `next_j` over to `unsigned` (or `size_t` or ...) then a lot of weird stuff goes away. The dependency chains in address calculation at the beginning of the loop are gone too, which seems a win. (Or I'm sure there's some other, more complicated, way to get the compiler to get rid of them.) But if the space hit from using `unsigned` is allowable, I'd expect it to be both faster and less brittle. The processor doesn't really know what you're up to, it only sees registers. When `j` is stored in `ecx`/`rcx` and `ecx` isn't changing, it knows it's free to push ahead pretty far on speculation. If the update to `ecx` is rare, putting it behind a well-predicted-not-taken branch will make it go away, as far as the speculation engine is concerned, and let the processor go far and fast. (The rollback on mispredict can be pretty painful, but, well, that's out-of-order execution for you.) That's what we're really trying to accomplish here: stuff that single register write behind a rare branch, somehow. Here's what that can look like: https://clang.godbolt.org/z/1ss6hsEKb https://clang.godbolt.org/z/1ss6hsEKb Note that I disabled unrolling because some approaches got unrolled more than others. (I saw no unrolling, 2x, and more!) Comparing them without unrolling is fairest, I think, though it's also interesting to see how far they can unroll without assistance. I also found that clang didn't need any additional fencing (or care if it was present), but gcc did, so there's an `asm volatile` style fence, which I think is a lot more clear than the other tricks. (Your mileage may vary; people who've done a lot of low-level work won't blink at these, while others will just stare agape. Perhaps also not blinking, but for opposite reasons!) (Mind you, I didn't actually run any of this, so, well, you get what you pay for.)
- purplesyringa 3mo ago
  > A huge part of the problem here is that you're playing with the 8-bit registers. [...] That's an interesting thought, though in this particular case I think it's a little misguided. 8-bit arithmetic (or, god forbid, 16-bit arithmetic) can quickly cause unexpected stalls, but there is no arithmetic here: the only inherent difference between 8-bit and 32-bit code is the use of `movzx` versus `mov` in a memory load, which to the best of my knowledge are equivalent in performance (modulo store-to-load forwarding and such). It does look like LLVM generates ugly code for address calculation, though. I don't think it's necessarily going to cause a large effect, since `movzx r8d, cl; lea rdx, [rdi + r8]` doesn't depend on the previous iteration, and the critical latency chain here is just `inc rax`, but it might affect throughput a little. It's quite unfortunate that the induction heuristics didn't do their best here. > so there's an `asm volatile` style fence I've seen a couple people suggest the compiler fence, and all of them did the same thing -- they put `asm volatile` after the assignment to `j`, not before. Could you explain your thought process here? I thought putting it before the second load would make more sense, because I can imagine if (j != next_j[i][j]) { j = next_j[i][j]; asm volatile("" : "+r"(j)); } being (de)optimized to unsigned char value = next_j[i][j]; _Bool flag = j != value; j = value; if (flag) { asm volatile("" : "+r"(j)); } which in turn could be compiled to `mov reg, [mem]; cmp reg, reg; mov reg, reg; je`, whereas if (j != next_j[i][j]) { asm volatile("" : "+r"(j)); j = next_j[i][j]; } doesn't permit such an optimization because it forces a conditional load, which you can't avoid putting behind a branch. I have no doubt that putting the fence after the assignment works in this scenario (clearly it does, since LLVM and GCC recognize it), but I don't intuitively see why.

112 points by birdculture 3mo ago

Brilliant! Hadn't seen this technique before.

latency optimization is a skill. I liked how you went till CSE pass. I myself wrote several passes to go to lowest latency possible

akoboldfrying 3mo ago

This is really surprising! I've never considered the possibility that using an equality test to skip a write that would be a no-op could break a dependency and thus lead to higher perf overall if the "equal" outcome occurs often enough. This might be applicable in many situations where you "edit" some data in-place, but most of the time there are few or no changes.

anthonj 3mo ago

I think this call for something similar to "__builtin_expect" or linux' likely()/unlikely(). Not very clean, but better than inserting obscure optimisations in the source.

gblargg 3mo ago
Assuming compilers are smart enough to insert an unnecessary branch to break the dependency.
- vitally3643 3mo ago
  That's what the hints are for. Expect/likely/unlikely are the programmer informing the compiler what it should expect and how it should optimize
purplesyringa 3mo ago
That would be great, if only it worked as intended! From the perspective of an optimizing compiler, `a == b ? a : b` is worse than `b` regardless of the probability you assign to `a == b`. ETA: someone on Lobsters (https://lobste.rs/s/1an425/quadrupling_code_performance_with#c_4clhdw https://lobste.rs/s/1an425/quadrupling_code_performance_with...) noticed that `[[unlikely]]` actually works on LLVM (not on GCC, and with worse codegen on LLVM, but it's still good to know) -- updated the post.
MaxBarraclough 3mo ago
I was wondering the same thing. Also, could profile-guided optimisation help here?

mcv 3mo ago

Interesting. I thought modern CPU optimisation required avoiding branches, but here adding the branch allows the branch pediction to parallelise what it otherwise couldn't.

zipy124 3mo ago
It does and the key here is that adding the if is akin to avoiding a branch, since getting data then doing something with it is a hidden branch if you already have the data. All this code does is formalise the hidden branch so that it can be avoided when possible.
- summarybot 3mo ago
  That's pretty cool. Is there something obcluding the compiler from noticing this parallelization opportunity without the new `if` ? My understanding is the assignment and the evaluation are somehow coupled in this case based on the essay, but I could use an explanation.
  - purplesyringa 3mo ago
    The optimization in the post is only advantageous if `next_j[i][j] == j` holds often enough. Without prior knowledge, the compiler can't know if it's going to improve performance, and the worst losses are greater than the best wins (branch misprediction is very expensive), so it decides not to interfere.
- nextaccountic 3mo ago
  > since getting data then doing something with it is a hidden branch if you already have the data You mean that the naive, simpler code, despite not having an if, has a "branch" on the microarchitectural state? (which is like.. if we have this already in cache, do something. if not, do something else) // Find the optimal encoding for each symbol. // Chunk boundaries are located where encodings change. uint8_t encoding[n_symbols]; uint8_t j = 0; // always start with encoding 0 for simplicity for (int i = 0; i < n_symbols; i++) { j = next_j[i][j]; encoding[i] = j; }

throawayonthe 3mo ago

lobsters comment points out [[unlikely]] works here for clang https://clang.godbolt.org/z/r4xYWfPfe https://clang.godbolt.org/z/r4xYWfPfe edit: oh the article also mentions it now :)

6510 3mo ago

my js brain keeps thinking encoding[i] = next_j[i][j];

pillmillipedes 3mo ago

wow, what an interesting optimization! how would you even figure out that that if is what's needed to make it faster?

purplesyringa 3mo ago
I knew the loop was latency-bound and I couldn't easily decrease the latency, so I knew I had to somehow avoid the dependency chain at all. I remembered that CPUs predict some properties of memory accesses (e.g. they might predict that a store and then a load from different addresses likely don't intersect), but not addresses, so I thought about another way to force it to predict `j` well. Branch prediction turned out to be the simplest way to do so. Actually, since then I've found out that I could reduce latency by replacing a load on the critical chain with a vector shuffle instruction (`pshufb`, takes just 1 cycle on x86). Ironically, if I realized that sooner, I probably wouldn't have tried to use branch prediction at all!

nonadhocproblem 3mo ago

I've also been working on a compressor recently, and the same general idea (letting the compiler know that a data dependency occurs very infrequently, and it should therefore assume none exists to exploit ILP) has allowed me to speed up my decompression by a lot: https://github.com/welcome-to-the-sunny-side/misa77/blob/777f329b30653162ee0ba66fb42d838618d1b030/src/decompress_impl.h#L55-L56 https://github.com/welcome-to-the-sunny-side/misa77/blob/777...

patrulek 3mo ago

You can utilize MLP (memory-level parallelism) and reduce memory latency by reading whole 8 bytes of next_j at every iteration. Just do something like `uint64_t packed_next_j = *(uint64_t*)(&next_j[i])` and then just shift right to find proper j. This way you remove dependency on previous iteration. Did you tried that?

purplesyringa 3mo ago
The right-shift is the problem. You need to shift right by `j * 8`, which itself requires a shift to compute (`j << 3`), so you have two shifts on the critical path, resulting in a latency of 2 cycles. It's better than a load, but it's still noticeable.
- patrulek 3mo ago
  2 cycles vs ~5 cycles is still nice improvement plus its more deterministic (but not that fast in optimistic case; better in pessimistic case) than `if` appraoch and probably easier to "invent" and reason about. Definitely not that cool as your `if` solution though :)
OptionOfT 3mo ago
Don't you need the previous iteration to find out how much you need to shift right?
- patrulek 3mo ago
  Yes you need, but the initial problem here were sequential loads from L1 into registers.

exmadscientist 3mo ago

A huge part of the problem here is that you're playing with the 8-bit registers. They work, but they're like travelling the back roads: the CPU designers put all their effort into the big highway next door, and not so much into keeping the back roads clear. They're infamous for random weird stalls and such. I wouldn't be surprised at all if there's dependency chain tracking weirdness using them. If you can change the type on `next_j` over to `unsigned` (or `size_t` or ...) then a lot of weird stuff goes away. The dependency chains in address calculation at the beginning of the loop are gone too, which seems a win. (Or I'm sure there's some other, more complicated, way to get the compiler to get rid of them.) But if the space hit from using `unsigned` is allowable, I'd expect it to be both faster and less brittle. The processor doesn't really know what you're up to, it only sees registers. When `j` is stored in `ecx`/`rcx` and `ecx` isn't changing, it knows it's free to push ahead pretty far on speculation. If the update to `ecx` is rare, putting it behind a well-predicted-not-taken branch will make it go away, as far as the speculation engine is concerned, and let the processor go far and fast. (The rollback on mispredict can be pretty painful, but, well, that's out-of-order execution for you.) That's what we're really trying to accomplish here: stuff that single register write behind a rare branch, somehow. Here's what that can look like: https://clang.godbolt.org/z/1ss6hsEKb https://clang.godbolt.org/z/1ss6hsEKb Note that I disabled unrolling because some approaches got unrolled more than others. (I saw no unrolling, 2x, and more!) Comparing them without unrolling is fairest, I think, though it's also interesting to see how far they can unroll without assistance. I also found that clang didn't need any additional fencing (or care if it was present), but gcc did, so there's an `asm volatile` style fence, which I think is a lot more clear than the other tricks. (Your mileage may vary; people who've done a lot of low-level work won't blink at these, while others will just stare agape. Perhaps also not blinking, but for opposite reasons!) (Mind you, I didn't actually run any of this, so, well, you get what you pay for.)

purplesyringa 3mo ago
> A huge part of the problem here is that you're playing with the 8-bit registers. [...] That's an interesting thought, though in this particular case I think it's a little misguided. 8-bit arithmetic (or, god forbid, 16-bit arithmetic) can quickly cause unexpected stalls, but there is no arithmetic here: the only inherent difference between 8-bit and 32-bit code is the use of `movzx` versus `mov` in a memory load, which to the best of my knowledge are equivalent in performance (modulo store-to-load forwarding and such). It does look like LLVM generates ugly code for address calculation, though. I don't think it's necessarily going to cause a large effect, since `movzx r8d, cl; lea rdx, [rdi + r8]` doesn't depend on the previous iteration, and the critical latency chain here is just `inc rax`, but it might affect throughput a little. It's quite unfortunate that the induction heuristics didn't do their best here. > so there's an `asm volatile` style fence I've seen a couple people suggest the compiler fence, and all of them did the same thing -- they put `asm volatile` after the assignment to `j`, not before. Could you explain your thought process here? I thought putting it before the second load would make more sense, because I can imagine if (j != next_j[i][j]) { j = next_j[i][j]; asm volatile("" : "+r"(j)); } being (de)optimized to unsigned char value = next_j[i][j]; _Bool flag = j != value; j = value; if (flag) { asm volatile("" : "+r"(j)); } which in turn could be compiled to `mov reg, [mem]; cmp reg, reg; mov reg, reg; je`, whereas if (j != next_j[i][j]) { asm volatile("" : "+r"(j)); j = next_j[i][j]; } doesn't permit such an optimization because it forces a conditional load, which you can't avoid putting behind a branch. I have no doubt that putting the fence after the assignment works in this scenario (clearly it does, since LLVM and GCC recognize it), but I don't intuitively see why.