Fosstodon

HabrGo 1.24: принципы работы и преимущества обновленной mapВ феврале 2025 года разработчики Go выпустили версию 1.24, в которой значительно улучшили производительность языка. Одно из ключевых изменений коснулось структуры map — встроенного типа данных, предназначенного для хранения и быстрого поиска значений по уникальному ключу. Новая реализация повысила эффективность работы map, оптимизировала использование памяти и ускорила операции поиска, вставки и удаления элементов. Привет, Хабр. Мы backend-разработчики SimbirSoft Павел и Алексей. В этой статье подробно разберём, как именно изменился механизм работы map и какие преимущества это даёт. Go🚀<a href="https://habr.com/ru/companies/simbirsoft/articles/899180/" rel="nofollow noopener" translate="no" target="_blank">https://habr.com/ru/companies/simbirsoft/articles/899180/</a><a href="https://zhub.link/tags/go" class="mention hashtag" rel="nofollow noopener" target="_blank">#go</a> <a href="https://zhub.link/tags/golang" class="mention hashtag" rel="nofollow noopener" target="_blank">#golang</a> <a href="https://zhub.link/tags/%D0%B0%D1%80%D1%85%D0%B8%D1%82%D0%B5%D0%BA%D1%82%D1%83%D1%80%D0%B0" class="mention hashtag" rel="nofollow noopener" target="_blank">#архитектура</a> <a href="https://zhub.link/tags/backend" class="mention hashtag" rel="nofollow noopener" target="_blank">#backend</a> <a href="https://zhub.link/tags/go_124" class="mention hashtag" rel="nofollow noopener" target="_blank">#go_124</a> <a href="https://zhub.link/tags/map" class="mention hashtag" rel="nofollow noopener" target="_blank">#map</a> <a href="https://zhub.link/tags/swisstable" class="mention hashtag" rel="nofollow noopener" target="_blank">#swisstable</a> <a href="https://zhub.link/tags/hashmap" class="mention hashtag" rel="nofollow noopener" target="_blank">#hashmap</a> <a href="https://zhub.link/tags/%D0%BE%D0%B1%D0%B7%D0%BE%D1%80_%D1%84%D0%B8%D1%87%D0%B5%D0%B9" class="mention hashtag" rel="nofollow noopener" target="_blank">#обзор_фичей</a>

HabrБолее быстрые хеш-таблицы: претенденты на место SwissTable24 ноября 2021 года на сайте ArXiv.org была опубликована научная статья «Крошечные указатели» ( Tiny Pointers ) с описанием новой структуры данных — «крошечных» указателей, которые указывают путь к фрагменту хранимых данных и занимают меньше памяти, чем традиционные указатели. Осенью 2021 года эту статью заметил Андрей Крапивин (Andrew Krapivin), студент Ратгерского университета в Нью-Джерси, и не придал ей особого значения, пишет Quanta Magazine, журнал о последних достижениях в математике ( перевод статьи на Хабре). Только через два года он нашёл время, чтобы внимательно ознакомиться с материалом. И понял, насколько это прорывное изобретение, если применить его для оптимизации хеш-таблиц. Данная тема уже упоминалась на Хабре , но заслуживает более подробного обсуждения.<a href="https://habr.com/ru/companies/ruvds/articles/887726/" rel="nofollow noopener" translate="no" target="_blank">https://habr.com/ru/companies/ruvds/articles/887726/</a><a href="https://zhub.link/tags/ruvds_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8" class="mention hashtag" rel="nofollow noopener" target="_blank">#ruvds_статьи</a> <a href="https://zhub.link/tags/%D1%85%D0%B5%D1%88%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B" class="mention hashtag" rel="nofollow noopener" target="_blank">#хештаблицы</a> <a href="https://zhub.link/tags/%D0%BD%D0%B0%D1%83%D0%BA%D0%B0_%D0%BE_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85" class="mention hashtag" rel="nofollow noopener" target="_blank">#наука_о_данных</a> <a href="https://zhub.link/tags/%D0%BA%D1%80%D0%BE%D1%88%D0%B5%D1%87%D0%BD%D1%8B%D0%B5_%D1%83%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D0%B8" class="mention hashtag" rel="nofollow noopener" target="_blank">#крошечные_указатели</a> <a href="https://zhub.link/tags/%D0%B0%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2" class="mention hashtag" rel="nofollow noopener" target="_blank">#ассоциативный_массив</a> <a href="https://zhub.link/tags/%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85" class="mention hashtag" rel="nofollow noopener" target="_blank">#структура_данных</a> <a href="https://zhub.link/tags/%D0%BF%D0%BE%D0%B8%D1%81%D0%BA" class="mention hashtag" rel="nofollow noopener" target="_blank">#поиск</a> <a href="https://zhub.link/tags/%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0" class="mention hashtag" rel="nofollow noopener" target="_blank">#вставка</a> <a href="https://zhub.link/tags/%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BA%D0%BE%D1%80%D0%BE%D1%81%D1%82%D1%8C" class="mention hashtag" rel="nofollow noopener" target="_blank">#предельная_скорость</a> <a href="https://zhub.link/tags/%D1%80%D0%B0%D0%B2%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B7%D0%BE%D0%BD%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5" class="mention hashtag" rel="nofollow noopener" target="_blank">#равномерное_зондирование</a> <a href="https://zhub.link/tags/uniform_probing" class="mention hashtag" rel="nofollow noopener" target="_blank">#uniform_probing</a> <a href="https://zhub.link/tags/%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%B7%D0%BE%D0%BD%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5" class="mention hashtag" rel="nofollow noopener" target="_blank">#линейное_зондирование</a> <a href="https://zhub.link/tags/%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D1%81_%D0%BF%D0%BE%D0%B2%D0%BE%D1%80%D0%BE%D1%82%D0%BE%D0%BC" class="mention hashtag" rel="nofollow noopener" target="_blank">#дерево_с_поворотом</a> <a href="https://zhub.link/tags/%D1%80%D0%B0%D1%81%D1%88%D0%B8%D1%80%D1%8F%D1%8E%D1%89%D0%B5%D0%B5%D1%81%D1%8F_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" class="mention hashtag" rel="nofollow noopener" target="_blank">#расширяющееся_дерево</a> <a href="https://zhub.link/tags/%D0%BA%D1%80%D0%B0%D1%81%D0%BD%D0%BE%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" class="mention hashtag" rel="nofollow noopener" target="_blank">#красночёрное_дерево</a> <a href="https://zhub.link/tags/Koloboke" class="mention hashtag" rel="nofollow noopener" target="_blank">#Koloboke</a> <a href="https://zhub.link/tags/SmoothieMap" class="mention hashtag" rel="nofollow noopener" target="_blank">#SmoothieMap</a> <a href="https://zhub.link/tags/ChronicleMap" class="mention hashtag" rel="nofollow noopener" target="_blank">#ChronicleMap</a> <a href="https://zhub.link/tags/SwissTable" class="mention hashtag" rel="nofollow noopener" target="_blank">#SwissTable</a> <a href="https://zhub.link/tags/F14" class="mention hashtag" rel="nofollow noopener" target="_blank">#F14</a> <a href="https://zhub.link/tags/SIMD" class="mention hashtag" rel="nofollow noopener" target="_blank">#SIMD</a>

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

