Making np.searchsorted up to 25× Faster in NumPy 2.5
10 points by itamarst
10 points by itamarst
Note that when the article says "vectorized" it's using the term as it's used in the Python ecosystem, meaning batch operations done using extensions written in a compiled language.
Thanks, I would not have picked up on that. Is there a reason why the Python ecosystem centered on this definition for "vectorised"?
Coming from the Python ecosystem, what is your definition of vectorized in computing?
The Python definition is certainly used outside of the ecosystem as well: https://en.wikipedia.org/wiki/Vectorization
In performance-oriented computing, vectorisation means expressing an algorithm in terms of SIMD (vector) CPU instructions with the goal of using the parallelism that they offer to speed up the algorithm even within one CPU core. If the algorithm is well suited to such parallelisation (e.g. because it doesn't really contain control flow and operates on a batch of data), this speedup can be expected to be 2-8x or even more depending on the width of the numbers involved, the hardware and how memory-bound the algorithm is.
I have no clue on the conventional usage within the Python ecosystem (I don't use Python outside some simple scripts), but I expect the link is that C compilers perform automatic vectorisation and the Python interpreter does not, and as such if you want vectorisation you have to move to a C extension. However, even without vectorisation compiled C will be faster than Python although I suppose the difference may be much smaller (or even nonexistent) when using a JIT compiler like PyPy.
You are on point. I would like to add that vectorize can also mean to work with lists/arrays like the mathematical concept of a vector. You can add vector A + the scalar B without needing to write a for-loop. np.vectorize is a good example of this, which let‘s you apply an arbitrary scalar function on to n-dimensional Numpy arrays. Performance optimization is not the goal here, but expressiveness.
Ah yes, you're right! That's another common use of the word.
EDIT: looking at np.vectorize, really just emitting a for loop without any additional processing is not what I, from an HPC standpoint, would call vectorisation. What I would call vectorization is jax.vmap, which actually changes the function (by tracing it first to get an AST) to operate on arrays of one dimension higher directly. This is usually a performance win but not quite always.
I believe the term is inherited from APL's notion of vectorisation, which far predates actual vector processors. Numpy is explicitly APL-inspired, as I understand it.
Whay I don't like about presentations like this is that they change the problem statement without saying that they do so. You don't make binary search 25x faster, you make batched binary search 25x faster. That's useful! But it's not the same as making one np.searchsorted call faster.
searchsorted() takes an array of needles to search for, as I understand it: https://numpy.org/doc/2.4/reference/generated/numpy.searchsorted.html
Exactly! There is also the tension between a simpler title and a super exact one. We could have a title that is "Making np.searchsorted (up to) 25x faster (when querying multiple keys)".
Anytime I read something like this I am like why use numpy for this at all. Dask etc at this point.
Dask's numeric array library runs on top of NumPy! So you want NumPy to be faster single-threaded.
As @itamarst points out, Dask runs on top of NumPy, which is why I didn't include it in the ecosystem comparison. I did include libraries that use multithreading and achieve comparable performance.
The main bottleneck of this algo is memory access. Since the single-threaded batched implementation can already generate substantial memory-level parallelism, adding threads may not improve throughput much on the same machine. It's worth benchmarking, though!
Using multiple machines would be a different story.