Контейнеры map/set и кэш процессора

#cpp #оптимизация #stl #cpp17

В книге Артур О'Двайр "Осваиваем C++17 STL"



на стр.104 наткнулся на удивительное заявление:


  Мудрость, накопленная в пост-C++11 мире, гласит, что std::map и
  std::set, будучи основанными на деревьях указателей, настолько
  недружественные к кешу процессора, что их всегда желательно избегать и
  взамен использовать std::unordered_map и std::unordered_set.


Рекомендация использовать хеш таблицы вместо сбалансированных деревьев вне зависимости
от контекста использования настолько сомнительна, что ее вряд ли имеет смысл обсуждать.
Интереснее фраза, что якобы хеш-таблицы гораздо лучше деревьев вписываются в кеш. У
меня по этому поводу возник вопрос - это действительно так? В самом деле существует
какая-то достоверная статистика, или же это очередное открытие британских ученых?
    

Ответы

Ответ 1

При однократном поиске в хэш-таблице без синонимов будет прочитано 2 линии кэша (если
так получилось, что данные по выравниванию не поместились в одну линию, то 3 линии
кэша), а для дерева очевидно, что больше, особенно если в узлах дерева хранятся указатели
на ключи (а не сами ключи). 

Если поисков много, активность (в смысле количества активных процессов в системе,
которые будут "вымывать" ваши данные из кэша) низкая, то искомые данные для обеих структур
окажутся в кэше и повторные поиски будут быстрее. 

Но и здесь, очевидно, что хэш-таблица будет быстрее.

Интересно, что для маленького дерева, которое вместе с данными (ключами) размещается
в 2-х последовательных линиях кэша (128 байт, последовательно размещенными в памяти
с адреса, кратного 64) даже 4 обращения к памяти (корень, ключ в корне, потомок, его
ключ) могут занять меньше времени, чем 2 обращения к памяти для хэш-таблицы (там наверняка
указатель из таблицы и данные будут сильно разнесены по адресам), поскольку ОС может
устанавливить политику доступа к кэшу для опережающего последовательного чтения линий кэша.