Открытие Эндрю Крапивина о хеш-таблицах и микро-указателях?
Чисто гипотетически, может и актуально, но лишь в чистой и голой computer science теории.
На практике же полно нюансов реализации, сводящихся к оптимизациям конкретных аппаратных платформ.

Например, есть #SwissTable известные с 2018 года, недавно #Golang перешёл на них (с версии 1.24). И до него на SwissTable перейти успел #Rust.

Хеш-таблицы Google SwissTable и Facebook F14 примерно одинаковые, одно лишь вариант другого.

Идея оптимизации работы вокруг использования #SIMD инструкций для поиска занятых ячеек и проверки ключа. И в тотально подавляющем большинстве случаев хватает одной проверки блока из восьми элементов.

Надо ещё много раз поиграться с вариантами реализации какой-либо идеи из чистого computer science. Посмотрев как оно ложится на аппаратную платформу сродни x86-64.

1. Есть prefetching памяти и работа с ОЗУ идёт через загрузку целиком всей cache line в ЦПУ, даже при обращении на чтение лишь к одному значению в пару байт.

2. Предыдущий пункт не только про cache misses, но и «локальность данных». Как повышающую производительность, так и приводящих к false sharing при многопоточном использовании структуры данных.  

3. Необходимо учитывать и размер страницы виртуальной памяти, чтобы снизить «давление» на TLB и уйти от TLB miss.

Для пример, в нагруженных системах используется донастройка системы на huge pages, например, все кто используют модный #DPDK сам по себе или с каким-нибудь #Seastar:

• Выбравшие не оригинальную #Kafka, а её более производительный аналог #RedPanda.
• Использующие вместо Apache #Cassandra более производительную #ScyllaDB

Голая теория computer science это хорошо и замечательно, но практика омерзительна свой приземлённостью. Прямой проход перебором по небольшому массиву оказывается быстрее, чем использование binary search tree. И совершенно не важно какого именно красно-чёрного или же АВЛ.

Это не вопрос ретроградства и вызова 40-летней теории :)

#software #SoftwareDevelopment #программирование #разработка #programming @russian_mastodon @ru @Russia