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

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

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

В слове может быть намного больше слотов, чем элементов. Допустим, у вас есть диктофон с в 3 раза большим количеством слотов, чем элементов. В каждом из этих слотов необходимо место для указателя на ключ и указателя, служащего концом связанного списка. Это в 6 раз больше, чем чисел, плюс все указатели на интересующие вас элементы. Учтите, что каждый из этих указателей занимает 8 байт в вашей системе и что в этой ситуации у вас есть 16384 defaultdicts. Приблизительно, вручную: 16384 вхождения * (8192 элемента / событие) * 7 (указатели / элемент) * 8 (байты / указатель) = 7 ГБ . Это было до того, как я добрался до фактических чисел , которые вы храните (каждый уникальный номер из которых сам является dict Python), внешнего dict, этого массива numpy или того, что Python отслеживает для попробуйте оптимизировать некоторые.

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

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

Mike Graham дает хорошее объяснение того, почему словари используют больше памяти, но я решил объяснить, почему ваша таблица dict of 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

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

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

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

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

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

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

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

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

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-битной сборке.

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