#branchless
Branchless Binary Search
Branchless Binary Search Branchless binary search is a binary search variant designed to reduce branch mispredictions. A normal binary search repeatedly branches on whether the middle value is less than the target. On modern CPUs, this branch can be hard to predict because the search direction depends on the data. A branchless version keeps the same comparison logic but updates the search position using conditional moves, masks, or arithmetic expressions....
Branchless Lower Bound
Branchless Lower Bound Branchless lower bound computes the first position where a value is greater than or equal to a target, without using unpredictable branches. It follows the same logical structure as binary search but replaces control flow with arithmetic updates or conditional moves. The result is the same as standard lower bound. The benefit is improved performance on modern CPUs when branch misprediction is expensive. Problem Given a sorted...