Seed для CRC32?

Question

[floppa322]

Контекст: решил написать хэш-таблицу без коллизий
Выбор пал между кукушкой и идеальным хешированием (двухуровневое хеширование в качестве реализации)
Выбрал 2-е (у кукушки мат. ожидание кеш миса 1.75, а у двухуровневого хеширования 1, если объекты небольшие)

В качестве хеш функции выбрал crc32-c (по советам разработчиков ClickHouse'а) - хорошее распределение хешей + высокая скорость (2 процессорных цикла, если использовать аппаратную реализацию _mm_crcX_uX, где X - количество бит)

Поскольку для подбора хеш функции без коллизий требуется её параметризировать, то в качестве параметра для crc32-c выбрал сам накопленный циклический код (1-й аргумент _mm_crcX_uX).

Собственно решил потестить за сколько в среднем попыток в зависимости от load factor'а бакета он заполнится без коллизий, меняя параметр (crc) хеш функции после каждой неудачи. Код

Вопрос: если в качестве параметра использовать обычный инкремент на каждой итерации (40-я закоменченная строка), то он никогда не покинет while(true), т.е. хеши при остатке от деления на 16 одинаковые для разных параметров. Но если в качестве crc взять хеш с предыдущей итерации (строка 25), то алгоритм сходится ~ за 5к попыток.
Чем можно объяснить такое поведение?

Comments

[mayton2019]

у кукушки мат. ожидание кеш миса 1.75

Вот это поворот! Как посчитал?

[floppa322]

mayton2019, ну если всё равновероятно, то 0.25 * 1 + 0.25 * 2 + 0.5 * 2 = 1.75 (0.25 * 1 - элемент есть и он в 1-й ячейке, 0.25 * 2 - элемент есть и он во 2-й ячейке, 0.5 * 2 - элемента нет)
Предполагается, что contains на одни и те же элементы не вызывается, а если вызывается, то их уже нет в кеше )

[floppa322]

mayton2019, вот гпт 3.5 дал мне ответ, хотя и довольно поверхностный, хотелось бы мат. обоснование

Да, для данной конкретной ситуации с хеш-функцией CRC32 можно предложить математическое объяснение такого поведения.

CRC32 - это циклический редундантный код (Cyclic Redundancy Check), который обычно используется для обнаружения ошибок в данных. Он оперирует с битами данных и вычисляет контрольную сумму для обнаружения ошибок в передаче данных.

При использовании CRC32 в вашем коде в качестве параметра хеш-функции для хэш-таблицы, вы фактически создаете некоторую последовательность хешей, каждый из которых зависит от предыдущего. Так как CRC32 обрабатывает данные по битам и вычисляет контрольную сумму, его свойства обеспечивают некоторую случайность и разнообразие в вычисленных хеш-значениях.

Когда вы используете хеш с предыдущей итерации для получения нового хеша (25-я строка), вы создаете последовательность хешей, которая зависит от предыдущих значений. Это приводит к тому, что каждый следующий хеш зависит от предыдущего и от входных данных (ключей), и, таким образом, обеспечивает разнообразие хешей. Кроме того, при каждом исполнении цикла происходит пересчет хеш-значения с новым параметром, что увеличивает разнообразие хешей в процессе.

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

Таким образом, математическое объяснение заключается в том, что использование CRC32 и его свойства циклического редундантного кода, а также зависимость от предыдущего значения, обеспечивают разнообразие хешей при использовании хеша с предыдущей итерации. Это позволяет алгоритму быстро находить подходящий параметр для успешного заполнения бакета без коллизий.

[floppa322]

mayton2019, короче выяснил, что для некоторого набора данных (ключей) существуют такие параметры (на картинке - evil_param), что если нарисовать граф, где вершина - это параметр, а ребро - текущий ключ + текущий параметр, то появляется цикл в таком графе

Поборосял с этим дефолтным способом: если алгоритм сильно много итераций не сходится, то меняю параметр на рандомный и пытаясь заново, вроде работает

Как я понял, с инкрементальными seed'ами просто вероятность в такой цикл попасть больше

Граф

[mayton2019]

