r/programming • u/fagnerbrack • 1d ago
Branch‑Avoidant Programming
https://easylang.online/blog/branchless30
u/bodiam 23h 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)
18
u/crozone 23h ago
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.
9
u/braaaaaaainworms 21h ago
CMOV is still practically a branch, just not the kind of branch that has a branch predictor, https://yarchive.net/comp/linux/cmov.html
1
u/randylush 16h ago
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.
3
u/SoSKatan 18h ago
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.)
5
2
u/happyscrappy 20h ago
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.
2
u/nukethebees 12h ago
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.
1
u/happyscrappy 12h ago
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.
2
u/nukethebees 12h ago edited 12h ago
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.
2
u/happyscrappy 11h ago edited 11h ago
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?
1
u/dacjames 15h ago edited 15h ago
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.
11
u/inio 22h ago edited 21h ago
Write up misses that with the chosen task the subsequent stores to the same array position are typically almost free thanks to the L1 cache. The first store to a line pays for the L1 eviction, and ensures the future write-back. Each later store to the same array position just updates the value in the cache.
Also unlike loads, stores are fire-and-forget and only cause bubbles if the cache can't accept the write immediately.
It also under-states just how critical the code change is and why the optimizer could never do this. Inventing a memory write that isn't in the code (even if the eventual memory state is the same) just isn't something that's allowed. Also the optimized version can write one index beyond where the slow version would, which would be a problem if you wrote this knowing exactly how many items would be written.
13
u/thedannyreg 1d ago
Interesting, I like the assembly comparison. I got a couple of questions / thoughts:
Wouldn’t the if statement make it easier to read?
Wouldn’t an if statement allow for early returns?
I guess if an optimization is needed this technique can be considered.
Anyways good post non the less, thanks for posting:)
17
u/Lonsdale1086 23h ago
Wouldn’t the if statement make it easier to read?
Yes
Wouldn’t an if statement allow for early returns?
Yes but that still generally wouldn't improve the speed.
2
u/B1anc 12h ago
Yes, it would allow for early returns, but early returns only improve performance if it allows you to skip work that is more costly than having to flush and refill the CPU pipeline.
By introducing an early return you also limit the CPU in how much speculative work it can do and how much data it can fetch/store in anticipation for this work. It can also prevent SIMD optimizations by preventing it from doing batch processing as well as function inlining if the compiler isn't sure how to optimize your code due to added complexity.
Early returns are good for readable control flow but it can hurt data flow and thus shouldn't be used in tight loops.
Less instructions doesn't always mean less cycles.
3
u/tomysshadow 11h ago
This is one of those optimizations that do truly exist but you really really need to profile to know if it's actually improving anything. You cannot just start writing branchless code everywhere on the assumption that it will speed up your code, because it often has the potential to make it slower depending on the specific circumstances.
(Sorry if that's, like, super obvious, but I just think it's worth emphasizing.)
Write the basic version using if statements first. Do this stuff if it results in code that is actually too slow.
2
u/ReDucTor 12h ago
There is so many caveats to things like this, your trading a branch for a loop carried load data dependency, which is not always the same going to be the same cost, change the data set to be more predictable it becomes slower, change the condition to something more expensive it becomes slower.
Avoiding branches and doing obvious branch free programming like this is not always an easy win, the loop carried dependency is not free.
4
u/Nwallins 17h ago
smlen = 0;
for (int i = 0; i < 1000; i++) {
small_numbers[smlen] = numbers[i];
smlen += (numbers[i] < 500);
}
How is this correct? Let's imagine the input array is entirely above the 500 threshold. The resulting array of small numbers will have a single entry, the first number from the input array.
5
u/ack_error 15h ago
It's not correct, in that it can write more
small_numberselements than the original routine. However, it's functionally equivalent for the intended resultsmall_numbers[0..smlen-1]and as long as that array is big enough. Typically the output count is not known beforehand and thus it would be allocated for the worst case (1000), which this version also will not exceed. But it's indeed not exactly the same and thus as noted why the optimizer usually can't make this transformation.3
u/nukethebees 16h ago
What's wrong about it? If all the numbers are >= 500 then the length will be 0 and the array will be full of uninitialised data.
6
u/Nwallins 16h ago
small_numbers[0] is unconditionally assigned; it will have a single element > 500.
4
u/nukethebees 15h ago
Ah, thanks for pointing that out.
It will have a value written to it, yes, but
smlenwill remain 0 in all cases so there shouldn't be any risk. In all cases the array hasSIZEelements.smlentells us how many contain valid numbers.3
1
u/meneldal2 11h ago
While you do avoid a branch, there are still data dependencies on the index on the small numbers array, so it still has to predict that address.
It helps that writes can be pushed back in order somewhat. but you still can't use simd.
I can't find of a way to use simd for this tbh, you'd need something like a conditional push where it can push multiple items (or none) depending on some state.
3
u/all_is_love6667 23h ago
in general, in data oriented programming, I just generate data, which is another way to avoid branching.
It's always faster to cache things even if it uses a lot of memory, instead of re-generate stuff when a lot of branching is involved
using arithmetics to generate an index is also a good way to avoid branching
-1
u/hacksoncode 21h ago
Trying to figure out what will be optimal for a particular processor family is a job for the compiler/optimizer.
Super Geniuses that try to optimize this stuff themselves are just annoying to the people that have to maintain the code.
That's not to say there aren't some very specific circumstances where hand-optimization like this can make a big improvement on a problem that's actually limited by loop efficiency in a way that optimizers can't figure out, but normally it's a bad thing to think about.
7
u/nukethebees 17h ago
Trying to figure out what will be optimal for a particular processor family is a job for the compiler/optimizer.
Which are not perfect. We can help them by writing code that is easy to optimise.
Super Geniuses that try to optimize this stuff themselves are just annoying to the people that have to maintain the code.
The example is changing an if to a conditional expression. It's not exactly complicated.
In general, if you take the "premature optimisation is evil" route, your architecture may be hamstrung from the very beginning. There's not a whole lot you can do if your code is a pointer soup of virtual functions and pointer-based data structures.
3
u/bwainfweeze 18h ago
To be fair, we are in the somewhat historically unique situation of AWS providing one exact architecture of server to run your same cluster for five, eight years at a time with zero substitutions. Anywhere else in software history, except supercomputers, it would be insane to optimize for a single processor.
Honestly am surprised they don’t end up retiring the old instance types sooner.
1
1
u/brissiebogan 13h ago
reminds me of programming microcontrollers in the 80's; that is when we had the luxury of using c.
1
u/Laicbeias 13h ago
just use binary blend masks to dynamically blend over large chunks of data bro, its easy bro
-7
u/nomad21cns 22h ago
It is a tough trade-off between performance and readability. Modern branch predictors handle so much now that this usually only makes a visible difference in really tight loops.
-3
u/OSS-Corpo-Shit 19h ago edited 19h ago
If I read this article and it is fucking hidden vtables again, I am going to lose my mind.
Edit -
It wasn’t, but it also seems that the branch less solution was only branch less due to mapping directly to an instruction.
For me, this is really more of less saying
“Have a good idea of at least some instructions your architecture provides, and understand if your backend uses them or not.”
That’s a pretty heavy ask.
5
u/nukethebees 17h ago
That’s a pretty heavy ask.
Are there many popular microarchitectures which don't have conditional move instructions? ARM and x86 have them and they comprise most of the general purpose CPU market.
1
u/OSS-Corpo-Shit 14h ago
It is a heavy ask because by far most developers will respond to “you should have an idea of certain easy to exploit performance idioms” with
“thEReS IO InVolVeD. PRemAtURe OpTimizAtIoN.”
-98
u/repeating_bears 1d ago
Call me a snob if you like but I find it hard to trust someone's technical opinion when their website is so ugly
It's not even just aesthetics, there's a lack of basic features like navigation. Why is the entire thing left-aligned?
47
u/cdb_11 1d ago
Yeah it should be a React page that makes you wait extra 3 seconds for the text to load in, with a ton of CSS and animations to make scrolling laggy, a sticky header that takes up 1/5th of the screen, and 50px padding on all elements. That would make it way easier to read
I'll take Web 1.0 over whatever we have today
12
7
4
u/its_the_rhys 1d ago
Not to mention a cookies notice that requires you click accept, which takes up the entire page
And half way down, have a newsletter popup
4
u/Sorry-Transition-908 23h ago
Try Mozilla Firefox with uBlock Origin with all the filters turned on. It is such a breath of fresh air.
2
-13
u/repeating_bears 1d ago
Redditors love to pretend the middle ground doesn't exist don't they
8
u/cdb_11 1d ago
It does exist, but I'll take it over modern web any day
https://web.archive.org/web/20240415053243/https://agner.org/optimize/
https://web.archive.org/web/20241004234625/http://0x80.pl/notesen.html
3
u/punkpang 1d ago
And there he is, generalizing after being shat on. You value presentation, not the facts. It's a stupid trait, definitely not one of a programmer.
14
9
u/punkpang 1d ago
So what you're saying is that you'd trust text on pretty website opposed to text posted, that you can verify and actually avoid trust by checking the facts?
If I post random AI gibberish on a beautiful website, you'd trust my opinion and not rely on the data that the text really conveys?
This is literally insane, that you value presentation over factual correctness. I guess this is why we have such shit software nowadays.
-11
u/repeating_bears 1d ago
I didn't say aesthetics was the only trust signal, no. But if you can't make a functional website in 2026 - and I think this is objectively non-functional without any navigation - then I'm going to doubt what else you know how to do
4
u/hammer-jon 23h ago
this is as functional as it needs to be for this content.
it loaded instantly and is extremely readable, doesnt hijack my scrollbar or distracting ads, no prompting to sign up, nothing.
perfect website, it's not clear what you're even complaining about.
-2
u/repeating_bears 23h ago
If me saying there's no navigation multiple times is "not clear" then I don't know what to tell you. Maybe you're just slow?
3
u/hammer-jon 22h ago
yeah. that's clearly intentional because this is a self contained page with nothing to do with the rest of the site.
go ahead, look at the other posts. they're all about the same easylang topic and allow navigation back to the logical root. This is a page where it makes little sense to link anywhere but reference for the topic.
0
u/repeating_bears 22h ago
Is it "clearly intentional" that the homepage for easylang doesn't link to the blog either then?
It's very normal for a company's blog to write about some random technical topic. If the technical article is good, then it can be a good way to create interest in the product. You shouldn't have to mangle or guess URLs to learn more.
You're absolutely gaslighting me if you say you think this is good UX
Fucking hell, I knew redditors would hate my opinion on the design because they have absolutely no taste whatsoever, but I didn't think they'd completely delude themselves about standard web functionality
4
u/punkpang 23h ago
The site is functional. The only signal you valued were aesthetics. You showed zero interest in what the link actually talks about. You're as shallow as they come.
1
u/repeating_bears 23h ago
You're welcome to think that but it's interesting to me that my opinion about a design made you so personally butthurt
3
u/punkpang 21h ago
If your code is as your conclusions are, then that explains why the world's full of warning labels.
1
u/repeating_bears 21h ago
You have so far personally attributed to me "why we have such shit software nowadays" and "why the world's full of warning labels"
I'm grateful that you think I'm so important to have such a global impact, even if it's negative, but I think you are mistaken
5
1
u/SpecificMachine1 23h ago
Well, I'm sure web 1.0 style sites aren't to everyone's liking, but given the topic it seems fitting to have a <200 line html page instead of a ~10 000 line monstrosity
-1
u/Entmaan 19h ago edited 19h ago
I am reading the replies to your post and I legit don't know what is going on, are people in some kind of mass psychotic state?
Like what motivations do people have to post these insane strawmans or obvious intentional misinterpretations of what you're saying. This website wouldn't be accepted as a 1st year college project, it is rather curious why someone who fancies himself a technical blogger would post his articles on this trash, it definitely doesn't lend him credibility
139
u/meamZ 23h ago
You don't actually need to avoid branches, you just need to make sure that most of the ones you have are very predictable, then their impact is not that big... Same with memory accesses and most other things... The more predictable, the better...