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, храня указатель на внешний массив с указателями.