Дружище Флоппа. Ну Кукушка она вообще не для поиска идеальной функции. Весь фокус в том
что если у тебя 1000 ключей и из них 150 популярны (перекошенная skew гистограмма частот)
а остальные 850 допустим редкие. И тогда кукушка поднимает популярные наверх и делает
иммитацию идеального хеша. Но она ничего не гарантирует при других условиях.

[floppa322]

mayton2019, немного не понял как тут поможет кукушка, можно подробнее плз )

Ну и я про кукушку говорил в контексте того, чтобы contains всегда за O(1), не амортизированно

[mayton2019]

У тебя github есть? Потому что pastebin это уродство какое-то.

[floppa322]

mayton2019, github

[mayton2019]

Выбор пал между кукушкой и идеальным хешированием (двухуровневое хеширование в качестве реализации)

Я несколько раз читал эту фразу и не могу ее понять.

Напомни пожалуйста. Двухуровневое - это когда для хранения 1000 ключей ты создаешь 2 таблицы 1000*2 = 2000 позиций.

Верно?

[floppa322]

mayton2019, ты сначала функцией h1 хешируешь во внешнюю хеш таблицу итемы, а потом для каждой ячейки внешней хеш таблицы подбираешь такую h2i, что все итемы ячейки захешируются без коллизий

[mayton2019]

floppa322, я-ж про потребление памяти спрашиваю.

[floppa322]

mayton2019, о, вот это её минус главный, внешняя таблица ~2n, а размер внутренней ~5, если до ближайшей степени 2, то 8, и того 2n * 8 = 16n

[mayton2019]

По поводу CRC32. Это очень примитивная функция. Она создавалась в 20-м веке
в эпоху 16 и 32х битных процессоров. И в основе ее лежит один раунд ХОРь ,
сдвиг и отображение из массива заранее расчетных констант.

У нее есть некоторые интересные совйства. Кажется она идеально хеширует int32
целое число. Вот. Но если-бы я хотел повторить такие свойства то я мог-бы
создать функцию к примеру которая-бы ... меняла левые 16 бит и правые.
Вот тоже самое свойство. Идеально отображает одно в другое.

Но что говорить о прочих свойствах?

[floppa322]

mayton2019, она, например, в ClickHouse'е используется для интов + как внутрення часть для cityHash для строк
ну и я сам посмотрел на некоторых дата-сетах у неё хорошее распределение

[mayton2019]

А как ты выбрал эти константы? Почему 16 и 14?

const size_t INNER_BUCKET_SIZE = 16;
    const size_t ITEM_PER_BUCKET = 14;
    bool innerBucket[INNER_BUCKET_SIZE];

[floppa322]

mayton2019, ну я пытался сделать эмуляцию заполнения внутренней хеш таблицы, в данном случае с load_factor = 16/14. Смотрел за сколько попыток в среднем это произойдёт (найдётся h2i что не будет коллизий)

[mayton2019]

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

[mayton2019]

Давай я тебе мысль закину. А ты подумай. Вот в твоем исходнике-же нет таблицы.
Там только ключи. Сет по сути. Тогда тебе можно завести битовый массив и включай биты
где надо. У тебя 5 млн ключей?

А я тебе предлагаю аллоцировать 512 Мб битов и этого тебе хватит для любого
целого числа от 0 до 4 млрд.

[floppa322]

mayton2019, да не, в том исходнике я исключительно тестировал за сколько он подберёт нужную хеш функцию )

[mayton2019]

floppa322, почитай еще про метод Робин-Гуда. Возможно тебе пригодится.

[floppa322]

mayton2019, читал :)

[mayton2019]

Отписал я вариант ответа. Чего тут еще придумывать. Ну ты подумай что двухуровневая таблица - это-ж фу-фу-фу.
Ни один нормальный разработчик не захочет тащить в проект накладные расходы ни с того ни с сего 2х от нужного размера. И кукуха здесь не поможет и Робин гуд. Если уж ты такой перфекционист.

[floppa322]

mayton2019, внешняя и все внутренние таблицы могут быть выделены в непрерывном куске памяти, только вот из-за того, что размер внутренней константный, перерасход памяти получается порядка 10-16n

