¿Por qué el código Python se ejecuta más rápido en una función?

836
def main():
    for i in xrange(10**8):
        pass
main()

Este fragmento de código en Python se ejecuta en (Nota: el tiempo se realiza con la función de tiempo en BASH en Linux).

real    0m1.841s
user    0m1.828s
sys     0m0.012s

Sin embargo, si el bucle for no se coloca dentro de una función,

for i in xrange(10**8):
    pass

entonces se ejecuta por mucho más tiempo:

real    0m4.543s
user    0m4.524s
sys     0m0.012s

¿Por qué es esto?

el jugo
fuente
16
¿Cómo hiciste realmente el tiempo?
Andrew Jaffe
53
Solo una intuición, no estoy seguro de si es cierto: supongo que se debe a los alcances. En el caso de la función, se crea un nuevo ámbito (es decir, una especie de hash con nombres de variables vinculados a su valor). Sin una función, las variables están en el ámbito global, cuando puede encontrar muchas cosas, por lo tanto, ralentiza el ciclo.
Scharron
44
@Scharron Eso no parece ser eso. Definió 200k variables ficticias en el alcance sin que eso afecte visiblemente el tiempo de ejecución.
Deestan
2
Alex Martelli escribió una buena respuesta sobre este stackoverflow.com/a/1813167/174728
John La Rooy
53
@Scharron estás medio correcto. Se trata de ámbitos, pero la razón por la que es más rápido en locales es que los ámbitos locales se implementan realmente como matrices en lugar de diccionarios (ya que su tamaño se conoce en tiempo de compilación).
Katriel

Respuestas:

532

Puede preguntar por qué es más rápido almacenar variables locales que globales. Este es un detalle de implementación de CPython.

Recuerde que CPython se compila en bytecode, que ejecuta el intérprete. Cuando se compila una función, las variables locales se almacenan en una matriz de tamaño fijo ( no a dict) y los nombres de las variables se asignan a los índices. Esto es posible porque no puede agregar dinámicamente variables locales a una función. Luego, recuperar una variable local es literalmente una búsqueda de puntero en la lista y un aumento de recuento en el PyObjectque es trivial.

Contraste esto con una búsqueda global ( LOAD_GLOBAL), que es una dictbúsqueda verdadera que implica un hash, etc. Por cierto, es por eso que debe especificar global isi desea que sea global: si alguna vez asigna a una variable dentro de un ámbito, el compilador emitirá STORE_FASTs para su acceso a menos que se lo indique.

Por cierto, las búsquedas globales todavía están bastante optimizadas. ¡Las búsquedas de atributos foo.barson realmente lentas!

Aquí hay una pequeña ilustración sobre la eficiencia variable local.

Katriel
fuente
66
Esto también se aplica a PyPy, hasta la versión actual (1.8 en el momento de escribir esto). El código de prueba del OP se ejecuta cuatro veces más lento en alcance global en comparación con el interior de una función.
GDorn
44
@Walkerneo No lo son, a menos que lo digas al revés. Según lo que dicen katrielalex y ecatmur, las búsquedas de variables globales son más lentas que las búsquedas de variables locales debido al método de almacenamiento.
Jeremy Pridemore
2
@Walkerneo La conversación principal que se desarrolla aquí es la comparación entre búsquedas de variables locales dentro de una función y búsquedas de variables globales que se definen a nivel de módulo. Si observa en su respuesta de comentario original a esta respuesta, dijo "No hubiera pensado que las búsquedas de variables globales fueran más rápidas que las búsquedas de propiedades de variables locales". Y no lo son. katrielalex dijo que, aunque las búsquedas de variables locales son más rápidas que las globales, incluso las globales son bastante optimizadas y más rápidas que las búsquedas de atributos (que son diferentes). No tengo suficiente espacio en este comentario para más.
Jeremy Pridemore
3
@Walkerneo foo.bar no es un acceso local. Es un atributo de un objeto. (Perdone la falta de formato) def foo_func: x = 5, xes local para una función. El acceso xes local. foo = SomeClass(), foo.bares el acceso al atributo. val = 5global es global. En cuanto a la velocidad local> global> atributo de acuerdo con lo que he leído aquí. Por lo tanto el acceso xen foo_funces el más rápido, seguido por val, seguido de foo.bar. foo.attrno es una búsqueda local porque en el contexto de esta convo, estamos hablando de búsquedas locales como una búsqueda de una variable que pertenece a una función.
Jeremy Pridemore
3
@thedoctar echa un vistazo a la globals()función. Si desea más información que esa, es posible que deba comenzar a buscar el código fuente de Python. Y CPython es solo el nombre de la implementación habitual de Python, por lo que probablemente ya lo esté utilizando.
Katriel el
661

