Live data from Hacker News

Mispredicted branches can multiply your running times

lemire.me

91–100 of 113 posts

Re: Mispredicted branches can multiply your running times

#91

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

> https://github.com/kstenerud/bit-tricks/blob/master/bytes_re... looks like over-engineering of (bits + 7) >> 3

Your solution can overflow.

Re: Mispredicted branches can multiply your running times

#92

Earlier quoted context omitted.

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?

Of course but that is a substantially different statement than “I automatically assume JavaScript developers to be completely oblivious to this entire class of software development knowledge.“

Programmers make the web is a true statement of fact it’s just that it’s a subset of programmers that do it.

The OPs statement is a lazy opinion about JavaScript developers in general unambiguously applied. So I welcome their later amendement.

Re: Mispredicted branches can multiply your running times

#93
post #51

Earlier quoted context omitted.

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…

>Elitism at its finest. Do you think doctors in training get to do open heart surgeries by themselves fresh out of university? Do you think we train aviators that can only fly using the autopilot? Because that's the way we treat software developers. This has nothing to do with elitism and everything with professionalism. Our industry has built training wheels in form of various VMs and high level languages because it…

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 literally every website on the web should have a 100% dedicated server box.

VMs are good for a great many of things, both noob-friendly and not.

As for high level languages, they were meant for one particular thing. To get a task done quickly. Which is largely the real reason why so much software out in the wild performs like crap.

Anyone can sit down and spend years making a highly performant piece of software. But when things have to move fast, corners get cut & there's not enough time dedicated to researching to get said product to be as highly performant.

Re: Mispredicted branches can multiply your running times

#94

Earlier quoted context omitted.

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?

Of course but that is a substantially different statement than “I automatically assume JavaScript developers to be completely oblivious to this entire class of software development knowledge.“ Programmers make the web is a true statement of fact it’s just that it’s a subset of programmers that do it. The OPs statement is a lazy opinion about JavaScript developers in general unambiguously applied. So I welcome their l…

[deleted]

Re: Mispredicted branches can multiply your running times

#95
post #78

Earlier quoted context omitted.

This is pretty awesome.

GPUs are designed to do massive parallel computations which all branch one way and don't have much (any?) branch prediction logic. You trade it off with increased code size which might spill the cache but for small tight loops not exceeding the cache line/ size it would still be a good win.

Would there be any benefit to adding branch prediction logic to a GPU?

Re: Mispredicted branches can multiply your running times

#96
post #41
post #37

Earlier quoted context omitted.

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

I've been thinking about this topic a lot lately and I find myself in agreement with you vsareto. I'm largely a JS dev by day (working on backend services) but I'm very passionate about low-level programming. I tend to hack around in Rust or C, even starting to hack with assembly language. Heck, I'm even reading the AMD x86_64 architecture books for fun :P.

There are so many challenges trying to understand what your Javascript is doing under the hood. Take Node.js development for example. Your code is running on V8, likely running within a Docker container, perhaps even on a Kubernetes node or other distributed cluster. To truly understand what your code is doing at the CPU level is a _very_ difficult thing to do. More often than not, the performance issues I've run into have to do with topics like: slow performing network communication, poorly thought out algorithm design (excessive code), "noisy neighbors" where other containers are causing performance problems unrelated to your own code (for example, one issue we had with excessive times for DNS resolution was caused by the networking stack/tech in our k8s cluster being misconfigured and doing a GC every 60 seconds for 4-5 seconds at a time), or poor database-access patterns that cause excessive times for queries.

The JavaScript code itself and inefficiencies of what the resulting machine code is seems to rarely be the case for me. But that may also be due to the domain that I work in (it's actually one of the things that has me super bored with the software I work on these days).

To echo your own points, I find myself most often coaching junior developers on data-access patterns and design, minimizing network activity (if you think missing the cache and going to memory is slow for software, just imagine hitting the network and going to different machines), etc.

Like I said though, it may just be due to the domains I work in and being on the backend.

And all of this from a person who is _loving_ learning more about the internals and playing around with lower-level programming. I feel like the more I have learned at that level has made me a much better programmer as well. I wish I would have learned this stuff 10-15 years ago. So I'm torn.

Re: Mispredicted branches can multiply your running times

#97
post #51

Earlier quoted context omitted.

>Elitism at its finest. Do you think doctors in training get to do open heart surgeries by themselves fresh out of university? Do you think we train aviators that can only fly using the autopilot? Because that's the way we treat software developers. This has nothing to do with elitism and everything with professionalism. Our industry has built training wheels in form of various VMs and high level languages because it…

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 software is paid by billions of users every day.

Re: Mispredicted branches can multiply your running times

#98
post #87

Earlier quoted context omitted.

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?

The first one naturally.

The tone of my previous remark is that optimization algorithms are orthogonal to programming languages, an language agnostic backend optimizer working on AST and SSA passes doesn't care what the input language was all about.

Re: Mispredicted branches can multiply your running times

#99
post #78

Earlier quoted context omitted.

GPUs are designed to do massive parallel computations which all branch one way and don't have much (any?) branch prediction logic. You trade it off with increased code size which might spill the cache but for small tight loops not exceeding the cache line/ size it would still be a good win.

Would there be any benefit to adding branch prediction logic to a GPU?

You would probably get some benefit on a per CUDA core basis, but the extra space required would mean less CUDA cores, overall it would probably be a net loss on problems well suited to GPU acceleration
Post reply on HN