That's interesting. Would this also apply to higher languages, like Java, which run on a JVM? (Not intending to rewrite my code, but I'm curious how much languages like Java benefit from branch prediction and brancheless approaches)
Not sure about Java specifically, but in the .NET framework, a lot of the tight loops within certain algorithms (eg hashing) use code like this, and the JIT has specific optimisations that allow it to emit CMOV when possible and avoid branching.
A lot of high level languages encourage you to present your code as a problem statement rather than an iterative solution. In this post’s example, a lot of languages allow you to write this as “filter array where values are less than 500” rather than “for each element in the array, if less than 500, add to another array.” IMO it’s always better to code in terms of problem definitions than solutions, because humans will invariably come up with inefficient solutions when they could have just given the compiler the original problem and had it solve it.
It’s not a language dependent issue, it’s just how modern CPU’s work. So yes it applies to all languages that emit branch instructions (or are interpreted which just adds another layer of branching.)
If it ends up getting compiled to native code it probably would, if not I'm not sure but it's probably not running frequently enough to matter (assuming HotSpot)
Well, the principle of the Spectre-type attacks including manipulating load mispredictions. And there are a fair number of variants of that which run in higher languages like Javascript.
So the principles can apply.
But in general none of this stuff is that important. Most of the time you should ignore it in C (low level languages) and so yes, ignore it in high level languages too.
This stuff is important in the most critical parts of performance critical tasks. But elsewhere it's not worth the trouble. This goes for several of the things that are frequently highlighted on /r/programming. Like cache-efficient code. These things end up here primarily because they are esoteric, meaning they really aren't all that important until you've already done a whole lot of other more ordinary stuff and your performance is still too low.
This goes for several of the things that are frequently highlighted on /r/programming. Like cache-efficient code. These things end up here primarily because they are esoteric, meaning they really aren't all that important until you've already done a whole lot of other more ordinary stuff and your performance is still too low.
I don't agree. Cache efficient code is something you often should architect for from the beginning. The basic principles are not esoteric. A core one is to prefer flat contiguous data structures (i.e. arrays).
For example: instead of using pointers for trees, put your elements in an array and use indices instead.
They are absolutely esoteric. If it isn't taught in the first years of programming in university then it's esoteric.
Tree versus array is a decision that is hard to make correct for all architectures (cache-oblivious). Sure, if you can keep all your data in order in an array then you're probably as good as you can be on all architectures. But given that most data is dynamically sized now you can't do that. You can't afford to leave space for an (essentially) unlimited number of entries in all cases.
The number one most important thing is that your code work. First design it to work. Simplify, not prematurely optimize. Write your code straightforward and using data structures your runtime offers.
Then once it's all done you can analyze how you can do better and more importantly where it is important to do better. Most of your code probably doesn't run often enough to bother trying to tweak. And then maybe go back and make your code less straightforward to get more speed.
Really probably you should be thinking more about computational complexity (big O) than cache effects when designing and writing your first implementation.
If it isn't taught in the first years of programming in university then it's esoteric.
You weren't taught about computer hardware in university? Regardless, if your profession involves programming a machine, shouldn't you have some basic knowledge of how it works?
Sure, if you can keep all your data in order in an array then you're probably as good as you can be on all architectures. But given that most data is dynamically sized now you can't do that.
Arrays don't require logically ordered data just because it's physically contiguous. That's why I said you can build a tree using indices. If you run out of space in an array you can just reallocate and extend it. Copying data is extremely fast and using indices has a further benefit that reallocating the backing storage won't invalidate your indices, whereas it will invalidate pointers to elements.
Simplify, not prematurely optimize.
Knuth was referring to people micro-optimising non-critical parts of a program, not ignoring performance until your profiler ignites.
A flat, array-orientated structure is generally as simple as you can get. The stereotype of things like OOP is deep inheritance chains and tons of indirection.
You generally won't have time to rewrite parts of your program to use cache-friendly structures if it's of any significant size, that's why I said it should be architected from the start.
Really probably you should be thinking more about computational complexity (big O) than cache effects when designing and writing your first implementation.
No, this is not true. Big O alone will often push people to using much slower implementations due to theoretical speed. The canonical example is inserting elements into a linked list vs a dynamic array. Once you have the insertion position, insertion into a linked list is O(1), whereas it's O(N) into a dynamic array as you may have to move many elements. In practice, the dynamic array is often substantially faster because copying elements is cheap and pointer chasing is expensive.
Furthermore, iterating through an array and a linked list are both O(N), but the linked list's allocations may be fragmented across the address space, making it potentially multiple orders of magnitude slower to traverse.
Another example would be searching. If you only have a few hundred elements, a linear search through an array will quite often be the fastest and simplest algorithm, despite being O(N). That's assuming you've laid out your data correctly and aren't using massive padded structs.
You weren't taught about computer hardware in university? Regardless, if your profession involves programming a machine, shouldn't you have some basic knowledge of how it works?
You're arguing circularly. Stating this is basic knowledge as begging the question.
And no, the first two years of computer engineering do not teach algorithms for efficient cache use.
Arrays don't require logically ordered data just because it's physically contiguous
I recommend against using the term physical when you are using virtual addressing. Remember your operating systems class.
That's why I said you can build a tree using indices.
It doesn't help. If you use a tree-type structure then you are not accessing linearly.
If you run out of space in an array you can just reallocate and extend it.
I don't think you thought about that before you wrote it. For many cases this is less efficient than using a tree.
Knuth was referring to people micro-optimising non-critical parts of a program
And so am I.
not ignoring performance until your profiler ignites.
How do you know your profiler is going to ignite before it ignites? And where? Assuming this is premature optimization.
You generally won't have time to rewrite parts of your program to use cache-friendly structures if it's of any significant size, that's why I said it should be architected from the start.
There is always time to do the job right. Especially if the current solution is not doing the job sufficiently well, right? You are addicted to circular arguments.
In practice, the dynamic array is often substantially faster because copying elements is cheap and pointer chasing is expensive.
I think you're mistaken. It really depends on how often you use a structure versus modify it. And regardless of any of this, you're cherry-picking. I said use the data structures your language provides. That means you use the built-in arrays. Most of the time this will not be a linked list. So suggesting it would be is just a strawman. You're creating a bad case to argue against it.
If you only have a few hundred elements, a linear search through an array will quite often be the fastest and simplest algorithm, despite being O(N)
Why in all this when I said you should be thinking about computational complexity do you assume I mean "and arriving at the wrong conclusions? Another strawman.
You here try to prove my statement about thinking about computational complexity wrong by thinking about computational complexity. Did that not seem odd to you when doing it?
In practice, it applies to any language that generates machine code, AOT or JIT.
In an interpreted language like Python, this optimization is much less effective. Bounds checking adds at least one hidden branch to every write but there's usually a lot more than that.
In my quick test of this example in Python, the branchless version is slightly slower, likely due to the extra writes.
29
u/bodiam 1d ago
That's interesting. Would this also apply to higher languages, like Java, which run on a JVM? (Not intending to rewrite my code, but I'm curious how much languages like Java benefit from branch prediction and brancheless approaches)