¿Cómo funciona el método append de una lista en CPython?

Vamos a empezar con más preguntas que respuestas.

Como sabéis, las listas de Python son arrays dinámicos. Por otro lado, las tuplas son arrays estáticos.

¿Qué implica que las listas sean arrays dinámicos?

Al ser un array dinámico podemos modificar sus elementos así como extender el array (lista).

¿Cómo funciona lo de extender el array (lista)?

Cada vez que usamos el método append de las listas se crea una copia de la lista original y se añade un elemento a esa copia para luego borrar el array original.

¿Es esto último cierto?

Más o menos.

Todos estaréis conmigo que si cada vez que añadimos un nuevo elemento tenemos que crear una copia y luego eliminar el array original podríamos crear cierto coste/gasto de recursos (en memoria, principalmente, creando copias).

Veamos un poco de código:

import sys

lista = []
for i in range(100):
    lista.append(i)
    txt = 'número de elementos = {0:>3} , tamaño de la lista = {1:>4}'
    print(txt.format(i + 1, sys.getsizeof(lista)))
número de elementos =   1 , tamaño de la lista =   96
número de elementos =   2 , tamaño de la lista =   96
número de elementos =   3 , tamaño de la lista =   96
número de elementos =   4 , tamaño de la lista =   96
número de elementos =   5 , tamaño de la lista =  128
número de elementos =   6 , tamaño de la lista =  128
número de elementos =   7 , tamaño de la lista =  128
número de elementos =   8 , tamaño de la lista =  128
número de elementos =   9 , tamaño de la lista =  192
número de elementos =  10 , tamaño de la lista =  192
número de elementos =  11 , tamaño de la lista =  192
número de elementos =  12 , tamaño de la lista =  192
número de elementos =  13 , tamaño de la lista =  192
número de elementos =  14 , tamaño de la lista =  192
número de elementos =  15 , tamaño de la lista =  192
número de elementos =  16 , tamaño de la lista =  192
número de elementos =  17 , tamaño de la lista =  264
número de elementos =  18 , tamaño de la lista =  264
número de elementos =  19 , tamaño de la lista =  264
número de elementos =  20 , tamaño de la lista =  264
número de elementos =  21 , tamaño de la lista =  264
número de elementos =  22 , tamaño de la lista =  264
número de elementos =  23 , tamaño de la lista =  264
número de elementos =  24 , tamaño de la lista =  264
número de elementos =  25 , tamaño de la lista =  264
número de elementos =  26 , tamaño de la lista =  344
número de elementos =  27 , tamaño de la lista =  344
número de elementos =  28 , tamaño de la lista =  344
número de elementos =  29 , tamaño de la lista =  344
número de elementos =  30 , tamaño de la lista =  344
número de elementos =  31 , tamaño de la lista =  344
número de elementos =  32 , tamaño de la lista =  344
número de elementos =  33 , tamaño de la lista =  344
número de elementos =  34 , tamaño de la lista =  344
número de elementos =  35 , tamaño de la lista =  344
número de elementos =  36 , tamaño de la lista =  432
número de elementos =  37 , tamaño de la lista =  432
número de elementos =  38 , tamaño de la lista =  432
número de elementos =  39 , tamaño de la lista =  432
número de elementos =  40 , tamaño de la lista =  432
número de elementos =  41 , tamaño de la lista =  432
número de elementos =  42 , tamaño de la lista =  432
número de elementos =  43 , tamaño de la lista =  432
número de elementos =  44 , tamaño de la lista =  432
número de elementos =  45 , tamaño de la lista =  432
número de elementos =  46 , tamaño de la lista =  432
número de elementos =  47 , tamaño de la lista =  528
número de elementos =  48 , tamaño de la lista =  528
número de elementos =  49 , tamaño de la lista =  528
número de elementos =  50 , tamaño de la lista =  528
número de elementos =  51 , tamaño de la lista =  528
número de elementos =  52 , tamaño de la lista =  528
número de elementos =  53 , tamaño de la lista =  528
número de elementos =  54 , tamaño de la lista =  528
número de elementos =  55 , tamaño de la lista =  528
número de elementos =  56 , tamaño de la lista =  528
número de elementos =  57 , tamaño de la lista =  528
número de elementos =  58 , tamaño de la lista =  528
número de elementos =  59 , tamaño de la lista =  640
número de elementos =  60 , tamaño de la lista =  640
número de elementos =  61 , tamaño de la lista =  640
número de elementos =  62 , tamaño de la lista =  640
número de elementos =  63 , tamaño de la lista =  640
número de elementos =  64 , tamaño de la lista =  640
número de elementos =  65 , tamaño de la lista =  640
número de elementos =  66 , tamaño de la lista =  640
número de elementos =  67 , tamaño de la lista =  640
número de elementos =  68 , tamaño de la lista =  640
número de elementos =  69 , tamaño de la lista =  640
número de elementos =  70 , tamaño de la lista =  640
número de elementos =  71 , tamaño de la lista =  640
número de elementos =  72 , tamaño de la lista =  640
número de elementos =  73 , tamaño de la lista =  768
número de elementos =  74 , tamaño de la lista =  768
número de elementos =  75 , tamaño de la lista =  768
número de elementos =  76 , tamaño de la lista =  768
número de elementos =  77 , tamaño de la lista =  768
número de elementos =  78 , tamaño de la lista =  768
número de elementos =  79 , tamaño de la lista =  768
número de elementos =  80 , tamaño de la lista =  768
número de elementos =  81 , tamaño de la lista =  768
número de elementos =  82 , tamaño de la lista =  768
número de elementos =  83 , tamaño de la lista =  768
número de elementos =  84 , tamaño de la lista =  768
número de elementos =  85 , tamaño de la lista =  768
número de elementos =  86 , tamaño de la lista =  768
número de elementos =  87 , tamaño de la lista =  768
número de elementos =  88 , tamaño de la lista =  768
número de elementos =  89 , tamaño de la lista =  912
número de elementos =  90 , tamaño de la lista =  912
número de elementos =  91 , tamaño de la lista =  912
número de elementos =  92 , tamaño de la lista =  912
número de elementos =  93 , tamaño de la lista =  912
número de elementos =  94 , tamaño de la lista =  912
número de elementos =  95 , tamaño de la lista =  912
número de elementos =  96 , tamaño de la lista =  912
número de elementos =  97 , tamaño de la lista =  912
número de elementos =  98 , tamaño de la lista =  912
número de elementos =  99 , tamaño de la lista =  912
número de elementos = 100 , tamaño de la lista =  912