[mayton2019]

10-16n

Тоесть ты хочешь сказать что вместо 5 млн слотов тебе надо будет 16 * 5 000 000 = 80_000_000 ?

Восемдесят лямов?

Ахахаха.

Answer 1

[mayton2019]

Я сразу попробую ответить на главный вопрос.

написать хэш-таблицу без коллизий

Написать такую таблицу можно если мы заранее знаем весь набор данных (в случае автора это
множество ключей (K). Здесь для простоты предполагаем что ключи - это целые числа int32 (DWORD).

Алгоритм примерно такой:
1) Берем размер хеш-таблицы в n = size(K). Метод открытой адресации.
2) Берем любую хеш-функцию (по области определения больше чем n
SHA1, MD5, xxhash, mur-mur-hash)
3) Начинаем наполнять таблицу.
4) Как только детектирована коллизия - удаляем старую таблицу и создаем новую
с размером например 120% от исходного n.
5) Повторяем алгортм до тех пор пока не будут расставлены все ключи.

Profit.

Если мы не знаем наши данные изначально (у нас их нет и мы не знаем количество и тип данных)
то мы не можем гарантировать отсустствие коллизий хотя-бы потому что у нас
нету такой хеш функции которая бы гарантировала отсутствие коллизий на вариативном
типе данных.

Изучать хеширование на базе целых чисел - вобщем-то не интересно. Более общий случай - это
строки (String) и я-бы делал эксперименты со строками и с реальными данными (мобильные
телефоны емейлы налоговые номера и прочее). Целые числа - это .... слишком синтетические
тесты и их результаты потом никуда натянуть нельзя.

UPD: Алгоритм в таком виде не работает. По крайней мере от коллизий мы не избавились.
Не голосуйте здесь пока.

Comments

[floppa322]

Алгоритм примерно такой:
1) Берем размер хеш-таблицы в n = size(K). Метод открытой адресации.
2) Берем любую хеш-функцию (по области определения больше чем n
SHA1, MD5, xxhash, mur-mur-hash)
3) Начинаем наполнять таблицу.
4) Как только детектирована коллизия - удаляем старую таблицу и создаем новую
с размером например 120% от исходного n.
5) Повторяем алгортм до тех пор пока не будут расставлены все ключи.

Такой подход, к сожалению, сходится к ~n^2 памяти

Изучать хеширование на базе целых чисел - вобщем-то не интересно. Более общий случай - это
строки (String) и я-бы делал эксперименты со строками и с реальными данными (мобильные
телефоны емейлы налоговые номера и прочее). Целые числа - это .... слишком синтетические
тесты и их результаты потом никуда натянуть нельзя.

А как же какой-нибудь Map(id, User) ))

[mayton2019]

Нормально.

Я 5 миллионов ключей записал в 5008333 слотов. Без коллизий за 2 итерации.

[floppa322]

mayton2019, а какие ключи (равномерное распределение, нормальное распределение, инкрементальные значения и т.д.) ? какая хеш функция ? с какой попытки сошлось ?

[mayton2019]

Короче я нашел свой старый исходник и сюда приложу а ты посмотри. Если какой-то API по Java ты не знаешь - то я могу подсказать.

UPD: Нет. Херовенько он работает. Надо подфиксить.

[mayton2019]

floppa322, функция mur-mur-hash. Линейное. Пока я фикшу баги.

Но ты булки не расслабляй. Кодь дальше.

[floppa322]

mayton2019, не понимаю, как оно за разумное время могло сработать при 5'000'000 в 5'008'333 слотов. Вот, например, рассмотрим момент, когда вставилось 2'500'000 ключей (т.е. load factor ~ 0.5) теперь осталось вставить ещё столько же ключей и для каждого вероятность, что он вызовет коллизию не меньше 0.5 (и она будет расти по мере продвижения), то есть после момента, как вставилось без коллизий 2.5кк ключей вероятность, что остальные вставятся без коллизий не меньше 0.5^2'500'000

[mayton2019]

Мда... От коллизий вообще не уйти. Может примем за допущение что 1 коллизия для 1 ключа это нормально?

