Статью — возможно сделаю. Но позднее. Всё-таки это большая работа всё проанализировать. Пока быстрый тест на части моих данных (синтетика это круто, но есть реальные данные, так что синтетику оставлю на потом). Сравнивать буду потребление памяти по мнению самого .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 реализация.
Ну да, сдаюсь. Я не буду переписывать TurboPFor с плюсов на C#, чтобы проводить бенчмарки. Может вы согласитесь на Roaring Bitmaps или CSharpFastPFOR? Я выставлю против них наивный и дилетантский VLQ
Давайте ещё раз. Я не сомневаюсь в способностях Даниэля. Но он решает свои конкретные задачи. И реализуют его работы другие люди, которые могут написать фуфло. Пример я привёл. Доверять ли конкретной реализации?
Использовать ли алгоритм, только потому что его написал какой-то известный Дядька?
Возьмём Roaring Bitmap — структура, предназначена для эффективной манипуляции со множествами. У меня постановка — хранение. Разные задачи. Будет ли эта структура волшебной и хранить эффективнее? Сомневаюсь.
Мы можем продолжать дискуссию, но я могу взять реализацию на Roaring Bitmap на C#, и первый попавшийся велосипед и сравнить на каких-то данных. Если Roaring Bitmap окажется хуже, вы признаете, что другие решения имеют право на жизнь, или скажете, что я всё неправильно понял, и надо всё равно использовать существующие решения? :) Т.е. стоит мне тратить время на сравнение, или вас не переубедить?
А потом задача не типовая и всё разваливается :)
Меня немного печалит современная тенденция, с другой стороны — я понимаю, время разработчика дорогое, а железо дешёвое. Но ведь всегда можно сделать быстро, а потом улучшать, можно даже в свободное от работы время. Просто потому что это не абстрактный pet project, а реальная задача. Иначе перестаёшь чувствовать себя программистом, а просто каким-то маляром, красящим от забора до обеда.
Я с вами не соглашусь. Для того, чтобы понимать оптимальные реализации, надо понимать в целом какие варианты есть, и что конкретная реализация оптимизирует какой-то конкретный фактор (скорость, память, использование аппаратных возможностей). Если тупо читать реализации — то всё будет казаться магией, которую сделали, какие-то абстрактные «умные люди». А люди решали свою проблему, возможно отсекли кучу неудачных вариантов. Но они могли быть неудачными для них, а не для вас.
А потом другие люди начинают по этим статьям делать аналогичные реализации на других языках. Но для них это магия, и получается такой код (пример из C# реализации Roaring Bitmap):
var groupbyHb = values.Distinct().OrderBy(t => t).GroupBy(Util.HighBits).OrderBy(t => t.Key).ToList();
При этом, если я буду реализовывать свою задачу (да, я пока не сделал её), я, естественно проанализирую все варианты, и выберу известный и стабильный, если он не особо хуже велосипеда. А если хуже? Использовать его только потому что автор какой-то известный, это я считаю совершенно неправильно.
Да, делить можно, но как бы эта задача не связана с той. Т.е. если ресурсы по реализации ограничены, то можно или шардировать, или подгружать с диска, будет проще и быстрее. Но вот эти варианты не отменяют ещё возможности оптимизировать хранение. И эта задача гораздо веселее чем скучное шардирование :)
500Мб на один сет. У вас их миллион. Вы тут ничего не сэкономили.
10Гб — не очень много, да. Но, есть другие задачи. Например, та же перестройка с нуля подобных сетов уже займёт ещё 10Гб (например, чтобы не париться с многопоточностью иногда проще пересобрать с нуля, чем править существующие). Я специально не рассказывал про проект, чтобы не отвлекаться, но тут 10Гб, там 10Гб, а потом Out of Memory :)
Их уже упомянули в комментариях. Давайте сформулирую свою статью так: я написал идеи, а вот конкретные реализации примерно основаны на этих идеях, только оптимизированы под CPU или определённые объёмы данных. Возможно, если будет время досконально разобраться в них, то напишу другую статью именно с объяснениями, зачем эти алгоритмы и что они дают. Но это достаточно большая работа, так что не обещаю.
У плавучки на 32 бита точность 7 значащих цифр. У инта — почти 10. Т.е. мы тысячу разных значений сольём в одно. Эффективно, да. Но как-то потеря данных — не то решение, которое хотелось бы сделать.
Да, я почитал про них. Пока есть ощущение, что решение для больших объёмов данных, но с возможностью хорошо проводить на них математику множеств. Надо будет посмотреть нюансы в качестве идей.
Выглядит как решение соседа по палате :) Надо будет попробовать. К сожалению, реализация на C# через нативный враппер. Он может быть быстрее, а может быть проблемным из-за маршаллинга. Надо посмотреть на память и скорость, может его стоит использовать в качестве основной реализации сета, а не хранилища, которое будет в него преобразовано.
А если меньше, то плохо выходит. + начало блока надо кодировать. В общем, при плотных данных это хороший вариант. Я подобный вариант описал в начале статьи, только ограничил всё числами от 0 до 255.
Для известного распределения — надо по идее использовать для информации все множества (в одном каждое число уникально и ничего мы не добьёмся). По идее тут Хаффман может подойти. Можете дать ссылку на VLQ в git? потому что попытки узнать что это, привели к коду, реализующему VLQ, опубликованному на гитхабе :)
Group varint — вариант для скорости, надо тут тестировать на C#, возможно ли получить преимущество, или невозможность делать некоторые вещи — сожрёт возможную выгоду.
Итак, 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 реализация.
Буду ли играться дальше — а почему бы и нет. :)
Использовать ли алгоритм, только потому что его написал какой-то известный Дядька?
Возьмём Roaring Bitmap — структура, предназначена для эффективной манипуляции со множествами. У меня постановка — хранение. Разные задачи. Будет ли эта структура волшебной и хранить эффективнее? Сомневаюсь.
Мы можем продолжать дискуссию, но я могу взять реализацию на Roaring Bitmap на C#, и первый попавшийся велосипед и сравнить на каких-то данных. Если Roaring Bitmap окажется хуже, вы признаете, что другие решения имеют право на жизнь, или скажете, что я всё неправильно понял, и надо всё равно использовать существующие решения? :) Т.е. стоит мне тратить время на сравнение, или вас не переубедить?
Меня немного печалит современная тенденция, с другой стороны — я понимаю, время разработчика дорогое, а железо дешёвое. Но ведь всегда можно сделать быстро, а потом улучшать, можно даже в свободное от работы время. Просто потому что это не абстрактный pet project, а реальная задача. Иначе перестаёшь чувствовать себя программистом, а просто каким-то маляром, красящим от забора до обеда.
А потом другие люди начинают по этим статьям делать аналогичные реализации на других языках. Но для них это магия, и получается такой код (пример из C# реализации Roaring Bitmap):
При этом, если я буду реализовывать свою задачу (да, я пока не сделал её), я, естественно проанализирую все варианты, и выберу известный и стабильный, если он не особо хуже велосипеда. А если хуже? Использовать его только потому что автор какой-то известный, это я считаю совершенно неправильно.
10Гб — не очень много, да. Но, есть другие задачи. Например, та же перестройка с нуля подобных сетов уже займёт ещё 10Гб (например, чтобы не париться с многопоточностью иногда проще пересобрать с нуля, чем править существующие). Я специально не рассказывал про проект, чтобы не отвлекаться, но тут 10Гб, там 10Гб, а потом Out of Memory :)
Group varint — вариант для скорости, надо тут тестировать на C#, возможно ли получить преимущество, или невозможность делать некоторые вещи — сожрёт возможную выгоду.