Pourquoi le code Python s'exécute-t-il plus rapidement dans une fonction ?

Question

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

Ce morceau de code en Python s'exécute dans (Note : Le chronométrage est fait avec la fonction time dans BASH sous Linux).

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

Cependant, si la boucle for n'est pas placée dans une fonction,

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

alors il fonctionne pendant un temps beaucoup plus long :

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

Pourquoi ?

Answer 1

A l'intérieur d'une fonction, le bytecode est :

  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        

Au niveau supérieur, le bytecode est :

  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 différence est que STORE_FAST est plus rapide ( !) que STORE_NAME . En effet, dans une fonction, i est un local mais au niveau supérieur, c'est un global.

Pour examiner le bytecode, utilisez la fonction dis module . J'ai pu désassembler directement la fonction, mais pour désassembler le code de niveau supérieur, j'ai dû utiliser la fonction compile intégré .

Answer 2

Vous pourriez demander pourquoi il est plus rapide de stocker des variables locales que des globales. Il s'agit d'un détail d'implémentation de CPython.

Rappelez-vous que CPython est compilé en bytecode, que l'interpréteur exécute. Lorsqu'une fonction est compilée, les variables locales sont stockées dans un tableau de taille fixe ( pas a dict ) et les noms de variables sont affectés aux index. Cela est possible parce que vous ne pouvez pas ajouter dynamiquement des variables locales à une fonction. Ensuite, la récupération d'une variable locale est littéralement une recherche de pointeur dans la liste et une augmentation du refcount sur la fonction PyObject ce qui est trivial.

Comparez cela à une recherche globale ( LOAD_GLOBAL ), qui est un véritable dict recherche impliquant un hachage et ainsi de suite. C'est d'ailleurs pour cette raison que vous devez spécifier global i si vous voulez qu'elle soit globale : si vous assignez à une variable à l'intérieur d'une étendue, le compilateur émettra STORE_FAST pour son accès, sauf si vous lui demandez de ne pas le faire.

D'ailleurs, les recherches globales sont encore assez optimisées. Recherches d'attributs foo.bar sont les vraiment les lents !

Voici un petit illustration sur l'efficacité des variables locales.

Answer 3

En dehors des temps de stockage variables locaux/globaux, prédiction des opcodes rend la fonction plus rapide.

Comme l'expliquent les autres réponses, la fonction utilise la fonction STORE_FAST dans la boucle. Voici le bytecode de la boucle de la fonction :

    >>   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

Normalement, lorsqu'un programme est exécuté, Python exécute chaque opcode l'un aprÃ?s l'autre, en gardant la trace de la pile et en effectuant d'autres vérifications sur la trame de la pile aprÃ?s l'exécution de chaque opcode. La prédiction d'opcode signifie que dans certains cas, Python est capable de sauter directement à l'opcode suivant, évitant ainsi une partie de cette surcharge.

Dans ce cas, chaque fois que Python voit FOR_ITER (le haut de la boucle), il "prédira" que STORE_FAST est le prochain opcode qu'il doit exécuter. Python jette alors un coup d'œil au prochain opcode et, si la prédiction est correcte, il passe directement à STORE_FAST . Cela a pour effet de comprimer les deux opcodes en un seul opcode.

D'autre part, le STORE_NAME L'opcode est utilisé dans la boucle au niveau global. Python fait *pas* faire des prédictions similaires lorsqu'il voit cet opcode. Au lieu de cela, il doit retourner au début de la boucle d'évaluation, ce qui a des implications évidentes sur la vitesse d'exécution de la boucle.

Pour donner un peu plus de détails techniques sur cette optimisation, voici une citation de l'étude de la Commission européenne sur l'optimisation de l'efficacité énergétique. ceval.c (le "moteur" de la machine virtuelle de Python) :

Certains opcodes ont tendance à venir par paires, ce qui permet de prédire le second code lorsque le premier est exécuté. Par exemple, GET_ITER est souvent suivi par FOR_ITER . Et FOR_ITER est souvent suivi de STORE_FAST ou UNPACK_SEQUENCE .

La vérification de la prédiction coûte un seul test à haute vitesse d'un registre par rapport à une constante. Si l'appariement est bon, alors la prédiction de branchement interne du processeur a de fortes chances de réussir. succès, ce qui se traduit par une transition presque sans frais généraux vers l'opcode code opérationnel suivant. Une prédiction réussie permet d'éviter un passage par la boucle d'évaluation y compris ses deux branches imprévisibles, la fonction HAS_ARG test et le switch-case. Combiné avec la prédiction de branchement interne du processeur, un test réussi PREDICT a pour effet de faire fonctionner les deux opcodes comme si comme s'il s'agissait d'un seul nouveau code avec les corps combinés.

Nous pouvons voir dans le code source de la FOR_ITER exactement là où la prédiction de STORE_FAST est faite :

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                                     

Le site PREDICT La fonction s'étend à if (*next_instr == op) goto PRED_##op c'est-à-dire que nous sautons juste au début de l'opcode prédit. Dans ce cas, nous sautons ici :

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 locale est maintenant définie et l'opcode suivant est prêt à être exécuté. Python continue à parcourir l'itérable jusqu'à ce qu'il atteigne la fin, en effectuant à chaque fois la prédiction réussie.

Le site Page wiki Python a plus d'informations sur le fonctionnement de la machine virtuelle de CPython.