3 ms·
Nice article! This sort of code is not just used in databases, it's also obviously the "merge" step in mergesort. The fact that you have to "lure" the compiler
by OskarS 5y ago
Nice article! This sort of code is not just used in databases, it's also obviously the "merge" step in mergesort.
The fact that you have to "lure" the compiler into making the hot loop branchless is a little bit weird: you'd think there would be a compiler intrinsic or something which was like `cond_val(condition, val1, val2)` which worked something like `condition ? val1 : val2` but was guaranteed (or close to it) to be free of branches. Shaders have something like that with the `step()` function, seems like a useful thing for this kind of high-performance code.
I mean, obviously you could always write this yourself with inline assembly (or using SSE2 intrinsics or whatever), but that would only work on some platforms and might mess with compiler optimizations, so that seems less optimal.
- gpderetta 5y agoyes, at least with GCC, it is very hard to get it to reliably generate a cmov (or prevent it from doing it). Flag tricks are a bit more reliable.
- Filligree 5y agoConditional moves aren't as good for performance as you'd think. You can take this as hearsay, because I haven't spent nearly enough time on this to form an opinion myself, but what I've heard-- Is that cmov is only faster than regular branches if the branch prediction regularly fails. Otherwise it's the same speed, or it can even be slower. And most branches are predictable. It doesn't change the data dependencies, it only reduces overhead from branch misprediction. I suppose the instruction itself has a lot of overhead.
- ncmncm 5y agoIt doesn't take many branch mispredictions for cmov to do better. My rule of thumb is that if it can't predict better than 90%, cmov will be better. But, if it does predict well, the cmov version can take twice as long. So the penalty for getting it wrong is pretty stiff. Pipeline stalls while recovering from branch mispredictions are only part of the problem. Dependency chains are trickier to reason about, and can be as big a problem. Generally, if the next iteration cares about what happened in the last iteration, you have a dependency chain and a problem.
- gpderetta 5y agoThese days cmov reg, reg is very cheap. Linus used to rant against it but then the latency was much higher.