7 ms·
Branchless Rust: Making a Filter 4x Faster by Removing an If
- deleted 2mo ago[deleted]
- codetiger 2mo agoThanks for sharing, optimisations like these are what keeps the fun in programming. I have been optimising my JSONLogic evaluator in rust and used arena allocator and preallocation tricks that gave me good jump in tuning. Let me see if branchless programming techniques can get any further in my case
- bormaj 2mo agoGreat explanation of why a branchless approach results in such a speed up. I've never really had to deal with performance optimization at this level. Generally it's probably best not to get too involved letting the CPU black box do its thing. I do wonder, would the performance characteristics of branchless vs branching be consistent across different CPUs/architectures? If you had a CPU that wasn't trying to be fancy with branch prediction, would the regular algo be faster?
- nvme0n1p1 2mo agoVirtually every CPU has branch prediction, going back to at least the original Pentium (1993), maybe earlier. If you're running on a very old CPU, yes, the regular algo should be faster.
- deleted 2mo ago[deleted]
- phire 2mo agoI think the Pentium is more or less the first microprocessor with branch prediction. Certainly the most mainstream. PowerPC 601 arrived at more or less the same time, and the Alpha 21064 was a year earlier. There were a few minicomputers and mainframes before that with branch predictors. Arguably the 486 could have done with a branch predictor (even a single entry loop predictor would have helped), and maybe the 386 too. But microcoded CISC designs didn't benefit much from predictors because they have multiple cycles to work it out. And RISC cpus were in their "branch delay slots are awesome" phase throughout most of the 80s. With a bit of trickery (very simple branch conditions and a 2 phase clock), your classic 5-stage MIPS design can fully hide all branches with just a single branch delay slot, so they were a little slow to adopt predictors. I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.
- toast0 2mo ago> I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be. It's got a lot to do with how cpu clock speeds were getting way faster, but ram wasn't. That's what makes deeper pipelines attractive, and if you give a cpu a deeper pipeline, it's gonna want a good branch predictor.
- phire 2mo agoI'm more thinking about how MIPS were quite late to branch predictors. They were shipping the high-performance R4000 and R4400 with 8 stage pipelines and no branch predictors. They could have really done with a branch predictor, each branch took three cycles (and the branch delay slot could fill only one instruction, often a useless NOP). The Pentium only had a 5 stage pipeline and massively benefited from its branch predictor. IBM was slapping branch predictors on PowerPC designs with 4 stage integer pipelines. You simply don't need a long pipeline to justify the benefits of a branch predictor.
- adrian_b 2mo agoPentium was the first CPU with a branch predictor that many people could afford to buy. Before dynamic branch prediction, where the prediction for every branch is updated after each branch execution, depending on its history, static branch prediction had been used for decades, since around 1960, typically using the rule that forwards branches are unlikely to be taken, but backwards branches are likely to be taken. An alternative was to have an instruction bit where the compiler stored its prediction about the probability of a branch being taken. Dynamic branch predictors began to be used since the mid seventies. I do not remember now if any notable monolithic CPU had a dynamic branch predictor before Pentium, but prior multi-chip CPUs certainly existed.
- phire 2mo ago> Before dynamic branch prediction... static branch prediction had been used for decades. I'm not sure that's true. At least not the "predict backwards branches are taken" part. Many RISC cpus did kind of have "predict forwards as not taken", but really thats just speculative execution with the complete absence of any branch prediction at all. IMO "All branches are not taken" is not a prediction. Actual Static Branch prediction is something that seems to have shown up at the exact same time as dynamic branch prediction (ie Pentium and PowerPC 601). Seems to be more of a "well do speculative execution now, what do we do when there is no dynamic prediction?" thing. Maybe there is a multi-chip CPU out there that has proper static prediction but not dynamic? But I checked the likely candidate (The RS/6000 aka POWER1) and it doesn't have any prediction at all (just a hole where the static prediction bits will go later). Probably because static prediction requires support for speculative execution, which it doesn't do.
- vlovich123 2mo agoCortex M0 and microprocessors generally do not. Cortex M3’s looks nothing like the branch prediction you think of when you think consumer or server CPU. Basically branch prediction requires extra power so it’s excluded or greatly simplified in low power use cases.
- throwaway_95283 2mo agoCPUs aren't black boxes. They are actually much better documented than almost all the software that runs on them. If you want to treat the CPU as a black box, trust me you do not want to use a CPU with out a branch predictor, your slow code will run like molasses frozen in antarctica. The regular algo will be lightyears slower on any CPU that does not have a branch predictor.
- Brian_K_White 2mo agoAnother recent story from github about case folding as part of code search, the simple version of the code had a couple of ifs, and the branchless version was actually slower. They have a stupendously fast version and it is also branchless, but it just required more than branchless alone. I'm fuzzy on the details but I think one of the ifs was an early exit, and without that the loop does a memory assignment on every byte instead of skipping most. The really fast version was also vectorized. The branchless makes it possible to vectorize, but it was the vectorization that actually made it fast.
- imtringued 2mo agoI'm not sure how your intuition can be that off, if you don't have a branch predictor then any branching code is going to be even slower than it already is, favouring branchless code even more for obvious reasons. I say this as someone who is interested in a special type of processor architecture that has no branch prediction at all and would need a branchless subset of Rust to meaningfully program it at high performance.
- benj111 2mo agoWhy no branch predictor at all? Even a brain-dead one that predicts all branches always/never taken is going to provide some benefit, it's not as if the processor can do anything else while it's waiting. Or am I missing something? I note the hazard 3 on the pi Pico rp2350 only predicts a branch if it's the last branch and was taken, ie a single loop. Which seems weird to me, so I'm probably lacking understanding somewhere.
- crazysim 2mo agoWould PGO figure this out?
- j16sdiz 2mo agoThey could. but.... running PGO is just too much pain. We can't do it "incrementally", can we? How about combining with LTO? edit: I was thinking profiling individual module on a test driver and link them after PGO
- stkdump 2mo agoI don't know if an optimization is allowed to "invent" a write, but I would be surprised if an optimizer goes that far because I have to believe that the number of cases where more writes improve performance are pretty slim.
- rdevulap 2mo agoa simple perf stat should show that the "Keep 50% of random data" case will have insanely more branch mis-predictions that the others.
- Sesse__ 2mo agoGenerally most forms of PGO does not try to capture number of mispredicted branches (which isn't the same as how often a branch is taken).
- bjourne 2mo agoKeep in mind that this is a synthetic benchmark. The task is to remove outliers and for that the roughly 99% correct guesses of the branch predictor is perfectly fine.
- veqq 2mo agoI've been doing leetcode in Janet in a (sometimes) tacit (variabless), branchless way: (def find-shared-gcd (comp (fn [e] (max ;(map (fn [d] (* d ;(map |(- 1 (min 1 (mod $ d))) e))) (range 1 (+ 1 (min ;e)))))) |((juxt* max min) ;$))) (defn max-diff `where elements increase` [& numbs] (reduce max -1 (filter |(< 0 $) # strip 0s and add -1 in case (= true (apply > numbs)) (map - numbs (accumulate2 min numbs)))))
- youaremidwit 2mo ago[dead]
- Retro_Dev 2mo agoThis article is 100% AI written. The data was interesting, the commentary overly verbose and hard to gain useful insights from.
- aduffy 2mo agoidk why this is getting downvoted, I also got this sense, plugged it into Pangram and indeed, 80% AI-written score. I guess that's fine, but after awhile I get a spidey-sense reading something that feels like a Claude session.
- nullsanity 2mo ago[flagged]
- Seattle3503 2mo agoSad to see you getting voted down. But I guess both the pro-AI crowd and anti-AI crowd hate Pangram.
- vips7L 2mo agoSad little world we live in tbh.
- inigyou 2mo agobecause it's not much better than an RNG?
- Seattle3503 2mo agoWhat data supports that conclusion about Pangram?
- kbelder 2mo agoI always got voted down when I posted the evaluation of the parent articles I got from my Ouija board. I just want to help people understand whether they should just reject bad articles, without having to bother reading them. I'm moving on to evaluating articles with a modified lie detector test and tarot cards, I'm sure that'll help my credibility and give my public rejections more authority.
- anematode 2mo agoNice post! You can do even a bit better if you're willing to use intrinsics. In particular this kind of operation is well-suited for compress-type operations, available as a first-class operation in at least AVX512, SVE and RVV; you can also emulate them reasonably quickly on NEON and AVX2. Here's an example, building on the OP's work: pub fn filter_compress(input: &[f64], threshold: f64) -> Vec<f64> { use std::arch::x86_64::*; let mut out = vec![0.0; input.len()]; let mut n = 0usize; let (head, tail) = input.as_chunks::<8>(); for chunk in head { unsafe { let p = _mm512_loadu_pd(chunk.as_ptr()); let m = _mm512_cmpnle_pd_mask(p, _mm512_set1_pd(threshold)); let compress = _mm512_maskz_compress_pd(m, p); _mm512_storeu_pd(out.as_mut_ptr().wrapping_add(n), compress); n += m.count_ones() as usize; } } for &x in tail { out[n] = x; n += (x > threshold) as usize; } out.truncate(n); out } For me it's about 25% less time than the branchless version with 1,000,000 elements, and 60% less with 10,000 elements where memory bandwidth effects are less relevant.
- ozgrakkurt 2mo agoThank you for sharing this. How would you emulate this kind of operation on avx2?
- variadix 2mo agoOnce you have a mask of the positions you want to compress, you can generate a shuffle index vector from that mask to place the desired elements in the low part of the vector. You can expand the mask into nibble-sized indices using pext/pdep and some magic constants, then expand those nibble-sized indices into a vector of indices to use as the shuffle indices.
- anematode 2mo agoYes, that's one approach. Another reasonable approach is to get out a mask from the comparison using `vmovmskpd` and use that to look up a shuffle constant, since there are only 16 possibilities. This also works well on NEON, although I wonder there whether it'd make more sense to find the shuffle dynamically rather than loading it.
- khuey 2mo agoWorth noting that as written the "trick" results in memory usage proportional to the size of the input rather than the output. If the filter rejects most of the input the difference could be quite noticeable.
- returningfory2 2mo agoI disagree in the sense that you can rewrite the code to use the trick and also not allocate in advance. Nothing about the trick requires you to allocate up front: before writing to out[n] you can extend the vector if it’s out of bounds. Or, after incrementing n, do out.push(0).
- khuey 2mo agoYou should try writing it out. Doing it without introducing another unpredictable branch is harder than it looks. I discussed this with a coworker earlier this week and the best they were able to come up with was for &x in input { out.push(x); n += (x > threshold) as usize; out.truncate(n); } which works but is ugly af imo.
- returningfory2 2mo agoYep realized this after that my second solution (push a 0 if n is incremented) has the same branch prediction problem. I think yours works. Alternatively in the loop: if out.len() < n { out.push(0); } out[n] = x; n += (x > threshold) as usize; In this case the if will be predicted well because it only triggers log(N) times, given how the std lib extends vectors.
- bjourne 2mo agoThis problem is called stream compaction and there is a wealth of research on it. The best methods use prefix scan. They first efficiently compute the index in the output array of each element that satisfies the predicate and then they gather them in one linear operation. Also, I can tell that you are a good writer. You didn't need the LLM to "polish" your text.
- dxdm 2mo agoThere is clearly LLM-prose involved, but it's pretty well done. Here's one example: "The reallocations were real, but they were never the bottleneck." LLMs love this pattern. Whether one put it into this text, or the author soaked it up and now used it himself, who knows. But it is one of the few things in the post that gives me the ick. And then, there's the verbosity. If I had to guess, an LLM was involved, but the author did a good job with manual writing and editing, too.
- claudetard 2mo agoIf your objects are large, I can see why you would compute indices first. But why do that for floats?
- bjourne 2mo agoBecause what makes stream compaction challenging is the loop carried dependency: the location you write to in a given iteration depends on the locations you wrote to in previous iterations. By first creating a lookup table of source -> destination locations you remove the dependency. Then you can apply extremely efficient parallel methods.
- mukundzzha 2mo ago[flagged]
- aarjaneiro 2mo agoI really hope all these guns give up smoking sometime soon...
- aonecode 2mo agoindeed
- haloboy777 2mo agoclaude sends its regards
- airstrike 2mo agoThe annoyance is real, and honestly? It's worth sitting with it.
- tonyhart7 2mo ago"A branch is cheap. A mispredicted branch is not." oh hell nah
- deleted 2mo ago[deleted]
- madhu_ghalame 2mo ago[dead]
- 3997531578 2mo ago[flagged]
- MagicMoonlight 2mo ago[dead]
- yturijea 2mo agoI like how we have pretty much established how branchless coding is superior to branched coding. However I wonder if the compiler itself could recognize these patterns and turn branches into branchless instead, rather than making the code harder to read? as removing if conditions of course have a readability impact on the code.
- adrian_b 2mo agoBranchless coding is superior to branched coding whenever the branches are more or less random, which happens frequently when checking some properties of input numbers, like their sign or whether they fall inside certain intervals, or when sorting an array that comes in random order. When a branch alternative will be taken much more frequently than the other, then branched coding with an "if" becomes superior. So neither is better in general than the other, whenever the program must choose between alternatives, you must think about whether one is more likely than the other, or if both have similar probabilities. For instance, when sorting an array, the optimal algorithm is not the same when you expect the input array to have a random order and when you expect it to be already almost sorted.
- tialaramex 2mo agoFor sorting, conveniently we always definitely need to look at all the elements at least once anyway, so although even the early introspective sorts from the end of last century aren't designed this way both the Timsort and a modern sort like a PDQ sort will end up making that decision early. "Oh, this was mostly already sorted, done" If you meant exactly rather than almost then you can still squeak a small win from having an algorithm which is optimised for this case but the vast bulk of your runtime is eaten by the unavoidable work of checking. "Don't check" is faster but then you're not a sort algorithm at all.
- amiga386 2mo agoThis is true, but the example given yesterday showed that even if branches can be very well predicted (e.g. processing UTF-8 text which is 99.9999% ASCII), branchless code can result in speedup by making autovectorisation possible. If the branchless code didn't transform to vector instructions, it would be strictly slower. But if it does, it allows the CPU to work on 16 bytes at a time instead of 1 at a time. https://github.blog/engineering/architecture-optimization/dont-stop-early-case-folding-source-code-at-memory-speed/ https://github.blog/engineering/architecture-optimization/do...
- rabiescow 2mo agothat's a really clever trick to write to out[n] multiple times but only move the index after the logical condition is true thus ending up with the correct values in out
- llama_drama 2mo agoBranchless code can indeed sometimes be slower than conventional one, but in this particular case, the article comes to the wrong conclusion. At a 1% kept, the branchless version is slower because it pays the cost of zero-initializing 8 MB of memory when allocating the Vec. This can be easily demonstrated by comparing it with a version that allocates uninitialized memory.
- rabiescow 2mo agoDid you read the article? The author was trying to even out the test cases and successfully did so. He stated that the idiomatic code was faster for the 1 % as you can see by quote below: The worst case became almost 4 times faster. And look how flat the branchless column is: the running time does not depend on the data anymore, exactly as we wanted. Notice the price we paid though. At 1% kept the idiomatic version wins, because an almost always correctly predicted branch is nearly free, while the branchless version always pays for one million writes. Branchless code is not faster in general: it trades the best case for the worst case.
- chrka 2mo agohttps://news.ycombinator.com/item?id=48035568 https://news.ycombinator.com/item?id=48035568
- claudetard 2mo agoThis is good technical content, but it's obvious that an AI wrote it.
- crest 2mo agoThis is a common pattern a compiler should recognise and optimise into an efficient data and control flow. So much for a sufficiently smart compiler. shrug
- amiga386 2mo agoA much clearer article from yesterday on making casefolding 15x faster by removing an if: https://github.blog/engineering/architecture-optimization/dont-stop-early-case-folding-source-code-at-memory-speed/ https://github.blog/engineering/architecture-optimization/do... Discussion: https://news.ycombinator.com/item?id=49127983 https://news.ycombinator.com/item?id=49127983
- OsamaJaber 2mo ago[dead]
- myshapeprotocol 2mo ago[flagged]
- germandiago 2mo ago"the smoking gun"... Mr. AI.
- tumdum_ 2mo ago> The reallocations were real, but they were never the bottleneck. Why do people not write their own blogposts on their own?!
- simojo 2mo ago> The predictor is like a barista who starts making your usual order the moment you walk in. If you are a regular, this is fantastic: the coffee is ready when you reach the counter. If you order something random every day, the barista keeps pouring drinks into the sink. I laughed out loud reading this. Interesting writeup. I wonder what kinds of tricks like this exist for computation graph compilers like JAX.
- Magicrafter13 2mo agoBased on the title, I knew the issue as soon as I looked at the first table. Still, great primer for those who don't know about such CPU shenanigans, and I did appreciate the solution, since I knew high level how to solve it, but didn't come up with an actual piece of code before the author presented theirs. I didn't know about branch prediction or pipelined CPUs back when I was profiling the code I wrote - honestly it probably would have helped.
- chrka 2mo agoI've written something like this in C - including resulting assembler code for ARM and x86. https://easylang.online/blog/branchless https://easylang.online/blog/branchless
- caruasdo 2mo agoEven though you used AI to help you with the article, knowing that performance trick is really cool.