Faster sorted array unions by reducing branches | Hacker News Reader

Faster sorted array unions by reducing branches

lemire.me

47 pointsingve27 comments

I 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

A detailed exploration of this sort of optimization

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.

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.

yes, 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.

Conditional 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.

These days cmov reg, reg is very cheap. Linus used to rant against it but then the latency was much higher.

It 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.

Unfortunately 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 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.

I'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)

The 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).

So 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 ...

Well, renaming allows removing false dependencies due to reuse of registers (for example allowing multiple iterations of a loop to partially overlap or even execute in parallel), but in this case it is a true dependency: the iteration variables depends on the values loaded off it, which prevent out of order execution.

Branch prediction would break the dependency, but the misprediction rate here is high enough for this specific algorithm to be usually a net negative.

Right, essentially loop unrolling through the renamed registers (if I remember my lessons on Hennessey and Patterson 25+ years ago).

I'm vaguely aware of this, but also honestly surprised the CPU isn't speculating on the move anyway.

In 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.

In 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.

Would 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.

Certainly, but the effectiveness is data dependent. It would work well for example if the two ranges have little overlap.

I'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.

Are 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++];

It 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.

Honestly I was mostly curious if it would even work, because it sure looks like it ought not to.

What about

  pos1 += (v1<=v2);

?

The optimizer will do this anyway.

The whole point of the article is that the optimizer in GCC did not do this.

Throw it in godbolt and see if the assembly is different. I would doubt not.

I 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

Reply on news.ycombinator.com