Are tuples more efficient than lists in Python?

by

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.

More Related Contents:

  1. Why can tuples contain mutable items?
  2. Tuple or list when using ‘in’ in an ‘if’ clause?
  3. Why is tuple faster than list in Python?
  4. how to unpack a tuple in this form (‘abc’, [20, 20])? [closed]
  5. Why is “1000000000000000 in range(1000000000000001)” so fast in Python 3?
  6. Fastest way to check if a value exists in a list
  7. Get difference between two lists
  8. Sort a list of tuples by 2nd item (integer value) [duplicate]
  9. How to convert comma-delimited string to list in Python?
  10. List vs tuple, when to use each? [duplicate]
  11. Convert tuple to list and back
  12. Unpacking a list / tuple of pairs into two lists / tuples
  13. What is the time complexity of popping elements from list in Python?
  14. Accessing a value in a tuple that is in a list
  15. How to convert a list to a list of tuples?
  16. Transform “list of tuples” into a flat list or a matrix
  17. Python: get a dict from a list based on something inside the dict
  18. Why is variable1 += variable2 much faster than variable1 = variable1 + variable2?
  19. How to convert nested list of lists into a list of tuples in python 3.3?
  20. Convert a columns of string to list in pandas
  21. Why can’t I use a list as a dict key in python? Exactly what can and cannot be used, and why?
  22. Is there a way to circumvent Python list.append() becoming progressively slower in a loop as the list grows?
  23. sum each value in a list of tuples
  24. Python: iterating over list vs over dict items efficiency
  25. First items in inner list efficiently as possible [duplicate]
  26. Improving performance of very large dictionary in Python
  27. Why does creating a list from a list make it larger?
  28. python – get list of tuples first index?
  29. In what case would I use a tuple as a dictionary key? [closed]
  30. deque.popleft() and list.pop(0). Is there performance difference?

Leave a Comment