Submission + - Boundless Binary Search: An up to 40% faster binary search implementation (github.com)
scandum writes: The most commonly used binary search variant was first published by Hermann Bottenbruch in 1962 and hasn't notably changed since. Binary searches are one of the corner stones of computer science and can be found in countless software applications, from Google's state of the art b-tree data structure to a browswer's unicode parser which runs a binary search every time it encounters an UTF-8 encoded emoticon.
Recently several new binary search variants have been published that can give a performance increase of up to 40% for 32 bit integers. Given the widespread use of binary searches these new variants (ranging from 15 to 30 lines of C code) could noticeably reduce the worldwide energy consumption by computing systems.
The reason the algorithms are faster appears to be a combination of simpler calculations, branch prediction, and a reduction in cache misses. The reason why it took 60 years to come up with an improved algorithm is likely due to the solution requiring two novel changes to the traditional algorithm.
Recently several new binary search variants have been published that can give a performance increase of up to 40% for 32 bit integers. Given the widespread use of binary searches these new variants (ranging from 15 to 30 lines of C code) could noticeably reduce the worldwide energy consumption by computing systems.
The reason the algorithms are faster appears to be a combination of simpler calculations, branch prediction, and a reduction in cache misses. The reason why it took 60 years to come up with an improved algorithm is likely due to the solution requiring two novel changes to the traditional algorithm.
