Храним числа экономно

    Недавно в одном из проектов встала задача: есть набор множеств (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 до 252 будут храниться одним байтом. Если больше, то:
    • если число от 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 будет бесполезным наполовину. А вот скорость просадит очень и очень сильно.

    Ещё совершенно не рассмотрены ситуации, когда мы знаем о том, что у нас множеств много и мы можем хранить их всех вместе, используя различные срезы. Тут я признаюсь — не уверен, что это получится. Сходу я не придумал варианты. Зато понял, что будет сложно. Впрочем, у вас могут быть другие мнения.

    Так что делитесь идеями в комментариях, может я пропустил какого-то очевидного слона, который позволит сэкономить ещё больше байт и получить такой результат, что домохозяйки из рекламы моющего средства (которого достаточно одной капли) будут нам всем завидовать!
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 60

      +1

      Вам нужно двигаться в другом направлении не дробить на byte, а упаковывать по несколько малых значений в один int используя какие-то биты для мето-данных.

        0
        Можно пример? И что делать, если нет малых значений?
          0

          Разбиваем пространство значений на блоки по 256.
          Если в один блок попало больше восьми чисел, то выгоднее представить блок как битовую карту, занимающую 32 байта, вместо 4*количество чисел.

            0
            А если меньше, то плохо выходит. + начало блока надо кодировать. В общем, при плотных данных это хороший вариант. Я подобный вариант описал в начале статьи, только ограничил всё числами от 0 до 255.
            0

            Есть varint, в protocol buffers используется чтобы плотно числа паковать.

              +1
              Я в статье его упоминал.
          0
          Еще варианты
          — RLE кодирование
          — список диапазонов, но тут на сами данные нужно смотреть, подойдет ли.
          ЗЫ Да и вообще для такого, сначала статистику нужно собрать, а что там будет храниться.
            0
            RLE на мой взгляд больше для битмапов подойдёт, или для очень специфичных данных, для которых можно и другие варианты подобрать. Что-то пока не могу придумать, чем RLE тут помогло.
            Про статистику я как раз писал — что всё зависит от данных, поэтому и расписал разные варианты.
              0
              RLE поможет если представить числа в виде последовательной цепочки бит. возможно придумать какую-то сортировку для увеличения эффективности. ну и далее, если каждое число представляет собой 64 бита, то к примеру у мелких цыфр RLE закодирует множественные нули вначале числа. или так же неплохо зайдет для чисел побольше, у которых внезапно всередине образовалось 10 (или 20) нулей или единиц подряд. не каждое число так упаковать получится правда.
            0

            В случае когда известно распределение чисел и мы храним данные в байтах, наиболее эффективной кодировкой будет следующий подход:


            • Создаём биективное отображение, которое отображает самое частое число в 0, следующее по частоте в 1, и т.д. (можно отображать не отдельные числа, а диапазоны, например, 128 наиболее частых чисел получают индексы 0-127, и т.д.)
            • Кодируем полученные индексы используя вариант VLQ использующийся в git-е.

            Это если мы заботимся только о плотности хранения. Если же нам важна ещё скорость упаковки/распаковки, то тут уже начинается поиск компромиссов. Например, Group Varint Encoding (вариант VLQ) менее плотен по сравнению с git VLQ, но за счёт меньшего количества ветвлений он быстрее на современных процессорах.

              0
              Для известного распределения — надо по идее использовать для информации все множества (в одном каждое число уникально и ничего мы не добьёмся). По идее тут Хаффман может подойти. Можете дать ссылку на VLQ в git? потому что попытки узнать что это, привели к коду, реализующему VLQ, опубликованному на гитхабе :)
              Group varint — вариант для скорости, надо тут тестировать на C#, возможно ли получить преимущество, или невозможность делать некоторые вещи — сожрёт возможную выгоду.
              +6

              Попробуйте посмотреть, например, в сторону Roaring Bitmaps, или аналогичного. Есть готовые реализации и биндинги ко всем основным языкам, проблема дурки решена тем, что вам этот код поддерживать не нужно. Довольно универсально и шустро работает. Естесственно, зная свои данные, можно изобрести более эффективный велосипедик именно для этих данных, как справедливо отмечает автор статьи.

                +1
                Выглядит как решение соседа по палате :) Надо будет попробовать. К сожалению, реализация на C# через нативный враппер. Он может быть быстрее, а может быть проблемным из-за маршаллинга. Надо посмотреть на память и скорость, может его стоит использовать в качестве основной реализации сета, а не хранилища, которое будет в него преобразовано.
                  +1
                  Совершенно верно — «сосед по палате» ибо решение там именно из тех же исходных целей что у вас в задаче. Но соседей этих уже много было (как и методов так и людей которые эти методики прорабатывали) и Roaring Bitmaps это довольно глубоко проработанное решение. Так что в качестве стандартной алтернативы велосипеду — вполне годное решение.

                  Но если есть специфика в данных то всегда можно из этой специфики что-то еще вытянуть для пользы компресии. Хотя бы сократить размерность чисел (кстати тоже довольно стандартная задача).
                    0
                    Да, я почитал про них. Пока есть ощущение, что решение для больших объёмов данных, но с возможностью хорошо проводить на них математику множеств. Надо будет посмотреть нюансы в качестве идей.
                –2
                может ассемблер?
                  0

                  Он то тут причем? Речь идёт об упаковке больших данных в оперативной памяти. На ассемблере такую же проблему пришлось бы решать.

                  0
                  Помнится на вики была статья про альтернативу хэшмапам — емнип Джулию, с дико сложным внутренним устройством. Но на большинстве тестов она показывала результаты не лучше хэшмапа.
                    0
                    Нашёл только язык программирования с таким названием. :(
                      +1
                      Judy array

                      Judy arrays are designed to minimize the number of expensive cache-line fills from RAM, and so the algorithm contains much complex logic to avoid cache misses as often as possible
                      Judy arrays are extremely complicated. The smallest implementations are thousands of lines of code.[5] In addition, Judy arrays are optimized for machines with 64 byte cache lines, making them essentially unportable without a significant rewrite.

                      hash table performance is strictly superior to Judy for under 10,000 items. Beyond that, hash table performance slows (as mentioned before, presumably due to secondary cacheing effects). Judy on sequential data maintains the same performance regardless of size, and is superior beyond 20,000 entries (on this machine, and tuning the hash table might change this crossover point). However, the hash table is strictly superior on all the random data presented here, generally by a factor of 2.
                        0
                        Как я понимаю — тут всё-таки перфоманс главное, а не размер памяти. Но спасибо за информацию, записал.
                          0
                          Мой мессендж был скорее — не надо усложнять, большинство усложнений себя не оправдывают. Скорее всего и у вашей задачи есть относительно простое решение, если найдете, будет интересно услышать.
                    +1
                    Давайте я поделюсь идеей. Точнее, идей у меня оригинальных, к сожалению, нет. Зато есть отправная точка.
                    Эта тема довольно хорошо изучена и начать можно, например, с https://arxiv.org/abs/1401.6399.
                    Или прямо с кода для C#:
                    https://github.com/Genbox/CSharpFastPFOR
                      0
                      Решение выглядит похожим на Group varint (может оно и есть). Надо будет глянуть. Спасибо.
                      0
                      может таки на диск свопнуть?)000)

                      А ещё можно множества в формулами кодировать или их смещение. Ну или хранить в double после запятой
                        +3
                        Пожалуй это лучшая КДПВ, которая полностью отражает суть заголовка
                          0

                          Если числа в последовательности уникальные и не повторяются, и последовательность в диапазоне от 0 до UINT_MAX. Создадим массив от 0 до UINT_MAX типа Boolean. Обходим всю входящую последовательность. Устанавливаем True элементам массива с тем индексами, значения элементов из последовательности которых получаем. Например, число в последовательности равно 265, значит, элементу массива с индексом 265 ставим True, следующее число в последовательности равно 621, значит элементу массива с индексом 621 ставим True, и так далее. Когда мы пройдём всю последовательность, то у нас в массиве будут отмечены элементы, индексы которых были в последовательности.


                          Затем мы можем обходить массив и смотреть. Элемент с индексом 0 равен True — значит число 0 было в последовательности. Элемент с индексом 1 равен True — значит число 1 было в последовательности. И так далее.


                          В этом случае нам понадобится UINT_MAX × SizeOf(Boolean) = 4 294 967 296 × 1 байт = 4 294 967 296 байт памяти. Четыре гигабайта — это меньше, чем 10 гигабайт из вступительной части статьи, но пока ещё много.


                          Если вместо массива Boolean использовать массив из бит, то достаточно выделить памяти 4 294 967 296 байт / 8 = 536 870 912 байт, это уже 500 мегабайт и возможно, что вполне достаточно. Только нужно будет организовать установку и сбрасывание нужного бита в такой битовой карте.

                            0
                            В условиях несколько миллионов сетов. Если каждый занимает 500 Мб…
                              0
                              500Мб на один сет? Это вы неплохо сэкономили. :) Умножьте теперь на их количество.
                              +1
                              Алгоритмам сжатия очень нравятся повторения, а тут их не очень много.

                              Если хранить отсортированный массив разность между отсортированными числами 1,2,3,4,8 => 1,1,1,1,4 => 1,0,0,0,3, то число повторений вырастет. Возможно, значительно (зависит от данных, да-да), что позволит "заархивировать" данные с существенным выигрышем по памяти.

                                0
                                Плавучку упустили, эффективно упаковывает 7 десятичных цифр с знаком и степенью в 4 байта. Причём поддерживается аппаратно на всех процессорах и многих 32-битных микроконтроллерах.

                                И при создании способов упаковки не надо забывать про накладные расходы по упаковке-распаковке. Сэкономите гигабайт памяти, но программа ваши 10 ГБ будет обрабатывать в десятки раз дольше… Можно, конечно, порекомендовать пользователям купить новый компьютер, но программист тоже должен уметь соблюдать баланс.
                                  0
                                  У плавучки на 32 бита точность 7 значащих цифр. У инта — почти 10. Т.е. мы тысячу разных значений сольём в одно. Эффективно, да. Но как-то потеря данных — не то решение, которое хотелось бы сделать.
                                  +2

                                  Советую ознакомиться с работами Daniel Lemire, Leonid Boytsov, Nathan Kurz и т.д. по данной теме.
                                  Соответственно, недостает сравнения с https://www.roaringbitmap.org/ и https://github.com/lemire/FastPFor.


                                  Без этого плюсануть статью совесть не позволяет.

                                    0
                                    Их уже упомянули в комментариях. Давайте сформулирую свою статью так: я написал идеи, а вот конкретные реализации примерно основаны на этих идеях, только оптимизированы под CPU или определённые объёмы данных. Возможно, если будет время досконально разобраться в них, то напишу другую статью именно с объяснениями, зачем эти алгоритмы и что они дают. Но это достаточно большая работа, так что не обещаю.
                                      +1

                                      Daniel Lemire с коллегами занимался этой темой (Integer Compression) более 6 лет. Собрал, наработал и опробовал массу идей, опубликовал около десятка работ и довел до ума несколько реализаций. А в https://github.com/lemire/FastPFor/blob/master/README.md пожалуй лучший набор ссылок по теме, как на научные работы (т.е. идеи с глубокой проработкой и выкладками), так и на реализации (с оптимизацией и т.д.).


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

                                        0
                                        Я с вами не соглашусь. Для того, чтобы понимать оптимальные реализации, надо понимать в целом какие варианты есть, и что конкретная реализация оптимизирует какой-то конкретный фактор (скорость, память, использование аппаратных возможностей). Если тупо читать реализации — то всё будет казаться магией, которую сделали, какие-то абстрактные «умные люди». А люди решали свою проблему, возможно отсекли кучу неудачных вариантов. Но они могли быть неудачными для них, а не для вас.
                                        А потом другие люди начинают по этим статьям делать аналогичные реализации на других языках. Но для них это магия, и получается такой код (пример из C# реализации Roaring Bitmap):
                                        var groupbyHb = values.Distinct().OrderBy(t => t).GroupBy(Util.HighBits).OrderBy(t => t.Key).ToList();


                                        При этом, если я буду реализовывать свою задачу (да, я пока не сделал её), я, естественно проанализирую все варианты, и выберу известный и стабильный, если он не особо хуже велосипеда. А если хуже? Использовать его только потому что автор какой-то известный, это я считаю совершенно неправильно.
                                          +1

                                          Пардон, ну так вы для начала просто прочитайте публикации Daniel Lemire по ссылкам.
                                          Причем если Дэниеля внятно спросить что-то beyond RTFM (тем более по-французски), то он очень хорошо отвечает.

                                            +1
                                            Давайте ещё раз. Я не сомневаюсь в способностях Даниэля. Но он решает свои конкретные задачи. И реализуют его работы другие люди, которые могут написать фуфло. Пример я привёл. Доверять ли конкретной реализации?
                                            Использовать ли алгоритм, только потому что его написал какой-то известный Дядька?
                                            Возьмём Roaring Bitmap — структура, предназначена для эффективной манипуляции со множествами. У меня постановка — хранение. Разные задачи. Будет ли эта структура волшебной и хранить эффективнее? Сомневаюсь.

                                            Мы можем продолжать дискуссию, но я могу взять реализацию на Roaring Bitmap на C#, и первый попавшийся велосипед и сравнить на каких-то данных. Если Roaring Bitmap окажется хуже, вы признаете, что другие решения имеют право на жизнь, или скажете, что я всё неправильно понял, и надо всё равно использовать существующие решения? :) Т.е. стоит мне тратить время на сравнение, или вас не переубедить?
                                              +2

                                              Да, давайте еще раз:


                                              • Есть ряд научных работ (разных ученых/исследователей) по теме сжатия целочисленных последовательностей, в которых собрано и проанализировано немало различных идей/подходов.
                                              • Есть FastPFOR (включая https://github.com/Genbox/CSharpFastPFOR), streamvbyte, TurboPFor и немало других реализаций под разные задачи/требования, где использованы результаты этих научных работ.
                                              • Кроме этого есть и упомянутые Roaring Bitmap (в том числе на C#, на Java и даже на JS).

                                              Соответственно, замечательно что вы пытаетесь самостоятельно разобраться и придумать что-то новое. Однако, без ознакомления с наработанным опытом из первого пункта (совершенно вне зависимости от остальных) результат вашей работы (включая статью) рискует быть излишне дилетантским и наивным.

                                                0
                                                Я вас понял. Если у меня нет учёной степени, то иду я нафиг.
                                                  +2

                                                  Нет, совсем не так.
                                                  Вне зависимости от ученой степени ваша работа может представлять интерес (не быть дилетантской и наивной), если хотя-бы одно из двух:


                                                  1. Вы со знанием дела теоретически показываете что предложили новый подход или улучшили уже известный.
                                                  2. Вы практически (бенчмарком) показываете ценность вашего подхода и/или идеи. Например, можно померятся силами с TurboPFor (там в README достаточно таблиц с результатам различных реализаций).

                                                  А пока вы просто не понимаете как смешно выглядите, уж извините за прямоту.

                                                    +1
                                                    Ну да, сдаюсь. Я не буду переписывать TurboPFor с плюсов на C#, чтобы проводить бенчмарки. Может вы согласитесь на Roaring Bitmaps или CSharpFastPFOR? Я выставлю против них наивный и дилетантский VLQ
                                                      0

                                                      Roaring Bitmaps не совсем то что вам нужно (не считая проблем шарповой реализации). А вот с CSharpFastPFOR померятся вполне уместно. Собственно этого достаточно чтобы соотнести результат вашего VLQ с остальными competitors в score-таблицах у TurboPFor и т.п.


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


                                                      P.S.
                                                      На всякий — про качество кода CSharpFastPFOR мне ничего не известно, т.е. там тоже могут быть какие-то перлы.

                                                        +4
                                                        Статью — возможно сделаю. Но позднее. Всё-таки это большая работа всё проанализировать. Пока быстрый тест на части моих данных (синтетика это круто, но есть реальные данные, так что синтетику оставлю на потом). Сравнивать буду потребление памяти по мнению самого .NET и выделенной памяти. Разница в том, что в .NET объекты больше 80КБ помещаются в LOH, который очень плохо оптимизируется сборщиком мусора. Т.е. с одной стороны, память может быть заиспользована дальше, с другой — некий показатель внутренней работы (выделения блоков и тому подобного). На самом деле, второй столбец просто для информации и реализации на плюсах, т.к. по-другому не посчитать память.

                                                        Итак, 1670118 хешсета, 234965944 суммарное количество интов.
                                                        Сохраняем тупо в интовых массивах. 955Мб/981Мб примерно сходится. Некоторые накладные расходы не очень существенны.

                                                        Для начала быстро глянул на Roaring Bitmaps
                                                        Попробуем CRoaring (это враппер, его нельзя использовать в продакшене, можно получить жёсткую утечку памяти): 67/864 (тут всё ушло в unmanaged память, прироста особо нет).

                                                        RoaringBitmap — нативная реализация на C#: 676/712

                                                        Да, вы правы, не очень подходит.

                                                        Переключаемся на CSharpFastPFOR: 639/954.
                                                        Отсортируем массивы: результат аналогичный.
                                                        Возьмём разницу между числами (вроде можно для этого алгоритма): 218/360

                                                        Тупой VLQ: 749/1041
                                                        VLQ с разницей: 307/509

                                                        В итоге CSharpFastPFOR с доработками победил. Да я проиграл. Буду ли я использовать CSharpFastPFOR? Его точно нет, его надо переписать полностью. Буду ли я использовать что-то аналогичное (если есть) — не знаю. VLQ пишется за 5 минут и всем понятен, тут — нужна production-ready реализация.

                                                        Буду ли играться дальше — а почему бы и нет. :)
                                  0
                                  На мой взгляд, если массивы сильно разряженные, лучше использовать список с указателем на следующий (и предыдущий) элемент.
                                  Если списки достаточно плотные от 50% заполнения то самый выгодный вариант будет использовать массив подсчёта. 1 в каждом бите, если элемент есть и 0, если не существует. Как уже писали выше если int значение, то потребуется 500Мбайт накладных расходов, если только положительные числа — в два раза меньше.

                                  Всё что Вы описали выше интересно с академической точки, но сомневаюсь, что в реальном проекте даже 2х-4х кратная экономия по памяти ценой таких накладных расходов оправдана.
                                  В одном проекте где потребовалось подсчитывать все int значения со счётчиком, я просто докупил памяти до 16 гб.
                                    0
                                    500Мб на один сет. У вас их миллион. Вы тут ничего не сэкономили.
                                    10Гб — не очень много, да. Но, есть другие задачи. Например, та же перестройка с нуля подобных сетов уже займёт ещё 10Гб (например, чтобы не париться с многопоточностью иногда проще пересобрать с нуля, чем править существующие). Я специально не рассказывал про проект, чтобы не отвлекаться, но тут 10Гб, там 10Гб, а потом Out of Memory :)
                                      0
                                      Вы бы подробнее рассказали про проект, в котором нужно искать пересечение миллиона множеств.
                                      И при таких объёмах данных разумнее мне кажется разделить множества на подмножества, и обрабатывать их по лимиту оперативной памяти.
                                        0
                                        Да, делить можно, но как бы эта задача не связана с той. Т.е. если ресурсы по реализации ограничены, то можно или шардировать, или подгружать с диска, будет проще и быстрее. Но вот эти варианты не отменяют ещё возможности оптимизировать хранение. И эта задача гораздо веселее чем скучное шардирование :)
                                          0
                                          На счёт веселее тут Вы правы. Но вся индустрия разработки давит на скорость обработки, в основном выравниванием стека, улучшением предсказания ветвлений, реже векторизацией, зачастую сильно завышенными затратами памяти.
                                          Я когда смотрю на современные языки типа Python, которые насилуют память, сверх не эффективно её используя, просто сердце щемит. Однако согласитесь, работает все очень быстро, на типовых задачах.
                                            0
                                            А потом задача не типовая и всё разваливается :)
                                            Меня немного печалит современная тенденция, с другой стороны — я понимаю, время разработчика дорогое, а железо дешёвое. Но ведь всегда можно сделать быстро, а потом улучшать, можно даже в свободное от работы время. Просто потому что это не абстрактный pet project, а реальная задача. Иначе перестаёшь чувствовать себя программистом, а просто каким-то маляром, красящим от забора до обеда.
                                        0

                                        А вот интересно, что это за задача такая, которая для миллиона множеств с миллионом элементов в каждом требует одновременного присутствия в оперативной памяти их всех сразу?

                                      +1
                                      А если не секрет, какого рода задача и какое распределение чисел получается?
                                      Хороший пример решения задачи такого рода — исходный код Люсены: ее индекс, собственно, это набор файлов, в котором хранятся числа разных распределений. Соответственно, для каждого типа файлов они придумывают свой собственный кодек, их можно посмотреть, например, здесь.
                                      Мне приходилось решать похожие задачи (хотя, скорее, для оптимизации хранения), я использовал комбинацию уже упоминавшихся тут приемов:
                                      — отсортировать числа
                                      — взять разницу между соседними (если числа разные, можно отнять 1)
                                      — закодировать Varint encoding (7 бит на значение, восьмой бит — флаг последнего байта)
                                      — разделить на куски и каждый кусок сжать deflate-ом (либо lz4, если нужна скорость).
                                        +1
                                        Вы угадали, с полнотекстом задача связана. Поиск по документам.
                                        0
                                        Можно хранить числа в фильтре Блума. Да это звучит странно. Но он позволяет хранить числа очень компактно. Такое примеряется в системе CRLite для проверки наличия сертификата в базе. Да это позволяет добавить число в структуру, но не позволяет прочитать его обратно. Уровень компактности можно варьировать в широких пределах, регулируя вероятность ложноположительного срабатывания.
                                        А какие недостатки будут, если завести 256 массивов, и отделить и хранить первый байт из четырёхбайтного числа в качестве индекса массива? Таким образом действительно храня в памяти только 3 байта из 4.
                                        Но обычно на практике чаще применяется дельта-кодирование с последующим сжатием компрессором словарным методом. И если позволяется сортировка чисел, то можно разбить набор на бакеты и к ним применять дельта-кодирование по отдельности. А так как первое число в дельта-кодировании хранится как есть и все числа не превышают первого числа следующего бакета, это позволит понять какой диапазон хранится в данном бакете. Для более быстрого доступа без распаковки всего объёма данных.
                                        То что вы упомянули что числа более случайны и вряд ли повторяются, это можно исправить с помощью BWT преобразования, которое добавит повторяемости даже без потери порядка элементов. Это довольно хитрый алгоритм, который позволяет добавить повторяемости и выявить закономерности для последующего применения словарных методов сжатия.
                                          0
                                          Фильтр Блума так и не понял, куда тут применить. Он для оптмизиации подходит, но не для хранения.
                                          Поможет ли тут BWT — тоже не ясно, т.е. так-то он поможет, но потом дожимать надо опять, и он очень медленный. Проще уж сразу в bzip2 сжимать :)
                                          0

                                          Если есть значительные промежутки между числами, можно сделать аналогично тому, как хранятся таблицы страниц для защищенного режима процессора.
                                          Для 32 бит адрес делится на 3 части 10+10+12 бит. Для первых 10 бит одна таблица, для вторых 10 бит набор других таблиц, остальное это сама страница размером 4kB. То есть первая таблица разбивает адресное пространство на диапазоны по 4MB. Если в таблице первого уровня в какой-то строке стоит бит 0, то страницы в этом диапазоне точно нет, и таблица второго уровня тоже отсутствует.


                                          Для чисел, в отличие от страниц, надо также хранить сами числа, можно хранить их не целиком, а только последние 12 бит. Например, если у нас всего 2 числа 1 и 232-2, то таблица первого уровня будет выглядеть как
                                          0x123000, NULL, NULL, ..., NULL, NULL, 0x124000
                                          (размером 1024*4 байт, присутствуют элементы из первого и последнего диапазона 4MB, числа в которых начинаются на 0x00?.. и 0xFF?...)


                                          по указанным адресам будут 2 таблицы второго уровня
                                          0x128000, NULL, NULL, ...
                                          NULL, NULL, ..., 0x129000
                                          (числа начинаются на 0x00000… и 0xFFFFF...)


                                          по этим адреса будут 2 таблицы с данными
                                          [1, 0x001] и [1, 0xFFE]
                                          (первый элемент длина, далее 12-битовые числа).
                                          Можно адреса таблиц на биты заменить, но тогда вторые таблицы надо размещать в одном большом массиве и подсчитывать биты в главной таблице, чтобы вычислить смещение.


                                          Как-то так. Для 2 чисел конечно есть оверхед, но для большего количества может быть экономия.

                                            0
                                            Насколько я понимаю, уже упоминавшийся выше Roaring Bitmap примерно так и работает: разбивает диапазон на под-диапазоны, и хранит только младшие биты в каждом, но у него (в оригинальном варианте) только один уровень вложенности: 64K страниц по максимум 64K элементов, причем каждая страница сжимается своим способом (битовый массив или набор чисел, в зависимости от количества элементов).

                                          Only users with full accounts can post comments. Log in, please.