Mengapa 'x' di ('x',) lebih cepat daripada 'x' == 'x'?

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

Juga berfungsi untuk tupel dengan banyak elemen, kedua versi ini tampaknya tumbuh secara linear:

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

Berdasarkan ini, saya pikir saya harus benar - benar mulai menggunakan di inmana - mana ==!

Markus Meskanen
sumber
167
Untuk jaga-jaga: Tolong jangan mulai menggunakan di inmana - mana ==. Ini adalah pengoptimalan prematur yang merusak keterbacaan.
Kolonel Thirty Two
4
coba x ="!foo" x in ("!foo",)danx == "!foo"
Padraic Cunningham
2
A dalam B = Nilai, C == D Nilai dan Jenis perbandingan
dsgdfg
6
Pendekatan yang lebih masuk akal daripada menggunakan inalih-alih ==adalah beralih ke C.
Mad Physicist
1
Jika Anda menulis dengan Python dan Anda memilih satu konstruksi di atas yang lain untuk kecepatan, Anda melakukannya dengan salah.
Veky

Jawaban:

257

Seperti yang saya sebutkan kepada David Wolever, ada lebih dari ini yang bisa dilihat; kedua metode dikirim ke is; Anda dapat membuktikan ini dengan melakukan

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

Yang pertama hanya bisa sangat cepat karena memeriksa dengan identitas.

Untuk mengetahui mengapa yang satu lebih lama dari yang lain, mari kita telusuri eksekusi.

Mereka berdua mulai ceval.c, COMPARE_OPsejak itu adalah bytecode yang terlibat

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();
}

Ini muncul nilai dari tumpukan (secara teknis hanya muncul satu)

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

dan menjalankan pembandingan:

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

cmp_outcome Apakah ini:

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

Di sinilah jalur dibagi. The PyCmp_INcabang tidak

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);
}

Perhatikan bahwa tuple didefinisikan sebagai

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

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

Jadi rantingnya

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

akan diambil dan *sqm->sq_contains, yang merupakan fungsinya (objobjproc)tuplecontains, akan diambil.

Ini tidak

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

... Tunggu, bukankah itu PyObject_RichCompareBoolyang diambil cabang lain? Tidak, itu tadi PyObject_RichCompare.

Jalur kode itu pendek sehingga kemungkinan hanya sampai pada kecepatan keduanya. Mari kita bandingkan.

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

    ...
}

Jalur kode di PyObject_RichCompareBoolhampir segera berakhir. Untuk PyObject_RichCompareitu

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

The Py_EnterRecursiveCall/ Py_LeaveRecursiveCallcombo tidak diambil di jalur sebelumnya, tetapi ini adalah makro yang relatif cepat yang akan pendek-sirkuit setelah incrementing dan decrementing beberapa GLOBALS.

do_richcompare tidak:

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;
        ...
    }
    ...
}

Ini melakukan beberapa pemeriksaan cepat untuk memanggil v->ob_type->tp_richcompareyang mana

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

yang mana

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

Yaitu, pintasan ini di left == right... tetapi hanya setelah dilakukan

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

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

Semua dalam semua jalur kemudian terlihat seperti ini (secara manual secara inuratif, membuka gulungan dan memangkas cabang yang dikenal)

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()                      #

vs.

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()                      #

Sekarang, PyUnicode_Checkdan PyUnicode_READYcukup murah karena mereka hanya memeriksa beberapa bidang, tetapi harus jelas bahwa yang paling atas adalah jalur kode yang lebih kecil, ia memiliki lebih sedikit pemanggilan fungsi, hanya satu pergantian pernyataan dan hanya sedikit lebih tipis.

TL; DR:

Keduanya mengirim ke if (left_pointer == right_pointer); perbedaannya hanyalah seberapa banyak pekerjaan yang mereka lakukan untuk sampai ke sana. inhanya kurang.

