3 ms·
Faster sorted array unions by reducing branches
- ncmncm 5y agoA detailed exploration of this sort of optimization https://cantrip.org/sortfast.html https://cantrip.org/sortfast.html It seems like the code presented could be improved further, something like: while ((pos1 < size1) & (pos2 < size2)) { v1 = input1[pos1]; v2 = input2[pos2]; bool less = v1 <= v2; output_buffer[pos++] = less ? v1 : v2; pos1 += less, pos2 += (1-less); } This is particularly likely in Gcc, which will not generate more than one CMOV instruction in a basic block. (Note: I did not check this in Godbolt. It probably needs some changes, such as s/(1-less)/(!less)/.) Where the compiler refuses to generate CMOV, such as when building without -march=native, something like output_buffer[pos++] = (-less & v1) | ((less-1) & v2); can be better than nothing. Again, maybe s/(less-1)/-!less/. Always benchmark! There are numerous surprises in this area.
- tralarpa 5y agoWhat about pos1 += (v1<=v2); ?
- zorgmonkey 5y agoI haven't benchmarked it, but surprisingly that seems to be enough to get the gcc assembly almost identical to what clang is producing https://gcc.godbolt.org/z/hfcYdP5rv https://gcc.godbolt.org/z/hfcYdP5rv
- layoutIfNeeded 5y agoThe optimizer will do this anyway.
- OskarS 5y agoThe whole point of the article is that the optimizer in GCC did not do this.
- Google234 5y agoThrow it in godbolt and see if the assembly is different. I would doubt not.
- deleted 5y ago[deleted]
- OskarS 5y agoNice 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 agoIn a previous life, I remember spending some time optimizing an inner loop almost like this (it was actually a sparse vector inner product). Whether full if-conversion or only partial was optimal depended a lot on the architecture and the data. Fun times.
- agbell 5y agoWould this benefit from the galloping optimization Tim Peter's was talking about on Hn recently? If one side is bigger than the other, try to find how many elements you can add from that side and advance that far.
- gpderetta 5y agoCertainly, but the effectiveness is data dependent. It would work well for example if the two ranges have little overlap.
- agbell 5y agoI'm sure the answer is you need to check, but would the cost of checking if you can gallop hurt performance in other cases. I'm wondering if this removing the branch idea and the galloping idea can coexist.
- leeter 5y agoI played around with the godbolt he put up, I honestly found that adding __restrict to the pointers appears to make the biggest generated code difference and the code seems to be written with that in mind. That does ruin portability sadly, but it does cut the number of instructions generated down significantly and allows the compiler to use memcpy. I'd be curious to compare that to his normal version in a benchmark
- rwmj 5y agoI'm surprised that conditional moves make much difference here. Aren't they essentially a compressed form of branch, and so still require speculation? Perhaps the fact that the code has a smaller size is what is making the difference. (Of course that's still a good outcome)
- gpderetta 5y agoThe branch predictor can't do a great job here as the branching is very data dependent. The conditional move prevents speculative execution (at the cost of adding a dependency).
- Filligree 5y agoI'm vaguely aware of this, but also honestly surprised the CPU isn't speculating on the move anyway.
- gpderetta 5y agoIn principle it could. But A) it would be a bit pointless because cmov is used to avoid badly predictable branches and B) IIRC after the whole spectre affair Intel gave the guarantee that cmov is never speculated. Regarding A, you could have a meta predictor that decides whether you should speculate or not, trained on the misprediciton rate. But then you do not need the cmov in the first place and you can just dynamically convert non-diverging jumps to predication. This is, I think, called Dynamic Hammock Predication and was implemented, in some restricted cases (IIRC jumping over a single instruction) in some recent POWER cpus from IBM. I think that RISC-V also doesn't have predication and an implementation is supposed to use this optimization instead.
- rwmj 5y agoSo the dependency is taken care of with register renaming? Trading renamed registers (which are basically "free" as modern processors have so many of them) for speculation. Interesting ...
- 5y ago
- contravariant 5y agoAre both sides of the ternary operator always evaluated? Otherwise you could even use this monstrosity: output_buffer[pos++] = (input1[pos1] <= input1[pos2]) ? input1[pos1++] : input2[pos2++];
- gpderetta 5y agoIt would work, but the point is not golfing but convincing the compiler to generate a cmov. The branches of your ?: have side effects, so it won't be easier for the compiler to optimize than a normal if.
- contravariant 5y agoHonestly I was mostly curious if it would even work, because it sure looks like it ought not to.
- ot 5y agoUnfortunately these hacks are very compiler-dependent and can become ineffective with a compiler update. Clang in particular is very stubborn about not emitting cmovs (see https://bugs.llvm.org/show_bug.cgi?id=40027 https://bugs.llvm.org/show_bug.cgi?id=40027 for example). In that thread the annotation __builtin_unpredictable() is discussed, which would be a good solution, but it does not support this case yet. In my code the only reliable alternative I found was inline ASM. Luckily with enough templating you can hide it away.