En el anterior código hemos creado una lista vacía y le hemos ido añadiendo elementos y hemos obtenido el tamaño de la lista usando la función getsizeof que nos indica el tamaño del objeto en bytes. Luego hemos mostrado en pantalla el número de elementos que tiene la lista y el tamaño que ocupa.

Pero, ¿qué ocurre?, ¿por qué aumentando el número de elementos, a veces, no aumenta el tamaño del objeto?, ¿por qué luego cambia?, ¿por qué a medida que hay más elementos en la lista tarda más en cambiar el tamaño de la misma?

Veamos qué dice el código original de las listas en el repo de Python localizado en Objects/listobject.c.

A partir de la línea 42 del código C podemos leer:

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

La última línea traducida a Python sería algo así:

new_allocated = (newsize >> 3) + (3 if newsize < 9 else 6)

En el primer paréntesis tenemos el operador bitwise right shift, similar a la versión en C (no hay que olvidar que CPython está escrito en C) mientras que en el segundo paréntesis tenemos el operador ternario (sin duda, un poco más legible que la versión en C).

¿Qué está pasando aquí?

Los buenos de los core developers de CPython han pensado que si usas un array dinámico será porque quieres hacer 'perrerías' con él, como ampliarlo. Y si lo amplías una vez es probable que lo amplíes varias veces. Es por ello que, normalmente, se usa un un tamaño un poco mayor, basado en el tamaño y siquiendo la regla mostrada más arriba, para el array (lista) y, de esta forma, podemos ampliarlo sin necesidad de crear tantas copias.

Veamos esto gráficamente:

Importamos matplotlib para poder crear los gráficos.

import matplotlib.pyplot as plt
plt.style.use('ggplot')
%matplotlib inline

Creamos nuestra lista y otra lista que almacenará los tamaños en bytes, sizes.

lista = list([1])
sizes = [sys.getsizeof(lista)]

for i in range(2, 100000):
    lista.append(i)
    sizes.append(sys.getsizeof(lista))

Y ahora dibujamos los tamaños en función del número de elementos dentro de la lista:

plt.figure(figsize = (10,10))
plt.plot(lista, sizes)
plt.xlabel('Número de elementos en la lista')
plt.ylabel('Tamaño en bytes para la lista de tamaño $N$')
<matplotlib.text.Text at 0x7f0655169c88>

