Comment se fait-il que le déballage soit plus rapide que l'accès par index?

Question

Je fais allusion à cette question, et surtout les commentaires de la première réponse de @David Robinson et @mgilson: Somme de la deuxième valeur de chaque tuple dans une liste

La question d'origine était à la somme de la deuxième valeur de chaque tuble:

structure = [('a', 1), ('b', 3), ('c', 2)]

Première Réponse:

sum(n for _, n in structure)

Deuxième Réponse:

sum(x[1] for x in structure)

Selon la discussion, la première réponse est de 50% plus rapide.

Une fois que j'ai compris ce que la première réponse ne (venir de Perl, j'ai Googlé pour le spécial _ moyens variables en python), je me suis demandais comment se fait-ce qui apparaît comme un pur sous-ensemble de tâches (obtenir que le deuxième élément de chaque tuple vs. trouver et de liaison dans des variables les deux éléments) est en fait plus lentement? Est-ce un manque de possibilité d'optimiser l'indice d'accès en Python? Ai-je raté quelque chose la deuxième réponse ne ce qui prend du temps?

Answer 1

Si vous jetez un oeil à la bytecode python, il devient assez évident très vite pourquoi le déballage est plus rapide:

>>> import dis
>>> def unpack_or_index(t=(0, 1)):
...     _, x = t
...     x = t[1]
... 
>>> dis.dis(unpack_or_index)
  2           0 LOAD_FAST                0 (t)
              3 UNPACK_SEQUENCE          2
              6 STORE_FAST               1 (_)
              9 STORE_FAST               2 (x)

  3          12 LOAD_FAST                0 (t)
             15 LOAD_CONST               1 (1)
             18 BINARY_SUBSCR       
             19 STORE_FAST               2 (x)
             22 LOAD_CONST               0 (None)
             25 RETURN_VALUE        

Le tuple déballage de l'opération est simple bytecode (UNPACK_SEQUENCE), tandis que l'opération d'indexation a pour appeler une méthode sur le n-uplet (BINARY_SUBSCR). L'opération de décompression peut prendre place, en ligne, en python la boucle d'évaluation, tandis que l'abonnement appel nécessite la recherche de la fonction de l'objet de tuple pour récupérer la valeur, à l'aide de PyObject_GetItem.

L' UNPACK_SEQUENCE opcode code source spéciale-cas d'un python tuple ou une liste de décompresser où la longueur de la séquence correspond à l'argument de la longueur exactement:

        if (PyTuple_CheckExact(v) &&
            PyTuple_GET_SIZE(v) == oparg) {
            PyObject **items = \
                ((PyTupleObject *)v)->ob_item;
            while (oparg--) {
                w = items[oparg];
                Py_INCREF(w);
                PUSH(w);
            }
            Py_DECREF(v);
            continue;
        } // followed by an "else if" statement for a list with similar code

Le code ci-dessus atteint dans la structure native de la n-uplet et récupère les valeurs directement, pas besoin d'utiliser de lourdes appels tels que PyObject_GetItem qui ont à prendre en compte le fait que l'objet pourrait être un custom python classe.

L' BINARY_SUBSCR opcode est seulement optimisé pour python listes; tout ce qui n'est pas un natif liste python nécessite un PyObject_GetItem appel.

Answer 2

L'indexation passe par la méthode spéciale __getitem__ , qui doit donc effectuer la recherche et l'exécution des fonctions pour chaque élément. Cela signifie que pour une liste d'éléments n , vous vous retrouvez à effectuer des recherches / appels n .

Le déballage n'a pas à gérer cela lorsque vous travaillez avec des listes / tuples natifs; il passe simplement par __iter__ qui est un seul appel, puis décompresse la séquence résultante en C.