itamarst

The bucket boundaries are often chosen from a random sample of the data, if the input data is very large. Sorting is O(nlogn), but using binary search per value to assign a bucket is O(n), plus the cost of creating the buckets on a sample. 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.

Better guesses reduce the number of guesses, so there will be less branch misprediction, but there will still be mispredictions for each remaining branch. So I would guess branchless interpolation search would still help.

In practice because the real code in scikit-learn is used in parallel, memory bandwidth starts being a problem in real usage. Plus, in the overall algorithm (this is just a small part) the time spent on binary search is now low enough that there are other, more significant bottlenecks elsewhere. So in practice the branchless optimization had enough impact on the original motivating code base that there didn't seem much point spending more time on it.

That's great! Would also be cool (separately from Pydantic use case) to add jiter backend to ijson.

Once you switch to ijson it will not save any memory, no, because ijson essentially uses zero memory for the parsing. You're just left with the in-memory representation.