We explore how to speed up binary search by batching independent searches with NumPy's vectorized operations. We then reformulate the algorithm so all searches progress together with only $O(1)$ additional memory, port it to C++, and achieve up to a 25× speedup over NumPy 2.4's implementation.
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.
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
score 1 · canonical
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.
score 1 · canonical
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.
score 2 · canonical
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.
score 1 · canonical
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.
score 1 · canonical
I see! Good trivia on the night before my PhD defence. :)
score 1 · canonical