Pourquoi «x» dans («x»,) est-il plus rapide que «x» == «x»?

274
>>> timeit.timeit("'x' in ('x',)")
0.04869917374131205
>>> timeit.timeit("'x' == 'x'")
0.06144205736110564

Fonctionne également pour les tuples avec plusieurs éléments, les deux versions semblent se développer de manière linéaire:

>>> timeit.timeit("'x' in ('x', 'y')")
0.04866674801541748
>>> timeit.timeit("'x' == 'x' or 'x' == 'y'")
0.06565782838087131
>>> timeit.timeit("'x' in ('y', 'x')")
0.08975995576448526
>>> timeit.timeit("'x' == 'y' or 'x' == 'y'")
0.12992391047427532

Sur cette base, je pense que je devrais totalement commencer à utiliser inpartout au lieu de ==!

Markus Meskanen
la source
167
Juste au cas où: Veuillez ne pas commencer à utiliser inpartout au lieu de ==. C'est une optimisation prématurée qui nuit à la lisibilité.
Colonel Thirty Two
4
essayer x ="!foo" x in ("!foo",)etx == "!foo"
Padraic Cunningham
2
A dans B = Valeur, C == D Valeur et comparaison de type
dsgdfg
6
Une approche plus raisonnable que d'utiliser inau lieu de ==consiste à passer à C.
Mad Physicist
1
Si vous écrivez en Python et que vous choisissez une construction plutôt qu'une autre pour la vitesse, vous vous trompez.
Veky

Réponses:

257

Comme je l'ai mentionné à David Wolever, il y a plus que cela à première vue; les deux méthodes sont envoyées à is; vous pouvez le prouver en faisant

min(Timer("x == x", setup="x = 'a' * 1000000").repeat(10, 10000))
#>>> 0.00045456900261342525

min(Timer("x == y", setup="x = 'a' * 1000000; y = 'a' * 1000000").repeat(10, 10000))
#>>> 0.5256857610074803

Le premier ne peut être aussi rapide car il vérifie par identité.

Pour savoir pourquoi l'un prendrait plus de temps que l'autre, suivons l'exécution.

Ils commencent tous les deux ceval.c, COMPARE_OPpuisque c'est le bytecode impliqué

TARGET(COMPARE_OP) {
    PyObject *right = POP();
    PyObject *left = TOP();
    PyObject *res = cmp_outcome(oparg, left, right);
    Py_DECREF(left);
    Py_DECREF(right);
    SET_TOP(res);
    if (res == NULL)
        goto error;
    PREDICT(POP_JUMP_IF_FALSE);
    PREDICT(POP_JUMP_IF_TRUE);
    DISPATCH();
}

Cela extrait les valeurs de la pile (techniquement, il n'en affiche qu'une seule)

PyObject *right = POP();
PyObject *left = TOP();

et exécute la comparaison:

PyObject *res = cmp_outcome(oparg, left, right);

cmp_outcome est-ce:

static PyObject *
cmp_outcome(int op, PyObject *v, PyObject *w)
{
    int res = 0;
    switch (op) {
    case PyCmp_IS: ...
    case PyCmp_IS_NOT: ...
    case PyCmp_IN:
        res = PySequence_Contains(w, v);
        if (res < 0)
            return NULL;
        break;
    case PyCmp_NOT_IN: ...
    case PyCmp_EXC_MATCH: ...
    default:
        return PyObject_RichCompare(v, w, op);
    }
    v = res ? Py_True : Py_False;
    Py_INCREF(v);
    return v;
}

C'est là que les chemins se séparent. La PyCmp_INbranche ne

int
PySequence_Contains(PyObject *seq, PyObject *ob)
{
    Py_ssize_t result;
    PySequenceMethods *sqm = seq->ob_type->tp_as_sequence;
    if (sqm != NULL && sqm->sq_contains != NULL)
        return (*sqm->sq_contains)(seq, ob);
    result = _PySequence_IterSearch(seq, ob, PY_ITERSEARCH_CONTAINS);
    return Py_SAFE_DOWNCAST(result, Py_ssize_t, int);
}

Notez qu'un tuple est défini comme

static PySequenceMethods tuple_as_sequence = {
    ...
    (objobjproc)tuplecontains,                  /* sq_contains */
};

PyTypeObject PyTuple_Type = {
    ...
    &tuple_as_sequence,                         /* tp_as_sequence */
    ...
};

Donc la branche

if (sqm != NULL && sqm->sq_contains != NULL)

sera prise et *sqm->sq_contains, qui est la fonction (objobjproc)tuplecontains, sera prise.

Cela ne

static int
tuplecontains(PyTupleObject *a, PyObject *el)
{
    Py_ssize_t i;
    int cmp;

    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
        cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),
                                           Py_EQ);
    return cmp;
}

... Attendez, n'est- PyObject_RichCompareBoolce pas ce que l'autre branche a pris? Non, c'était PyObject_RichCompare.

Ce chemin de code était court donc il se résume probablement à la vitesse de ces deux. Comparons.

