Mispredicted branches can multiply your running times • Hacker News Board

Re: Mispredicted branches can multiply your running times

#51

Post by emsy » Wed, Oct 16, 2019, 2:22 PM UTC

NotATroll wrote: post #47

emsy wrote: post #40

Earlier quoted context omitted.

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

>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 missed the opportunity to properly train its workforce.

Re: Mispredicted branches can multiply your running times

#52

Post by omgtehlion » Wed, Oct 16, 2019, 2:26 PM UTC

kstenerud wrote: post #13

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

Re: Mispredicted branches can multiply your running times

#53

Post by SloopJon » Wed, Oct 16, 2019, 2:28 PM UTC

XJ6 wrote: post #8

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

It strikes me that the example is a bit contrived: why is howmany decremented unconditionally? The first loop populates out with howmany numbers. The second loop may set none (other than the ignored value that you point out). I suppose you can use the same trick:

  howmany -= (val bitand 1);

But that might complicate the benchmark.

Coincidentally, this was the subject of the first Stack Overflow question Bjarne addressed in an interview the other day:

https://stackoverflow.com/questions/11227809/why-is-processi...

Re: Mispredicted branches can multiply your running times

#54

Post by XJ6 » Wed, Oct 16, 2019, 2:56 PM UTC

kstenerud wrote: post #29

XJ6 wrote: post #19

Earlier quoted context omitted.

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

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

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.

Re: Mispredicted branches can multiply your running times

#55

Post by heisenbit » Wed, Oct 16, 2019, 3:31 PM UTC

vsareto wrote: post #30

naikrovek wrote: post #25

Earlier quoted context omitted.

> Let's not drastically increase job requirements for no good reason. Well, I would say that it's a very good reason, and that learning about branch prediction and caches is not a "drastic" step by any means. Is there any software that you write whose users would not be made happier if the software performed better? Any at all? > Many of these platforms have undocumented CPU instructions You don't need to know the se…

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

Exactly, usually the big mistakes are made on the macro level. Worrying too much about the micro level is taking away attention where it belongs.

There is certainly worth in awareness of performance issues - the key is to recognize the - for most of us - rare instances where it matters.

Re: Mispredicted branches can multiply your running times

#56

Post by minipci1321 » Wed, Oct 16, 2019, 3:52 PM UTC

pjmlp wrote: post #50

minipci1321 wrote: post #43

Earlier quoted context omitted.

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.

(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?)

Re: Mispredicted branches can multiply your running times

#57

Post by ScottFree » Wed, Oct 16, 2019, 4:02 PM UTC

naikrovek wrote: post #22

meheleventyone wrote: post #20

Earlier quoted context omitted.

> 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. This is a shame because not only are there lots of developers who write JS that have low-level backgrounds there are also a lot who haven't and are still interested. It seems rathe…

I realize that it is unfair to categorize ALL JS devs in this way, and it certainly is a tight fit for the JS developers that I have worked with in the past.

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

Re: Mispredicted branches can multiply your running times

#58

Post by SilasX » Wed, Oct 16, 2019, 4:03 PM UTC

vsareto wrote: post #30

naikrovek wrote: post #25

Earlier quoted context omitted.

> Let's not drastically increase job requirements for no good reason. Well, I would say that it's a very good reason, and that learning about branch prediction and caches is not a "drastic" step by any means. Is there any software that you write whose users would not be made happier if the software performed better? Any at all? > Many of these platforms have undocumented CPU instructions You don't need to know the se…

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

Yes! I mean, isn't the tradeoff exactly what got us Spectre? "Hey, let's aggressively pre-compute and cache for performance. Oh, darn, turns out that leaks information..."

https://en.wikipedia.org/wiki/Spectre_(security_vulnerabilit...

Re: Mispredicted branches can multiply your running times

#59

Post by pjmlp » Wed, Oct 16, 2019, 4:04 PM UTC

hamilyon2 wrote: post #26

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…

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

Like Wirth puts it, algorithms + data structures.

Programming paradigms are orthogonal to that.

Re: Mispredicted branches can multiply your running times

#60

Post by ScottFree » Wed, Oct 16, 2019, 4:09 PM UTC

vsareto wrote: post #34

kasey_junk wrote: post #33

Earlier quoted context omitted.

> Good algorithm knowledge and practice is the most cost-effective way of writing performant code I’d love to see that common thought validated because in practice I’ve seen it to not be true at all. There are lots of cases where the complexity effects of the algorithm are swamped by cache effects. In fact basic foundational assumptions about complexity analysis are dangerously untrue on modern systems. In my experie…

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