←back to thread

Beautiful branchless binary search

(probablydance.com)
386 points ingve | 1 comments | 28 Apr 23 05:46 UTC | HN request time: 0.46s | source
Show context
SleepyMyroslav ◴[28 Apr 23 07:34 UTC] No.35738552[source]▶
If being branchless is important property of the algorithm then it is better to enforce it. Or at least test for it. If his GCC version will get an update and it will stop producing assembly that he wants no-one will ever know.

Which brings us back to regular discussion: C ( and C++ ) does not match hardware anymore. There is no real control over important properties of generated code. Programmers need tools to control what they write. Plug and pray compilation is not a solid engineering approach.

replies(6): >>35738629 #>>35738633 #>>35738677 #>>35738943 #>>35741009 #>>35745436 #
1. Arnt ◴[28 Apr 23 08:40 UTC] No.35738943[source]▶
We lost that control when CPUs became increasingly multilayered and complicated, with 20-step pipelines, enough parallelism to run a hundred instructions at the same time, with micro-ops and microcode, with branch predictors good enough to unroll some loops completely. What programmer today understands the branch prediction logic used on production system? Well enough to understand what difference branchlessness makes?

And it doesn't seem to hurt. I at least have both worked on systems where I can read and write assembly and on one where I can't, and my "need to control" isn't such that the lack of assembly knowledge makes a significant impact on my effectiveness on the latter platform.