Dentro de una función, el código de bytes es:

  2           0 SETUP_LOOP              20 (to 23)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_CONST               3 (100000000)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                 6 (to 22)
             16 STORE_FAST               0 (i)

  3          19 JUMP_ABSOLUTE           13
        >>   22 POP_BLOCK           
        >>   23 LOAD_CONST               0 (None)
             26 RETURN_VALUE        

En el nivel superior, el código de bytes es:

  1           0 SETUP_LOOP              20 (to 23)
              3 LOAD_NAME                0 (xrange)
              6 LOAD_CONST               3 (100000000)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                 6 (to 22)
             16 STORE_NAME               1 (i)

  2          19 JUMP_ABSOLUTE           13
        >>   22 POP_BLOCK           
        >>   23 LOAD_CONST               2 (None)
             26 RETURN_VALUE        

La diferencia es que STORE_FASTes más rápido (!) Que STORE_NAME. Esto se debe a que en una función, ies un local, pero a nivel global es un global.

Para examinar el código de bytes, use el dismódulo . Pude desmontar la función directamente, pero para desmontar el código de nivel superior tuve que usar el compileincorporado .

ecatmur
fuente
171
Confirmado por experimento. Insertar global ien la mainfunción hace que los tiempos de ejecución sean equivalentes.
Deestan
44
Esto responde a la pregunta sin contestar la pregunta :) En el caso de las variables de función local, CPython realmente las almacena en una tupla (que es mutable desde el código C) hasta que se solicita un diccionario (por ejemplo locals(), vía , inspect.getframe()etc.). Buscar un elemento de matriz por un entero constante es mucho más rápido que buscar un dict.
dmw
3
Es lo mismo con C / C ++ también, el uso de variables globales produce una significativa desaceleración
codejammer
3
Este es el primero que he visto de bytecode. ¿Cómo se mira y es importante saberlo?
Zack
44
@gkimsey Estoy de acuerdo. Solo quería compartir dos cosas i) Este comportamiento se observa en otros lenguajes de programación ii) El agente causal es más el lado arquitectónico y no el lenguaje en sí mismo
codejammer
42

Además de los tiempos de almacenamiento de variables locales / globales, la predicción de código de operación hace que la función sea más rápida.

Como explican las otras respuestas, la función usa el STORE_FASTcódigo de operación en el bucle. Aquí está el código de bytes para el bucle de la función:

    >>   13 FOR_ITER                 6 (to 22)   # get next value from iterator
         16 STORE_FAST               0 (x)       # set local variable
         19 JUMP_ABSOLUTE           13           # back to FOR_ITER

Normalmente, cuando se ejecuta un programa, Python ejecuta cada código de operación uno tras otro, haciendo un seguimiento de la pila y realizando otras comprobaciones en el marco de la pila después de ejecutar cada código de operación. La predicción del código de operación significa que, en ciertos casos, Python puede saltar directamente al siguiente código de operación, evitando así parte de esta sobrecarga.

En este caso, cada vez que Python vea FOR_ITER(la parte superior del bucle), "predecirá" STORE_FASTcuál es el próximo código de operación que debe ejecutar. Python luego mira el siguiente código de operación y, si la predicción fue correcta, salta directamente a STORE_FAST. Esto tiene el efecto de comprimir los dos códigos de operación en un solo código de operación.

