I saw a sentence in a paper "Transforming branches into data dependencies to avoid mispredicted branches." (Page 6)
I wonder how to change the code from branches into data dependencies.
This is the paper: http://www.adms-conf.org/p1-SCHLEGEL.pdf
Update: How to transform branches in the binary search?
The basic idea (I would presume) would be to change something like:
if (a>b)
return "A is greater than B";
else
return "A is less than or equal to B";
into:
static char const *strings[] = {
"A is less than or equal to B",
"A is greater than B"
};
return strings[a>b];
For branches in a binary search, let's consider the basic idea of the "normal" binary search, which typically looks (at least vaguely) like this:
while (left < right) {
middle = (left + right)/2;
if (search_for < array[middle])
right = middle;
else
left = middle;
}
We could get rid of most of the branching here in pretty much the same way:
size_t positions[] = {left, right};
while (left < right) {
size_t middle = (left + right)/2;
positions[search_for >= array[middle]] = middle;
}
(For general purpose code use left + (right-left)/2 instead of (left+right)/2.)
We do still have the branching for the loop itself, of course, but we're generally a lot less concerned about that--that branch is extremely amenable to prediction, so even if we did eliminate it, doing so would gain little as a rule.