Открытие Эндрю Крапивина о хеш-таблицах и микро-указателях?
Чисто гипотетически, может и актуально, но лишь в чистой и голой computer science теории.
На практике же полно нюансов реализации, сводящихся к оптимизациям конкретных аппаратных платформ.
Например, есть #SwissTable известные с 2018 года, недавно #Golang перешёл на них (с версии 1.24). И до него на SwissTable перейти успел #Rust.
Хеш-таблицы Google SwissTable и Facebook F14 примерно одинаковые, одно лишь вариант другого.
Идея оптимизации работы вокруг использования #SIMD инструкций для поиска занятых ячеек и проверки ключа. И в тотально подавляющем большинстве случаев хватает одной проверки блока из восьми элементов.
Надо ещё много раз поиграться с вариантами реализации какой-либо идеи из чистого computer science. Посмотрев как оно ложится на аппаратную платформу сродни x86-64.
Есть prefetching памяти и работа с ОЗУ идёт через загрузку целиком всей cache line в ЦПУ, даже при обращении на чтение лишь к одному значению в пару байт.
Предыдущий пункт не только про cache misses, но и «локальность данных». Как повышающую производительность, так и приводящих к false sharing при многопоточном использовании структуры данных.
Необходимо учитывать и размер страницы виртуальной памяти, чтобы снизить «давление» на TLB и уйти от TLB miss.
Для пример, в нагруженных системах используется донастройка системы на huge pages, например, все кто используют модный #DPDK сам по себе или с каким-нибудь #Seastar:
Голая теория computer science это хорошо и замечательно, но практика омерзительна свой приземлённостью. Прямой проход перебором по небольшому массиву оказывается быстрее, чем использование binary search tree. И совершенно не важно какого именно красно-чёрного или же АВЛ.
Это не вопрос ретроградства и вызова 40-летней теории :)
#software #SoftwareDevelopment #программирование #разработка #programming @russian_mastodon @ru @Russia
