Mispredicted branches can multiply your running times

https://lemire.me/blog/2019/10/15/mispredicted-branches-can-multiply-your-running-times/

by ingve • 7 years ago

114 107 7 years ago

ncmncm2• 7 years ago

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.

ithkuil3• 7 years ago

no kidding

Well, that also means that some loops are fully unrolled :-)

mac010212• 7 years ago

And some loops use only unconditional jumps.

sifar• 7 years ago

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<howmany;i++) {
       
       out[index] = random();

    }

Ofcourse variable length loops would still have the branches.

ncmncm2• 7 years ago

Haswell and later can run loops with 4 instructions, including 2 ALU ops and two conditional branches -- provided only one is taken -- in one cycle.

Compilers prefer to order the instructions so they take two or more cycles.

dvhh• 7 years ago

related stackoverflow example:

https://stackoverflow.com/questions/11227809/why-is-processi...

saagarjha• 7 years ago

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…

rdc122• 7 years ago

At the software level, you don't get a choice about this thou, the CPU is going to speculate about a bounds check regardless, the optimization is it a different abstraction layer.

Pretty much any thing on the market with the compute power of a cellphone, is going to have a feature like this too

mac010212• 7 years ago

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? 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?

ThePadawan• 7 years ago

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

hellofunk• 7 years ago

This is pretty awesome.

vardump• 7 years ago

Just like you can do on x86/ARM SIMD. It often pays to compute both sides and mask out the undesired results.

gpderetta5• 7 years ago

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 specialization. edit: or stick with a potentially suboptimal number.

[1] https://en.wikipedia.org/wiki/Delay_slot

planteen3• 7 years ago

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

sv_h1b2• 7 years ago

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.

ericpauley• 7 years ago

Aside from other comments about weaknesses of delay slots, modern processors already do this automatically in the form of out of order execution. A branch can be moved up and assigned priority to an execution unit if it doesn't depend on some of the previous instructions. These instructions can be queued or assigned to other execution units.

dooglius• 7 years ago

It looks as though you're being downvoted but I'm not sure why. This matches my mental model of OoO execution, for instance if you have a loop like:

  sub eax, 1
  (several non-flags-touching instructions)
  jmpne loop_start

I would expect that a branch predictor wouldn't be needed as the jump only needs the flags register to figure out where the branch is going to go.

marcosdumay2• 7 years ago

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.

morelisp2• 7 years ago

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.

gpderetta5• 7 years ago

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

XJ64• 7 years ago

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.

lifthrasiir• 7 years ago

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.

XJ64• 7 years ago

Then you've got a bug which crashes if all your results were even and index is left zero.

SloopJon• 7 years ago

It strikes me that the example is a bit contrived: why is howmany decremented unconditionally? The first loop populates out with howmany numbers. The second loop may set none (other than the ignored value that you point out). I suppose you can use the same trick:

  howmany -= (val bitand 1);

But that might complicate the benchmark.

Coincidentally, this was the subject of the first Stack Overflow question Bjarne addressed in an interview the other day:

https://stackoverflow.com/questions/11227809/why-is-processi...

inetknght2• 7 years ago

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

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

kstenerud4• 7 years ago

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

omgtehlion2• 7 years ago

https://github.com/kstenerud/bit-tricks/blob/master/bytes_re...

looks like over-engineering of (bits + 7) >> 3

skrimp• 7 years ago

Your solution can overflow.

jacobolus• 7 years ago

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

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

naikrovek6• 7 years ago

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 getting slower more rapidly than hardware has been getting faster for nearly a decade, and the free performance gains that software people have taken advantage of when better hardware is made available are just about exhausted.

It's time to learn your platforms, software people.

[later addition] This kind of thing is also one of the reasons that teaching OOP principles as they are taught today is so bad for software performance. Modeling object relationships to match the real world will, in every non-toy program, produce object structures that are actively unfriendly to cache efficiency, and will therefore produce software which performs very poorly when compared to software that was written with the hardware platform in mind.

