Почему дикты defaultdict (int) используют так много памяти? (и другие простые вопросы производительности Python)

Question

Я понимаю, что запрос несуществующего ключа в defaultdict так же, как я, добавит элементы в defaultdict. Вот почему было бы справедливо сравнить мой второй фрагмент кода с моим первым с точки зрения производительности.

import numpy as num
from collections import defaultdict

topKeys = range(16384)
keys = range(8192)

table = dict((k,defaultdict(int)) for k in topKeys)

dat = num.zeros((16384,8192), dtype="int32")

print "looping begins"
#how much memory should this use? I think it shouldn't use more that a few
#times the memory required to hold (16384*8192) int32's (512 mb), but
#it uses 11 GB!
for k in topKeys:
    for j in keys:
        dat[k,j] = table[k][j]

print "done"

Что здесь происходит? Кроме того, этот похожий скрипт требует выполнения эонов по сравнению с первым, а также использует абсурдное количество памяти.

topKeys = range(16384)
keys = range(8192)
table = [(j,0) for k in topKeys for j in keys]

Я полагаю, что Python-интенты могут быть 64-битными, что может объяснить некоторые из них, но действительно ли эти относительно естественные и простые конструкции приводят к таким огромным накладным расходам? Я предполагаю, что эти сценарии показывают, что они делают, поэтому мой вопрос: что именно вызывает высокое использование памяти в первом сценарии и длительное время выполнения и высокое использование памяти второго сценария, и есть ли способ избежать этих затрат?

Edit: Python 2.6.4 на 64-битной машине.

Редактировать 2: я понимаю, почему, в первом приближении, моя таблица должна занимать 3 ГБ 16384 *8192* (12 + 12) байтов и 6 ГБ с коэффициентом загрузки по умолчанию, который заставляет его резервировать вдвое больше места. Тогда неэффективность в распределении памяти съедает другой фактор 2.

Итак, вот мои оставшиеся вопросы: Есть ли способ для меня, чтобы сказать, как использовать 32-битные целые числа как-то?

И почему мой второй фрагмент кода выполняется навсегда по сравнению с первым? Первый занимает около минуты, а второй я убил через 80 минут.

Answer 1

Python-интты внутренне представлены как C longs (на самом деле это немного сложнее), но это не совсем корень вашей проблемы.

Самые большие накладные расходы - это использование диктов. (defaultdicts и dicts примерно одинаковы в этом описании). Дикты реализуются с использованием хеш-таблиц, что приятно, поскольку позволяет быстро найти общие ключи. (Это не так необходимо, когда вам нужно только искать последовательные цифровые клавиши, поскольку их можно легко вывести на экран.)

У диктанта может быть гораздо больше слотов, чем у него предметов. Допустим, у вас есть диктат с 3-кратным количеством слотов как предметов. Каждому из этих слотов требуется место для указателя на клавишу и указателя, служащего концом связанного списка. Это в 6 раз больше очков, чем чисел, плюс все указатели на элементы, которые вас интересуют. Учтите, что каждый из этих указателей имеет 8 байт в вашей системе, и что в этой ситуации у вас 16384 по умолчанию. Как грубо, хриплый взгляд на это, 16384 occurrences * (8192 items/occurance) * 7 (pointers/item) * 8 (bytes/pointer) = 7 GB. Это до того, как я добрался до фактических чисел , которые вы храните (каждое уникальное число которых является самим диктатом Python), внешним диктовкой, этим массивом или материалом, который Python отслеживает для попытаться оптимизировать некоторые.

Ваши накладные расходы звучат немного выше, чем я подозреваю, и мне было бы интересно узнать, было ли это 11GB для всего процесса или вы рассчитали его только для таблицы. В любом случае, я ожидаю, что размер этой структуры данных dict-of-defaultdicts будет на несколько порядков больше, чем представление массива.

Что касается "есть ли способ избежать этих затрат?" ответ: «используйте numpy для хранения больших непрерывных числовых массивов фиксированного размера, а не dicts!» Вы должны быть более конкретными и конкретными в отношении того, почему вы нашли такую ​​структуру необходимой для лучшего совета о том, что является лучшим решением.

Answer 2

