Caso de error de optimización de adición de cadena CPython

La pregunta

¿Por qué, en CPython, hace

def add_string(n): s = '' for _ in range(n): s += ' ' 

tomar tiempo lineal, pero

 def add_string_in_list(n): l = [''] for _ in range(n): l[0] += ' ' 

tomar tiempo cuadrático?


Prueba:

 Timer(partial(add_string, 1000000)).timeit(1) #>>> 0.1848409200028982 Timer(partial(add_string, 10000000)).timeit(1) #>>> 1.1123797750042286 
 Timer(partial(add_string_in_list, 10000)).timeit(1) #>>> 0.0033865350123960525 Timer(partial(add_string_in_list, 100000)).timeit(1) #>>> 0.25131178900483064 

Lo que yo sé

CPython tiene una optimización para la adición de cadenas cuando la cadena que se agrega tiene un recuento de referencia de 1.

Esto se debe a que las cadenas en Python son inmutables, por lo que normalmente no se pueden editar. Si existen varias referencias a una cadena y ésta está mutada, ambas referencias verán la cadena modificada. Esto obviamente no es deseado, por lo que la mutación no puede ocurrir con múltiples referencias.

Sin embargo, si solo hay una referencia a la cadena, mutar el valor solo cambiará la cadena para esa referencia, que quiere que se cambie. Puede probar que esta es una causa probable como tal:

 from timeit import Timer from functools import partial def add_string_two_references(n): s = '' for _ in range(n): s2 = s s += ' ' Timer(partial(add_string_two_references, 20000)).timeit(1) #>>> 0.032532954995986074 Timer(partial(add_string_two_references, 200000)).timeit(1) #>>> 1.0898985149979126 

No estoy seguro de por qué el factor es solo 30x, en lugar del esperado 100x, pero creo que es una sobrecarga.


Lo que no se

Entonces, ¿por qué la versión de lista está creando dos referencias? ¿Es esto lo que está impidiendo la optimización?

Puede comprobar que no se tratan los objetos normales de manera diferente:

 class Counter: def __iadd__(self, other): print(sys.getrefcount(self)) s = Counter() s += None #>>> 6 class Counter: def __iadd__(self, other): print(sys.getrefcount(self)) l = [Counter()] l[0] += None #>>> 6 

En el enfoque basado en listas, la cadena del índice 0 de la lista se toma y modifica antes de volver a la lista en el índice 0.
Para este breve momento, el intérprete aún tiene la versión anterior de la cadena en la lista y no puede realizar la modificación en el lugar.
Si echa un vistazo a la fuente de Python , verá que no hay soporte para modificar el elemento de la lista en su lugar. Por lo tanto, el objeto (cadena en este caso) debe recuperarse de la lista, modificarse y luego volver a colocarse.
En otras palabras, el tipo de list es completamente ajeno al soporte de tipo str para el operador += .

Y considera el siguiente código:

 l = ['abc', 'def'] def nasty(): global l l[0] = 'ghi' l[1] = 'jkl' return 'mno' l[0] += nasty() 

El valor de l es ['abcmno', 'jkl'] que prueba que 'abc' se tomó de la lista, luego se ejecutó nasty() modificando el contenido de la lista, las cadenas 'abc' y 'mno' se concatenaron y el resultado fue asignado a l[0] . Si se evaluó nasty() antes de acceder a l[0] para modificarlo en su lugar, el resultado sería 'ghimno' .

Entonces, ¿por qué la versión de la lista está creando dos referencias?

En l[0] += ' ' , una referencia está en l[0] . Se crea temporalmente una referencia para realizar el += encendido.

Aquí hay dos funciones más simples para mostrar el efecto:

 >>> def f(): ... l = [''] ... l[0] += ' ' ... >>> def g(): ... s = '' ... s += ' ' ... 

Desmontándolos da

 >>> from dis import dis >>> dis(f) 2 0 LOAD_CONST 1 ('') 3 BUILD_LIST 1 6 STORE_FAST 0 (l) 3 9 LOAD_FAST 0 (l) 12 LOAD_CONST 2 (0) 15 DUP_TOPX 2 18 BINARY_SUBSCR 19 LOAD_CONST 3 (' ') 22 INPLACE_ADD 23 ROT_THREE 24 STORE_SUBSCR 25 LOAD_CONST 0 (None) 28 RETURN_VALUE >>> dis(g) 2 0 LOAD_CONST 1 ('') 3 STORE_FAST 0 (s) 3 6 LOAD_FAST 0 (s) 9 LOAD_CONST 2 (' ') 12 INPLACE_ADD 13 STORE_FAST 0 (s) 16 LOAD_CONST 0 (None) 19 RETURN_VALUE 

En f , la BINARY_SUBSCR (rebanar) coloca l[0] en la parte superior de la stack de VM. DUP_TOPX duplica los n elementos principales en la stack. Ambas funciones (ver ceval.c ) aumentan el conteo de referencia; DUP_TOPX ( DUP_TOP_TWO en Py3) lo hace directamente, mientras que BINARY_SUBSCR usa PyObject_GetItem . Por lo tanto, el recuento de referencia de la cadena es ahora al menos tres.

g no tiene este problema Crea una referencia adicional cuando el elemento se empuja con LOAD_FAST , dando un refcount de dos, el número mínimo para un elemento en la stack de VM, por lo que puede hacer la optimización.