Por otro lado, el STORE_NAMEcódigo de operación se usa en el ciclo a nivel global. Python * no * hace predicciones similares cuando ve este código de operación. En cambio, debe volver a la parte superior del ciclo de evaluación, lo que tiene implicaciones obvias para la velocidad a la que se ejecuta el ciclo.

Para dar más detalles técnicos sobre esta optimización, aquí hay una cita del ceval.carchivo (el "motor" de la máquina virtual de Python):

Algunos códigos de operación tienden a venir en pares, por lo que es posible predecir el segundo código cuando se ejecuta el primero. Por ejemplo, a GET_ITERmenudo le sigue FOR_ITER. Y a FOR_ITERmenudo es seguido porSTORE_FAST o UNPACK_SEQUENCE.

Verificar la predicción cuesta una sola prueba de alta velocidad de una variable de registro contra una constante. Si el emparejamiento fue bueno, entonces la propia predicación interna de la rama del procesador tiene una alta probabilidad de éxito, lo que resulta en una transición de casi cero sobrecarga al siguiente código operativo. Una predicción exitosa ahorra un viaje a través del ciclo de evaluación que incluye sus dos ramas impredecibles, la HAS_ARGprueba y el caso de cambio. Combinado con la predicción de rama interna del procesador, un éxito PREDICTtiene el efecto de hacer que los dos códigos de operación se ejecuten como si fueran un solo código de operación nuevo con los cuerpos combinados.

Podemos ver en el código fuente del código de FOR_ITERoperación exactamente dónde se realiza la predicción STORE_FAST:

case FOR_ITER:                         // the FOR_ITER opcode case
    v = TOP();
    x = (*v->ob_type->tp_iternext)(v); // x is the next value from iterator
    if (x != NULL) {                     
        PUSH(x);                       // put x on top of the stack
        PREDICT(STORE_FAST);           // predict STORE_FAST will follow - success!
        PREDICT(UNPACK_SEQUENCE);      // this and everything below is skipped
        continue;
    }
    // error-checking and more code for when the iterator ends normally                                     

La PREDICTfunción se expande a, if (*next_instr == op) goto PRED_##opes decir, simplemente saltamos al inicio del código de operación predicho. En este caso, saltamos aquí:

PREDICTED_WITH_ARG(STORE_FAST);
case STORE_FAST:
    v = POP();                     // pop x back off the stack
    SETLOCAL(oparg, v);            // set it as the new local variable
    goto fast_next_opcode;

La variable local ahora está configurada y el siguiente código operativo está en ejecución. Python continúa a través del iterable hasta que llega al final, haciendo la predicción exitosa cada vez.

La página wiki de Python tiene más información sobre cómo funciona la máquina virtual de CPython.

Alex Riley
fuente
Actualización menor: a partir de CPython 3.6, los ahorros de la predicción disminuyen un poco; en lugar de dos ramas impredecibles, solo hay una. El cambio se debe al cambio de bytecode a wordcode ; ahora todos los "códigos de palabras" tienen un argumento, es cero cuando la instrucción no toma un argumento lógicamente. Por lo tanto, la HAS_ARGprueba nunca ocurre (excepto cuando el rastreo de bajo nivel está habilitado tanto en la compilación como en el tiempo de ejecución, lo que no ocurre en la construcción normal), dejando solo un salto impredecible.
ShadowRanger
Incluso ese salto impredecible no ocurre en la mayoría de las compilaciones de CPython, debido al nuevo comportamiento de gotos computados (a partir de Python 3.1 , habilitado por defecto en 3.2 ); cuando se usa, la PREDICTmacro está completamente deshabilitada; en su lugar, la mayoría de los casos terminan en una DISPATCHrama directa. Pero en las CPU de predicción de bifurcación, el efecto es similar al de la PREDICTbifurcación (y la predicción) es por código de operación, lo que aumenta las probabilidades de una predicción de bifurcación exitosa.
ShadowRanger