Why can't python vectorize map() or list comprehensions

Question

I don't know that much about vectorization, but I am interested in understanding why a language like python can not provide vectorization on iterables through a library interface, much like it provides threading support. I am aware that many numpy methods are vectorized, but it can be limiting to have to work with numpy for generic computations.

My current understanding is that python is not capable of vectorizing functions even if they match the "SIMD" pattern. For instance, in theory shouldn't any list comprehension or use of the map() function be vectorizable because they output a list which is the result of running the same function on independent inputs from an input list?

With my niave understanding, it seems that anytime I use map(), in theory, I should be able to create an instruction set that represents the function; then each element in the input just needs to be run through the same function that was compiled. What is the technical challenge to designing a tool that provides simd_map(func, iterable), which attempts to compile func "just in time" and then grabs batches of input from iterable and utilizes the processor's simd capabilities to run those batches through func()?

Thanks!

Answer 1

The operation applied by map is arbitrary Python code. CPython is an interpreter, not a JIT compiler.

CPython could maybe have some canned C functions (ahead-of-time compiled as part of the interpreter) for SIMD operations over arrays, but it doesn't AFAIK. Even so, it would have to optimize the supplied func down to something it could do pattern-recognition on to notice that it was e.g. doing a[i] = max(a[i], some_value).

But normally CPython doesn't do that; interpreter overhead is a huge problem for looping over elements of an array. CPython is nowhere near the performance of a native scalar loop so there's huge room for gains even without auto-vectorization. Like factors of 200 slower IIRC. e.g. Why are bitwise operators slower than multiplication/division/modulo? shows that some operations don't even have a "fast-path" for small integers, and that overhead is enough to make & slower than // which internally uses a hardware division instruction.

Also, Python lists aren't stored as simple contiguous arrays of int32_t or double so CPU SIMD isn't efficient anyway. That's why numpy arrays are special: they do store values like a C array of primitive types.

---

(Caveat: I barely know Python and don't use it regularly. But I think I know enough for this answer to be correct: It's an interpreter written in C that doesn't do any on-the-fly generation of native machine code. The only native loops that can run are ones pre-compiled as part of the interpreter, or in NumPy libraries.)

Answer 2

You want vectorization or JIT compilation use numba, pypy or cython but be warned the speed comes at the cost of flexibility.

numba is a python module that will jit compile certain functions for you but it does not support many kinds of input and barfs on some (many) python constructs. It is really fast when it works but can be difficult to wrangle. It is also very targeted at working with numpy arrays.

pypy is a complete replacement for the cpython interpreter that is a JIT. It supports the entire python spec but does not integrate with extensions well so some libraries will not work.

cython is an extension of python which compiles to a binary which will behave like a python module. However it does require you to use special syntax to take advantage of the speed gains and requires you to explicitly declare things as ctypes to real get any advantage.

My recommendation is: use pypy if you are pure python. (if it works for you it's basically effortless) Use numba if you need to speed up numeric calculations that numpy doesn't have a good way to do. Use cython if you need the speed and the other 2 don't work.