Comments 23
Спасибо, про симд интересно, но нету примеров, простите, только ссылки, думал будет обзор сравнение
Тема не раскрыта. Почему не написать подробную статью?
у симда есть мельница, вот это тема, крутишь и считай шагаешь
и за пределы не вылетишь ) потомучто блок фиксированный ) и там наверняка еще кучи нюансов есть интересных )
а тут что идёшь в тривиальном случае по хешу, в обзоре видел, после симда не интересно ) ну хотябы на 256 было б поинтереснее ), там как раз с шафлом всё ок в 256 по маске прям тут же не отходя от кассы можно сделать шафл нужный, я читал книгу про Юникс, там писалось про расходы на создание после PDP-11, и там писалось про переносимость кода и проблемы, и там 1 из моментов указывался новые регистры и возможность переноса кода, я даже подумал почему на SIMD ОС не перенесут, хотябы тестово, получается это новая мощ, новые инструкции более быстрые и прочее
Тема заслуживает более подробного материала.
Поэтому на любых разумных загрузках таблиц (до 90%) - "цепочка проверки" очень редко превышает 1
Вообще, гугл говорит, что нужно ресайзить хеш-таблицу при достижении заполненности в 70%.
Так это для "классических" таблиц, где сравнение происходит по 1 элементу, а не сразу по 8. Но по числу в 90% хотелось бы каких-то пруфов, что ли.
Мне тоже непонятно про 90%
Если просто перемножить вероятности для блока длиной 8 получаем 35% шанс не влезть, что довольно прилично
Они используют 7/8 как resize factor, т. е. 87.5%
https://github.com/abseil/abseil-cpp/blob/f1b7d000b8b8a74640e93cb3c06bc5fa384126de/absl/container/internal/raw_hash_set.h#L1108-L1126
Проверяют по 16 слотов на машинах с SSE2 (любые современные x86), по 8 слотов на каких-то ARM: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/hashtable_control_bytes.h#L353
При этом фактор заполненности не меняют. Хотя мб могли бы, на 8-слотах поставить 6/8, т. е. 75%.
Они используют 7/8 как resize factor, т. е. 87.5%
At our max load factor of 12/14 [ ~ 86% ], the expected probe length when searching for an existing key (find hit) is 1.04, and fewer than 1% of keys are not found in one of the first 3 chunks. When searching for a key that is not in the map (find miss) the expected probe length at max load factor is 1.275 and the P99 probe length is 4.
https://github.com/facebook/folly/blob/main/folly/container/F14.md
такое ощущение что буст с симда достигается следующей схемой взаимодействия (пользователь спрашивает индекс -> хеш на симд (+матан на симд) ) тоесть симд это плоское облако расчетов на 1 запрос, какая разница прошлись в симде или не прошлись надо узнать мегабыстро индекс, ну хотя прошлись/не прошлись это уже могут быть разные реализации
От статьи с таким заголовком ожидаешь обзора на 100500 страниц с зубодробительным матаном, а тут всего лишь сообщение о том, что автор не согласен с журналистом, изнасиловавшем учёного.
С одной стороны, вы правы, что новый алгоритм не «ускорит интернет». Мало того, по моим ощущениям, поиск несуществующего ключа там заметно дороже, чем в SwissTable.
Однако, это всё-таки является достижением, т.к. впервые для хэш-таблиц постулируются сразу несколько гарантий:
гарантия вставки за ограниченное число операций,
гарантия поиска за ограниченное число операций,
гарантия неподвижности элемента (по-крайней мере, пока не превысится процент заполнения)
гарантию достижения целевого процента заполнения (или я приврал?)
Существующие алгоритмы не дают такой гарантии. Кукушка и Робин-Гуд дают гарантию поиска за ограниченное число операций, но не дают такой гарантии для вставки, гарантию неподвижности и гарантию заполнения. Кукушка с доп.буфером даёт больше гарантий (емнип, гарантию на сложность вставки и процент заполнения), но не гарантию неподвижности.
Емнип, SwissTable даёт гарантию неподвижности и заполненности, но не гарантию числа операций. Хотя она и очень быстрая.
Отсутствие гарантий на количество операций является самым частым аргументом против хэш-таблиц в системах, чувствительных к максимальному времени (системы реального времени, и просто многие системные штуки). Из-за этого там чаще применяют балансированные деревья поиска.
А неподвижность элементов упрощает итерацию при мутации хэш-таблицы. (Хотя Робин-Гуд эффектно позволяет удалять текущий элемент во время итерации.)
Если новый алгоритм будет быстрее сбалансированных деревьев и не слишком сложен в реализации, вполне возможно хэш-таблицы на его основе начнут появляться там, где раньше хэш-таблицы не допускались.
Кстати, не очень понял: в Go хэш-таблицы и раньше проверяли по 8 элементов с помощью SIMD инструкции. Так что, в этом смысле SwissTable не привнёс улучшений. Возможно выгода была Open-Addressing vs Chains-of-Buckets? Т.е. старая организация бакетов (по 8 элементов каждый) в виде односвязного списка имела меньшую локальность по памяти, чем практически Linear-Probing организация бакетов в SwissTable.
Если использовать криптографическую хеш-функцию и "cooperative" resizing/growth где в течение какого-то времени каждая вставка делает по часть resize работы (как в Го), то фактически гарантии будут и со SwissTable. А если НЕ использовать криптографическую хеш-функцию, то гарантий нет только при прицельной DoS атаке, что возможно далеко не всегда
Кстати, не очень понял: в Go хэш-таблицы и раньше проверяли по 8 элементов с помощью SIMD инструкции. Так что, в этом смысле SwissTable не привнёс улучшений. Возможно выгода была Open-Addressing vs Chains-of-Buckets? Т.е. старая организация бакетов (по 8 элементов каждый) в виде односвязного списка имела меньшую локальность по памяти, чем практически Linear-Probing организация бакетов в SwissTable.
Скорее всего.
Нет, SwissTable не гарантирует ограниченность длинны цепочки. И даже с криптографическими функциями ограниченность длинны цепочки не гарантируется.
SwissTable уже есть в новом Go 1.24, вот сравнение с подробностями и бенчмарками https://dev.to/ocodista/go-124-uses-swiss-table-what-are-they-3c2l
Lookup 35.67% faster
Insertion 43.99% faster
Deletion -53.85% slower
Также там описывается этот новый Elastic Hashing из статьи, но по нему пока ещё данных нет.
Как-то, года три назад, заморочился - sha256 на SIMD реализовал. Увы, распараллелить процесс в силу алгоритма невозможно, к тому же память и диск не дали алгоритму вволю развернуться. А раз так, то и к дальнейшему развитию интерес упал.
О новых алгоритмах хеш-таблиц