Недавно в одном из проектов встала задача: есть набор множеств (Set), которые надо достаточно эффективно хранить в оперативной памяти. Потому что множеств много, а памяти мало. И с этим надо что-то делать.
Так как язык, на котором всё это написано — C#, то есть нюансы. А именно, что стандартный HashSet<int> на хранение одного числа тратит 16 байт, также влияет филл фактор. Есть более эффективные реализации (когда-нибудь и про них напишу), но с другой стороны, можно же тупо хранить в массивах, по 4 байта на число (требуется хранить инты), что достаточно эффективно. Но можно ли уменьшить ещё?
Сразу скажу, у меня нет ответа, как лучше сделать, возможно его не существует, ибо есть множество факторов, связанных с особенностями распределения конкретных данных. Но есть идеи, которыми я поделюсь: какие варианты экономии памяти существуют. Также рекомендую до прочтения поста подумать самостоятельно, всё-таки это неплохая разминка для ума. Для определённости сформулирую задачу следующим образом:
Есть набор неотрицательных уникальных интов (32 бита). Требуется хранить их эффективно в оперативной памяти, из операций — создание набора и получение всех элементов. Не нужно получать элементы по индексу, добавлять новые или удалять.
В статье будет много букв и цифр и ни одной картинки (кроме упакованного котика на КДПВ).
Я специально не указываю что за проект, что за задача конкретно, т.к. в целом, это неважно. Допустимые решения сильно зависят от данных. Какие-то лучше подходят для одних, какие-то для других, также не забываем про скорость работы. Где-то лучше максимально экономить память, а где-то стоит соблюдать баланс.
Также, не рассматриваю решения вида — тупо хранить на диске и использовать кеш для горячих данных, это отдельная задача.
Просто для понимания количества данных, с которыми я столкнулся: несколько миллионов сетов, в каждом из которых от одного элемента до двух миллионов. В памяти это занимает около 10 ГБ
Итак, у нас есть базовые данные — массив из интов, 4 байта (32 бита) на число. Будем отталкиваться от этого показателя.
Для начала выскажу гениальную мысль: чтобы число занимало в памяти меньше 32 бит, надо хранить его, используя меньшее количество бит. Крутая идея, да? А люди за подобное получают известность и признание. Так что чем я хуже.
Лирическое отступление: несколько лет назад специалисты из РЖД выяснили, что если делать колёса круглыми и одинакового размера, то поезд идёт быстрее и тише.
Разделяем числа по размеру
Для начала простое решение: Числа от 0 до 255 можно хранить с помощью 1 байта на число, до 65536 — двумя, до 16777216 — тремя. Отсюда первое решение:
Создаем 4 массива, в одном храним числа по 1 байту, в другом по 2, в третьем по 3, а что в четвёртом, предлагаю догадаться самостоятельно.
Хлоп, и уже мы экономим. Но зачем оставаться на достигнутом? Давайте будем использовать 32 массива! И хранить числа по 1, 2… бита. Стало ещё экономнее.
С другой стороны, что есть массив? Это указатель на блок памяти (8 байт), длина и для C# ещё память на сам объект массива (20 байт). Итого, каждый массив нам обходится в 32 байта (на самом деле, в C# объект занимает минимум 24 байта с шагом по 8, из которых 20 байт на объект, а 4 — на то что осталось или тупо на выравнивание). Здесь и далее расчёты для 64-х битной системы. Для 32 бит указатели в 2 раза меньше, выравнивание тоже на 4, так что почти всё экономнее в 2 раза.
К чему этот пассаж? К тому, что 32 массива сожрут у нас 1КБ памяти просто на самих себя. Что с этим делать? А всё просто: будем хранить эти 32 массива в одном массиве!
В первом элементе храним длину однобитного массива, потом сам массив, потом длина для двух бит и т.д. В результате, всего 32 байта накладных расходов и эффективное хранение.
Пытливый читатель (всегда нравилась эта фраза) может заметить некоторую проблему: для хранения чисел из одного бита мы вначале потратим 2 бита на длину (0, 1 или 2), а потом 2 бита на сами числа. А ведь можно потратить всего 2 бита: первый бит — есть ли 0, второй — есть ли 1.
Мы только что придумали битовую карту. Можно сильно не париться и хранить числа от 0 до 255 этим методом — есть число — 1, нет — 0. И потратить на это 32 байта (8 бит в байте * 32 = 256). Естественно, с каждым новым значением — эффективность карты начинает падать. Т.е. для хранения всех интов нам нужно 536870912 байт… Как-то многовато. Так что, когда остановиться: на 256-ти, на 16-ти, на 65536-ти — зависит от данных. Пусть будет 256. Мне нравится это число, красивое.
Т.е. первые 256 чисел храним битовой картой, дальше храним длину чисел определённой длины в битах и сами числа.
Но смотрите, что получается: числа от 0 до 511 требуют для хранения 9 бит. В тоже время, мы числа от 0 до 255 — мы уже сохранили. Т.е. в диапазоне 9 бит не может попасться число 12. Только 256 и больше. Так зачем их ранить 9 битами, если можно хранить число от 0 до 255 и потом прибавить в уме недостающее 256. Сэкономили ещё один бит! Естественно каждый следующий диапазон тоже будет экономнее на 1 бит. Мы молодцы!
Что ещё можно сделать? А можно посмотреть на данные. Если они очень плотные (1,2,3,5,6), то можно хранить не сами числа, а те, которых нет (4). Т.е. вместо хранения условных 5 чисел, будем хранить одно. Простое правило: больше половины есть — храним те, которых нет, иначе наоборот. Где хранить? А в длине! Смотрите: чтобы хранить числа длиной в 10 бит, нам надо 11 бит (потому что от 0 до 1024 включительно). Но при этом значений в 11 бит можно засунуть 2048, а используем мы только 1025. Вот и будем хранить: положительная длина — храним числа. Отрицательная — храним то, чего нет. Детальный расчёт предлагаю совершить читателю самому в качестве самостоятельного упражнения (потому что я не уверен, что всё сойдётся, так что сделаю вид, что так и надо).
В результате мы получили: массив, в котором первые 16 байт битовая маска наличия чисел от 0 до 255, дальше — длина с указанием — храним числа или их отсутствие, сами числа, битовая длина для следующего и т.д.
После того, как вы это реализуете, да ещё и без ошибок, думаю, вы отправитесь прямиком в дурку, последующие программисты, пытающиеся понять этот код — отправятся за вами следом. Так что давайте попробуем ещё варианты.
Думаем над порядком
Смотрите. У нас есть массив. Что у него есть, в отличие от множества? А есть у него: порядок элементов. Это дополнительная информация, а мы её ещё никак не заиспользовали. Что же можно с этим сделать?
А можно хранить не сами элементы, а разницу между ними:
1,2,3,4,8 => 1,1,1,1,4
Т.е. первый храним как есть, второй — добавляем значение первого ко второму и т.д. Что нам это даёт? А то, что если мы заранее отсортируем массив, то у нас значения в нём станут в целом меньше, и их можно хранить меньшим количеством бит.
Кроме того, у нас по условию задачи — все элементы разные, т.е. мы от разницы можем ещё вычесть единичку, чтобы сэкономить битики:
1,2,3,4,8 => 1,1,1,1,4 => 1,0,0,0,3
Это несложно, так что почему бы и нет.
Но теперь вылезла проблема. Т.к. мы теперь не можем хранить числа независимо, а только в том же порядке, то способ с массивом и длинами — уже не подходит. Надо придумывать что-то другое, т.к. все числа должны храниться по порядку.
Храним длину числа битах перед самим числом
Неплохой вариант. Число занимает от 1 до 32 бит, т.е. на длину нам надо 5 бит, а потом само число. Можно для удобства отсекать крайние случаи (ну чо мы там наэкономим? копейки!), или наоборот, выделять их особо — например, если длина 0 — то значит число 0, если длина 1 — число — 1, если длина 2 — то следующие 2 бита число 2,3,4,5 (мы уже знаем, что можем сдвигать на то, чего не может быть) и т.д.
А может хранить длину числа в самом числе?
Variable-length quantity
Как бы не мы первые задаёмся этим вопросом, поэтому есть стандартное решение. Используется для хранения строк в UTF-8 и много где ещё. Смысл простой.
Если число от 0 до 127 включительно — храним его 1 байтом (хотя использовали только 7 бит). Если больше, то ставим 8-ой бит в 1 и используем следующий байт аналогичным образом (7 бит, не хватает — флажок и следующий). Т.е. маленькие числа будут храниться одним байтом, чуть больше — двумя, и так до 5.
Вы можете сказать — фуу… мы только что с битами игрались, а тут байты пошли, не круто! Да, не круто, с другой стороны, работать с байтами всё-таки проще чем с битами, чуть меньше экономия, зато выше скорость работы и понятнее код. Но… тратить по биту в байте как-то не очень круто, может есть решения лучше?
Используем значения как флаги
Пропустим все рассуждения и сразу определимся. Будем хранить следующим образом:
- числа от 0 до 253 будут храниться одним байтом. Если больше, то:
- если число от 252 до 252+256=508 ставим значение 252, а в следующем байте число — 252 (да-да, мы уже умеем сдвигать значения)
- если от 252+256 до 252+256+65536, ставим 253 и используем следующие 2 байта для хранения самого числа — ненужную разницу
- если от 252+256+65536 до 252+256+65536+16777216, ставим 254 и 3 байта
- иначе — 255 и 4 байта.
Хорош ли этот способ? Всё относительно. В один байт мы можем запихать значения до 252, в то время как в VLQ только до 127, зато в 2 байта всего 508, а в VLQ уже 16383. Т.е. метод хорош, если у вас числа достаточно плотно расположены, и тут мы будем выигрывать. Но зато метод хорош тем, что его можно подгонять под разные диапазоны. Например, если мы знаем, что большинство чисел от 10000 до 50000, то мы можем хранить их всегда двумя байтами, но если вылезет какое-то большое число, мы напишем 65535 и будем использовать уже 4. Фактически, оптимизируем хранения нужного диапазона ценой неэффективного хранения ненужного.
Заключение
Мы рассмотрели основные способы экономить память (на самом деле, у меня иссякла фантазия, но признаваться в этом не буду). Данные техники можно комбинировать, использовать для других задач, дорабатывать под ситуацию. Какая техника в итоге лучше? Всё зависит от ваших данных. Берите их и пробуйте. Благо не надо реализовывать всё полностью сразу. Можно достаточно просто написать код, который просто оценит длину. А после оценки уже реализовывать то, что вам приглянулось.
Не стоит забывать и про скорость всего этого дела: готовы ли вы тратить много времени на подготовку данных или на получение. Стоит ли затевать борьбу с битами, или ниже байтов опускаться не стоит. Достаточно ли оптимизировать частые ситуации, оставив редкие с неэффективной реализацией. Можно ли в зависимости от данных использовать разные способы хранения (например, до 8 байт тупо хранить в массиве, т.к. побочные расходы сожрут весь выигрыш, а из 1 байта — вообще хранить в псевдомассиве из одного элемента, т.е. в самом числе).
Также пару слов про сжатие: тут оно будет не очень эффективным. Алгоритмам сжатия очень нравятся повторения, а тут их не очень много. Если взять условный Zip, который в состоит из LZ77+Huffman, навряд ли что-то полезное получится с помощью LZ77, но Huffman может попытаться сэкономить байты. Получается, Zip будет бесполезным наполовину. А вот скорость просадит очень и очень сильно.
Ещё совершенно не рассмотрены ситуации, когда мы знаем о том, что у нас множеств много и мы можем хранить их всех вместе, используя различные срезы. Тут я признаюсь — не уверен, что это получится. Сходу я не придумал варианты. Зато понял, что будет сложно. Впрочем, у вас могут быть другие мнения.
Так что делитесь идеями в комментариях, может я пропустил какого-то очевидного слона, который позволит сэкономить ещё больше байт и получить такой результат, что домохозяйки из рекламы моющего средства (которого достаточно одной капли) будут нам всем завидовать!
Автор: force
