Compute Both Answers and Throw One Away, Which Is Faster Than Deciding Which to Compute
Last timeGuessing Which Way You Will Go
An unpredictable branch can be turned into arithmetic that always runs. You pay for work you discard and you stop paying for mistaken guesses. Here is where the line falls.
Choosing without jumping
The previous lesson ended with a loop losing nine cycles an iteration to a
branch the processor could not guess. The remedy is to remove the thing being
guessed.
A processor can select between two values without any jump at all. The
comparison sets a flag, and a single instruction copies one of two registers
depending on that flag. No guess is made because no instruction stream was ever
in question: the same instructions execute in the same order regardless of the
data. The whole operation costs about one cycle, every time, with no variance.
with a branch:
if a > b:
m = a
else:
m = b
without one:
flag = (a > b)
m = select(flag, a, b)
the accumulate case, with a branch:
if a[i] > t:
total = total + a[i]
and without:
flag = (a[i] > t)
total = total + select(flag, a[i], 0)The accumulate case at the bottom is the loop from the previous lesson. The
addition now happens on every iteration regardless, adding zero when the
element is below the threshold. The total comes out identical and no branch was
involved.
Paying for the path not taken
The transformation is not free and the cost is always the same shape. Both arms
of the conditional are computed on every visit, so the work done per iteration
is the work of the if-arm plus the work of the else-arm, rather than one of
them.
When each arm is a comparison and an addition, that is an extra cycle or two
and nobody notices. When one arm contains a multiplication chain, or a function
call, or a load from memory, the picture changes completely, because that cost
is now paid on every iteration including the ones that did not want it.
The lesson stops here
2 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents