Несерьёзный Выдумщик<p>Открытие Эндрю Крапивина о хеш-таблицах и микро-указателях?<br>Чисто гипотетически, может и актуально, но лишь в чистой и голой computer science теории.<br>На практике же полно нюансов реализации, сводящихся к оптимизациям конкретных аппаратных платформ.</p><p>Например, есть <a class="hashtag" href="https://idealists.su/tag/swisstable" rel="nofollow noopener noreferrer" target="_blank">#SwissTable</a> известные с 2018 года, недавно <a class="hashtag" href="https://idealists.su/tag/golang" rel="nofollow noopener noreferrer" target="_blank">#Golang</a> перешёл на них (с версии 1.24). И до него на SwissTable перейти успел <a class="hashtag" href="https://idealists.su/tag/rust" rel="nofollow noopener noreferrer" target="_blank">#Rust</a>.</p><p>Хеш-таблицы Google <a href="https://abseil.io/about/design/swisstables" rel="nofollow noopener noreferrer" target="_blank">SwissTable</a> и Facebook <a href="https://github.com/facebook/folly/blob/main/folly/container/F14.md" rel="nofollow noopener noreferrer" target="_blank">F14</a> примерно одинаковые, одно лишь вариант другого.</p><p>Идея оптимизации работы вокруг использования <a class="hashtag" href="https://idealists.su/tag/simd" rel="nofollow noopener noreferrer" target="_blank">#SIMD</a> инструкций для поиска занятых ячеек и проверки ключа. И в тотально подавляющем большинстве случаев хватает одной проверки блока из восьми элементов.</p><p>Надо ещё много раз поиграться с вариантами реализации какой-либо идеи из чистого computer science. Посмотрев как оно ложится на аппаратную платформу сродни x86-64.</p><ol><li><p>Есть <a href="https://en.wikipedia.org/wiki/Cache_prefetching" rel="nofollow noopener noreferrer" target="_blank">prefetching</a> памяти и работа с ОЗУ идёт через загрузку целиком всей <a href="https://en.wikipedia.org/wiki/CPU_cache#Cache_entries" rel="nofollow noopener noreferrer" target="_blank">cache line</a> в ЦПУ, даже при обращении <strong>на чтение</strong> лишь к одному значению в пару байт.</p></li><li><p>Предыдущий пункт не только про cache misses, но и «локальность данных». Как повышающую производительность, так и приводящих к false sharing при многопоточном использовании структуры данных. </p></li><li><p>Необходимо учитывать и размер страницы виртуальной памяти, чтобы снизить «давление» на TLB и уйти от <a href="https://en.wikipedia.org/wiki/Translation_lookaside_buffer#TLB-miss_handling" rel="nofollow noopener noreferrer" target="_blank">TLB miss</a>.</p></li></ol><p>Для пример, в нагруженных системах используется донастройка системы на huge pages, например, все кто используют модный <a class="hashtag" href="https://idealists.su/tag/dpdk" rel="nofollow noopener noreferrer" target="_blank">#DPDK</a> сам по себе или с каким-нибудь <a class="hashtag" href="https://idealists.su/tag/seastar" rel="nofollow noopener noreferrer" target="_blank">#Seastar</a>:</p><ul><li>Выбравшие не оригинальную <a class="hashtag" href="https://idealists.su/tag/kafka" rel="nofollow noopener noreferrer" target="_blank">#Kafka</a>, а её более производительный аналог <a class="hashtag" href="https://idealists.su/tag/redpanda" rel="nofollow noopener noreferrer" target="_blank">#RedPanda</a>.</li><li>Использующие вместо Apache <a class="hashtag" href="https://idealists.su/tag/cassandra" rel="nofollow noopener noreferrer" target="_blank">#Cassandra</a> более производительную <a class="hashtag" href="https://idealists.su/tag/scylladb" rel="nofollow noopener noreferrer" target="_blank">#ScyllaDB</a></li></ul><p>Голая теория computer science это хорошо и замечательно, но практика омерзительна свой приземлённостью. Прямой проход перебором по небольшому массиву оказывается быстрее, чем использование binary search tree. И совершенно не важно какого именно красно-чёрного или же АВЛ.</p><p>Это не вопрос ретроградства и вызова 40-летней теории :)</p><p><a class="hashtag" href="https://idealists.su/tag/software" rel="nofollow noopener noreferrer" target="_blank">#software</a> <a class="hashtag" href="https://idealists.su/tag/softwaredevelop" rel="nofollow noopener noreferrer" target="_blank">#SoftwareDevelop</a> <a class="hashtag" href="https://idealists.su/tag/программирование" rel="nofollow noopener noreferrer" target="_blank">#программирование</a> <a class="hashtag" href="https://idealists.su/tag/разработка" rel="nofollow noopener noreferrer" target="_blank">#разработка</a> <a class="hashtag" href="https://idealists.su/tag/programming" rel="nofollow noopener noreferrer" target="_blank">#programming</a> <span class="h-card"><a class="u-url mention" href="https://mastodon.social/@russian_mastodon" rel="nofollow noopener noreferrer" target="_blank">@<span>russian_mastodon</span></a></span> <span class="h-card"><a class="u-url mention" href="https://lor.sh/@ru" rel="nofollow noopener noreferrer" target="_blank">@<span>ru</span></a></span> <span class="h-card"><a class="u-url mention" href="https://3zi.ru/@Russia" rel="nofollow noopener noreferrer" target="_blank">@<span>Russia</span></a></span></p>