Немонотонное потребление памяти в словарях Python2

Question

Может ли кто-нибудь объяснить использование немонотонной памяти словаря в CPython 2.7?

>>> import sys 
>>> sys.getsizeof({}) 
280 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5}) 
280 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6}) 
1048 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7}) 
1048 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'e 
ight': 8}) 
664 
>>> sys.getsizeof({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'e 
ight': 8, 'nine': 9}) 
664 

Python3 Разумно здесь, он печатает размер {'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7} как 480.

Я пробовал это на Ubuntu 15.10 и OS X 10.11.

Answer 1

TLDR: 6-и 7-литровые литералы диктата плохо фиксируют хэш-таблицу, а затем увеличивают размер в четыре раза по размеру.

---

Когда CPython 2,7 оценивает ДИКТ буквальным, прежде чем он начнет заполнение записей, опкод он использует для создания Dict является BUILD_MAP. Она принимает один аргумент, намек на сколько записей ДИКТ будет содержать, which it uses to presize the dict:

TARGET(BUILD_MAP) 
    { 
     x = _PyDict_NewPresized((Py_ssize_t)oparg); 
     PUSH(x); 
     if (x != NULL) DISPATCH(); 
     break; 
    } 

Это предназначено, чтобы свести к минимуму количество раз ДИКТ изменяется в процессе создания, но так как они не учитывают коэффициент нагрузки, он не совсем устраняет изменения размеров.

Как указывается source code comments, _PyDict_NewPresized предназначен для «создания нового словаря с предварительным размером для хранения предполагаемого количества элементов». Точный размер хеш-таблицы в созданном dict зависит от ряда деталей реализации, таких как минимальный размер (#define PyDict_MINSIZE 8) и требование о том, чтобы размер был равен 2 (чтобы избежать необходимости разделения в реализации).

Для битовых литералов до 7 записей _PyDict_NewPresized инициализирует хеш-таблицу с 8 входами; для 8 записей он инициализирует хеш-таблицу с 16 входами, поскольку используемая в ней процедура изменения размера всегда увеличивает емкость, большую, чем аргумент.

---

Dicts resize on insertion when they become at least 2/3 full. Для ДИКТ литералов 6- и 7-входа, ДИКТ начинается с 8 записей, таким образом, изменение размера происходит на 6-й вставки. ДИКТ достаточно мал, что изменение размера четверок размер хеш-таблицы:

return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used); 

mp->ma_used является количество используемых записей в хэш-таблице, 6 в этой точке. 6 меньше 50000, поэтому мы вызываем dictresize(mp, 4 * 6), который изменяет размер хеш-таблицы на 32 записи, наименьшая мощность 2 больше 24.

Напротив, для 8-тичного литерала dict хэш-таблица начиналась с 16 записей. Дикт не становится 2/3 полным во время создания, поэтому исходная хеш-таблица с 16 входами сохраняется в создании dict, а полученный dict меньше, чем с 6- и 7-входными литералами dict.

---

Python 3 использует different growth policy, среди прочих изменений реализации ДИКТ, поэтому вы видели различные результаты в Python 3.

Answer 2

Ну я попробовал немного, и давайте посмотрим:

dct = {'four': 3, 'three': 2, 'two': 1, 'one': 0} 
print(sys.getsizeof(dct))        # = 272 
print(sys.getsizeof(dict(dct)))      # = 272 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 272 

dct = {'four': 3, 'three': 2, 'five': 4, 'two': 1, 'one': 0} 
print(sys.getsizeof(dct))        # = 272 
print(sys.getsizeof(dict(dct)))      # = 272 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 272 

dct = {'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'one': 0} 
print(sys.getsizeof(dct))        # = 1040 
print(sys.getsizeof(dict(dct)))      # = 656 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

dct = {'seven': 6, 'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'one': 0} 
print(sys.getsizeof(dct))        # = 1040 
print(sys.getsizeof(dict(dct)))      # = 656 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

dct = {'seven': 6, 'six': 5, 'three': 2, 'two': 1, 'four': 3, 'five': 4, 'eight': 7, 'one': 0} 
print(sys.getsizeof(dct))        # = 656 
print(sys.getsizeof(dict(dct)))      # = 1040 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

Я не уверен, какая оптимизация происходит здесь, но я предполагаю, что это потому, что эти структуры используют различные «передовые методы». Я имею в виду, когда выделять сколько памяти для хеш-таблицы. Например, если у вас есть одиннадцать или более элементов, вы получите еще странное несоответствие:

dct = {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10:10, 11:11} 
print(sys.getsizeof(dct))        # = 1808 
print(sys.getsizeof(dict(dct)))      # = 1040 
print(sys.getsizeof({k: v for k, v in dct.items()})) # = 1040 

Так что это, вероятно, просто какой-то потребление памяти «оптимизация» при создании словарей по-разному, почему это не монотонный останец для литерального синтаксиса при использовании 6 или 7 элементов: я не знаю. Может быть, некоторая оптимизация памяти пошла не так, и это ошибка, которая выделяет слишком много памяти? Я еще не прочитал исходный код.