Представление в памяти

Перемещая элементы в структурах данных общего назначения, мы копируем адрес. Т.е. всегда существует одна копия объекта, независимо от того, сколько раз он появляется в tuple/list/dict

Int

x = 123

refcount
address of type -> type <int>
123

String

s = 'Hello!'

refcount
address of type -> type <str>
length
hash
flags
address = 0
'Hello!'

Tuple

t = (1, 2.0, 'Hello!')

refcount
address of type -> type <tuple>
length
address -> int <1>
address -> float <2.0>
address -> str <'Hello!'>

Для последних трех адресов эта техника называется indirection, т.е. хранятся просто адреса, а не объекты.

Вот как tuple(10, 20) описан на C:

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;

Заметьте, что tuple включает в себя непосредственно два указателя на данные.

Dict

За каждым dict - массив, в котором ключи хранятся на индексах согласно их hash value. Каждый слот должен хранить ключ и хэш.

Словарь обычно растёт увеличиваясь в 2 или в 4 раза. Расширение происходит, когда он заполнен на 2/3.

List

my_list = [1, 2, 3]

Чтобы расти, списку необходимо переместиться, но объекты в Python не могут менять адрес. Спасает двойной indirection.

refcount
address of type -> type <list>
length = 3
array address -> указывает на список из 4 элементов, один из которых пустой, о нём ниже

array len = 4

Почему есть пустой элемент во "внутреннем" списке? Если бы не резервировалось для него место, то для каждого append() надо было заноыо выделять место. Это дорого - каждый адрес эл-та копируется в новое место.

Релокация на каждом следующем append() суммируется:
- Чтобы добавить 2 эл-т в список нужно скопировать адрес 1 эл-та
- Чтобы добавить 3 эл-т в список нужно скопировать адрес 1 и 2 эл-тов
И т.д.
append() на полный список запрашивает доп слоты для элементов. Списки в среднем используют 94% своих слотов, потребляя на 6% больше места, чем они используют.

Вот описание на C:

   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;

Заметьте, что список включает в себя указатель ещё один уровень indirect, храня указатель на внешний массив с указателями.