11–20 of 113 posts
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.
The code assumes that, once the loop finishes, out[0] through out[index-1] contains the desired output. out[index] is not a part of that output.
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…
Two issues:
- It is not easy for the compiler to always fill up a single delay slot. Filling dozen of them (as required for a deeply pipelined modern processor) would be significantly harder.
- The number of delay slots would depend on the depth of the cpu pipeline. If you do not want to expose microarchitectural details in your ISA, you need either JIT or install time specialization. edit: or stick with a potentially suboptimal number.
Earlier quoted context omitted.
The code assumes that, once the loop finishes, out[0] through out[index-1] contains the desired output. out[index] is not a part of that output.
Then you've got a bug which crashes if all your results were even and index is left zero.
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 getting slower more rapidly than hardware has been getting faster for nearly a decade, and the free performance gains that software people have taken advantage of when better hardware is made available are just about exhausted.
It's time to learn your platforms, software people.
[later addition] This kind of thing is also one of the reasons that teaching OOP principles as they are taught today is so bad for software performance. Modeling object relationships to match the real world will, in every non-toy program, produce object structures that are actively unfriendly to cache efficiency, and will therefore produce software which performs very poorly when compared to software that was written with the hardware platform in mind.
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…
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…
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 = 5000000;
let index = 0;
const out = [];
while (howmany) {
const val = Math.floor(Number.MAX_SAFE_INTEGER * Math.random());
if (val % 2) {
out[index] = val;
index += 1;
}
howmany--;
}
// Optimized for branch prediction
let howmany = 5000000;
let index = 0;
const out = [];
while (howmany) {
const val = Math.floor(Number.MAX_SAFE_INTEGER * Math.random());
out[index] = val;
index += (val & 1);
howmany--;
}Earlier quoted context omitted.
Then you've got a bug which crashes if all your results were even and index is left zero.
The original code can end with index = 0 as well. The only difference is that in the optimized code, it will write to index 0, whereas in the original it will not.
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.
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…
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 rather snobby to jump in and write off a bunch of people because of the language they use on the assumption that they use the language without being aware of the implications.
On OOP versus more cache friendly approaches and branch prediction this talk from CPPCon 2019 is great: https://www.youtube.com/watch?v=HG6c4Kwbv4I
The interesting result is that although the DoD approach is eventually faster a branch misprediction causes havoc until uncovered.