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

41–50 of 113 posts

Re: Mispredicted branches can multiply your running times

#41

Post by vsareto »

emsy wrote: post #37
vsareto wrote: post #32

Earlier quoted context omitted.

>I wouldn't let a mechanic anywhere near my car if I knew s/he didn't understand the basics of an Otto engine. That's hilarious because most of the electronics of cars are utter shit and it has nothing to do with how well those developers knew the CPU. >So we should get the vendors to publish a proper documentation. This doesn't change anything about software developers responsibilities. Most responsibilities are not…

>That's hilarious because most of the electronics That was an analogy. I wasn't talking about car electronics. I was talking about the lack of professional education in programming. >Most responsibilities are not concerned with low-level optimizations when javascript in particular typically deals with network connections I have yet to encounter a javascript program that doesn't run on a CPU. Also, javascript is one o…

>That was an analogy. I wasn't talking about car electronics. I was talking about the lack of professional education in programming.

Yeah and I'm pointing out that for Javascript dev, there's a lot more knowledge with a higher priority to learn than low-level CPU code.

That's why we shouldn't add it to job descriptions unncessarily.

>If it didn't we wouldn't need WASM, asm.js and countless ridiculous JS engine optimizations.

This is probably why Javascript from the OP was probably the worst language to choose to make an argument. If you want to know the platform, you'll have to learn these things as well.

OTOH you can just write your super high performance thing in C or assembly and spend less time learning the extra layers between JS and the CPU. Then the low-level tuning becomes more important and obvious, and its merit is way more understandable.

This kind of knowledge is totally okay for jobs in C or assembly. It's not a great idea as a requirement for javascript jobs.

Re: Mispredicted branches can multiply your running times

#42

Post by dooglius »

ericpauley wrote: post #16
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…

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.

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.

Re: Mispredicted branches can multiply your running times

#43

Post by minipci1321 »

pjmlp wrote: post #21
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 when you outsmart the compiler, the CPU gets a microcode update and those clever micro-optimizations are thrown out of the window.

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

Re: Mispredicted branches can multiply your running times

#44

Post by vsareto »

naikrovek wrote: post #39
vsareto wrote: post #30

Earlier quoted context omitted.

>Is there any software that you write whose users would not be made happier if the software performed better? Any at all? I'd say security is a bigger issue than performance most of the time. And most gains are going to happen within the code itself by, e.g., not writing n^2 when there's a log(n) solution or something similar. Plus we're talking about javascript, and that's likely to be software with network concerns…

> I'd say security is a bigger issue than performance most of the time. 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. I was asking about performance. You can be secure and perform well. I ask again: Is there any software that you write whose users would not be made happier if the software performed better? An…

>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 "don't increase these job requirements unnecessarily"

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

Yeah, a lot of websites. It just doesn't matter after a certain point.

From 10 seconds to 1 seconds? Definitely happier.

From 1 second to 0.1 seconds? Happier, but not as much as the first gain.

0.1 to 0.01 or further? They might not even notice it. And this is where the network makes further gains cost ineffective.

Take my arguments to C or assembly land with systems programming and I immediately lose on most fronts. Especially if you can translate fractions of a second into more money, there should be no restrictions on how much performance to go after IF speed == money.

But if you're doing systems programming with javascript and want the utmost performance, this just looks silly for both of us.

>This is one of those things that everyone "knows" but is actually not true.

You and kasey_junk have different/better experience than I do, because those questions come up way more often in javascript jobs than what you're promoting.

Re: Mispredicted branches can multiply your running times

#45

Post by amelius »

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.

Re: Mispredicted branches can multiply your running times

#46

Post by gpderetta »

vsareto wrote: post #44
naikrovek wrote: post #39

Earlier quoted context omitted.

> I'd say security is a bigger issue than performance most of the time. 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. I was asking about performance. You can be secure and perform well. I ask again: Is there any software that you write whose users would not be made happier if the software performed better? An…

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

Re: Mispredicted branches can multiply your running times

#47

Post by NotATroll »

emsy wrote: post #40
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 Do you also go to a doctor that came out of a bootcamp? Is your house built by a constructor that came out of a bootcamp? Would you fly with an aviator that came out of a bootcamp? Would you run banking software made by a developer that came out of a bootcamp?

So how, precisely, is anyone supposed to get experience if it's unacceptable to hire them fresh out of "boot camp".

Even if you go "INTERNSHIP". Well what, is everyone supposed to stick the unpaid intern on toy apps that don't give them any actual real world experience writing actual production software?

Cause then the next argument will just be "Do you also go to a doctor that came out of an internship? Is you house built by a constructor that came out of an internship?".

Elitism at its finest.

Re: Mispredicted branches can multiply your running times

#48

Post by gpderetta »

dooglius wrote: post #42
ericpauley wrote: post #16

Earlier quoted context omitted.

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.

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.

that's not how ooo cpu work in practice. Jumps are resolved at the fetch stage, always by consulting the predictor; at this stage there is no opportunity to actually execute the jmpne instruction and check if the sign flag is set or not. When the jumpne is executed later in the pipeline, its only effect it to either commit or rollback the speculation.

This is not specific of OoO cpus. In order cpus work the same way, assuming they have a predictor of course.

edit: to be more precise, jumps are not not resolved at the fetch stage, but in one of the early stages, in fact there is often a bubble for taken branches as the fetcher will fetch the next instruction in the stream by default.

Re: Mispredicted branches can multiply your running times

#49

Post by dspillett »

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.

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.

Re: Mispredicted branches can multiply your running times

#50

Post by pjmlp »

minipci1321 wrote: post #43
pjmlp wrote: post #21

Earlier quoted context omitted.

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

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

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.

Post reply on HN