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.
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`.
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.
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.
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.
> 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;
}
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!
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:
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.
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 :)
21 comments
[ 0.16 ms ] story [ 17.8 ms ] threadNot very clean, but better than inserting obscure optimisations in the source.
My understanding is the assignment and the evaluation are somehow coupled in this case based on the essay, but I could use an explanation.
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)
https://clang.godbolt.org/z/r4xYWfPfe
edit: oh the article also mentions it now :)
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!
https://github.com/welcome-to-the-sunny-side/misa77/blob/777...
`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?