16 ms·
Mispredicted branches can multiply your running times
- dvhh 7y agorelated stackoverflow example: https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi...
- ncmncm 7y 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.
- ithkuil 7y ago> no kidding Well, that also means that some loops are fully unrolled :-)
- mac01021 7y agoAnd some loops use only unconditional jumps.
- ithkuil 7y agoYes, those of the infinite variety
- 0xdeadbeefbabe 7y agoHaven't seen any, and I never expect to. (will it halt? == yes)
- ithkuil 7y agosure, pulling the plug is perfectly valid mechanism for terminating a loop, albeit an external one :-)
- sifar 7y agoMost 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.
- ncmncm 7y agoHaswell 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.
- saagarjha 7y 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…
- rdc12 7y agoAt 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
- mac01021 7y agoI 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?
- marcosdumay 7y 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.
- morelisp 7y 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.
- lippel82 7y agoTo be slightly pedantic here: Power is energy per second, so power consumption itself would go down. Total energy consumption, which is power*time could go up.
- morelisp 7y agoThe correction is welcome - I am just a little sad we trained a cohort of developers to care about power, but not well enough to understand that race-to-sleep is usually the best way to achieve that.
- XJ6 7y agoAnd 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 7y agoThe 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.
- XJ6 7y agoThen you've got a bug which crashes if all your results were even and index is left zero.
- kstenerud 7y agoThe original code can end with index = 0 as well. The only difference is that in the optimized code, it will write to index 0, whereas in the original it will not.
- XJ6 7y agoIn the original code, an index = 0 would not be a problem. Here, trying to access out[index-1] would error. Yes, you could then guard against that of course, but then that's even more code to maintain. If this code is a critical hot-path then sure, micro-optimizations can make sense but doing so without over-commenting and a rigorous test suite to catch introduced bugs is a recipe for disaster.
- kstenerud 7y agoI 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 inputs were even, and neither attempts to access out[index-1].
- kstenerud 7y agoThis 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 https://github.com/kstenerud/bit-tricks
- omgtehlion 7y ago> https://github.com/kstenerud/bit-tricks/blob/master/bytes_required_for_bits.h https://github.com/kstenerud/bit-tricks/blob/master/bytes_re... looks like over-engineering of (bits + 7) >> 3
- skrimp 7y agoYour solution can overflow.
- omgtehlion 7y agothis won't: (bits + 7LL) >> 3
- jacobolus 7y agoIn https://github.com/kstenerud/bit-tricks/blob/master/sign.h https://github.com/kstenerud/bit-tricks/blob/master/sign.h Why not use: (x > 0) - (x < 0)
- naikrovek 7y agoThis 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 7y 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 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--; }
- naikrovek 7y agoYeah, 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.
- Const-me 7y ago> However, there are tricks that compilers cannot use safely. Why not? VC++ emits cmov quite often, for operator ? and similar code.