gildas• 7 years ago

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 = 5000000;
    let index = 0;
    const out = [];
    while (howmany) {
        const val = Math.floor(Number.MAX_SAFE_INTEGER * Math.random());
        if (val % 2) {
          out[index] = val;
          index += 1;
        }
        howmany--;
    }


    // Optimized for branch prediction
    let howmany = 5000000;
    let index = 0;
    const out = [];
    while (howmany) {
        const val = Math.floor(Number.MAX_SAFE_INTEGER * Math.random());
        out[index] = val;
        index += (val & 1);
        howmany--;
    }

naikrovek6• 7 years ago

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

This single person is also the only JS developer I know who has any clue how to actually improve performance in existing code.

djokkataja• 7 years ago

I tried both of those out in the console in firefox and chrome and found that in chrome the optimized version was about 10% faster, but in firefox the unoptimized version was about 5% faster.

Also it ran 30x faster in chrome... (~200ms vs ~6000ms)

meheleventyone3• 7 years ago

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.

This is a shame because not only are there lots of developers who write JS that have low-level backgrounds there are also a lot who haven't and are still interested. It seems rather snobby to jump in and write off a bunch of people because of the language they use on the assumption that they use the language without being aware of the implications.

On OOP versus more cache friendly approaches and branch prediction this talk from CPPCon 2019 is great: https://www.youtube.com/watch?v=HG6c4Kwbv4I

The interesting result is that although the DoD approach is eventually faster a branch misprediction causes havoc until uncovered.

naikrovek6• 7 years ago

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.

pjmlp7• 7 years ago

And when you outsmart the compiler, the CPU gets a microcode update and those clever micro-optimizations are thrown out of the window.

minipci13212• 7 years ago

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

vsareto6• 7 years ago

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 learn the platform fully if they keep that a secret.

Secondly, we've had CPU-level issues like spectre and meltdown introduced that affected performance in some cases. We can't even trust the platform makers to get it right!

naikrovek6• 7 years ago

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

Well, I would say that it's a very good reason, and that learning about branch prediction and caches is not a "drastic" step by any means.

Is there any software that you write whose users would not be made happier if the software performed better? Any at all?

Many of these platforms have undocumented CPU instructions

You don't need to know the secrets of a platform to understand branch prediction and caches, or to use that knowledge to produce software that performs far better than software written without that knowledge. You don't need to know the platform on a logic gate level, you need to understand how the platform executes your code, so that you can take advantage of the strengths of the platform. You don't need to know any hidden instructions or secrets to take advantage of the platform.

we've had CPU-level issues like spectre and meltdown introduced that affected performance in some cases

those things didn't affect performance, the fixes for those things did. The fixes also required no code changes outside of the firmware and the operating system, and knowing the platform is still the best way to write performant software, no matter what is going on to avoid hardware vulnerabilities.

emsy7• 7 years ago

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

If anything, job requirements for programming are way too low. I wouldn't let a mechanic anywhere near my car if I knew s/he didn't understand the basics of an Otto engine. I'm the first to admit I don't know as much about modern CPUs as I should, but I don't live in a fantasy world where I convince myself that I don't need to know it.

Many of these platforms have undocumented CPU instructions

So we should get the vendors to publish a proper documentation. This doesn't change anything about software developers responsibilities.

CPU-level issues

Perfectly answered in a sibling comment so I'll just leave it at that.

imtringued• 7 years ago

what's the point? You can't learn the platform fully if they keep that a secret.

By that logic we should never learn anything.

toast0• 7 years ago

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.

hamilyon22• 7 years ago

What good software modeling techniques could one learn instead of OOP?

pjmlp7• 7 years ago

Like Wirth puts it, algorithms + data structures.

Programming paradigms are orthogonal to that.

naikrovek6• 7 years ago

Data Driven Development is the single most impactful way to write performant code, if I had to single out some single thing. CPUs work on data, not a developer's abstractions about the data.

