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

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

Este fragmento de código en Python se ejecuta en (Nota: la sincronización 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

luego se ejecuta durante mucho más tiempo:

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

¿Por qué es esto?

11
  • 18
    ¿Cómo hiciste realmente el cronometraje? 28/06/12 a las 9:21
  • 56
    Solo una intuición, no estoy seguro de si es verdad: supongo que se debe a los alcances. En el caso de la función, se crea un nuevo alcance (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 puedes encontrar muchas cosas, lo que ralentiza el ciclo. 28/06/12 a las 9:22
  • 5
    @Scharron Eso no parece serlo. Se definieron 200k variables ficticias en el alcance sin que eso afectara visiblemente el tiempo de ejecución.
    Deestan
    28/06/12 a las 9:27
  • 58
    @Scharron tienes la mitad de razón. Se trata de ámbitos, pero la razón por la que es más rápido en locales es que los ámbitos locales en realidad se implementan como matrices en lugar de diccionarios (ya que su tamaño se conoce en tiempo de compilación).
    Katriel
    28/06/12 a las 10:31
  • 3
    @AndrewJaffe La salida sugeriría el timecomando de linux . 28/06/12 a las 15:35
669

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 local, pero en el nivel superior es global.

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

14
  • 175
    Confirmado por experimento. Insertar global ien la mainfunción hace que los tiempos de ejecución sean equivalentes.
    Deestan
    28/06/12 a las 9:33
  • 46
    Esto responde a la pregunta sin responder a 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(), via , inspect.getframe()etc.). Buscar un elemento de matriz por un entero constante es mucho más rápido que buscar un dict.
    dmw
    28/06/12 a las 21:53
  • 3
    Lo mismo ocurre con C / C ++ también, el uso de variables globales provoca una desaceleración significativa 29/06/12 a las 0:49
  • 3
    Esta es la primera vez que veo un código de bytes. ¿Cómo se ve? Y es importante saberlo?
    Zack
    30/06/12 a las 22:30
  • 4
    @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í en el verdadero sentido 19/07/12 a las 13:28
565

Quizás se pregunte 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 código de bytes, 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 refcount, lo PyObjectcual es trivial.

Compare esto con una búsqueda global ( LOAD_GLOBAL), que es una dictbúsqueda verdadera que involucra un hash y así sucesivamente. Por cierto, esta es la razón por la que debe especificar global isi desea que sea global: si alguna vez asigna a una variable dentro de un alcance, el compilador emitirá STORE_FASTs para su acceso a menos que usted le indique que no lo haga.

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

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

16
  • 6
    Esto también se aplica a PyPy, hasta la versión actual (1.8 en el momento de escribir este artículo). El código de prueba del OP se ejecuta aproximadamente cuatro veces más lento en el alcance global en comparación con el interior de una función.
    GDorn
    28/06/12 a las 17:17
  • 4
    @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. 28/06/12 a las 18:21
  • 2
    @Walkerneo La conversación principal que se lleva a cabo aquí es la comparación entre las búsquedas de variables locales dentro de una función y las búsquedas de variables globales que se definen a nivel de módulo. Si nota 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 están bastante optimizadas y son más rápidas que las búsquedas de atributos (que son diferentes). No tengo suficiente espacio en este comentario para más. 29/06/12 a las 0:21
  • 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 a una función. El acceso xes local. foo = SomeClass(), foo.bares acceso a atributos. val = 5global es global. En cuanto al atributo local> global> de velocidad según 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 conversación, estamos hablando de búsquedas locales que son una búsqueda de una variable que pertenece a una función. 29/06/12 a las 1:57
  • 4
    @thedoctar echa un vistazo a la globals()función. Si desea más información, 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, ¡así que probablemente ya lo esté usando!
    Katriel
    6/07/12 a las 14:45
45

Aparte de los tiempos de almacenamiento de variables locales / globales, la predicción del 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 que se ejecuta cada código de operación. La predicción de 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 ve FOR_ITER(la parte superior del ciclo), "predecirá" STORE_FASTcuál es el siguiente código de operación que tiene que 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 utiliza en el bucle 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):

Some opcodes tend to come in pairs thus making it possible to predict the second code when the first is run. For example, GET_ITER is often followed by FOR_ITER. And FOR_ITER is often followed by STORE_FAST or UNPACK_SEQUENCE.

Verifying the prediction costs a single high-speed test of a register variable against a constant. If the pairing was good, then the processor's own internal branch predication has a high likelihood of success, resulting in a nearly zero-overhead transition to the next opcode. A successful prediction saves a trip through the eval-loop including its two unpredictable branches, the HAS_ARG test and the switch-case. Combined with the processor's internal branch prediction, a successful PREDICT has the effect of making the two opcodes run as if they were a single new opcode with the bodies combined.

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, 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 de operación está listo para su 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.

2
  • 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, simplemente se pone a 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 con ninguna compilación normal), dejando solo un salto impredecible. 29/03/19 a las 14:56
  • Incluso ese salto impredecible no ocurre en la mayoría de las compilaciones de CPython, debido al nuevo comportamiento de gotos calculado (a partir de Python 3.1 , habilitado por defecto en 3.2 ); cuando se usa, la PREDICTmacro está completamente deshabilitada; en cambio, la mayoría de los casos terminan en una DISPATCHque se ramifica directamente. Pero en las CPU de predicción de rama, el efecto es similar al de PREDICT, ya que la ramificación (y la predicción) es por código de operación, lo que aumenta las probabilidades de una predicción de rama exitosa. 29/03/19 a las 15:03