4 ms·
One 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
by repsilat 6y ago
One 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!