Mispredicted branches can multiply your running times • Hacker News Board

Re: Mispredicted branches can multiply your running times

#61

Post by toast0 » Wed, Oct 16, 2019, 4:11 PM UTC

vsareto wrote: post #23

naikrovek wrote: post #15

This is one of those things that is completely lost on someone who has never written in a low level language. I automatically assume JavaScript developers to be completely oblivious to this entire class of software development knowledge. It is important to understand your platform all the way down to the CPU, including things like branch prediction and caches if you want to have performant software. Software has been…

>It is important to understand your platform all the way down to the CPU, including things like branch prediction and caches if you want to have performant software. Let's not drastically increase job requirements for no good reason. >It's time to learn your platforms, software people. Many of these platforms have undocumented CPU instructions, so until you get a full accounting of that, what's the point? You can't l…

> Let's not drastically increase job requirements for no good reason.

Here's the short version of branch predictor awareness. If you can write your inner loop with fewer conditionals, it will probably perform better.

Is it relevant and worth doing? At some level, only if your loop is frequent and fairly tight -- otherwise the difference is likely to be in the noise. On the other hand, writing your code to avoid branches in general can be a reasonable style and get you in the right place by default.

Everybody is claiming to be a 'Full Stack' developer these days, but apparently that doesn't include much of the stack.

Re: Mispredicted branches can multiply your running times

#62

Post by inetknght » Wed, Oct 16, 2019, 4:14 PM UTC

XJ6 wrote: post #8

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

> And just like that, a micro-optimisation has introduced a bug.

If only the function had a unit test to catch such bugs

Re: Mispredicted branches can multiply your running times

#63

Post by inetknght » Wed, Oct 16, 2019, 4:15 PM UTC

amelius wrote: post #45

naikrovek wrote: post #15

This is one of those things that is completely lost on someone who has never written in a low level language. I automatically assume JavaScript developers to be completely oblivious to this entire class of software development knowledge. It is important to understand your platform all the way down to the CPU, including things like branch prediction and caches if you want to have performant software. Software has been…

Instead of peephole optimizing your code, I think more can be gained by ensuring that your code doesn't perform useless computations. For example, a game that recomputes the entire scene every frame, or a UI that recomputes an entire virtual-dom tree after every user action.

Or a machine learning algorithm which recomputes everything on every iteration

Re: Mispredicted branches can multiply your running times

#64

Post by 0xdeadbeefbabe » Wed, Oct 16, 2019, 4:15 PM UTC

ithkuil wrote: post #18

mac01021 wrote: post #7

Earlier quoted context omitted.

And some loops use only unconditional jumps.

Yes, those of the infinite variety

Haven't seen any, and I never expect to. (will it halt? == yes)

Re: Mispredicted branches can multiply your running times

#65

Post by marcosdumay » Wed, Oct 16, 2019, 4:21 PM UTC

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, actual clock speed isn't really relevant and has a complex relation to CPU speed. That circuitry isn't affecting clock speed, so it wouldn't change.

Re: Mispredicted branches can multiply your running times

#66

Post by littlestymaar » Wed, Oct 16, 2019, 4:22 PM UTC

naikrovek wrote: post #24

gildas wrote: post #17

Earlier quoted context omitted.

> I automatically assume JavaScript developers to be completely oblivious to this entire class of software development knowledge. Surprisingly, In JavaScript the technique described in the article is quite efficient on Firefox whereas the gain is almost negligible on Chrome. https://jsperf.com/mispredicted-branches Edit: Jsperf seeems to be down. Here are the 2 snippets of code I tested: // Unoptimized let howmany =…

Yeah, of course performance gains can be had in JavaScript, and I will add to that fact with the experience that I've had when working with JavaScript developers: only one that I've ever known has ever considered performance and worked to produce performant JS before multiple users complained and an issue was raised. All others simply do not care about Javascript performance until there is an issue created to address…

This matches my experience as well (as a former full-time JavaScript dev), but in most cases, where JavaScript devs don't care about performance, you don't even need to understand how the machine works to speed things up. 90% of the time, the algorithmic complexity isn't thought at all and there are plenty of quadratic (or worse) behaviors everywhere.

Re: Mispredicted branches can multiply your running times

#67

Post by meheleventyone » Wed, Oct 16, 2019, 4:51 PM UTC

ScottFree wrote: post #57

naikrovek wrote: post #22

Earlier quoted context omitted.

I realize that it is unfair to categorize ALL JS devs in this way, and it certainly is a tight fit for the JS developers that I have worked with in the past.

OT: Why did you feel the need to add this disclaimer? Isn't it assumed that there are always exceptions anytime somebody makes a statement on the macro level? I don't think anybody would mistake "JS devs" for "Every single last individual JS dev".

I don’t think that is a general assumption. Particularly when the generality is made not as a statement of fact but of opinion and in a disparaging manner.

Re: Mispredicted branches can multiply your running times

#68

Post by planteen » Wed, Oct 16, 2019, 4:57 PM UTC

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…

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 difficulty in filling the delay slots as you mentioned. If you were really lucky, your branch would also result in a register window overflow. By the time handling that was done, you lost your mental context of what was going on. shudder

Re: Mispredicted branches can multiply your running times

#69

Post by hellofunk » Wed, Oct 16, 2019, 5:02 PM UTC

ThePadawan wrote: post #10

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…

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.

Re: Mispredicted branches can multiply your running times

#70

Post by sifar » Wed, Oct 16, 2019, 5:04 PM UTC

ncmncm wrote: post #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.

Most DSPs have zero overhead loops (still branches) which don't incur a branch penalty. So something like below may take 1-2 cycles atmost, per iteration.

    for(i=0;i


Ofcourse variable length loops would still have the branches.


    
      Permalink
      View on HN
      Reply on HN
      Top