Хорошо, посмотрите, что на самом деле делает ваш код:

topKeys = range(16384)
table = dict((k,defaultdict(int)) for k in topKeys)

Это создает диктат, содержащий 16384 defaultdict(int). У dict есть определенное количество служебных данных: сам объект dict находится между 60 и 120 байтами (в зависимости от размера указателей и ssize_t в вашей сборке.) Это просто сам объект; если значение dict не превышает пару элементов, данные представляют собой отдельный блок памяти размером от 12 до 24 байт и всегда заполнены между 1/2 и 2 / 3rds. И defaultdicts на 4 - 8 байтов больше, потому что у них есть эта дополнительная вещь для хранения. И интервалы по 12 байт каждая, и хотя они используются повторно, где это возможно, этот фрагмент не будет использовать большинство из них. Таким образом, реально, в 32-битной сборке этот фрагмент займет 60 + (16384*12) * 1.8 (fill factor) байт для table dict, 16384 * 64 байт для defaultdicts, которые он хранит в качестве значений, и 16384 * 12 байт для целых чисел. Так что это чуть более полутора мегабайт без сохранения чего-либо в ваших defaultdicts . И это в 32-битной сборке; 64-битная сборка будет в два раза больше.

Затем вы создаете простой массив, который на самом деле довольно консервативен с памятью:

dat = num.zeros((16384,8192), dtype="int32")

Это будет иметь некоторые накладные расходы для самого массива, обычные накладные расходы на объекты Python плюс размеры и тип массива и тому подобное, но это будет не более 100 байт, и только для одного массива. Тем не менее, он хранит 16384*8192 int32 в ваших 512Mb.

И тогда у вас есть довольно необычный способ заполнения этого массива:

for k in topKeys:
    for j in keys:
        dat[k,j] = table[k][j]

Сами два цикла не занимают много памяти, и они используют ее каждую итерацию. Однако table[k][j] создает новое целое число Python для каждого запрашиваемого вами значения и сохраняет его в defaultdict . Созданное целое число всегда равно 0, и так получилось, что оно всегда используется повторно, но при сохранении ссылки на него по-прежнему используется место в defaultdict: вышеупомянутые 12 байтов на запись, умноженные на коэффициент заполнения (между 1,66 и 2. ) Таким образом, вы получаете почти 3 ГБ реальных данных и 6 ГБ в 64-разрядной сборке.

Кроме того, из-за того, что вы добавляете данные, по умолчанию вы должны продолжать расти, что означает, что они должны продолжать перераспределение. Из-за внешнего интерфейса malloc Python (obmalloc) и того, как он выделяет меньшие объекты в своих собственных блоках, а также из-за того, как память процесса работает в большинстве операционных систем, это означает, что ваш процесс будет выделять больше и не сможет его освободить; на самом деле он не будет использовать все 11 ГБ, и Python будет повторно использовать доступную память между большими блоками для defaultdicts, но общее отображаемое адресное пространство будет 11 ГБ.

Answer 3

Майк Грэм дает хорошее объяснение того, почему словари используют больше памяти, но я подумал, что объясню, почему ваша таблица dict defaultdicts начинает занимать так много памяти.

Способ настройки defaultdict (DD) прямо сейчас, всякий раз, когда вы извлекаете элемент, которого нет в DD, вы получаете значение по умолчанию для DD (0 для вашего случая), но также и для DD сейчас хранит ключ, которого раньше не было в DD, со значением по умолчанию 0. Мне лично это не нравится, но так оно и есть. Однако это означает, что для каждой итерации внутреннего цикла выделяется новая память, поэтому она занимает вечность. Если вы измените строки

for k in topKeys:
    for j in keys:
        dat[k,j] = table[k][j]

до

for k in topKeys:
    for j in keys:
        if j in table[k]:
            dat[k,j] = table[k][j]
        else:
            dat[k,j] = 0

тогда значения по умолчанию не назначаются клавишам в DD, и поэтому для меня память остается около 540 МБ, что в основном является памятью, выделенной для dat. DD приемлемы для разреженных матриц, хотя, вероятно, вам следует просто использовать разреженные матрицы в Scipy, если вы этого хотите.