Branchless Rust: Making a Filter 4x Faster by Removing an If (greyblake.com)

Thanks 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

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

Would PGO figure this out?

I'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)))))

This article is 100% AI written. The data was interesting, the commentary overly verbose and hard to gain useful insights from.

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

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

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

[flagged]

I really hope all these guns give up smoking sometime soon...

"A branch is cheap. A mispredicted branch is not."

oh hell nah

[dead]

[flagged]

[dead]

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

that'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

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

  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.

This is good technical content, but it's obvious that an AI wrote it.

This 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

A much clearer article from yesterday on making casefolding 15x faster by removing an if:

https://github.blog/engineering/architecture-optimization/do...

Discussion: https://news.ycombinator.com/item?id=49127983

[dead]

[flagged]