Redesigning Python's named tuples

Deficiencies in the startup time for Python, along with the collections.namedtuple() data structure being identified as part of the problem, led Guido van Rossum to decree that named tuples should be optimized. That immediately set off a mini-storm of thoughts about the data structure and how it might be redesigned in the original python-dev thread, but Van Rossum directed participants over to python-ideas, where a number of alternatives were discussed. They ranged from straightforward tweaks to address the most pressing performance problems to elevating named tuples to be a new top-level data structure—joining regular tuples, lists, sets, dictionaries, and so on.

A named tuple simply adds field names for the entries in a tuple so that they can be accessed by index or name. For example:

    >>> from collections import namedtuple
    >>> Point = namedtuple('Point', ['x', 'y'])
    >>> p = Point(1,2)
    >>> p.y
    2
    >>> p[1]
    2

To some extent, the current named tuple implementation has been a victim of its own success. It is now routinely used in the standard library and in other popular modules such that its performance has substantially contributed to Python's slow startup time. The existing implementation creates a _source attribute with pure Python code to create a class, which is then passed to exec() to build it. That attribute is then available for use in programs or to directly create the named tuple class by incorporating the source code. The pull request currently under consideration effectively routes around most of the use of exec(), though it is still used to add the __new__() function to create new instances of the named tuple class.

After Van Rossum's decree, Raymond Hettinger reopened the bug with an explicit set of goals. His plan was to extend the patch set from the pull request so that it was fully compatible with the existing implementation and to measure the impact of it, including for alternative Python implementations (e.g. PyPy, Jython). But patch author Jelle Zijlstra wondered if it made sense to investigate a C-based implementation of named tuples created by Joe Jevnik.

Benchmarks were posted. Jevnik summarized his findings about the C version as follows: "type creation is much faster; instance creation and named attribute access are a bit faster". Zijlstra's benchmarks of his own version showed a 4x speedup for creating the class (versus the existing CPython implementation) and roughly the same performance as CPython for instantiation and attribute access. Those numbers caused Zijlstra to suggest using the C version:

There are some downsides to a C implementation, however. As the original bug reporter, Naoki Inada, pointed out, maintenance is more difficult for C-based code. In addition, only CPython can directly benefit from it; alternative language implementations will either need to reimplement it or forgo it.

Class creation performance is only one area that could use improvement, however. Victor Stinner noted that accessing tuple values by name was nearly twice as slow when compared to the somewhat similar, internal PyStructSequence that is used for things like sys.version_info. It would be desirable for any named tuple upgrade to find a way to reduce the access-by-name overhead, several said. In fact, Giampaolo Rodolà pointed out that the asyncio module could serve nearly twice as many requests per second if the performance of PyStructSequence could be attained.

But Rodolà would like to go even further than that. He proposed new syntax that would allow the creation of named tuples on the fly. He gave two possibilities for how that might look:

    >>> ntuple(x=1, y=0)
    (x=1, y=0)

    >>> (x=1, y=0)
    (x=1, y=0)

Either way (or both) would be implemented in C for speed. It would allow named tuples to be created without having to describe them up front, as is done now. But it would also remove one of the principles that guided the design of named tuples, as Tim Peters said:

Post-decree, Ethan Furman moved the discussion to python-ideas and suggested looking at his aenum module as a possible source for a new named tuple. But that implementation uses metaclasses, which could lead to problems when subclassing as Van Rossum pointed out.

Jim Jewett's suggestion to make named tuples simply be a view into a dictionary ran aground on too many incompatibilities with the existing implementation. Python dictionaries are now ordered by default and are optimized for speed, so they might be a reasonable choice, Jewett said. As Greg Ewing and others noted, though, that would lose many of the attributes that are valued for named tuples, including low memory overhead, access by index, and being a subclass of tuple.

Rodolà revived his proposal for named tuples without a declaration, but there are a number of problems with that approach. One of the main stumbling blocks is the type of these on-the-fly named tuples—effectively each one created would have its own type even if it had the same names in the same order. That is wasteful of memory, as is having each instance know about the mapping from indexes to names; the current implementation puts that in the class, which can be reused. There might be ways to cache these on-the-fly named tuple types to avoid some of the wasted memory, however. Those problems and concern that it would be abused led Van Rossum to declare the "bare" syntax (e.g. (x=1, y=0)) proposal as dead.

But the discussion of ntuple(x=1, y=0) continued for a while before seemingly running aground as well. Part of the problem is that it combines two things in an unexpected way: declaring the order of the fields in the named tuple and using keyword arguments where order should not matter. For the x and y case, it is fairly clear, but named tuples could be used for types where the order is not so clear. As Steven D'Aprano put it:

He elaborated on the ordering problem by giving an example of a named tuple that stored the attributes of elementary particles (e.g. flavor, spin, charge) which do not have an automatic ordering. That argument seemed to resonate with several thread participants.

So it would seem that a major overhaul of the interface for building named tuples is not likely anytime soon—if ever. The C reimplementation has some major performance benefits (and could presumably pick up the PyStructSequence performance for access by name), but it would seem that the first step will be to merge Zijlstra's Python-based implementation. That will allow for a fallback with better performance for alternative implementations, while still leaving open the possibility of replacing it with an even faster C version later.