71–80 of 198 posts
It's funny how people struggle so much to write branchless code. The code is clearly not branchless as written, and relies on non-trivial optimizations for it to happen. Just write it correctly to begin with.
It's easy, just run all the instructions from all branches, and select the output you want based on conditionals.
A cool related algorithm is https://algorithmica.org/en/eytzinger In addition to being branchless, it also has better cache properties than a standard binary search tree. If you're doing a binary search in an array, you start in the middle, and then jump all the way to the midway point of one half, and so on. As a result, there's a lot of distance between each read that you do in the array. Thus, each read is putting…
Isn't that like storing a heap inside an array, with indices and values like this: 0: top of heap, 1: left of top, 2: right of top, 3: left of left of top ... ?
A cool related algorithm is https://algorithmica.org/en/eytzinger In addition to being branchless, it also has better cache properties than a standard binary search tree. If you're doing a binary search in an array, you start in the middle, and then jump all the way to the midway point of one half, and so on. As a result, there's a lot of distance between each read that you do in the array. Thus, each read is putting…
Pretty cool stuff. The algorithm returns the largest item that’s at most the size of x. At each step it checks array[k] and then checks either 2k or 2k+1 next. The last k will be past the end of the array so you have to backtrack to discover the actual lower bound. k records it’s turns in binary such as 10111. After another right turn it’s 101111. So to backtrack, you strip off the trailing 1s. How to do that though?…
Earlier quoted context omitted.
The myth that they match has been busted since at very least Pentium came to be. A good read of Michael Abrash books explains that quite well, as does playing around Intel's VTune.
For those looking for it https://www.jagregory.com/abrash-black-book If some/most of the actual tricks are not up to date (ahem) the whole book is filled with techniques, stories, concepts... It's more than ever a Zen of optimization opus. Can someone on HN close to him tell Michael Abrash, should he write again, whatever he wants, even gardening or vulkanstuff wrangling, he has guaranteed readers.
Earlier quoted context omitted.
It's a requirement thing. For security the requirement is code needs to be branchless. In HPC the requirement is high performance, the branchless algorithm is an implementation detail. In fact branchless code is often much slower then the branching version.
You don't really want branchless in security. The requirement is constant-time and side-channel resistance. The branchless algorithm is an implementation detail.
Some information on the CMOV can be found on the Intel Optimization Reference Manual ( https://cdrdv2-public.intel.com/671488/248966-046A-software-... ). Torvalds was famously critical of it ( https://yarchive.net/comp/linux/cmov.html); part of the criticism is now moot though, due to low latencies on modern processors (it seems 1 cycle or less, although the instruction consumes internal flags). His idea seems to be…
This is one area where Profile-Guided Optimization (PGO) can help a lot! With PGO, you run your program on some sample input and it logs info like how many times each side of a branch was taken. From there, you can recompile your code. If the compiler sees that one side of the branch dominates, it can emit code to prioritize that branch. However if the branch counts are approximately even and the branch is hard to pr…
I can only assume the compiler is marking all the bounds checks as unlikely to fail, and correctly predicted branches must be more or less free in modern CPUs. It’s the only way I can explain it.
Does gtest (that the author used) help with these things? Does anything?