Live data from Hacker News

Mispredicted branches can multiply your running times

lemire.me

101–110 of 113 posts

Re: Mispredicted branches can multiply your running times

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

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

Re: Mispredicted branches can multiply your running times

#102
post #81

Earlier quoted context omitted.

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

> That’s an unpopular opinion on HN

Too bad for HN, then, because commodifying web development has done it no favors.

> Many are still enjoying a low skill/high pay career and want to remain blissfully ignorant of their future.

That's where I was a few years ago. I'm a web developer who recently went back and re-learned all the low level stuff I forgot and didn't think was necessary 20 years ago. I was wrong.

Re: Mispredicted branches can multiply your running times

#103
post #44

Earlier quoted context omitted.

>you are fucking SKILLED at dodging questions and changing the topic to suit your own needs. you would fail out of a debate class in the first week, though. Look, you're trying to argue that javascript dev jobs should have this kind of knowledge on their descriptions and I'm arguing there's way more shit to worry about and this is near the bottom level of things javascript devs should know. That's why I opened with "…

> 0.1 to 0.01 or further? They might not even notice it. And this is where the network makes further gains cost ineffective. true. Of course the vast majority of web sites are nowhere near this point, not even to the 10 to 1 seconds.

Right, and moving from 0.1 seconds to 0.01 seconds means you can use one TENTH of the CPU time or Lambda time or whatever, so you can do more with fewer resources or scale down your infrastructure.

Performance matters, a LOT, and not just to end users; if you perform better, you save money on infrastructure.

Re: Mispredicted branches can multiply your running times

#104

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.

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.

Re: Mispredicted branches can multiply your running times

#105

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…

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

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.

Re: Mispredicted branches can multiply your running times

#106
post #97

Earlier quoted context omitted.

Again, just more insane elitism. You keep going to the "OH MY GOD, PEOPLE WOULD DIE" examples to try and make a fairly weak point. No one is going to die, because some noob made a crappy little site out of the millions of crappy little sites, and it's not performing like a demi-god. VMs and high level languages aren't "training wheels". Especially not VMs, that's just complete and utter non-sense. Unless you think li…

Just to be clear: VM means a language VM like the JVM. I don’t have a problem with high level languages in general, but the gains in developer efficiency tend to be paid for by the CPU. No I don’t think people die (although I wouldn’t be surprised if that was the case). I just don’t want to have to buy a 3000$ PC so I can run a fucking chat app, an editor and a browser somewhat decently. The opportunity cost of bad s…

Yet all that performance optimization gets thrown away when running on virtualized containers alongside sanitizers.

By the way, my language VM is your language runtime.

Re: Mispredicted branches can multiply your running times

#107
post #106
post #97

Earlier quoted context omitted.

Just to be clear: VM means a language VM like the JVM. I don’t have a problem with high level languages in general, but the gains in developer efficiency tend to be paid for by the CPU. No I don’t think people die (although I wouldn’t be surprised if that was the case). I just don’t want to have to buy a 3000$ PC so I can run a fucking chat app, an editor and a browser somewhat decently. The opportunity cost of bad s…

Yet all that performance optimization gets thrown away when running on virtualized containers alongside sanitizers. By the way, my language VM is your language runtime.

Yes runtime is the better word and the JVM was a bad example anyway. There are much worse offenders when it comes to throwing away CPU power.

Re: Mispredicted branches can multiply your running times

#108
post #18

Earlier quoted context omitted.

Yes, those of the infinite variety

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

sure, pulling the plug is perfectly valid mechanism for terminating a loop, albeit an external one :-)

Re: Mispredicted branches can multiply your running times

#109

Earlier quoted context omitted.

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

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

I am quite sure that writing performant code for current architectures is great idea. I am sure one can learn that skill.

My question is quite orthogonal to that. OOP lets you model your application in a way that somewhat natural. It's principles are well-researched. Resulting code is widely understood. It can be applied across many different domains.

I know no competing way to model software that comes even close to that qualities. Maybe I am wrong and data driven approach provides all that.

Re: Mispredicted branches can multiply your running times

#110
post #54

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…

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

I'm failing to see how "index" is the count of how many numbers you want to be in out[] rather than the count of how many numbers actually ARE in out[], or why this would be different between code examples.

> 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, that's the point, as was explicitly stated in the article.

> Yes, you can solve this by 'manually' only returning the first "index" elements but it's just asking for trouble and a source of bugs as seen in your attempt to describe it have a difference between the reality and your description.

What is there to solve? The end result in both cases is that variable "index" is 0, because 0 of the values in out[] are valid.

> You might not consider that to matter, but the point I'm trying to make isn't just nitpicking, it's that there are certain expected behaviours from code, and an array which is "all odd numbers, except maybe all odd but one last even number" is bound to lead to broken expectations.

Yes, and the expectation is that "index" tells you where the first garbage element is in the array (in both examples). You're either going to have an array with all garbage (index = 0), all garbage except the first element (index = 1), all garbage except the first and second elements (index = 2), and so on. What actual values are in a garbage index (even or odd or 0 or 1 or 2 or Martin Luther's birth year), are irrelevant because you're not going to read from those indices.

Post reply on HN