Profiling Python code one x86 instruction at a time

Question

I recently had a discussion about what the Python interpreter is actually doing when you multiply an array with an integer, e.g. [1] * 3. Someone suggested that Python will generate 3 copies of [1] in memory and then concatenate those copies. A more efficient solution would be a list comprehension (e.g. [1 for _ in range(3)]), which would avoid all this overhead.

That sounds pretty logical, but then I decided to compare the runtime of both methods

>>> timeit.timeit('[1] * 1000000', number=100)
0.6567943999999954
>>> timeit.timeit('[1 for _ in range(1000000)]', number=100)
6.787221699999975

(Python 3.9.7 on Windows)

Looks like the array multiplication method is an order of magnitude faster than the list comprehension.

I wanted to understand what's going on under the hood, so I tried to disassemble the function:

>>> def array_multiply():
...     return [1] * 3
...
>>> import dis
>>> dis.dis(array_multiply)
  2           0 LOAD_CONST               1 (1)
              2 BUILD_LIST               1
              4 LOAD_CONST               2 (3)
              6 BINARY_MULTIPLY
              8 RETURN_VALUE

Well, that wasn't helpful. It just says BINARY_MULTIPLY, but not what's happening when you multiply a list and an integer.

Is there a way to go one level deeper? See the C code that handles [1] * 3, or inspect the machine code Python is producing when I execute this function?

user_14720380 · Answer

Here is the generated c code from cython code that will give you an idea of whats happening:

Cython:

x = [1]*3

Generated C code:

  __pyx_t_1 = PyList_New(1 * 3); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 2, __pyx_L1_error)
  __Pyx_GOTREF(__pyx_t_1);
  { Py_ssize_t __pyx_temp;
    for (__pyx_temp=0; __pyx_temp < 3; __pyx_temp++) {
      __Pyx_INCREF(__pyx_int_1);
      __Pyx_GIVEREF(__pyx_int_1);
      PyList_SET_ITEM(__pyx_t_1, __pyx_temp, __pyx_int_1);
    }
  }
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_x, __pyx_t_1) < 0) __PYX_ERR(0, 2, __pyx_L1_error)
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;

Seems like it:

Make a new PyList object with length of N_elements in list to copy (1) * how many copies (3)
Loop over the number of times to copy the list
Loop over the items in the list to copy
Set the value of the item in the new list with the value in the old list

Edit:

To do this yourself, install cython and make a jupyter notebook. On the first cell, run:

%load_ext cython

On the next cell, run:

%%cython -a

x = [1]*3

Profiling Python code one x86 instruction at a time

1 Answers