int
PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
{
    PyObject *res;
    int ok;

    /* Quick result when objects are the same.
       Guarantees that identity implies equality. */
    if (v == w) {
        if (op == Py_EQ)
            return 1;
        else if (op == Py_NE)
            return 0;
    }

    ...
}

Le chemin de code dans PyObject_RichCompareBoolse termine presque immédiatement. Car PyObject_RichCompare,

PyObject *
PyObject_RichCompare(PyObject *v, PyObject *w, int op)
{
    PyObject *res;

    assert(Py_LT <= op && op <= Py_GE);
    if (v == NULL || w == NULL) { ... }
    if (Py_EnterRecursiveCall(" in comparison"))
        return NULL;
    res = do_richcompare(v, w, op);
    Py_LeaveRecursiveCall();
    return res;
}

Le combo Py_EnterRecursiveCall/ Py_LeaveRecursiveCalln'est pas repris dans le chemin précédent, mais ce sont des macros relativement rapides qui court-circuiteront après incrémentation et décrémentation de certains globaux.

do_richcompare Est-ce que:

static PyObject *
do_richcompare(PyObject *v, PyObject *w, int op)
{
    richcmpfunc f;
    PyObject *res;
    int checked_reverse_op = 0;

    if (v->ob_type != w->ob_type && ...) { ... }
    if ((f = v->ob_type->tp_richcompare) != NULL) {
        res = (*f)(v, w, op);
        if (res != Py_NotImplemented)
            return res;
        ...
    }
    ...
}

Cela fait quelques vérifications rapides pour appeler v->ob_type->tp_richcomparece qui est

PyTypeObject PyUnicode_Type = {
    ...
    PyUnicode_RichCompare,      /* tp_richcompare */
    ...
};

qui fait

PyObject *
PyUnicode_RichCompare(PyObject *left, PyObject *right, int op)
{
    int result;
    PyObject *v;

    if (!PyUnicode_Check(left) || !PyUnicode_Check(right))
        Py_RETURN_NOTIMPLEMENTED;

    if (PyUnicode_READY(left) == -1 ||
        PyUnicode_READY(right) == -1)
        return NULL;

    if (left == right) {
        switch (op) {
        case Py_EQ:
        case Py_LE:
        case Py_GE:
            /* a string is equal to itself */
            v = Py_True;
            break;
        case Py_NE:
        case Py_LT:
        case Py_GT:
            v = Py_False;
            break;
        default:
            ...
        }
    }
    else if (...) { ... }
    else { ...}
    Py_INCREF(v);
    return v;
}

A savoir, ces raccourcis sur left == right... mais seulement après avoir fait

    if (!PyUnicode_Check(left) || !PyUnicode_Check(right))

    if (PyUnicode_READY(left) == -1 ||
        PyUnicode_READY(right) == -1)

Dans l'ensemble, les chemins ressemblent alors à quelque chose comme cela (alignement récursif manuel, déroulement et élagage des branches connues)

POP()                           # Stack stuff
TOP()                           #
                                #
case PyCmp_IN:                  # Dispatch on operation
                                #
sqm != NULL                     # Dispatch to builtin op
sqm->sq_contains != NULL        #
*sqm->sq_contains               #
                                #
cmp == 0                        # Do comparison in loop
i < Py_SIZE(a)                  #
v == w                          #
op == Py_EQ                     #
++i                             # 
cmp == 0                        #
                                #
res < 0                         # Convert to Python-space
res ? Py_True : Py_False        #
Py_INCREF(v)                    #
                                #
Py_DECREF(left)                 # Stack stuff
Py_DECREF(right)                #
SET_TOP(res)                    #
res == NULL                     #
DISPATCH()                      #

contre

POP()                           # Stack stuff
TOP()                           #
                                #
default:                        # Dispatch on operation
                                #
Py_LT <= op                     # Checking operation
op <= Py_GE                     #
v == NULL                       #
w == NULL                       #
Py_EnterRecursiveCall(...)      # Recursive check
                                #
v->ob_type != w->ob_type        # More operation checks
f = v->ob_type->tp_richcompare  # Dispatch to builtin op
f != NULL                       #
                                #
!PyUnicode_Check(left)          # ...More checks
!PyUnicode_Check(right))        #
PyUnicode_READY(left) == -1     #
PyUnicode_READY(right) == -1    #
left == right                   # Finally, doing comparison
case Py_EQ:                     # Immediately short circuit
Py_INCREF(v);                   #
                                #
res != Py_NotImplemented        #
                                #
Py_LeaveRecursiveCall()         # Recursive check
                                #
Py_DECREF(left)                 # Stack stuff
Py_DECREF(right)                #
SET_TOP(res)                    #
res == NULL                     #
DISPATCH()                      #

Maintenant, PyUnicode_Checket PyUnicode_READYsont assez bon marché car ils ne vérifient que quelques champs, mais il devrait être évident que celui du haut est un chemin de code plus petit, il a moins d'appels de fonction, une seule instruction switch et est juste un peu plus mince.