Veedrac
sumber
18
Ini jawaban yang luar biasa. Apa hubungan Anda dengan proyek python?
kdbanman
9
@kdbanman Tidak ada, sungguh, meskipun saya telah berhasil memaksa saya sedikit;).
Veedrac
21
@varepsilon Aww, tapi tidak ada yang mau repot-repot membaca pos yang sebenarnya! Inti dari pertanyaan ini bukanlah jawabannya tetapi proses yang digunakan untuk mendapatkan jawabannya - semoga tidak akan ada satu ton orang yang menggunakan hack ini dalam produksi!
Veedrac
181

Ada tiga faktor yang berperan di sini yang, jika digabungkan, menghasilkan perilaku mengejutkan ini.

Pertama: inoperator mengambil jalan pintas dan memeriksa identitas ( x is y) sebelum memeriksa kesetaraan ( x == y):

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

Kedua: karena string Python diinternir, keduanya "x"dalam "x" in ("x", )akan identik:

>>> "x" is "x"
True

(peringatan besar: ini adalah perilaku khusus implementasi! isJangan pernah digunakan untuk membandingkan string karena terkadang akan memberikan jawaban yang mengejutkan; misalnya "x" * 100 is "x" * 100 ==> False)

Ketiga: sebagaimana dirinci dalam jawaban fantastis Veedrac , tuple.__contains__( kirax in (y, ) - kira setara dengan (y, ).__contains__(x)) sampai pada titik melakukan pemeriksaan identitas lebih cepat daripada str.__eq__(sekali lagi, kirax == y - kira setara dengan x.__eq__(y)).

Anda dapat melihat bukti untuk ini karena x in (y, )secara signifikan lebih lambat dari logis setara, 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

The x in (y, )kasus lambat karena, setelah isperbandingan gagal, inoperator yang jatuh kembali ke memeriksa kesetaraan normal (yaitu, menggunakan ==), sehingga perbandingan mengambil tentang jumlah waktu yang sama seperti ==, rendering seluruh operasi lebih lambat karena overhead menciptakan tupel , berjalan anggotanya, dll.

Perhatikan juga bahwa a in (b, )itu hanya lebih cepat ketika 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

(Mengapa a in (b, )lebih cepat daripada a is b or a == b? Dugaan saya akan lebih sedikit instruksi mesin virtual -  a in (b, )hanya ~ 3 instruksi, di mana a is b or a == bakan ada lebih banyak instruksi VM)

Jawaban Veedrac - https://stackoverflow.com/a/28889838/71522 - menjelaskan lebih detail tentang apa yang terjadi pada masing-masing ==dan indan layak dibaca.

David Wolever
sumber
3
Dan alasan dilakukannya hal ini memungkinkan X in [X,Y,Z]untuk bekerja dengan benar tanpa X,, Yatau Zharus mendefinisikan metode kesetaraan (atau lebih tepatnya, kesetaraan standar is, sehingga menghemat harus memanggil __eq__objek tanpa ditentukan pengguna __eq__dan ismenjadi benar harus menyiratkan nilai -persamaan).
aruisdante
1
Penggunaan float('nan')potensi menyesatkan. Ini adalah properti nanyang tidak sama dengan dirinya sendiri. Itu dapat mengubah waktunya.
dawg
@ Dawg ah, poin bagus - contoh nan itu hanya dimaksudkan untuk menggambarkan jalan pintas yang indiambil pada tes keanggotaan. Saya akan mengubah nama variabel untuk memperjelas.
David Wolever
3
Sejauh yang saya mengerti, dalam CPython 3.4.3 tuple.__contains__diimplementasikan oleh tuplecontainsyang memanggil PyObject_RichCompareBooldan yang segera kembali dalam kasus identitas. unicodeada di PyUnicode_RichComparebawah tenda, yang memiliki pintasan yang sama untuk identitas.
Cristian Ciupitu
3
Itu berarti "x" is "x"belum tentu demikian True. 'x' in ('x', )akan selalu ada True, tetapi tampaknya tidak lebih cepat dari ==.
David Wolever