3 ms·
Writing branch-free code (which I find myself sometimes doing to take advantage of simd vectorization) is always really painful. I wonder if someone has made an
by cozzyd 6y ago
Writing branch-free code (which I find myself sometimes doing to take advantage of simd vectorization) is always really painful. I wonder if someone has made an attempt at better tooling for this.
- klyrs 6y agoI tend to use the same method as the author has presented. 1. Write your branchy code 2. Massage the branches until their code is identical (testing frequently) 3. Trim a useless branch, and eat a piece of chocolate
- tomcam 6y agoI don’t mind boasting that I’m a world class talent at part 2 of step 3
- repsilat 6y agoOne thing people have made is array languages. The "primitive" operations apply to arrays of data, so branches around individual elements can't be expressed. I think it's also generally less expressive, though. Writing Lomuto's partition as efficiently would likely be impossible, but writing it branch-free might not be -- you would compose branch-free primitives like left = filter(array, array < array[0]) right = filter(array, array > array[0]) where `filter` is branch-free and takes an array of Boolean values as its second argument. Shrugs, aside from some standard set of functions/primitives and idioms I'm not sure it would help much, though perhaps a mindset-shift is a more likely solution than something more technical.
- VHRanger 6y agoThis sort of vectorised pseudo branching is often used in SIMD algorithms
- cozzyd 6y agoYes... and the transformations are often non-trivial (especially when considering the possibility of out-of-bounds elements, which can't just safely be multiplied by zero--they might be a NaN, or on the edge of a page). It would be nice if there was a tool (or compiler option!) that could convert my branchy code into an "identical" (assuming floating-point associativity, etc.) branchless version.
- snovv_crash 6y agoThe Eigen Array [1] object is fairly close to this. Combining the 'select' with comparisons, chained operators etc. Eigen vectorized stuff pretty effectively too. 1. https://eigen.tuxfamily.org/dox/group__TutorialArrayClass.html https://eigen.tuxfamily.org/dox/group__TutorialArrayClass.ht...
- cozzyd 6y agoInteresting... I've used Eigen for matrix operations before, I did not know they had such a smart general-purpose array implementation!