Why is tuple faster than list in Python?

Question

I've just read in "Dive into Python" that "tuples are faster than lists".

Tuple is immutable, and list is mutable, but I don't quite understand why tuple is faster.

Anyone did a performance test on this?

Fairman

Please edit your question and add a link to the context of where you're getting this claim from. I'll even be kind and give it to you so you don't have to go searching for it again: diveintopython3.org/native-datatypes.html#tuples – Nectarous

I read the PDF version, so I don't have the link. Thanks for that :), I'll add it into the question – Fairman

On another note, you are right to question claims such as these. The Python interpreter changes in every release; performance claims should always be empirically validated on your own platform before following them. wiki.python.org/moin/PythonSpeed/PerformanceTips Alec Thomas's answer is a shining example of how to do this quickly for yourself in the future. See also the timeit documentation: docs.python.org/library/timeit.html – Nectarous

@gotgenes: reading them right now, thanks :) – Fairman

Answer 1

The reported "speed of construction" ratio only holds for constant tuples (ones whose items are expressed by literals). Observe carefully (and repeat on your machine -- you just need to type the commands at a shell/command window!)...:

$ python3.1 -mtimeit -s'x,y,z=1,2,3' '[x,y,z]'
1000000 loops, best of 3: 0.379 usec per loop
$ python3.1 -mtimeit '[1,2,3]'
1000000 loops, best of 3: 0.413 usec per loop

$ python3.1 -mtimeit -s'x,y,z=1,2,3' '(x,y,z)'
10000000 loops, best of 3: 0.174 usec per loop
$ python3.1 -mtimeit '(1,2,3)'
10000000 loops, best of 3: 0.0602 usec per loop

$ python2.6 -mtimeit -s'x,y,z=1,2,3' '[x,y,z]'
1000000 loops, best of 3: 0.352 usec per loop
$ python2.6 -mtimeit '[1,2,3]'
1000000 loops, best of 3: 0.358 usec per loop

$ python2.6 -mtimeit -s'x,y,z=1,2,3' '(x,y,z)'
10000000 loops, best of 3: 0.157 usec per loop
$ python2.6 -mtimeit '(1,2,3)'
10000000 loops, best of 3: 0.0527 usec per loop

I didn't do the measurements on 3.0 because of course I don't have it around -- it's totally obsolete and there is absolutely no reason to keep it around, since 3.1 is superior to it in every way (Python 2.7, if you can upgrade to it, measures as being almost 20% faster than 2.6 in each task -- and 2.6, as you see, is faster than 3.1 -- so, if you care seriously about performance, Python 2.7 is really the only release you should be going for!).

Anyway, the key point here is that, in each Python release, building a list out of constant literals is about the same speed, or slightly slower, than building it out of values referenced by variables; but tuples behave very differently -- building a tuple out of constant literals is typically three times as fast as building it out of values referenced by variables! You may wonder how this can be, right?-)

Answer: a tuple made out of constant literals can easily be identified by the Python compiler as being one, immutable constant literal itself: so it's essentially built just once, when the compiler turns the source into bytecodes, and stashed away in the "constants table" of the relevant function or module. When those bytecodes execute, they just need to recover the pre-built constant tuple -- hey presto!-)

This easy optimization cannot be applied to lists, because a list is a mutable object, so it's crucial that, if the same expression such as [1, 2, 3] executes twice (in a loop -- the timeit module makes the loop on your behalf;-), a fresh new list object is constructed anew each time -- and that construction (like the construction of a tuple when the compiler cannot trivially identify it as a compile-time constant and immutable object) does take a little while.

That being said, tuple construction (when both constructions actually have to occur) still is about twice as fast as list construction -- and that discrepancy can be explained by the tuple's sheer simplicity, which other answers have mentioned repeatedly. But, that simplicity does not account for a speedup of six times or more, as you observe if you only compare the construction of lists and tuples with simple constant literals as their items!_)

Dealer

great answer, but quite hard to read the shell snippet. please consider rewriting or adding a summary table. – Leatherback

Answer 2

Executive Summary

Tuples tend to perform better than lists in almost every category:

1) Tuples can be constant folded.

2) Tuples can be reused instead of copied.

3) Tuples are compact and don't over-allocate.

4) Tuples directly reference their elements.

Tuples can be constant folded

