Сколько памяти занимает 1 миллион целых чисел?
Меня часто донимали размышление о том, насколько эффективно Python использует память по сравнению с другими языками программирования. Например, сколько памяти нужно, чтобы работать с 1 миллионом целых чисел? А с тем же количеством строк произвольной длины?
Как оказалось, в Python есть возможность получить необходимую информацию прямо из интерактивной консоли, не обращаясь к исходному коду на C (хотя, для верности, мы туда все таки заглянем).
Удовлетворив любопытство, мы залезем внутрь типов данных и узнаем, на что именно расходуется память.
Все примеры были сделаны в CPython версии 2.7.4 на 32 битной машине. В конце приведена таблица для потребности в памяти на 64 битной машине.
Необходимые инструменты
sys.getsizeof и метод __sizeof__()
Первый инструмент, который нам потребуется находится в стандартной библиотеки sys. Цитируем официальную документацию:
sys.getsizeof(объект[, значение_по_умолчанию])
Возвращает размер объекта в байтах.
Если указано значение по умолчанию, то оно вернется, если объект не предоставляет способа получить размер. В противном случае возникнет исключение TypeError.
Getsizeof() вызывает метод объекта __sizeof__ и добавляет размер дополнительной информации, которая хранится для сборщика мусора, если он используется.
Алгоритм работы getsizeof(), переписанной на Python, мог бы выглядеть следующем образом:
Py_TPFLAGS_HAVE_GC = 1 << 14 # константа. в двоичным виде равна 0b100000000000000
def sys_getsizeof(obj, default = None)
if obj.hasattr('__sizeof__'):
size = obj.__sizeof__()
elif default is not None:
return default
else:
raise TypeError('Объект не имеет атрибута __sizeof__')
# Если у типа объекта установлен флаг HAVE_GC
if type(obj).__flags__ & Py_TPFLAGS_HAVE_GC:
size = size + размер PyGC_Head
return size
Где PyGC_Head — элемент двойного связанного списка, который используется сборщиком мусора для обнаружения кольцевых ссылок. В исходном коде он представлен следующей структурой:
typedef union _gc_head {
struct {
union _gc_head *gc_next;
union _gc_head *gc_sourcev;
Py_ssize_t gc_refs;
} gc;
long double dummy;
} PyGC_Head;
Размер PyGC_Head будет равен 12 байт на 32 битной и 24 байта на 64 битной машине.
Попробуем вызвать getsizeof() в консоли и посмотрим, что получится:
>>> import sys
>>> GC_FLAG = 1 << 14
>>> sys.getsizeof(1)
12
>>> (1).__sizeof__()
12
>>> bool(type(1).__flags__ & GC_FLAG)
False
>>> sys.getsizeof(1.1)
16
>>> (1.1).__sizeof__()
16
>>> bool(type(1.1).__flags__ & GC_FLAG)
False
>>> sys.getsizeof('')
21
>>> ''.__sizeof__()
21
>>> bool(type('').__flags__ & GC_FLAG)
False
>>> sys.getsizeof('hello')
26
>>> sys.getsizeof(tuple())
24
>>> tuple().__sizeof__()
12
>>> bool(type(tuple()).__flags__ & GC_FLAG)
True
>>> sys.getsizeof(tuple((1, 2, 3)))
36
За исключением магии с проверкой флагов, все очень просто.
Как видно из примера, int и float занимают 12 и 16 байт соответственно. Str занимает 21 байт и еще по одному байту на каждый символ содержимого. Пустой кортеж занимает 12 байт, и дополнительно 4 байта на каждый элемент. Для простых типов данных (которые не содержат ссылок на другие объекты, и соответственно, не отслеживаются сборщиком мусора), значение sys.getsizeof равно значению, возвращаемого методом __sizeof__().
id() и ctypes.string_at
Теперь выясним, на что именно расходуется память.
Для этого нужно нам нужны две вещи: во-первых, узнать, где именно хранится объект, а во-вторых, получить прямой доступ на чтение из памяти. Несмотря на то, что Python тщательно оберегает нас от прямого обращения к памяти, это сделать все таки возможно. При этом нужно быть осторожным, так как это может привести к ошибке сегментирования.
Встроенная функция id() возвращает адрес памяти, где храниться начала объекта (сам объект является C структурой)
>>> obj = 1
>>> id(obj)
158020320
Чтобы считать данные по адресу памяти нужно воспользоваться функцией string_at из модуля ctypes. Ее официальное описание не очень подробное:
ctypes.string_at(адрес[, длина])
Это функция возвращает строку, с началом в ячейки памяти «адрес». Если «длина» не указана, то считается что строка zero-terminated,
Теперь попробуем считать данные по адресу, который вернул нам id():
>>> import ctypes
>>> obj = 1
>>> sys.getsizeof(obj)
12
>>> ctypes.string_at(id(obj), 12)
'u\x01\x00\x00 \xf2&\x08\x01\x00\x00\x003\x01\x00\x00 \xf2&\x08\x00\x00\x00\x001\x00\x00\x00'
Вид шестнадцатеричного кода не очень впечатляет, но мы близки к истине.
Модель Struct
Для того чтобы представить вывод в значения, удобные для восприятия, воспользуемся еще одним модулем. Здесь нам поможет функция unpack() из модуля struct.
struct
Этот модуль производит преобразование между значениями Python и структурами на C, представленными в виде строк.
struct.unpack(формат, строка)
Разбирает строку в соответствие с данным форматов. Всегда возвращает кортеж, даже если строка содержит только один элемент. Строка должна содержать в точности то количество информации, как описано форматом.
Форматы данных, которые нам потребуются.
| символ | Значение C | Значение Python | Длина на 32битной машине |
| c | char | Строка из одного символа | 1 |
| i | int | int | 4 |
| l | long | int | 4 |
| L | unsigned long | int | 4 |
| d | double | float | 8 |
Теперь собираем все вместе и посмотрим на внутреннее устройство некоторых типов данных.
Int
>>> obj = 1
>>> sys.getsizeof(obj), obj.__sizeof__()
(12, 12)
>>> struct.unpack('LLl', ctypes.string_at(id(obj), 12))
(373, 136770080, 1)
О формате значений несложно догадаться.
Первое число (373) — количество указателей, на объект.
>>> obj2 = obj
>>> struct.unpack('LLl', ctypes.string_at(id(obj), 12))
(374, 136770080, 1)
Как видно, число увеличилось на единицу, после того как мы создали еще одну ссылку на объект.
Второе число (136770080) — указатель (id) на тип объекта:
>>> type(obj)
<type 'int'>
>>> id(type(obj) )
136770080
Третье число (1) — непосредственно содержимое объекта.
>>> obj = 1234567
>>> struct.unpack('LLl', ctypes.string_at(id(obj), 12))
(1, 136770080, 1234567)
Наши догадки можно подтвердить, заглянув в исходный код CPython
typedef struct {
PyObject_HEAD
long ob_ival;
} PyIntObject;
Здесь PyObject_HEAD — макрос, общий для всех встроенных объектов, а ob_ival — значение типа long. Макрос PyObject_HEAD добавляет счетчик количества указателей на объект и указатель на родительский тип объекта — как раз то, что мы и видели.
Float
Число с плавающей запятой очень похоже на int, но представлено в памяти C значением типа double.
typedef struct {
PyObject_HEAD
double ob_fval;
} PyFloatObject;
В этом легко убедиться:
>>> obj = 1.1
>>> sys.getsizeof(obj), obj.__sizeof__()
(16, 16)
>>> struct.unpack('LLd', ctypes.string_at(id(obj), 16)
(1, 136763968, 1.1)
Строка (Str)
Строка представлена в виде массива символов, оканчивающимся нулевым байтом. Также в структуре строки отдельного сохраняется ее длина, хэш от ее содержания и флаг, определяющий, хранится ли она во внутреннем кэше interned.
typedef struct {
PyObject_VAR_HEAD
long ob_shash; # хэш от строки
int ob_sstate; # находится ли в кэше?
char ob_sval[1]; # содержимое строки + нулевой байт
} PyStringObject;
Макрос PyObject_VAR_HEAD включает в себя PyObject_HEAD и добавляет значение long ob_ival, в котором хранится длина строки.
>>> obj = 'hello world'
>>> sys.getsizeof(obj), obj.__sizeof__()
(32, 32)
>>> struct.unpack('LLLli' + 'c' * (len(obj) + 1), ctypes.string_at(id(obj), 4*5 + len(obj) + 1))
(1, 136790112, 11, -1500746465, 0, 'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '\x00')
Четвертое значение соответствует хэшу от строки, в чем нетрудно убедиться.
>>> hash(obj)
-1500746465
Как видно, значение sstate равно 0, так что строка сейчас не кэшируется. Попробуем ее добавить в кэш:
>>> intern(obj)
'hello world'
>>> struct.unpack('LLLli' + 'c' * (len(obj) + 1), ctypes.string_at(id(obj), 4*5 + len(obj) + 1))
(2, 136790112, 11, -1500746465, 1, 'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '\x00') Кортеж (Tuple)
Кортеж представлен в виде массива из указателей. Так как его использование может приводить к возникновению кольцевых ссылок, он отслеживается сборщиком мусора, на что расходуется дополнительная память (об этом нам напоминает вызов sys.getsizeof())
Структура tuple похоже на строку, только в ней отсутствуют специальные поля, кроме длины.
typedef struct {
PyObject_VAR_HEAD
PyObject *ob_item[1];
} PyTupleObject;
>>> obj = (1,2,3)
>>> sys.getsizeof(obj), obj.__sizeof__()
(36, 24)
>>> struct.unpack('LLL'+'L'*len(obj), ctypes.string_at(id(obj), 12+4*len(obj)))
(1, 136532800, 3, 146763112, 146763100, 146763088)
>>> for i in obj: print i, id(i)
1 146763112
2 146763100
3 146763088
Как видим из примера, последние три элементы кортежа являются указателями на его содержимое.
Остальные базовые типы данных (unicode, list, dict, set, frozenset) можно исследовать аналогичным образом.
Что в итоге?
| Тип | Имя в CPython | формат | Формат, для вложенных объектов | Длина на 32bit | Длина на 64bit | Память для GC* |
| Int | PyIntObject | LLl | 12 | 24 | ||
| float | PyFloatObject | LLd | 16 | 24 | ||
| str | PyStringObject | LLLli+c*(длина+1) | 21+длина | 37+длина | ||
| unicode | PyUnicodeObject | LLLLlL | L*(длина+1) | 28+4*длина | 52+4*длина | |
| tuple | PyTupleObject | LLL+L*длина | 12+4*длина | 24+8*длина | Есть | |
| list | PyListObject | L*5 | L*длину | 20+4*длина | 40+8*длина | Есть |
| Set/ frozenset |
PySetObject | L*7+(lL)*8+lL | LL* длина | (<=5 элементов) 100 (>5 элементов) 100+8*длина |
(<=5 элементов) 200 (>5 элементов) 200+16*длина |
Есть |
| dict | PyDictObject | L*7+(lLL)*8 | lLL*длина | (<=5 элементов) 124 (>5 элементов) 124+12*длина |
(<=5 элементов) 248 (>5 элементов) 248+24*длина |
Есть |
Мы видим, что простые типы данных в Python в два-три раза больше своих прототипов на C. Разница обусловлена необходимостью хранить количество ссылок на объект и указатель на его тип (содержимое макроса PyObject_HEAD). Частично это компенсируется внутренним кэшированием, который позволяет повторно использовать ранее созданные объекты (это возможно только для неизменяемых типов).
Для строк и кортежей разница не такая значительная — добавляется некоторая постоянная величина.
А списки, словари и множества, как правило, занимают больше на 1/3, чем необходимо. Это обусловлено реализацией алгоритма добавления новых элементов, который приносит в жертву память ради экономии времени процессора.
Итак, отвечаем на вопрос в начале статьи: чтобы сохранить 1 миллион целых чисел нам потребуется 11.4 мегабайт (12*10^6 байт) на сами числа и дополнительно 3.8 мегабайт (12 + 4 + 4*10^6 байт) на кортеж, которых будет хранить на них ссылки.
UPD: Опечатки.
UPD: В подзаголовке «1 миллион целых чисел», вместо «1 миллион простых чисел»