Но глубина пробирования будет в 1 шаг. После первой коллизии мы применяем ту-же хеш-функцию типа CRC или mur-mur но с другим seed.

Если после 2 шага коллизия - то растягиваем таблицу.

[floppa322]

mayton2019, ну я хотел либо попробовать похешировать столько раз, чтобы distance от места вставки до реального расположения был небольше какой-то константы (как в робин гуде) ну и дальше что-то поулучшать там. Либо придумать так, чтобы кукушка из 2-х рандомных меств памяти не читала, либо читала но редко

[mayton2019]

Мне как базовику очень не нравится что кукушка постоянно что-то тасует в памяти. Было-бы более ясно если есть фаза генерации или популяции таблицы. И после этого мы ее фиксируем и больше ключи не вращаются.

[floppa322]

mayton2019, ну если речь идёт о статичной таблице (однажды построилась и далее с неё только читают, не модифицируют), то кукушка будет пробовать строиться, пока не построится так, чтобы каждому элементу было отведено место (не было циклов), ну а дальше просто запросы get/contains в зависимости от того мапа это или сет, ничего никуда больше перемещаться не будет))

[floppa322]

mayton2019, кстати, насчёт "skewed histograms" на самом деле, хорошую идею подкинул, если такой шаблон встретился где-то.
Действительно, можно отсортировать данные по частоте заросов на них, скажем на 10% объектов приходится 90% запросов contains/get, тогда можно с обычным линейным пробированием эти 10% запихать первыми (так, чтобы distance от места вставки до реального места был не больше 1.05 скажем), а остальные 90% запихать потом. Тогда мат. ожидание кеш мисса будет близко к 1.

Единственный минус это большие таблицы. То есть, например, может так получиться, чтобы сохранить инвариант distance <= 1.05 для 10% объектов может потребоваться массив размером, например, 60n, если данных очень много. Из-за того что вероятность коллизии как квадрат растёт от n, к сожалению

[mayton2019]

floppa322, я вот решил следующее посчитать. Допустим я не буду вставлять конфликтующие ключи. А просто буду вести их список. Долг типа. Вот получилось так на 5 млн.

2023-07-28 20:06:28,511 : [INFO] - Start demo
2023-07-28 20:06:29,417 : [INFO] - Populated successfully!
2023-07-28 20:06:29,417 : [INFO] - Inserted : 3160854
2023-07-28 20:06:29,419 : [INFO] - Collision list size : 1839146
2023-07-28 20:06:29,419 : [INFO] - Hash set physical size is 5000000 slots (20000000 bytes)
2023-07-28 20:06:29,419 : [INFO] - Inserted/slots ratio : 63%
2023-07-28 20:06:29,419 : [INFO] - Finish

Из 5 лямов успешно вставились порядка 3.1 млн. Долговых ключей на 1.8. Хорошая новость
их хотя-бы не так много. Далее я могу рекурсивно применить алгоритм построения этой-же
таблицы к списку долговых ключей. Но теперь мне уже не нужно 5 млн слотов. Я сразу создаю
1.8. И если эта геометрическая прогрессия работает (100% - 63% = 37%) то каждый раз
я буду получать треть от оригнального размера. Хеш функцию в данном случае можно
даже не менять. Просто меняется у нас остаток от деления. Будет пирамида таблиц.

[mayton2019]

Действительно, можно отсортировать данные по частоте заросов на них, скажем на 10% объектов приходится 90% запросов contains/get, тогда можно с обычным линейным пробированием эти 10% запихать первыми (так, чтобы distance от места вставки до реального места был не больше 1.05 скажем), а остальные 90% запихать потом. Тогда мат. ожидание кеш мисса будет близко к 1.

Да и если использовать этот пирамидальный вариант таблиц то можно пускать в population ключи
в порядке их частоты. Сначала - самые популярные. Они займут толстый слой пирамиды. А потом
уже те кто пореже будут заселены на 2 и 3 и выше уровня. Но нам - пофиг. Они - редкие посетители.

[floppa322]