Tuples of constants can be precomputed by Python's peephole optimizer or AST-optimizer. Lists, on the other hand, get built-up from scratch:

    >>> from dis import dis

    >>> dis(compile("(10, 'abc')", '', 'eval'))
      1           0 LOAD_CONST               2 ((10, 'abc'))
                  3 RETURN_VALUE   

    >>> dis(compile("[10, 'abc']", '', 'eval'))
      1           0 LOAD_CONST               0 (10)
                  3 LOAD_CONST               1 ('abc')
                  6 BUILD_LIST               2
                  9 RETURN_VALUE 

Tuples do not need to be copied

Running tuple(some_tuple) returns immediately itself. Since tuples are immutable, they do not have to be copied:

>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True

In contrast, list(some_list) requires all the data to be copied to a new list:

>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False

Tuples do not over-allocate

Since a tuple's size is fixed, it can be stored more compactly than lists which need to over-allocate to make append() operations efficient.

This gives tuples a nice space advantage:

>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200

Here is the comment from Objects/listobject.c that explains what lists are doing:

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 * Note: new_allocated won't overflow because the largest possible value
 *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
 */

Tuples refer directly to their elements

References to objects are incorporated directly in a tuple object. In contrast, lists have an extra layer of indirection to an external array of pointers.

This gives tuples a small speed advantage for indexed lookups and unpacking:

$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'a[1]'
10000000 loops, best of 3: 0.0304 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'a[1]'
10000000 loops, best of 3: 0.0309 usec per loop

$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'x, y, z = a'
10000000 loops, best of 3: 0.0249 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'x, y, z = a'
10000000 loops, best of 3: 0.0251 usec per loop

Here is how the tuple (10, 20) is stored:

    typedef struct {
        Py_ssize_t ob_refcnt;
        struct _typeobject *ob_type;
        Py_ssize_t ob_size;
        PyObject *ob_item[2];     /* store a pointer to 10 and a pointer to 20 */
    } PyTupleObject;

Here is how the list [10, 20] is stored:

    PyObject arr[2];              /* store a pointer to 10 and a pointer to 20 */

    typedef struct {
        Py_ssize_t ob_refcnt;
        struct _typeobject *ob_type;
        Py_ssize_t ob_size;
        PyObject **ob_item = arr; /* store a pointer to the two-pointer array */
        Py_ssize_t allocated;
    } PyListObject;

Note that the tuple object incorporates the two data pointers directly while the list object has an additional layer of indirection to an external array holding the two data pointers.

Tidewater

Answer 3

Alex gave a great answer, but I'm going to try to expand on a few things I think worth mentioning. Any performance differences are generally small and implementation specific: so don't bet the farm on them.

In CPython, tuples are stored in a single block of memory, so creating a new tuple involves at worst a single call to allocate memory. Lists are allocated in two blocks: the fixed one with all the Python object information and a variable sized block for the data. That's part of the reason why creating a tuple is faster, but it probably also explains the slight difference in indexing speed as there is one fewer pointer to follow.

There are also optimisations in CPython to reduce memory allocations: de-allocated list objects are saved on a free list so they can be reused, but allocating a non-empty list still requires a memory allocation for the data. Tuples are saved on 20 free lists for different sized tuples so allocating a small tuple will often not require any memory allocation calls at all.

Optimisations like this are helpful in practice, but they may also make it risky to depend too much on the results of 'timeit' and of course are completely different if you move to something like IronPython where memory allocation works quite differently.

Ita

"one fewer pointer to follow" -- not so; while there are differences in memory allocation, the functions to get a particular item are (after stripping out error checking) identical: PyObject * PyBLAH_GetItem(PyObject *op, Py_ssize_t i) {return ((PyBLAHObject *)op) -> ob_item[i];} – Tillman

Yes so. In the data structure for a tuple ob_item is an array at the end of the structure. In a list ob_item is a pointer to an array. The C code to access an element of either array is identical but in the case of a list there is an extra memory read to fetch the value of the pointer. – Ita

You are correct. tupleobject.h has PyObject * ob_item[1]; listobject.h has PyObject ** ob_item; – Tillman

Answer 4

With the power of the timeit module, you can often resolve performance related questions yourself:

$ python2.6 -mtimeit -s 'a = tuple(range(10000))' 'for i in a: pass'
10000 loops, best of 3: 189 usec per loop
$ python2.6 -mtimeit -s 'a = list(range(10000))' 'for i in a: pass' 
10000 loops, best of 3: 191 usec per loop

