Hacker News Reader

It’s possible to design an algorithm which branches and is also constant time. If, for all inputs, the instruction length (# of instructions executed) is the same even for different branch paths, then they must all run in the same time. This, of course, isn’t accounting for different (microscopic) execution times of individual instructions, but constant time isn’t really a measure of clock time anyway.

View on HN

If your CPU is as simple as the one designed during a one quarter year uni class then sure. But that's simply not a realistic scenario with a modern CPU. Even if you have the same amount of instructions then branch prediction, memory latencies, super scalar execution and more will throw a wrench in that quickly. Even if you have the same instruction stream with different input data the latencies can be different. That is exactly what you are preventing with branchless code. It's been proven that it's possible to use this as an attack vector.

See a trivial example here: https://stackoverflow.com/questions/11227809/why-is-processi...

Where first massaging the data so the processing is branch predictor friendly results in a 6 time speedup. These things are not microscopic.

Reply on news.ycombinator.com