Why 'in' is faster than `contains`?

Question

I thought that in is just a manifest of __contains__

In [1]: li = [1, 2, 3, 4, 5]

In [2]: 4 in li
Out[2]: True

In [3]: li.__contains__(4)
Out[3]: True

However in is 2x faster

In [4]: %timeit 4 in li
10000000 loops, best of 3: 103 ns per loop

In [5]: %timeit li.__contains__(4)
The slowest run took 10.06 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 213 ns per loop

Can you explain the differences between the two and why is in faster?

Probably the same reason why `{}` is faster than `dict()`. The method call overhead — Moses Koledoye, Jul 15 '16 at 15:53

score 5 · Answer 1 · answered Jul 15 '16 at 15:56

5

Probably the same reason why {} is faster than dict(). The method call introduces an extra overhead:

>>> from dis import dis
>>> li = [1, 2, 3, 4, 5]
>>> c = lambda: 4 in li
>>> d = lambda: li.__contains__(4)
>>> dis(c)
  1           0 LOAD_CONST               1 (4)
              3 LOAD_GLOBAL              0 (li)
              6 COMPARE_OP               6 (in)
              9 RETURN_VALUE
>>> dis(d)
  1           0 LOAD_GLOBAL              0 (li)
              3 LOAD_ATTR                1 (__contains__)
              6 LOAD_CONST               1 (4)
              9 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             12 RETURN_VALUE

See CALL_FUNCTION in the later case.

answered Jul 15 '16 at 15:56

Moses Koledoye

77,341
8
133
139

2

This doesn't explain why `in` doesn't have the same method call overhead. – user2357112 Jul 15 '16 at 15:59
`in` applies `COMPARE_OP` – Moses Koledoye Jul 15 '16 at 16:00
And you'd expect `COMPARE_OP` to call the `__contains__` method of `li`, incurring method call overhead. – user2357112 Jul 15 '16 at 16:02
I wouldn't expect `__contains__` to be called as an attribute (via dot reference) when using `in` since it's a language construct – Moses Koledoye Jul 15 '16 at 16:07
And it's not, but you should explain how it *is* called. For someone unfamiliar with the CPython internals, it's not clear how else `__contains__` could possibly be invoked. – user2357112 Jul 15 '16 at 16:09
How can I know which function is being called at stage 9? Does `__contains__` calls `in`? – Aguy Jul 15 '16 at 16:10
@Aguy `__contains__` does not call `in`. It already implements the logic to check for list membership. – Moses Koledoye Jul 15 '16 at 16:15
@user2357112 I would suppose there are alternative hooks for calling such methods. I haven't had much experience with CPython internals. Would be great if you could help improve the answer in that regard – Moses Koledoye Jul 15 '16 at 16:17

user2357112 · Accepted Answer · 2016-07-15T19:48:08.300

In the standard implementation of Python, in doesn't quite use __contains__ directly. in actually uses the C-level sq_contains function pointer in the struct representing an object's type. For types with a __contains__ implemented in Python, sq_contains points to a function that looks up and invokes the __contains__ method, but for types with a __contains__ implemented in C, sq_contains points straight to the C implementation of the method.

Since list.__contains__ is implemented in C, 4 in li gets to invoke the C implementation directly, without passing through the overhead of a Python method lookup and a Python function call. li.__contains__(4) has to perform the Python method lookup and Python function call, so it's substantially slower.

If you want to see the code path involved for 4 in li, you can follow the call hierarchy down from COMPARE_OP in the bytecode evaluation loop. You'll see that it uses cmp_outcome:

TARGET(COMPARE_OP)
{
    w = POP();
    v = TOP();
    if (PyInt_CheckExact(w) && PyInt_CheckExact(v)) {
        ...
    }
    else {
      slow_compare:
        x = cmp_outcome(oparg, v, w);
    }

cmp_outcome uses PySequence_Contains:

static PyObject *
cmp_outcome(int op, register PyObject *v, register PyObject *w)
{
    int res = 0;
    switch (op) {
    ...
    case PyCmp_IN:
        res = PySequence_Contains(w, v);
        if (res < 0)
            return NULL;
        break;

PySequence_Contains looks up the sq_contains field of the tp_as_sequence field of the C struct representing the list type:

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

This field stores a function pointer to list_contains, the C function implementing the list containment check. At no point does Python have to perform any dict lookups to find the method, or allocate a method object to represent the method, or build a tuple of arguments to pass to the method.

Your last paragraph is somewhat confusing, do you mean `list.__contains__` doesn't require dict-lookups, etc? You earlier stated that it does (and `meth = li.__contains__; meth(4)` is faster than `li.__contains(4)`). Also you forgot the code formatting in the middle. But I like your answer, very handy background knowledge especially about the control flow. Much better than just disassembling (in my opinion) the code or my attempt at answering. — MSeifert, Jul 15 '16 at 16:46

score 2 · Answer 3 · answered Jul 15 '16 at 16:20

This answer somewhat builds upon the explanation of @MosesKoledoye but without any disassembling of source code.

There are several reasons why the .__contains__ is slower than just using in:

Each time you access a method/function/class/property by using . this introduces a lookup inside the class/instance dictionary. This introduces some overhead.
For custom classes a call to in is translated to .__contains__ (or .__iter__) but this isn't necessarily true for all python builtins. Python lists are implemented in C and so a something in list can be translated to a C-function without needing to call __contains__ or __iter__.
The in list is directly forwarded to C code (COMPARE_OP) which is much faster than accessing a python function and then calling the C code (CALL_FUNCTION).

In general: For python built-ins using literals like in may be faster but this is (in general) not true for custom classes. Most of the data model in python applies to custom classes. list.__contains__ is probably only implemented to fit the data model conventions and not because it is needed or faster.

Why 'in' is faster than `contains`?

3 Answers3

Linked

Why 'in' is faster than `__contains__`?

3 Answers3

Linked

Why 'in' is faster than `contains`?