This shows that tuple is negligibly faster than list for iteration. I get similar results for indexing, but for construction, tuple destroys list:

$ python2.6 -mtimeit '(1, 2, 3, 4)'   
10000000 loops, best of 3: 0.0266 usec per loop
$ python2.6 -mtimeit '[1, 2, 3, 4]'
10000000 loops, best of 3: 0.163 usec per loop

So if speed of iteration or indexing are the only factors, there's effectively no difference, but for construction, tuples win.

Sepulchre

can you please rewrite your code in Python 3.0, so I can test it? :) – Fairman

@Vimvq1987 Did you try that code with Python 3.0 before asking for a re-write? – Nectarous

Almost nobody uses Python 3. Install 2.x, don't expect people to jump hoops for you. – Kara

@Glenn The code runs perfectly fine in Python 3. @Vimvq1987 would have known that had he tried it before asking. – Nectarous

ahhh, I forgot to import timeit, sorry, I'm new with this – Fairman

The only case I see where tuples are significantly faster is constructing them, and that's largely the point--tuples are used a lot for returning multiple values from a function, so they're optimized for that case. In general, the choice to use tuples isn't based on performance. (In quick tests, tuples are actually about 20% slower than lists for indexing; I havn't bothered to look into why.) – Kara

>>> import timeit >>> -mtimeit -s 'a = tuple(range(10000))' 'for i in a: pass' SyntaxError: invalid syntax can anyone please tell my what's wrong here? – Fairman

Run the command Alec gave you on the command line (DOS if you're on Windows). – Condescension

@Glenn Good point. Updated with timings for small tuple/list construction. – Sepulchre

It's also worth noting that you save (at least on my machine) .0001 usec by leaving off the parentheses =P. – Hallah

reading comments from 6 years ago "almost nobody uses Python 3" ha – Delineator

Answer 5

One area where a list is notably faster is construction from a generator, and in particular, list comprehensions are much faster than the closest tuple equivalent, tuple() with a generator argument:

$ python --version
Python 3.6.0rc2
$ python -m timeit 'tuple(x * 2 for x in range(10))'
1000000 loops, best of 3: 1.34 usec per loop
$ python -m timeit 'list(x * 2 for x in range(10))'
1000000 loops, best of 3: 1.41 usec per loop
$ python -m timeit '[x * 2 for x in range(10)]'
1000000 loops, best of 3: 0.864 usec per loop

Note in particular that tuple(generator) seems to be a tiny bit faster than list(generator), but [elem for elem in generator] is much faster than both of them.

Selinaselinda

Answer 6

In python, we have two types of objects. 1. Mutable, 2. Immutable.
In python, lists come under mutable objects and tuples comes under immutable objects.

• Tuples are stored in a single block of memory. Tuples are immutable so, It doesn't require extra space to store new objects.

• Lists are allocated in two blocks: the fixed one with all the Python object information and a variable-sized block for the data.

• It is the reason creating a tuple is faster than List.

• It also explains the slight difference in indexing speed is faster than lists, because in tuples for indexing it follows fewer pointers.

Advantages of using tuples:

• Tuples are that they use less memory where lists use more memory.

• We can use tuples in a dictionary as a key but it's not possible with lists.

• We can access elements with an index in both tuples and lists.

Disadvantages of tuples:

• We cannot add an element to tuple but we can add an element to list.

• We can't sort a tuple but in a list, we can sort by calling list.sort() method.

• We can't remove an element in tuple but in a list, we can remove an element.

• We can't replace an element in tuple but you can in a list.

---

Source

Roam

if a tuple contains a list like s = ('a', [1,2,3], 'b'), then if we append element to list, How is space going to be allocated ? @M.Rostami – Sardanapalus

Good answer, but it's important to note that although tuples do not have the sort method, they can in fact be sorted using the built-in sorted function: sorted((4, 2, 1)) will return (1, 2, 4) – Trig

Answer 7

Essentially because tuple's immutability means that the interpreter can use a leaner, faster data structure for it, compared to list.

Tarshatarshish

Answer 8

Tuples are identified by python compiler as one immutable constant so compiler created only one entry in hash table and never changed

Lists are mutable objects.So compiler update the entry when we update the list so it is little bit slower compare to tuple

Topotype