Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Mispredicted branches can multiply your running times

lemire.me

Post reply on HN
Print view View original

71–80 of 113 posts

Re: Mispredicted branches can multiply your running times

#71

Post by gpderetta »

planteen wrote: post #68
gpderetta wrote: post #12

Earlier quoted context omitted.

You just reinvented delay slots [1]. Two issues: - It is not easy for the compiler to always fill up a single delay slot. Filling dozen of them (as required for a deeply pipelined modern processor) would be significantly harder. - The number of delay slots would depend on the depth of the cpu pipeline. If you do not want to expose microarchitectural details in your ISA, you need either JIT or install time specializat…

Oh this takes me back to a horrible time in my life when I was tracking down a terrible intermittent crash on a LEON (SPARC) processor. I was down at the assembly level, stepping over instructions. It was a bit mind bending to always have an instruction execute AFTER the branch (you wouldn't know if the branch was taken or not until AFTER the delay slot instruction). Often the delay instruction was a NOP, showing the…

Right, SPARC has both register windows and branch delay slots, truly a great collection of architectural dead ends :).

Re: Mispredicted branches can multiply your running times

#72

Post by couchand »

XJ6 wrote: post #54
kstenerud wrote: post #29

Earlier quoted context omitted.

I think you may have misread the code: while (howmany != 0) { val = random(); if( val is odd) { out[index] = val; index += 1; } howmany--; } vs while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; } Both of these store a list of odd numbers in out[], with "index" containing the resulting count of how many numbers are in out[]. Both will have an "index" (count) value of 0 if all…

You were right I misinterpreted "out[0] to out[index-1]" but your next statement: > count of how many numbers are in out[] is not true, in the latter case it's a count of how many numbers you want to be in out[]. Consider what happens if howmany is 1 and it generates a single even number. In the original you have an empty array and index 0, in the newer one you have an array e.g. [2] and an index 0. Yes, you can solv…

Granted, the examples lack enough detail to know precisely how `out` is allocated. However, it seems safe to assume from the context that `out` is allocated by the client and `index` is returned to indicate the total number. There is no case where `out` is an "empty array", it always must have enough space for `howmany` integers.

Re: Mispredicted branches can multiply your running times

#73

Post by morelisp »

marcosdumay wrote: post #65
mac01021 wrote: post #6

I 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…

> How much circuitry would we save by leaving out the predictor? Enough to allow a measurable speedup in the CPU clock speed? Considering the complex predictors on current PCs, we would save quite a lot of circuitry. But that circuitry is there because it is the most effective place to increase the CPU speed, if you used it for something else, speed would go down, not up (but power consumption would improve). Also, a…

> speed would go down, not up (but power consumption would improve).

Power consumption per second might go down, but overall may go up, depending on how many more seconds the computation takes.

Re: Mispredicted branches can multiply your running times

#74

Post by gpderetta »

marcosdumay wrote: post #65
mac01021 wrote: post #6

I 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…

> How much circuitry would we save by leaving out the predictor? Enough to allow a measurable speedup in the CPU clock speed? Considering the complex predictors on current PCs, we would save quite a lot of circuitry. But that circuitry is there because it is the most effective place to increase the CPU speed, if you used it for something else, speed would go down, not up (but power consumption would improve). Also, a…

In fact, to increase clock speed you need more pipeline stages, which means higher mispredict penality which means you need a better branch predictor...

Re: Mispredicted branches can multiply your running times

#75

Post by jacobolus »

kstenerud wrote: post #13

This is the main reason why I've codified a bunch of bit tricks so I don't forget them [1]. They're often not worth using, but can sometimes work as a last-mile optimization after you've done all your algorithmic changes, cache locality, sizing, alignment, etc. [1] https://github.com/kstenerud/bit-tricks

In https://github.com/kstenerud/bit-tricks/blob/master/sign.h

Why not use: (x > 0) - (x < 0)

Re: Mispredicted branches can multiply your running times

#76

Post by gpderetta »

XJ6 wrote: post #54
kstenerud wrote: post #29

Earlier quoted context omitted.

I think you may have misread the code: while (howmany != 0) { val = random(); if( val is odd) { out[index] = val; index += 1; } howmany--; } vs while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; } Both of these store a list of odd numbers in out[], with "index" containing the resulting count of how many numbers are in out[]. Both will have an "index" (count) value of 0 if all…

You were right I misinterpreted "out[0] to out[index-1]" but your next statement: > count of how many numbers are in out[] is not true, in the latter case it's a count of how many numbers you want to be in out[]. Consider what happens if howmany is 1 and it generates a single even number. In the original you have an empty array and index 0, in the newer one you have an array e.g. [2] and an index 0. Yes, you can solv…

You are reading too much in a minimalistic example to show some specific detail.

Re: Mispredicted branches can multiply your running times

#77

Post by sv_h1b »

gpderetta wrote: post #12
mac01021 wrote: post #6

I 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…

You just reinvented delay slots [1]. Two issues: - It is not easy for the compiler to always fill up a single delay slot. Filling dozen of them (as required for a deeply pipelined modern processor) would be significantly harder. - The number of delay slots would depend on the depth of the cpu pipeline. If you do not want to expose microarchitectural details in your ISA, you need either JIT or install time specializat…

Plus, the delay slots are typically _fixed_ 1-5 cycles depending on CPU architectures. The problem is sometimes the real delay could easily be 200+ cycles (TLB/ cache reload, bus contention etc.) and _variable_.

There's no way you could cover all variable latency scenarios with fixed delay slots, unless you have a highly specific scenario like a GPU where you control all the internals.

Re: Mispredicted branches can multiply your running times

#78

Post by sv_h1b »

hellofunk wrote: post #69
ThePadawan wrote: post #10

Earlier quoted context omitted.

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

This is pretty awesome.

GPUs are designed to do massive parallel computations which all branch one way and don't have much (any?) branch prediction logic.

You trade it off with increased code size which might spill the cache but for small tight loops not exceeding the cache line/ size it would still be a good win.

Re: Mispredicted branches can multiply your running times

#79

Post by planteen »

pjmlp wrote: post #50
minipci1321 wrote: post #43

Earlier quoted context omitted.

Your logic would also apply to the compiler back-end to the same measure. Should it emit optimized code then?

Yep, it is easier to update the compiler than doing manual clever tricks, specially if the compiler happens to be an AOT/JIT with PGO feedback loop. Most people aren't able to outsmart their compiler optimizers.

The article is C++, so not sure why you are bringing up AOT/JIT since it doesn't apply here. And clearly there is a large gain possible by doing a calculation rather than a conditional with a high entropy result, otherwise, the article's mentioned speedup wouldn't have happened. A PGO feedback loop isn't going to do anything on a high entropy conditional. I saw a great talk at CppCon 2019 by Andrei Alexandrescu about speeding up std::sort. He does this same trick among others to speed up the C++ std library sort routine.

https://www.youtube.com/watch?v=FJJTYQYB1JQ

Post reply on HN