¿Por qué las matrices de Python son lentas?

arrays performance

Question

Esperaba que array.array fuera más rápido que las listas, ya que las matrices parecen estar sin caja.

Sin embargo, obtengo el siguiente resultado:

In [1]: import array

In [2]: L = list(range(100000000))

In [3]: A = array.array(''l'', range(100000000))

In [4]: %timeit sum(L)
1 loop, best of 3: 667 ms per loop

In [5]: %timeit sum(A)
1 loop, best of 3: 1.41 s per loop

In [6]: %timeit sum(L)
1 loop, best of 3: 627 ms per loop

In [7]: %timeit sum(A)
1 loop, best of 3: 1.39 s per loop

¿Cuál podría ser la causa de tal diferencia?

Answer 1

El almacenamiento está "sin caja", pero cada vez que accede a un elemento, Python tiene que "encajonarlo" (incrustarlo en un objeto Python normal) para poder hacer algo con él. Por ejemplo, su sum(A) itera sobre la matriz y encajona cada número entero, uno a la vez, en un objeto int Python regular. Eso cuesta tiempo. En su sum(L) , todo el boxeo se realizó en el momento en que se creó la lista.

Entonces, al final, una matriz es generalmente más lenta, pero requiere sustancialmente menos memoria.

Aquí está el código relevante de una versión reciente de Python 3, pero las mismas ideas básicas se aplican a todas las implementaciones de CPython desde que se lanzó Python por primera vez.

Aquí está el código para acceder a un elemento de la lista:

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    /* error checking omitted */
    return ((PyListObject *)op) -> ob_item[i];
}

Hay muy poco: somelist[i] solo devuelve el i -ésimo objeto en la lista (y todos los objetos Python en CPython son punteros a una estructura cuyo segmento inicial se ajusta al diseño de una struct PyObject ).

Y aquí está la implementación de __getitem__ para una array con código de tipo l :

static PyObject *
l_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong(((long *)ap->ob_item)[i]);
}

La memoria sin procesar se trata como un vector de enteros long C nativos de la plataforma; el i ''th C long se lee; y luego se llama a PyLong_FromLong() para envolver ("caja") el C long nativo en un objeto long Python (que, en Python 3, que elimina la distinción de Python 2 entre int y long , en realidad se muestra como tipo int ).

Este boxeo tiene que asignar nueva memoria para un objeto int Python, y rociar los bits de C long nativos en él. En el contexto del ejemplo original, la vida útil de este objeto es muy breve (solo lo suficiente como para que sum() agregue el contenido a un total acumulado), y luego se necesita más tiempo para desasignar el nuevo objeto int .

Aquí es de donde viene la diferencia de velocidad, siempre ha venido, y siempre vendrá en la implementación de CPython.

Answer 2

Para agregar a la excelente respuesta de Tim Peters, las matrices implementan el protocolo de buffer , mientras que las listas no. Esto significa que, si está escribiendo una extensión C (o el equivalente moral, como escribir un módulo Cython ), puede acceder y trabajar con los elementos de una matriz mucho más rápido que cualquier cosa que Python pueda hacer. Esto le dará mejoras considerables de velocidad, posiblemente por encima de un orden de magnitud. Sin embargo, tiene una serie de inconvenientes:

1. Ahora está en el negocio de escribir C en lugar de Python. Cython es una forma de mejorar esto, pero no elimina muchas diferencias fundamentales entre los idiomas; debe estar familiarizado con la semántica en C y comprender lo que está haciendo.
2. La API C de PyPy funciona hasta cierto punto , pero no es muy rápida. Si está apuntando a PyPy, probablemente debería escribir un código simple con listas regulares y luego dejar que JITter lo optimice por usted.
3. Las extensiones C son más difíciles de distribuir que el código Python puro porque deben compilarse. La compilación tiende a depender de la arquitectura y el sistema operativo, por lo que deberá asegurarse de que está compilando para su plataforma de destino.

Ir directamente a las extensiones C puede estar usando un mazo para aplastar una mosca, dependiendo de su caso de uso. Primero debe investigar NumPy y ver si es lo suficientemente poderoso como para hacer cualquier matemática que intente hacer. También será mucho más rápido que Python nativo, si se usa correctamente.

Answer 3

Tim Peters respondió por qué esto es lento, pero veamos cómo mejorarlo .

De acuerdo con su ejemplo de sum(range(...)) (factor 10 más pequeño que su ejemplo para que quepa en la memoria aquí):

import numpy
import array
L = list(range(10**7))
A = array.array(''l'', L)
N = numpy.array(L)

%timeit sum(L)
10 loops, best of 3: 101 ms per loop

%timeit sum(A)
1 loop, best of 3: 237 ms per loop

%timeit sum(N)
1 loop, best of 3: 743 ms per loop

De esta manera, Numpy también necesita box / unbox, que tiene una sobrecarga adicional. Para hacerlo rápido, uno debe permanecer dentro del código c numpy:

%timeit N.sum()
100 loops, best of 3: 6.27 ms per loop

Entonces, desde la solución de la lista hasta la versión numpy, este es un factor 16 en tiempo de ejecución.

Veamos también cuánto tiempo lleva crear esas estructuras de datos.

%timeit list(range(10**7))
1 loop, best of 3: 283 ms per loop

%timeit array.array(''l'', range(10**7))
1 loop, best of 3: 884 ms per loop

%timeit numpy.array(range(10**7))
1 loop, best of 3: 1.49 s per loop

%timeit numpy.arange(10**7)
10 loops, best of 3: 21.7 ms per loop

Claro ganador: Numpy

También tenga en cuenta que crear la estructura de datos lleva casi tanto tiempo como sumar, si no más. La asignación de memoria es lenta.

Uso de memoria de aquellos:

sys.getsizeof(L)
90000112
sys.getsizeof(A)
81940352
sys.getsizeof(N)
80000096

Entonces estos toman 8 bytes por número con una sobrecarga variable. Para el rango que utilizamos, las entradas de 32 bits son suficientes, por lo que podemos proteger algo de memoria.

N=numpy.arange(10**7, dtype=numpy.int32)

sys.getsizeof(N)
40000096

%timeit N.sum()
100 loops, best of 3: 8.35 ms per loop

Pero resulta que agregar entradas de 64 bits es más rápido que las entradas de 32 bits en mi máquina, por lo que solo vale la pena si está limitado por la memoria / ancho de banda.