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

177

17 октября 2019, 12:50

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

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

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

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

Answer 1

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

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

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

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