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

html.parser python 3

Question

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 un tiempo mucho más largo:

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

¿Por qué es esto?

Answer 1

Aparte 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 utiliza el código de operación STORE_FAST en el bucle. Aquí está el bytecode 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, realizando un seguimiento de la pila y realizando otras verificaciones 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í una parte de esta sobrecarga.

En este caso, cada vez que Python vea FOR_ITER (la parte superior del bucle), "predecirá" que STORE_FAST es el siguiente código de operación que debe ejecutar. Python se asoma al siguiente código de operación y, si la predicción fue correcta, saltará 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_NAME operación STORE_NAME se usa en el bucle a nivel global. Python * no * hace predicciones similares cuando ve este código de operación. En su lugar, debe volver a la parte superior del ciclo de evaluación, 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 archivo ceval.c (el "motor" de la máquina virtual de Python):

Algunos códigos de operación tienden a aparecer en pares, por lo que es posible predecir el segundo código cuando se ejecuta el primero. Por ejemplo, GET_ITER es seguido a menudo por FOR_ITER . Y FOR_ITER suele ir seguido de STORE_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 predicción de rama interna del procesador tiene una alta probabilidad de éxito, lo que resulta en una transición de casi cero a la cabeza del siguiente código de operación. Una predicción exitosa guarda un viaje a través del ciclo de evaluación que incluye sus dos ramas impredecibles, la prueba HAS_ARG y la caja de conmutación. Combinado con la predicción de rama interna del procesador, un PREDICT exitoso tiene 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 operación FOR_ITER exactamente donde se realiza la predicción para 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 función PREDICT expande a if (*next_instr == op) goto PRED_##op es decir, simplemente if (*next_instr == op) goto PRED_##op 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 ya está configurada y el siguiente código de operación está listo para su ejecución. Python continúa a través de lo 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.

Answer 2

Dentro de una función, el bytecode 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 bytecode 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_FAST es más rápido (!) Que STORE_NAME . Esto se debe a que en una función, i es local, pero en el nivel superior es global.

Para examinar el bytecode, use el módulo dis . Pude desmontar la función directamente, pero para desensamblar el código de nivel superior tuve que usar la compile integrada .

Answer 3

Podría 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 está compilado a 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 un 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 en el PyObject que es trivial.

Contraste esto con una búsqueda global ( LOAD_GLOBAL ), que es una verdadera búsqueda de LOAD_GLOBAL que involucra un hash y así sucesivamente. Por cierto, esta es la razón por la que necesita especificar global i si desea que sea global: si alguna vez asigna una variable dentro de un ámbito, el compilador emitirá STORE_FAST s para su acceso, a menos que le diga que no.

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

Aquí hay una pequeña illustration de la eficiencia variable local.