HabrО новых алгоритмах хеш-таблицХотелось бы прокомментировать публикацию Ильи Кабанова в Медузе по поводу новых разработок в алгоритмах хеширования: " Optimal Bounds for Open Addressing Without Reordering " (Farach-Colton, Krapivin, and Kuszmaul, 2025) и последующую " The Bathroom Model: A Realistic Approach to Hash Table Algorithm Optimization " (Wang, 2025). И особенно кликбейтное: "в перспективе метод Крапивина и его коллег может ускорить многие процессы в интернете." Я около 7 лет очень плотно занимался темой хеш-таблиц и написал много их вариантов: Koloboke , SmoothieMap , memory-mapped вариации . Я потерял к теме интерес с выходом гугловской SwissTable (2018), и ее фейсбучного варианта F14 , которые основаны на SIMD. Они проверяют загруженность ячеек и совпадения "тега" элемента сразу блоками по 8 соседних слотов. Поэтому на любых разумных загрузках таблиц (до 90%) - "цепочка проверки" очень редко превышает 1 (то есть, одну проверку 8-элементного блока). В этих SIMD-based алгоритмах, ухищрения и теоретические по поводу "алгоритма шагания" просто не играют никакой роли -- алгоритм шагания можно сказать отсутствует, потому что если можно вставить элемент внутри 8-элементного блока, то это и стоит сделать. Именно эти разработки, а не Крут и не статья Yao, которую "опровергли" новые работы, стали "практическим концом теории" хеш-таблиц, на мой взгляд. SwissTable стали стандартным алгоритмом хеш-таблиц в Расте, и, буквально в этом месяце, в Golang 1.24 . В заключение, отвечая Илье Кабанову: к "ускорению интернета" эти теоретические алгоритмы не приведут :)<a href="https://habr.com/ru/articles/887024/" rel="nofollow noopener" translate="no" target="_blank">https://habr.com/ru/articles/887024/</a><a href="https://zhub.link/tags/%D1%85%D0%B5%D1%88%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B" class="mention hashtag" rel="nofollow noopener" target="_blank">#хештаблицы</a> <a href="https://zhub.link/tags/swisstable" class="mention hashtag" rel="nofollow noopener" target="_blank">#swisstable</a> <a href="https://zhub.link/tags/simd" class="mention hashtag" rel="nofollow noopener" target="_blank">#simd</a>

Recent searches

Search options

Administered by:

Server stats:

#swisstable