How do you investigate python's implementation of built-in methods?

Question

I'm currently going through a basic compsci course. We use Python's in a lot. I'm curious how it's implemented, what the code that powers in looks like.

I can think of how my implementation of such a thing would work, but something I've learned after turning in a couple homework assignments is that my ways of doing things are usually pretty terrible and inefficient.. So I want to start investigating 'good' code.

Answer 1

The thing about builtin functions and types and operators and so on is that they are not implemented in Python. Rather, they're implemented in C, which is a much more painful and verbose programming language that won't always translate well to Python (usually because things are easier some other way in Python.)

With that said, you can investigate all of Python's implementation online, via their public source repository.

The implementation for in is scattered -- there's one implementation per type, plus a more general implementation that calls the type-specific implementation (more on that later). For example, for lists, we'd look for the implementation of lists. In the Python source tree, the source for all builtin objects is in the Objects directory. In that directory you'll find listobject.c , which contains the implementation for the list object and all its methods.

On the repository at the time of answering, if you look at line 393 you'll find the implementation of the in operator (also known as the __contains__ method, which explains the name of the function). It's fairly straightforward, just loops through all the elements of the list until either the element is found, or there's no more elements, and returns the result of the search. :)

If it helps, in Python the idiomatic way to write this would be:

def __contains__(self, obj):
    for item in self:
        if item == obj:
            return True

    return False

---

I said earlier that there was a more general implementation. That can be seen in the implementation of PySequence_Contains in abstract.c. It tries to call the type-specific version, and if that fails, resorts to regular iteration. That loop there is what a regular Python for loop looks like when you write it in C (using the Python C-API).

Answer 2

From the Data Model section of the Python Language Reference:

The membership test operators (in and not in) are normally implemented as an iteration through a sequence. However, container objects can supply the following special method with a more efficient implementation, which also does not require the object be a sequence.

object.__contains__(self, item)

Called to implement membership test operators. Should return true if item is in self, false otherwise. For mapping objects, this should consider the keys of the mapping rather than the values or the key-item pairs.

For objects that don’t define __contains__(), the membership test first tries iteration via __iter__(), then the old sequence iteration protocol via __getitem__(), see this section in the language reference.

So, by default Python iterates over a sequence to implement the in operator. If an object defines the __contains__ method, Python uses it instead of iterating. So what happens in the __contains__ method? To know exactly, you would have to browse the source. But I can tell you that Python's lists implement __contains__ using iteration. Python dictionaries and sets are implemented as hash tables, and therefore support faster membership testing.