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

81–90 of 113 posts

Re: Mispredicted branches can multiply your running times

#81

Post by emsy »

ScottFree wrote: post #60
vsareto wrote: post #34

Earlier quoted context omitted.

>I’d love to see that common thought validated because in practice I’ve seen it to not be true at all. If you have Javascript devs that came out of some boot camp with no knowledge of either, do you teach algorithms 101 or low-level CPU programming 101 first? I would argue your codebase would benefit from teaching them algorithms first, then the other one. >In my experience in either high throughput or low latency sy…

> If you have Javascript devs that came out of some boot camp with no knowledge of either, do you teach algorithms 101 or low-level CPU programming 101 first? The latter. It's also known as "computer architecture" and is something typically taught in the first two years of a bachelor's degree. How can you hope to learn to properly program a computer if you don't know what a computer is?

That’s an unpopular opinion on HN, and not because you can’t learn those thing outside of university (because you absolutely can). But because there’s a push by the industry to make programming a low skill/low wage job. Many are still enjoying a low skill/high pay career and want to remain blissfully ignorant of their future.

Re: Mispredicted branches can multiply your running times

#82

Post by rhinoceraptor »

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…

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.

Re: Mispredicted branches can multiply your running times

#83

Post by djokkataja »

gildas wrote: post #17
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…

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

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)

Re: Mispredicted branches can multiply your running times

#84

Post by lippel82 »

morelisp wrote: post #73
marcosdumay wrote: post #65

Earlier quoted context omitted.

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

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

Re: Mispredicted branches can multiply your running times

#85

Post by ThrowawayR2 »

DrScientist wrote: post #35
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…

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.

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

Re: Mispredicted branches can multiply your running times

#86

Post by morelisp »

lippel82 wrote: post #84
morelisp wrote: post #73

Earlier quoted context omitted.

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

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

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

Re: Mispredicted branches can multiply your running times

#87

Post by pjmlp »

planteen wrote: post #79
pjmlp wrote: post #50

Earlier quoted context omitted.

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…

Because implementation and programming language are not the same thing?

Speaking of which, better catch up on the C++ interpreters and JIT related talks from CppCon 2019.

Re: Mispredicted branches can multiply your running times

#88

Post by pjmlp »

minipci1321 wrote: post #56
pjmlp wrote: post #50

Earlier quoted context omitted.

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.

(This missed my question. Once the compiler is updated to the uArch change, we don't rebuild all binaries out there that were built by the old versions, and their speed is possibly compromised by the uArch change. Should we then even care about emitting binary code optimized for a given uArch, if we can guarantee it is stable in time?)

Depends on the use case.

One reason mainframes still use bytecode as executable format is that it allows for AOT compiling the world after and OS or hardware upgrade.

And there are solutions for doing that to plain native opcodes as well.

Finally there is the whole issue that many micro-opmizations, while fun to implement, seldom contribute for visible optimizations of the business case at hand.

Re: Mispredicted branches can multiply your running times

#89

Post by planteen »

pjmlp wrote: post #87
planteen wrote: post #79

Earlier quoted context omitted.

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…

Because implementation and programming language are not the same thing? Speaking of which, better catch up on the C++ interpreters and JIT related talks from CppCon 2019.

I can't tell if you are trying to troll here. So you reject the notion of branchless coding as a premature optimization because you think it is going to be made irrelevant by a potential future microcode update? Or are you saying that a C++ interpreter/JIT would have made this branchless at run-time, but that optimization isn't made at compile time?

Re: Mispredicted branches can multiply your running times

#90

Post by ScottFree »

meheleventyone wrote: post #67
ScottFree wrote: post #57

Earlier quoted context omitted.

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.

Are you telling me when somebody says "Programmers make the web", you can't infer from context that they're not talking about all programmers?
Post reply on HN