Mispredicted branches can multiply your running times
1–10 of 113 posts
Re: Mispredicted branches can multiply your running times
#2> most loops are actually implemented as branches.
No kidding!
But the article does call attention to a very important technique. It merits serious thought over all the ways it can be applied, that may not look much like this one, on the surface.
Re: Mispredicted branches can multiply your running times
#3related stackoverflow example:
https://stackoverflow.com/questions/11227809/why-is-processi...
Re: Mispredicted branches can multiply your running times
#4> most loops are actually implemented as branches. No kidding! But the article does call attention to a very important technique. It merits serious thought over all the ways it can be applied, that may not look much like this one, on the surface.
> no kidding
Well, that also means that some loops are fully unrolled :-)
Re: Mispredicted branches can multiply your running times
#5> If you are accessing the content of an array, many languages will add “bound checking”: before accessing the array value, there will be a hidden check to see whether the index is valid. If the index is not valid, then an error is generated, otherwise the code proceeds normally. Bound checks are predictable since all accesses should (normally) be valid. Consequently, most processors should be able to predict the outcome nearly perfectly.
Warning! This is just a stone's throw from the kind of thing that got us Spectre, so keep in mind this sort of optimization can occasionally come back to bite you…
Re: Mispredicted branches can multiply your running times
#6I am not a computer engineer and I always wondered:
What if we had a modern, pipelined CPU architecture with no branch predictor, which instead unconditionally executed the X instructions immediately following every branch before (possibly) proceeding with the branch's target instruction?
Would compilers and programmers be able to find most of the efficiencies that we currently rely on the branch predictor to find? What would be the common cases where it would be hard to do that?
How much circuitry would we save by leaving out the predictor? Enough to allow a measurable speedup in the CPU clock speed?
Re: Mispredicted branches can multiply your running times
#7> most loops are actually implemented as branches. No kidding! But the article does call attention to a very important technique. It merits serious thought over all the ways it can be applied, that may not look much like this one, on the surface.
> no kidding Well, that also means that some loops are fully unrolled :-)
And some loops use only unconditional jumps.
Re: Mispredicted branches can multiply your running times
#8And just like that, a micro-optimisation has introduced a bug.
If the last number generated is even, it will still appear in the result set in the new code, and not in the old code.
Re: Mispredicted branches can multiply your running times
#9And just like that, a micro-optimisation has introduced a bug. If the last number generated is even, it will still appear in the result set in the new code, and not in the old code.
The code assumes that, once the loop finishes, out[0] through out[index-1] contains the desired output. out[index] is not a part of that output.
Re: Mispredicted branches can multiply your running times
#10I am not a computer engineer and I always wondered: What if we had a modern, pipelined CPU architecture with no branch predictor, which instead unconditionally executed the X instructions immediately following every branch before (possibly) proceeding with the branch's target instruction? Would compilers and programmers be able to find most of the efficiencies that we currently rely on the branch predictor to find? W…
Not a computer engineer either, but I did do some GPGPU in college (~6 years ago).
Notably, branching on a flag f on the GPU was so slow that most of the time it was faster to (manually) compute both branches b1 and b2 and then calculate the result as r = f * b1 + (1-f) * b2 (where f is either 0 or 1).