Branchless implementations are so hard to reason about.
Sometimes they are faster, sometimes they are slower, sometimes they are faster but your benchmark isn't random enough and the branch predictor makes the branchy implementation look like a winner, begging the question how random your real world data is.
Like I have these two functions. The first is at once twice as fast as the second, but also 20% slower, depending on whether you bench using the same sets of two 512-item buffers or if you rotate between 32 different buffers between iterations.
uint32_t retain_values_lin(std::span<CombinedDocId const> span) noexcept {
const auto start = span.cbegin();
const auto end = span.cend();
auto iter = span.cbegin();
while (read_ < end_ && iter < end) {
const CombinedDocId bv = data_[read_];
const CombinedDocId pv = *iter;
if (bv >= pv) { ++iter; }
if (bv <= pv) { ++read_; }
if (bv == pv) { retained_[write_++] = bv; }
}
return std::distance(start, iter);
}
uint32_t retain_values_lin_nonbranch(std::span<CombinedDocId const> span) noexcept {
const auto start = span.cbegin();
const auto end = span.cend();
auto iter = span.cbegin();
while (read_ < end_ && iter < end) {
const CombinedDocId bv = data_[read_];
const CombinedDocId pv = *iter;
iter += (bv >= pv);
read_ += (bv <= pv);
if (bv == pv) { retained_[write_++] = bv; }
}
return std::distance(start, iter);
}
(things tried that haven't made much difference is lifting the read_ and write_ updates into local variables to turn into registers, making the bv==pv case branchless, using naked pointers instead of iterators; the compiler already does all this because it's not a dum-dum)
--edit--
I forgot to make my point, which was something like it's not branches that are the problem, but branch prediction errors, and for something like a sort or merge function, those can vary quite dramatically based on the data (as you're typically rarely sorting strongly randomized numbers).
You're right. When the data is nearly sorted, the advantage of branchless partitioning is much smaller. In this case, a simple Lomuto quicksort using the middle element as the pivot is very fast.
marginalia | 22 hours ago
Branchless implementations are so hard to reason about.
Sometimes they are faster, sometimes they are slower, sometimes they are faster but your benchmark isn't random enough and the branch predictor makes the branchy implementation look like a winner, begging the question how random your real world data is.
Like I have these two functions. The first is at once twice as fast as the second, but also 20% slower, depending on whether you bench using the same sets of two 512-item buffers or if you rotate between 32 different buffers between iterations.
(things tried that haven't made much difference is lifting the
read_andwrite_updates into local variables to turn into registers, making the bv==pv case branchless, using naked pointers instead of iterators; the compiler already does all this because it's not a dum-dum)--edit--
I forgot to make my point, which was something like it's not branches that are the problem, but branch prediction errors, and for something like a sort or merge function, those can vary quite dramatically based on the data (as you're typically rarely sorting strongly randomized numbers).
[OP] chkas | 21 hours ago
You're right. When the data is nearly sorted, the advantage of branchless partitioning is much smaller. In this case, a simple Lomuto quicksort using the middle element as the pivot is very fast.