python - ¿Por qué es[] más rápido que list()?

performance instantiation

Question

Recientemente comparé las velocidades de procesamiento de [] y list() y me sorprendió descubrir que [] ejecuta más de tres veces más rápido que list() . Ejecuté la misma prueba con {} y dict() y los resultados fueron prácticamente idénticos: [] y {} ambos tomaron alrededor de 0.128 segundos / millón de ciclos, mientras que list() y dict() tomaron aproximadamente 0.428 segundos / millón de ciclos cada uno.

¿Por qué es esto? Do [] y {} (y probablemente () y '''' también) devuelven inmediatamente copias de un literal de stock vacío mientras que sus homólogos explícitamente nombrados ( list() , dict() , tuple() , str() ) ¿Crear completamente un objeto, tengan o no elementos?

No tengo idea de cómo difieren estos dos métodos, pero me encantaría descubrirlo. No pude encontrar una respuesta en los documentos o en SO, y la búsqueda de paréntesis vacíos resultó ser más problemático de lo que esperaba.

timeit.timeit("[]") mis resultados de tiempo llamando a timeit.timeit("[]") y timeit.timeit("list()") , y timeit.timeit("{}") y timeit.timeit("dict()") , para comparar listas y diccionarios, respectivamente. Estoy ejecutando Python 2.7.9.

Recientemente descubrí " ¿Por qué si es Verdadero más lento que si 1? ", Que compara el rendimiento de if True con if 1 y parece tocar un escenario similar literal versus global similar; quizás valga la pena considerarlo también.

Answer 1

¿Por qué es [] más rápido que list() ?

La razón más importante es que Python trata la list() como una función definida por el usuario, lo que significa que puede interceptarla aliasando algo más para list y hacer algo diferente (como usar su propia lista subclasificada o tal vez una deque).

Inmediatamente crea una nueva instancia de una lista integrada con [] .

Mi explicación busca darte la intuición para esto.

Explicación

[] se conoce comúnmente como sintaxis literal.

En la gramática, esto se conoce como "visualización de lista". De los documentos :

Una visualización de lista es una serie posiblemente vacía de expresiones encerradas entre corchetes:

list_display ::=  "[" [starred_list | comprehension] "]"

Una visualización de lista produce un nuevo objeto de lista, el contenido se especifica mediante una lista de expresiones o una comprensión. Cuando se proporciona una lista de expresiones separadas por comas, sus elementos se evalúan de izquierda a derecha y se colocan en el objeto de la lista en ese orden. Cuando se suministra una comprensión, la lista se construye a partir de los elementos resultantes de la comprensión.

En resumen, esto significa que se crea un objeto incorporado de la list de tipos.

No hay forma de eludir esto, lo que significa que Python puede hacerlo tan rápido como sea posible.

Por otro lado, list() se puede interceptar creando una list integrada utilizando el constructor de la lista integrada.

Por ejemplo, supongamos que queremos que nuestras listas se creen ruidosamente:

class List(list):
    def __init__(self, iterable=None):
        if iterable is None:
            super().__init__()
        else:
            super().__init__(iterable)
        print(''List initialized.'')

Luego podríamos interceptar la list de list en el ámbito global del nivel del módulo, y luego, cuando creamos una list , en realidad creamos nuestra lista de subtipos:

>>> list = List
>>> a_list = list()
List initialized.
>>> type(a_list)
<class ''__main__.List''>

Del mismo modo, podríamos eliminarlo del espacio de nombres global

del list

y ponerlo en el espacio de nombres incorporado:

import builtins
builtins.list = List

Y ahora:

>>> list_0 = list()
List initialized.
>>> type(list_0)
<class ''__main__.List''>

Y tenga en cuenta que la visualización de la lista crea una lista incondicionalmente:

>>> list_1 = []
>>> type(list_1)
<class ''list''>

Probablemente solo hagamos esto temporalmente, así que deshazcamos nuestros cambios: primero elimine el nuevo objeto List de los builtins:

>>> del builtins.list
>>> builtins.list
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: module ''builtins'' has no attribute ''list''
>>> list()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name ''list'' is not defined

Oh, no, perdimos la noción del original.

No se preocupe, todavía podemos obtener la list : es el tipo de una lista literal:

>>> builtins.list = type([])
>>> list()
[]

Asi que...

¿Por qué es [] más rápido que list() ?

Como hemos visto, podemos sobrescribir la list , pero no podemos interceptar la creación del tipo literal. Cuando usamos la list , tenemos que hacer búsquedas para ver si hay algo allí.

Luego tenemos que llamar a cualquier llamada que hayamos buscado. De la gramática:

Una llamada llama a un objeto invocable (por ejemplo, una función) con una serie de argumentos posiblemente vacía:

call                 ::=  primary "(" [argument_list [","] | comprehension] ")"

Podemos ver que hace lo mismo con cualquier nombre, no solo con la lista:

>>> import dis
>>> dis.dis(''list()'')
  1           0 LOAD_NAME                0 (list)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE
>>> dis.dis(''doesnotexist()'')
  1           0 LOAD_NAME                0 (doesnotexist)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE

Para [] no hay llamada de función en el nivel de bytecode de Python:

>>> dis.dis(''[]'')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE

Simplemente va directamente a la construcción de la lista sin búsquedas ni llamadas a nivel de bytecode.

Conclusión

Hemos demostrado que la list puede ser interceptada con el código de usuario usando las reglas de alcance, y esa list() busca un invocable y luego lo llama.

Mientras que [] es una visualización de lista, o un literal, y por lo tanto evita la búsqueda de nombre y la llamada a la función.

Answer 2

Debido a que list es una function para convertir, digamos una cadena en un objeto de lista, mientras que [] se usa para crear una lista desde el principio. Pruebe esto (puede tener más sentido para usted):

x = "wham bam"
a = list(x)
>>> a
["w", "h", "a", "m", ...]

Mientras

y = ["wham bam"]
>>> y
["wham bam"]

Te da una lista real que contiene todo lo que pones en ella.

Answer 3

Las respuestas aquí son geniales, al punto y cubren completamente esta pregunta. Dejaré un paso más abajo del código de bytes para aquellos interesados. Estoy usando el repositorio más reciente de CPython; las versiones anteriores se comportan de manera similar a este respecto, pero pueden existir ligeros cambios.

Aquí hay un desglose de la ejecución para cada uno de estos, BUILD_LIST para [] y CALL_FUNCTION para list() .

La instrucción BUILD_LIST :

Deberías ver el horror:

PyObject *list =  PyList_New(oparg);
if (list == NULL)
    goto error;
while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();

Terriblemente enrevesada, lo sé. Así de simple es:

• Cree una nueva lista con PyList_New (esto asigna principalmente la memoria para un nuevo objeto de lista), oparg indicando el número de argumentos en la pila. Directo al grano.
• Compruebe que nada salió mal con if (list==NULL) .
• Agregue cualquier argumento (en nuestro caso, esto no se ejecuta) ubicado en la pila con PyList_SET_ITEM (una macro).

¡No es de extrañar que sea rápido! Está hecho a medida para crear nuevas listas, nada más :-)

La instrucción CALL_FUNCTION :

Esto es lo primero que ve cuando mira el código que maneja CALL_FUNCTION :

PyObject **sp, *res;
sp = stack_pointer;
res = call_function(&sp, oparg, NULL);
stack_pointer = sp;
PUSH(res);
if (res == NULL) {
    goto error;
}
DISPATCH();

Parece bastante inofensivo, ¿verdad? Bueno, no, desafortunadamente no, call_function no es un tipo directo que llamará a la función de inmediato, no puede. En cambio, toma el objeto de la pila, toma todos los argumentos de la pila y luego cambia según el tipo de objeto; Es una:

• PyCFunction_Type ? No, es una list , la list no es del tipo PyCFunction
• PyMethodType ? No, ver anterior.
• PyFunctionType ? No, ver anterior.

Estamos llamando al tipo de list , el argumento pasado a call_function es PyList_Type . CPython ahora tiene que llamar a una función genérica para manejar cualquier objeto invocable llamado _PyObject_FastCallKeywords , yay más llamadas a funciones.

Esta función nuevamente realiza algunas comprobaciones para ciertos tipos de funciones (que no puedo entender por qué) y luego, después de crear un dict para kwargs si es necesario , llama a _PyObject_FastCallDict .

_PyObject_FastCallDict finalmente nos lleva a alguna parte. Después de realizar incluso más comprobaciones , toma la ranura tp_call del type del type que hemos pasado, es decir, toma type.tp_call . Luego procede a crear una tupla a partir de los argumentos pasados ​​con _PyStack_AsTuple y, finalmente, ¡ finalmente se puede hacer una llamada !

tp_call , que coincide con el type.__call__ hace cargo y finalmente crea el objeto de lista. Llama a las listas __new__ que corresponde a PyType_GenericNew y le asigna memoria con PyType_GenericAlloc : esta es la parte en la que finalmente se PyList_New día con PyList_New . Todo lo anterior es necesario para manejar objetos de forma genérica.

Al final, type_call llama a la list.__init__ e inicializa la lista con cualquier argumento disponible, luego regresamos por donde vinimos. :-)

Finalmente, LOAD_NAME , ese es otro tipo que contribuye aquí.

Es fácil ver que, cuando se trata de nuestra entrada, Python generalmente tiene que saltar a través de los aros para descubrir realmente la función C adecuada para hacer el trabajo. No tiene la cortesía de llamarlo de inmediato porque es dinámico, alguien podría enmascarar la list ( y mucha gente lo hace ) y se debe tomar otro camino.

Aquí es donde list() pierde mucho: la exploración de Python debe hacer para descubrir qué diablos debería hacer.

La sintaxis literal, por otro lado, significa exactamente una cosa; no se puede cambiar y siempre se comporta de manera predeterminada.

^{Nota al pie: Todos los nombres de funciones están sujetos a cambios de una versión a otra. El punto sigue en pie y lo más probable es que permanezca en cualquier versión futura, es la búsqueda dinámica que ralentiza las cosas.}

Answer 4

Porque [] y {} son sintaxis literal . Python puede crear bytecode solo para crear la lista o los objetos del diccionario:

>>> import dis
>>> dis.dis(compile(''[]'', '''', ''eval''))
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
>>> dis.dis(compile(''{}'', '''', ''eval''))
  1           0 BUILD_MAP                0
              3 RETURN_VALUE        

list() y dict() son objetos separados. Deben resolverse sus nombres, la pila debe estar involucrada para enviar los argumentos, el marco debe almacenarse para recuperarlo más tarde y debe realizarse una llamada. Todo eso lleva más tiempo.

Para el caso vacío, eso significa que tiene al menos un LOAD_NAME (que tiene que buscar a través del espacio de nombres global, así como el módulo __builtin__ ) seguido de un CALL_FUNCTION , que debe preservar el marco actual:

>>> dis.dis(compile(''list()'', '''', ''eval''))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(compile(''dict()'', '''', ''eval''))
  1           0 LOAD_NAME                0 (dict)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        

Puede timeit búsqueda de nombres por separado con timeit :

>>> import timeit
>>> timeit.timeit(''list'', number=10**7)
0.30749011039733887
>>> timeit.timeit(''dict'', number=10**7)
0.4215109348297119

La discrepancia de tiempo probablemente es una colisión de hash de diccionario. Resta esos tiempos de los tiempos para llamar a esos objetos, y compara el resultado con los tiempos para usar literales:

>>> timeit.timeit(''[]'', number=10**7)
0.30478692054748535
>>> timeit.timeit(''{}'', number=10**7)
0.31482696533203125
>>> timeit.timeit(''list()'', number=10**7)
0.9991960525512695
>>> timeit.timeit(''dict()'', number=10**7)
1.0200958251953125

Por lo tanto, tener que llamar al objeto requiere 1.00 - 0.31 - 0.30 == 0.39 segundos adicionales por cada 10 millones de llamadas.

Puede evitar el costo de búsqueda global timeit los nombres globales como locales (usando una configuración de timeit , todo lo que vincula a un nombre es un local):

>>> timeit.timeit(''_list'', ''_list = list'', number=10**7)
0.1866450309753418
>>> timeit.timeit(''_dict'', ''_dict = dict'', number=10**7)
0.19016098976135254
>>> timeit.timeit(''_list()'', ''_list = list'', number=10**7)
0.841480016708374
>>> timeit.timeit(''_dict()'', ''_dict = dict'', number=10**7)
0.7233691215515137

pero nunca puede superar ese costo de CALL_FUNCTION .

Answer 5

list() requiere una búsqueda global y una llamada a función, pero [] compila en una sola instrucción. Ver:

Python 2.7.3
>>> import dis
>>> print dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
None
>>> print dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
None