TL; DR:

Les deux expédient à if (left_pointer == right_pointer); la différence est juste combien de travail ils font pour y arriver. infait juste moins.

Veedrac
la source
18
Ceci est une réponse incroyable. Quelle est votre relation avec le projet python?
kdbanman
9
@kdbanman Aucun, vraiment, même si j'ai réussi à forcer mon chemin un peu;).
Veedrac
21
@varepsilon Aww, mais personne ne prendrait la peine de parcourir le message! Le point de la question n'est pas vraiment la réponse mais le processus utilisé pour obtenir la réponse - j'espère qu'il n'y aura pas une tonne de personnes utilisant ce hack en production!
Veedrac
181

Il y a trois facteurs en jeu ici qui, combinés, produisent ce comportement surprenant.

Premièrement: l' inopérateur prend un raccourci et vérifie l'identité ( x is y) avant de vérifier l'égalité ( x == y):

>>> n = float('nan')
>>> n in (n, )
True
>>> n == n
False
>>> n is n
True

Deuxièmement: en raison de l'internement de chaînes de Python, les deux "x"s dans "x" in ("x", )seront identiques:

>>> "x" is "x"
True

(grand avertissement: ce comportement est spécifique, de mise en œuvre! isdoit jamais être utilisé pour comparer des chaînes , car il va donner des réponses surprenantes parfois, par exemple "x" * 100 is "x" * 100 ==> False)

Troisièmement: comme détaillé dans la réponse fantastique de Veedrac , tuple.__contains__( x in (y, )est à peu près équivalent à (y, ).__contains__(x)) arrive au point d'effectuer le contrôle d'identité plus rapidement que str.__eq__(encore une fois, x == yest à peu près équivalent à x.__eq__(y)).

Vous pouvez en voir la preuve car il x in (y, )est beaucoup plus lent que son équivalent logique x == y:

In [18]: %timeit 'x' in ('x', )
10000000 loops, best of 3: 65.2 ns per loop

In [19]: %timeit 'x' == 'x'    
10000000 loops, best of 3: 68 ns per loop

In [20]: %timeit 'x' in ('y', ) 
10000000 loops, best of 3: 73.4 ns per loop

In [21]: %timeit 'x' == 'y'    
10000000 loops, best of 3: 56.2 ns per loop

Le x in (y, )cas est plus lent car, après l' iséchec de la comparaison, l' inopérateur revient à la vérification d'égalité normale (c'est-à-dire à l'aide ==), de sorte que la comparaison prend environ le même temps que ==, ce qui rend toute l'opération plus lente en raison de la surcharge de création du tuple , promener ses membres, etc.

Notez également que ce a in (b, )n'est plus rapide que lorsque a is b:

In [48]: a = 1             

In [49]: b = 2

In [50]: %timeit a is a or a == a
10000000 loops, best of 3: 95.1 ns per loop

In [51]: %timeit a in (a, )      
10000000 loops, best of 3: 140 ns per loop

In [52]: %timeit a is b or a == b
10000000 loops, best of 3: 177 ns per loop

In [53]: %timeit a in (b, )      
10000000 loops, best of 3: 169 ns per loop

(pourquoi est a in (b, )plus rapide que a is b or a == b? Je suppose qu'il y aurait moins d'instructions de machine virtuelle - il  a in (b, )n'y a que 3 instructions, où il y a is b or a == baura pas mal d'autres instructions de machine virtuelle)

La réponse de Veedrac - https://stackoverflow.com/a/28889838/71522 - va beaucoup plus de détails sur ce qui se passe précisément au cours de chacune ==et inet vaut bien la lecture.

David Wolever
la source
3
Et la raison pour laquelle cela est susceptible de permettre X in [X,Y,Z]de fonctionner correctement sans X, You d' Zavoir à définir des méthodes d'égalité (ou plutôt, l'égalité par défaut est is, donc cela évite d'avoir à appeler des __eq__objets sans définition utilisateur __eq__et isêtre vrai devrait impliquer une valeur -égalité).
aruisdante
1
L'utilisation de float('nan')est potentiellement trompeuse. C'est une propriété de nance qu'il n'est pas égal à lui-même. Cela peut changer le timing.
dawg
@dawg ah, bon point - l'exemple nan était juste destiné à illustrer les raccourcis indes tests d'adhésion. Je vais changer le nom de la variable pour clarifier.
David Wolever
3
Pour autant que je comprends, dans CPython 3.4.3 tuple.__contains__est mis en œuvre par tuplecontainslequel les appels PyObject_RichCompareBoolet qui revient immédiatement en cas d'identité. unicodea PyUnicode_RichComparesous le capot, qui a le même raccourci pour l'identité.
Cristian Ciupitu
3
Cela signifie que ce "x" is "x"ne sera pas nécessairement le cas True. 'x' in ('x', )sera toujours True, mais il peut ne pas sembler être plus rapide que ==.
David Wolever