Comment by mcv

3 days 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.

5 comments

mcv

Reply
zipy124  3 days 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.

  • nextaccountic  2 days 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;
    }

    • mcv  2 days ago

      It's not so much a branch, but a dependency between subsequent iterations of the loop, which means execution of each iteration has to wait for the result from the previous iteration, slowing things down. But if most of the time j == next_j[i][j], that dependency is often unnecessary. So the branch allows the system to predict that it can be parallelized. But that's only really worth it if the branch condition is false most of the time. Whenever it turns out to be true, the CPU will have to backtrack and redo that work.

  • summarybot  2 days 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  2 days 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.