6× faster binary search: from compiled code to mechanical sympathy

Re:6× faster binary search: from compiled code to mechanical... by itamarst on Friday July 17, 2026 @11:34AM (#48948628)

The bucket boundaries are often chosen from a random sample of the data, if the input data is very large. Sorting is O(nlogn) on, but using binary search per value to assign a bucket is O(n). So once you hit a large enough number of values this scales better.

Binary search does give random access but in this case there's only up to 255 buckets typically, so it's random access on cached memory.

[ Parent | on HN ]

Re:6× faster binary search: from compiled code to mechanical... by wrsh07 on Friday July 17, 2026 @09:33PM (#48954244)

Can you say more about what happens for bucket assignment? Eg is it appending to a file or writing to a 2d array?

Agreed on linear vs n log n, ofc, and streaming considerations might also be relevant

[ Parent | on HN ]