Everything from your structs and objects all the way up should be written with the data in mind.

Think about what pieces of data are needed at the same time, or in sequence, and not what classes you need to perform a certain action. Structuring your data types to keep pieces of data that will be operated on together, or read together alone can dramatically improve performance.

It's difficult for me to explain, and I'm confident once one sees examples that demonstrates the concept well, it will become clear pretty quickly.

DrScientist2• 7 years ago

And if your platform is a virtual machine or interpreter running across a number of chip archs?

Perhaps it would be better to simply have appropriate tests and benchmarks to see what's slow on what platform?

Otherwise it's guess work based on incomplete understanding of the many layers below.

ip26• 7 years ago

Generically cache and branch predict friendly code is worth most of the benefit. Micro-tuning is small potatoes compared to accidentally wiping the cache on each instruction (e.g. with badly designed objects) or mispredicting a thousand times in a row (e.g. with a poorly designed loop)

ThrowawayR2• 7 years ago

"And if your platform is a virtual machine or interpreter running across a number of chip archs?"

Outside of microcontrollers, I can't think of a processor in common use that doesn't have branch prediction or caches.

naikrovek6• 7 years ago

Even then, you're not going to be running on a wildly different set of architectures, I'm betting; it will be a finite set, of course, so you can attend to all the common optimizations and give the virtual machine what it needs to optimize the best it can.

No one is going to write a single piece of code that runs on both a z80 and a 56-core Xeon, for example.

amelius• 7 years ago

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.

inetknght2• 7 years ago

Or a machine learning algorithm which recomputes everything on every iteration

dspillett• 7 years ago

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.

I would agree it can be useful to understand the lower levels, for the majority of developers macro optimisations are far far more important. Things like not forcing unnecessary redraws client-side, or excess DOM manipulations in general, caching values and references instead of rederiving them on each iteration of a loop, avoiding excess database hits, not using a naive sorting method, being aware of network latency issues, not properly indexing the database, and so on, will dwarf the effect of micro-optimisations for branch prediction and CPU caching if you get them wrong.

understand your platform all the way down to the CPU

Which platform though? Not everyone is a back-end or embedded dev with constrained hardware to support. Are you targetting amd64 or ARM or something else? Any particular generation of CPU? In many cases an optimisation for one will have no effect elsewhere or worse will make others slower. Unless you are doing much tight-loop number crunching, is faffing around at this level really worth your time? Some understanding of cache concepts will help with overall algorithm design but most of what that knowledge will help you with generally (rather than for specific CPUs) is good practise for other reasons too.

JavaScript developers

JS and other JIT compiled languages make tweaks for specific platforms even less important. For the most part let the optimising compiler worry about that for the platform it is compiling for at the time or consider a lower level language.

never written in a low level language

I've written in assembly in the distant past (6502 & related, Z80, early x86 and a little of later x86). I did once used knowledge of cache sizes and population behaviour to optimise a little image processing (having the routine work on blocks of the pixel data that were small enough to remain in cache for longer than they would if not dividing into smaller chunks or if jumping around more randomly) done in inline assembly because Delphi's compiler produced a massively less optimal result if it wasn't.

I have enough low-level knowledge to feel safe saying I know that most developers (especially junior devs away from embedded (or other low-resource) systems) don't really need it, at least not in as much detail, in the current multi-platform world. They aren't working on code where the benefit of optimisations enabled by that knowledge aren't dwarfed by many other factors.

rhinoceraptor• 7 years ago

How is it not a good thing that you don't need to worry about CPU branch prediction when you're writing Javascript to POST a form to your server?

In most cases you don't need to go that deep to fix performance issues. Your SPA is probably slow because your app bundle is 10mb, not because you have an inner loop that is tripping the branch predictor.

Const-me• 7 years ago

However, there are tricks that compilers cannot use safely.

Why not? VC++ emits cmov quite often, for operator ? and similar code.

Mispredicted branches can multiply your running times

Related Stories