News for hackers. Stuff that matters.
Re:Branch predictor: How many “if”s are too many? by acidbaseextract on Thursday May 06, 2021 @07:41PM (#27070227)
As you point out, the exact properties that make binary search algorithmically fast can slow it down on real computer hardware.

Branch predictors like low entropy (unsurprising) branches, but binary search is algorithmically fast because it maximizes the entropy (information gained) from the few branch checks that it does make.

There are no comments on this comment yet.