mayton2019, и да, нужно, чтобы запросов, где на contains/get было false/null, было мало, иначе в этом подходе не будет смысла особого

[floppa322]

floppa322, я вот решил следующее посчитать. Допустим я не буду вставлять конфликтующие ключи. А просто буду вести их список. Долг типа. Вот получилось так на 5 млн.

2023-07-28 20:06:28,511 : [INFO] - Start demo
2023-07-28 20:06:29,417 : [INFO] - Populated successfully!
2023-07-28 20:06:29,417 : [INFO] - Inserted : 3160854
2023-07-28 20:06:29,419 : [INFO] - Collision list size : 1839146
2023-07-28 20:06:29,419 : [INFO] - Hash set physical size is 5000000 slots (20000000 bytes)
2023-07-28 20:06:29,419 : [INFO] - Inserted/slots ratio : 63%
2023-07-28 20:06:29,419 : [INFO] - Finish

Из 5 лямов успешно вставились порядка 3.1 млн. Долговых ключей на 1.8. Хорошая новость
их хотя-бы не так много. Далее я могу рекурсивно применить алгоритм построения этой-же
таблицы к списку долговых ключей. Но теперь мне уже не нужно 5 млн слотов. Я сразу создаю
1.8. И если эта геометрическая прогрессия работает (100% - 63% = 37%) то каждый раз
я буду получать треть от оригнального размера. Хеш функцию в данном случае можно
даже не менять. Просто меняется у нас остаток от деления. Будет пирамида таблиц.

Если честно, у меня пока нет никаких мыслей, как это можно развить, чтобы было O(1) без жирных констант на contains

[mayton2019]

Ну я вообще тестирую set. В нем только и будет contains. А get не имеет смысла.

[mayton2019]

Если честно, у меня пока нет никаких мыслей, как это можно развить, чтобы было O(1) без жирных констант на contains

Если ты дойдешь до практики реализации кешей. То там окажется что оперативная память неодинаково
работает. Если делать тюнинг структур данных под L1/L2/L3 то может оказаться что такое зональное
деление ключей на популярные и непопулярные очень полезно для кеша.

Вот. Поэтому лучше остановись и сделай бенчмарк в сравнении с хешами STL, Google e.t.c.

O(1) - это чистая теория. А практика может показать что твой теоретический хороший O(1) может быть хуже например логарифма но адаптированного к железу. Бегаешь по красно-черному дереву но ближе к CPU. А пробирования хещ-таблиц будут всегда промахами для железа.

Вот мой десктоп дома (Ryzen-5) имеет на борту 8М кеша L3. И если я его прогрею полностью
(положу туда одну зону из хеш-таблицы) то я почти гарантирую очень короткий отклик
без вовлечения оперативной памяти.

[floppa322]

mayton2019, я не знал, что там речь шла именно о популярных/непопулярных ключах
Почему O(1) нельзя в данном случае ? Всегда можно сделать размер таблицы n^2 и захешировать, в среднем за 2 раза без коллизий сойдётся. Но с одной стороны так много памяти жалко, с другой, даже, если там будет всего лишь 10к интов, то оно даже в L3 не уложится (нужно 400 мб для этого, а стандавртный серверный L3 обычно 128/256 мб)

[mayton2019]

Ну... популярность ключей это-ж краеугольный камень всего перформанс тюнинга. Это и для баз данных актуально. Для файловых систем. И для веб-приложений с Rest.

И один великий сказал дескыть всего 2 проблемы у нас. Как обозвать переменную и как инвалидировать
кеш. А все остальное - решаемо.

[mayton2019]

Еще одна оптимизация. Если есть предположение что будем отбивать 90% негативных реквестов на contains - то можно соединить хеш таблицу с фильтром Блума.

Расчет размеров будет такой. Для 5 млн ключей https://hur.st/bloomfilter/?n=5000000&p=0.01&m=&k=

размер биткарты будет 5 мегабайт и нужно 7 хеш-функций (на самом деле можно одну
только к аргументу единичку прибавлять) и фактор ложно-позитивного срабатывания
0.01. Вот такой фильтр будет дешевой проверкой чтоб отбивать реквесты от хешмапы.