Article URL: https://purplesyringa.moe/blog/quadrupling-code-performance-with-a-useless-if/ Comments URL: https://news.ycombinator.com/item?id=48889148 Points: 52 # Comments: 3

One important problem was chunking the input string and optimally choosing the most compact encoding for each chunk (different encodings compress different characters better, so where to split is not immediately obvious). The previous post describes the algorithm if you’re interested, but it boils down to finding the shortest path on a grid. For each cell, the algorithm computes the best cell following it. Following references from the first cell to the last one gives the optimal coding order. That long loop is not the topic of this post, it’s well-optimized. We’re here to talk about the second loop, which at first glance looks much simpler. Excluding the write, the body of the loop is just j = next_j[i][j], which compiles to a single mov instruction. How could this possibly not be optimal? If we were programming in 1984, it would be, but modern processors have instruction-level parallelism – that is, they can execute multiple instructions in parallel. This works even across iterations of a loop, and it’s one reason why we usually don’t pay attention to instructions for i < n_symbols and i++ when evaluating loop performance – they don’t usually prevent the CPU from doing more work. Crucially, though, you cannot run two dependent instructions at the same time. In our case, each iteration of the loop cannot begin before the previous iteration ends because j is threaded through the loop, so we’re limited by the latency of memory access, which is pretty noticeable even with cache. Can this be fixed? In this specific case, yes! We don’t expect too many chunks, so next_j[i][j] is quite likely to just be equal to j. If we could tell the CPU to predict that j stays intact, the loop would become throughput-bound rather than latency-bound. While we don’t have direct control over address prediction, we can simulate this with branch prediction: If the CPU predicts the if body as unlikely, it will ignore it and thus not see any dependency between different iterations. When the condition eventually evaluates to true, branch misprediction resolution will kick in, undo wrong speculative writes, and restart with the right j. That’s exactly what we want!