Why do lists with the same data have different sizes?

Question

Say I create python lists in two ways.

In the first case I use simple assignment:

my_list = []
print(my_list, '->', my_list.__sizeof__())
my_list = [1]
print(my_list, '->', my_list.__sizeof__())
my_list = [1, 1]
print(my_list, '->', my_list.__sizeof__())

In the second case I use append() method on list:

my_list = []
print(my_list, '->', my_list.__sizeof__())
my_list.append(1)
print(my_list, '->', my_list.__sizeof__())
my_list.append(1)
print(my_list, '->', my_list.__sizeof__())

But I get unexpected (for me) output:

=== WITH ASSIGNMENT ===
([], '->', 40)
([1], '->', 48)
([1, 1], '->', 56)
=== WITH APPEND ===
([], '->', 40)
([1], '->', 72)
([1, 1], '->', 72)

What happens internally with Python memory management? Why do the 'same' lists have different sizes?

Answer 1

When you append to a list, memory is over-allocated to the list for performance reasons so that multiple appends would not require corresponding reallocations of memory for the list which would slow the overall performance in the case of repeated appends.

The CPython source clearly describes this behaviour in a comment:

/* 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.
 */

In the other case, the list is constructed from a literal, and the size of the list reflects the size of the container itself and the references to each contained object.

The exact allocation behaviour may vary with other Python implementations (see list.append implementations for Jython and PyPy) and over-allocation is not guaranteed to exist.