Vemos como los "escalones" en el tamaño de la lista con N elementos va aumentando y el escalón cada vez es más largo a medida que aumenta el tamaño de la lista.

Veamos como es el valor del tamaño dividido por el número de elementos de la lista a medida que va aumentando el mismo (los ejes de la gráfica tienen escala logarítmica):

increment = [s/l for s, l in zip(sizes, lista)]

plt.figure(figsize = (10,10))
plt.yscale('log')
plt.xscale('log')
plt.ylim(7, max(increment))
plt.plot(lista, increment)
plt.xlabel('Número de elementos en la lista')
plt.ylabel('Bytes por número de elementos')
<matplotlib.text.Text at 0x7f06552ada20>

Curioso, ¿no?

Espero que hayáis aprendido tanto como he aprendido yo elaborando esta entrada.

SyntaxError: more than 255 arguments

Para el que no lo sepa, las funciones en CPython tienen una limitación de 255 argumentos ([*] leed más abajo para más información). Mirad la siguiente pieza de código C en ast.c en el repositorio oficial de CPython:

    if (nargs + nkeywords + ngens > 255) {
        ast_error(c, n, "more than 255 arguments");
        return NULL;
    }

Y probad, por ejemplo, lo siguiente en vuestra consola/editor de Python favorito:

def fn(*args):
    pass

fn(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
   21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,
   39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,
   57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,
   75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,
   93,94,95,96,97,98,99,100,101,102,103,104,105,106,
   107,108,109,110,111,112,113,114,115,116,117,118,
   119,120,121,122,123,124,125,126,127,128,129,130,
   131,132,133,134,135,136,137,138,139,140,141,142,
   143,144,145,146,147,148,149,150,151,152,153,154,
   155,156,157,158,159,160,161,162,163,164,165,166,
   167,168,169,170,171,172,173,174,175,176,177,178,
   179,180,181,182,183,184,185,186,187,188,189,190,
   191,192,193,194,195,196,197,198,199,200,201,202,
   203,204,205,206,207,208,209,210,211,212,213,214,
   215,216,217,218,219,220,221,222,223,224,225,226,
   227,228,229,230,231,232,233,234,235,236,237,238,
   239,240,241,242,243,244,245,246,247,248,249,250,
   251,252,253,254,255,256)

El resultado debería ser similar al título de esta entrada:

SyntaxError: more than 255 arguments

Parece que esto es una limitación de la implementación CPython y no es una especificación del lenguaje. Podéis leer esta conversación en la que Raymond Hettinger comenta que Guido lo considera una limitación arbitraria y que debería ser eliminada en algún momento de CPython (pero ahí sigue en mi CPython3.4). En Pypy lo han implementado exactamente igual ([offtopic] ¿deberían respetar la implementación oficial hasta en cosas que se podrían mejorar? [/offtopic])

[*] Por lo visto, es una limitación del bytecode compilado cuando llamamos a una función (no es un problema de la función en sí, pero sí de la llamada a la función).

Como explican en el último enlace del párrafo anterior, esta limitación se puede sortear de forma muy sencilla usando *args y **kwargs:

argumentos = (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
   21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,
   39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,
   57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,
   75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,
   93,94,95,96,97,98,99,100,101,102,103,104,105,106,
   107,108,109,110,111,112,113,114,115,116,117,118,
   119,120,121,122,123,124,125,126,127,128,129,130,
   131,132,133,134,135,136,137,138,139,140,141,142,
   143,144,145,146,147,148,149,150,151,152,153,154,
   155,156,157,158,159,160,161,162,163,164,165,166,
   167,168,169,170,171,172,173,174,175,176,177,178,
   179,180,181,182,183,184,185,186,187,188,189,190,
   191,192,193,194,195,196,197,198,199,200,201,202,
   203,204,205,206,207,208,209,210,211,212,213,214,
   215,216,217,218,219,220,221,222,223,224,225,226,
   227,228,229,230,231,232,233,234,235,236,237,238,
   239,240,241,242,243,244,245,246,247,248,249,250,
   251,252,253,254,255,256)

fn(*argumentos) #ahora no daría un error de sintaxis

No es que sea algo muy importante y no es habitual usar más de 255 argumentos en una función pero me ha parecido curioso, lo he investigado un poco y lo pongo aquí por si a alguien más le puede interesar.

Saludos.

P.D.: Como siempre, si algo de lo que he escrito es erróneo, por favor, comentadlo y lo actualizo tan rápidamente como pueda.