A better starting point is: use a better language. Python is terrible and unbearably slow. If you need anything serious or performant, switch to something else.
> 2. Use a compiled language to write a Python extension.
It's fine to be grumpy about languages, but python is the de facto standard in many industries, and a lot of people don't get to choose.
So, yes, asking "how do you speed up computational python code?" is a good, fine, normal question.
> Consider the following real problem, one of the steps in scikit-learn’s gradient histogram boosting algorithm:
> You have a large array of floating point numbers.
> You want to assign them to the integer range 0-254, spread out evenly.
Naively I would consider sorting the initial array and then using something like `batched` from itertools to chunk them into the 255 buckets - binary search will give you a bunch of random accesses, and sorting can be cache-oblivious (eg efficient for arbitrary data sizes)
But I'm somewhat concerned I don't fully understand the underlying problem being solved with this step, so I might be misunderstanding the intended result
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.
> As far as the number of while loop iterations, I’m instead going to iterate a fixed number of times, log2 of the number of buckets. For some value this might involve a bit more work, if previously the bucket would be found in an iteration or two, but the saving in speed from avoiding branch mispredictions will make it worth it.
pillmillipedes•5d ago
I'd also want to try interpolation search for this (not necessarily linear interpolation since we're doing floats) - you can take much better guesses than "it's in the middle somewhere" by not having to look at the data through a 1-bit-wide pinhole as comparison algorithms do.
itamarst•5d ago
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.