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:
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.
> 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;
}
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.
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`.
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.
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/777...
wow, what an interesting optimization! how would you even figure out that that if is what's needed to make it faster?
lobsters comment points out [[unlikely]] works here for clang
https://clang.godbolt.org/z/r4xYWfPfe
edit: oh the article also mentions it now :)
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.
> 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)
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.
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.
Brilliant! Hadn't seen this technique before.
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.
Assuming compilers are smart enough to insert an unnecessary branch to break the dependency.
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
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...) 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.
I was wondering the same thing. Also, could profile-guided optimisation help here?
latency optimization is a skill. I liked how you went till CSE pass. I myself wrote several passes to go to lowest latency possible
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.
my js brain keeps thinking encoding[i] = next_j[i][j];