Python: is the iteration of the multidimensional array super slow?

Question

I have to iterate all items in two-dimensional array of integers and change the value (according to some rule, not important).

I'm surprised how significant difference in performance is there between python runtime and C# or java runtime. Did I wrote totally wrong python code (v2.7.2)?

import numpy
a = numpy.ndarray((5000,5000), dtype = numpy.int32)
for x in numpy.nditer(a.T):
    x = 123

>python -m timeit -n 2 -r 2 -s "import numpy; a = numpy.ndarray((5000,5000), dtype=numpy.int32)" "for x in numpy.nditer(a.T):" "  x = 123"
2 loops, best of 2: 4.34 sec per loop

For example the C# code performs only 50ms, i.e. python is almost 100 times slower! (suppose the matrix variable is already initialized)

for (y = 0; y < 5000; y++)
for (x = 0; x < 5000; x++)
    matrix[y][x] = 123;

Answer 1

If you need to do operations on a multidimensional array that depend on the value of the array but don't depend on the position inside the array then .itemset is 5 times faster than nditer for me.

So instead of doing something like

image = np.random.random_sample((200, 200,3));
with np.nditer(image, op_flags=['readwrite']) as it:
    for x in it:
        x[...] = x*4.5 if x<0.2 else x

You can do this

image2 = np.random.random_sample((200, 200,3));
for i in range(0,image2.size):
    x = image2.item(i)
    image2.itemset(i, x*4.5 if x<0.2 else x);

Answer 2

The nditer code does not assign a value to the elements of a. This doesn't affect the timings issue, but I mention it because it should not be taken as a good use of nditer.

a correct version is:

for i in np.nditer(a, op_flags=[["readwrite"]]):
    i[...] = 123

The [...] is needed to retain the reference to loop value, which is an array of shape ().

There's no point in using A.T, since its the values of the base A that get changed.

I agree that the proper way of doing this assignment is a[:]=123.

Answer 3

C++ emphasizes machine time over programmer time.

Python emphasizes programmer time over machine time.

Pypy is a python written in python, and they have the beginnings of numpy; you might try that. Pypy has a nice JIT that makes things quite fast.

You could also try cython, which allows you to translate a dialect of Python to C, and compile the C to a Python C extension module; this allows one to continue using CPython for most of your code, while still getting a bit of a speedup. However, in the one microbenchmark I've tried comparing Pypy and Cython, Pypy was quite a bit faster than Cython.

Cython uses a highly pythonish syntax, but it allows you to pretty freely intermix Python datatypes with C datatypes. If you redo your hotspots with C datatypes, it should be pretty fast. Continuing to use Python datatypes is sped up by Cython too, but not as much.

Answer 4

Python is a much more dynamic language than C or C#. The main reason why the loop is so slow is that on every pass, the CPython interpreter is doing some extra work that wastes time: specifically, it is binding the name x with the next object from the iterator, then when it evaluates the assignment it has to look up the name x again.

As @Sven Marnach noted, you can call a method function numpy.fill() and it is fast. That function is compiled C or maybe Fortran, and it will simply loop over the addresses of the numpy.array data structure and fill in the values. Much less dynamic than Python, which is good for this simple case.

But now consider PyPy. Once you run your program under PyPy, a JIT analyzes what your code is actually doing. In this example, it notes that the name x isn't used for anything but the assignment, and it can optimize away binding the name. This example should be one that PyPy speeds up tremendously; likely PyPy will be ten times faster than plain Python (so only one-tenth as fast as C, rather than 1/100 as fast).

http://pypy.org

As I understand it, PyPy won't be working with Numpy for a while yet, so you can't just run your existing Numpy code under PyPy yet. But the day is coming.

I'm excited about PyPy. It offers the hope that we can write in a very high-level language (Python) and yet get nearly the performance of writing things in "portable assembly language" (C). For examples like this one, the Numpy might even beat the performance of naive C code, by using SIMD instructions from the CPU (SSE2, NEON, or whatever). For this example, with SIMD, you could set four integers to 123 with each loop, and that would be faster than a plain C loop. (Unless the C compiler used a SIMD optimization also! Which, come to think of it, is likely for this case. So we are back to "nearly the speed of C" rather than faster for this example. But we can imagine trickier cases that the C compiler isn't smart enough to optimize, where a future PyPy might.)

But never mind PyPy for now. If you will be working with Numpy, it is a good idea to learn all the functions like numpy.fill() that are there to speed up your code.

Answer 5

The example you gave was presumably meant to set all items of a two-dimensional NumPy array to 123. This can be done efficiently like this:

a.fill(123)

or

a[:] = 123

Answer 6

Yep! Iterating through numpy arrays in python is slow. (Slower than iterating through a python list, as well.)

Typically, you avoid iterating through them directly.

If you can give us an example of the rule you're changing things based on, there's a good chance that it's easy to vectorize.

As a toy example:

import numpy as np

x = np.linspace(0, 8*np.pi, 100)
y = np.cos(x)

x[y > 0] = 100

However, in many cases you have to iterate, either due to the algorithm (e.g. finite difference methods) or to lessen the memory cost of temporary arrays.

In that case, have a look at Cython, Weave, or something similar.