Эта хитрость для HDD, для SSD и флешек как я понимаю, используют «лишние» байты на служебные цели. Просто потому, что память для них делают всё-таки «круглого» двоичного размера.
Фильтр Блума так и не понял, куда тут применить. Он для оптмизиации подходит, но не для хранения.
Поможет ли тут BWT — тоже не ясно, т.е. так-то он поможет, но потом дожимать надо опять, и он очень медленный. Проще уж сразу в bzip2 сжимать :)
Естественно 90% кода лучше писать красиво, а не эффективно, но есть 10%… которые сейчас работают хорошо, а потом стреляют. Через год, в другом проекте, через утёкшую абстракцию. Когда уже никто ничего не помнит.
Несколько раз ходить по IEnumerable — это отличный способ выстрелить себе в ногу. Почему? А потому что сегодня это коллекция, а завтра это поток сообщений с удалённого сервера, который не остановить, и перемотка назад повторит все операции.
Да, это крайние случаи, и в статье про подобное сказано, но могу добавить следующее:
1. Когда пишется неоптимальный код, сразу надо думать — а есть ли возможность сделать его потом оптимально, если потребуется? Или мы в погоне за красотой должны всё переписать
2. Будет ли этот код кто-то поддерживать, или он уйдёт в библиотеку Common, которой пользуются все, но никто не помнит, что там есть и как работает
3. А может оптимальный но некрасивый код будет лучше читать? Всякие цепочки вида .Where.Select.GroupBy.Select.Where.Distinct.Any через некоторое время становятся совершенно непонятными, а тупой цикл for можно разметить комментариями и крутить в голове
4. Знаю ли я, как работает абстракция? Сколько она стоит? Возьмём Distinct — что там внутри? Какая сложность алгоритма? Не взорву ли я мир через 2 месяца?
Опять же, подчеркну, большинству кода это не надо. Но я неоднократно был свидетелем, когда вылезали жёсткие перфоманс проблемы на продакшен сервере (там данных больше и пользователи щаче ходят), которые было уже не пофиксить без серьёзного вникания в логику и переписывания больших кусков. И это времени занимало больше, чем подумать заранее и преждевременно оптимизировать.
Статью — возможно сделаю. Но позднее. Всё-таки это большая работа всё проанализировать. Пока быстрый тест на части моих данных (синтетика это круто, но есть реальные данные, так что синтетику оставлю на потом). Сравнивать буду потребление памяти по мнению самого .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. Т.е. мы тысячу разных значений сольём в одно. Эффективно, да. Но как-то потеря данных — не то решение, которое хотелось бы сделать.
Да, я почитал про них. Пока есть ощущение, что решение для больших объёмов данных, но с возможностью хорошо проводить на них математику множеств. Надо будет посмотреть нюансы в качестве идей.
Поможет ли тут BWT — тоже не ясно, т.е. так-то он поможет, но потом дожимать надо опять, и он очень медленный. Проще уж сразу в bzip2 сжимать :)
Несколько раз ходить по IEnumerable — это отличный способ выстрелить себе в ногу. Почему? А потому что сегодня это коллекция, а завтра это поток сообщений с удалённого сервера, который не остановить, и перемотка назад повторит все операции.
Да, это крайние случаи, и в статье про подобное сказано, но могу добавить следующее:
1. Когда пишется неоптимальный код, сразу надо думать — а есть ли возможность сделать его потом оптимально, если потребуется? Или мы в погоне за красотой должны всё переписать
2. Будет ли этот код кто-то поддерживать, или он уйдёт в библиотеку Common, которой пользуются все, но никто не помнит, что там есть и как работает
3. А может оптимальный но некрасивый код будет лучше читать? Всякие цепочки вида .Where.Select.GroupBy.Select.Where.Distinct.Any через некоторое время становятся совершенно непонятными, а тупой цикл for можно разметить комментариями и крутить в голове
4. Знаю ли я, как работает абстракция? Сколько она стоит? Возьмём Distinct — что там внутри? Какая сложность алгоритма? Не взорву ли я мир через 2 месяца?
Опять же, подчеркну, большинству кода это не надо. Но я неоднократно был свидетелем, когда вылезали жёсткие перфоманс проблемы на продакшен сервере (там данных больше и пользователи щаче ходят), которые было уже не пофиксить без серьёзного вникания в логику и переписывания больших кусков. И это времени занимало больше, чем подумать заранее и преждевременно оптимизировать.
Итак, 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 :)