[prog.c++] Попробовал было сделать что-то вроде small object optimization с использованием std::pmr::monotonic_buffer_resource...

...но что-то пошло не совсем так.

Был у меня объект со словарем внутри. Что-то вроде:

struct info_t {...}; using info_map_t = std::map<key_t, info_t>; class info_holder_t {   ... private:   info_map_t m_infos;   ... };

Захотелось немного оптимизировать этот info_holder_t::m_infos. Дело в том, что сбор статистики по реальному использованию info_holder_t показал, что в подавляющем большинстве случаев (сильно больше 95%) в m_infos хранится либо один, либо два экземпляра info_t.

Более того, была еще одна очень важная особенность: в абсолютном большинстве случаев m_infos только наполняется, ничего оттуда не удаляется до самого уничтожения info_holder_t.

Вот я и подумал, что std::map -- это же дерево, где каждый узел -- это динамически созданный объект. А new/delete не самые дешевые операции. Что, если завести в info_holder_t буфер под два info_map_t::value_type и "выделять" память оттуда? А уже когда этот буфер исчерпается, переходить на использование обычных new/delete.

При этом очень и очень хотелось сохранить реализацию основных методов info_holder_t прежней. Т.е. если бы остался именно m_infos типа info_map_t, то это было бы идеально. А вот если бы вместо m_infos оказался какой-то std::variant, в котором был бы отдельный кейс для крошечного словаря, и отдельный кейс для полноценного std::map, то пришлось бы перелопатить более тысячи строк уже отлаженного и проверенного на разных сценариях кода, что не вселяло оптимизма.

Оказалось, что благодаря std::pmr такой оптимизированный std::map можно сделать с минимальными усилиями. Всего-то нужно:

struct info_t {...}; // Вместо просто std::map теперь std::pmr::map. using info_map_t = std::pmr::map<key_t, info_t>; class info_holder_t {   ... private:   // Локальный буфер.   std::array<std::byte, какой-то-размер> m_small_map_fixed_buffer;   // То, что будет превращать m_small_map_fixed_buffer в арену   // памяти для m_infos.   std::pmr::monotonic_buffer_resource m_infos_memory_resource{     m_small_map_fixed_buffer.data(), m_small_map_fixed_buffer.size()   };   // Модицифированный словарь.   info_map_t m_infos{ std::addressof(m_infos_memory_resource) };   ... };

Получается, что для первых нескольких элементов в m_infos память "выделяется" из m_small_map_fixed_buffer через m_infos_memory_resource. А если элементов становится больше, то m_infos_memory_resource сам обращается к динамической памяти посредством std::pmr::get_default_resource. Как раз то, что мне было нужно.

Казалось бы, золотой ключик уже в кармане.

Но есть несколько "Но".

Во-первых, какое выравнивание должно быть у m_small_map_fixed_buffer?

Во-вторых, какой же размер должен быть у m_small_map_fixed_buffer?

Оба эти вопроса упираются в то, что std::map::value_type -- это же не реальный тип узла дерева. Это только тип того, что внутри дерева поиска содержится. Но кроме этого в узле должны быть еще и какие-то указатели (по крайней мере на дочерние узлы и, вероятно, на родительский узел).

Поскольку реальный тип узла дерева std::map наружу никак не выставляет, а код должен работать на разных ОС и собираться разными компиляторами, то хороших ответов на эти вопросы я лично не вижу.

И если с выравниванием есть надежное (но может и не оптимальное) решение:

// Локальный буфер. alignas(std::max_align_t) std::array<std::byte, какой-то-размер> m_small_map_fixed_buffer;

То вот с размером этого буфера начинаются какие-то пляски с бубном. Для эксперимента просто взял (sizeof(info_map_t::value_type) * 10)), этого хватило, чтобы сделать замеры производительности.

И вот замеры удивили еще больше, чем необходимость искать ответы на два озвученных выше вопроса: на простеньком бенчмарке, который был сделан для проверки гипотезы о выгоде подобной оптимизации, оказалось, что связка из буфера и monotonic_buffer_resource не дает никакого выигрыша по сравнению с первоначальной простой реализацией. Т.е. и там, и там при добавлении в m_infos одного-двух элементов время работы бенчмарка оказывается практически одинаковым.

Полагаю, здесь сказывается несколько факторов:

• в проекте уже используется mimalloc, а он делает операции new/delete очень быстрыми. Особенно когда и new, и delete происходят на контексте одной и той же нити (что и имело место для моего info_holder-а);
• появление в info_holder-е дополнительной "начинки", которая требует инициализации (речь про конструктор std::pmr::monotonic_buffer_resource и передачу указателя на него в m_infos) утяжеляет процедуру создания info_holder_t. Плюс к тому, работа monotonic_buffer_resource все же не бесплатна.

Добавлю сюда два обозначенных выше вопроса, хороших ответов на которые у меня нет, и получаю, что простая попытка сделать small object optimization на базе std::pmr::monotonic_buffer_resource завершилась с отрицательным результатом.

PS. Вообще, идея std::pmr, на первый взгляд, очень простая и красивая. Кажется, что разобраться с этим не так уж и сложно. Но, как обычно в C++, кроличья нора гораздо глубже, чем кажется.

[prog.c++] Простой способ ускорить поиск в map/unordered_map в случае "тяжелых" ключей

Все знают про наличие в std::map/unordered_map методов find. Но, наверное, не все знают, что у этого find-а есть несколько вариантов. Кроме старого и привычного:

iterator find( const Key& key );

В std::map начиная с C++14 есть еще и:

template< class K > iterator find( const K& x );

А в std::unordered_map второй вариант find-а был добавлен в C++20.

Что же следует из того, что в find можно передать не Key, которым мы параметризовали свой map/unordered_map, а какой-то другой тип?

Следует то, что мы можем сделать поиск в map/unordered_map более эффективным если тип Key дорог в конструировании, например, когда внутри Key есть std::string-и или другие типы, динамически выделяющие и освобождающие память.

Недавно мне довелось столкнуться с ситуацией, когда ключом поиска был тип вроде вот такого:

using full_key_t = std::pair<std::size_t, std::string>;

Соответственно, поиск выполнялся как-то так:

const auto id = get_id(...); const std::string & description = get_description(...); if(const auto it = _map.find(full_key_t{id, description}); it != _map.end()) {   ... }

Проблема в том, что экземпляр full_key_t нужно полностью сконструировать. А значит нужно сделать полную копию description и поместить эту копию в новый объект full_key_t. Что недешево. И, что особенно обидно, объект full_key_t разрушается сразу после завершения поиска. Т.е. мы создаем временный ключ, тратим на это время, а затем тупо выбрасываем временный ключ за ненадобностью.

К счастью, упомянутые выше "новые" варианты find-а позволяют нам избежать создания "тяжелых" экземпляров full_key_t. Теперь в C++ можно делать вот так:

using light_key_t = std::pair<std::size_t, const std::string*>; ... const auto id = get_id(...); const std::string & description = get_description(...); if(const auto it = _map.find(light_key_t{id, &description}); it != _map.end()) {   ... }

Однако, чтобы это работало, нужно сделать несколько дополнительных телодвижений. Давайте рассмотрим их на примере std::unordered_map.

Первое, что нам потребуется -- это такой тип хэш-функции, который будет применим как к full_key_t, так и к light_key_t. Поскольку обычно хэш для unordered_map -- это структура со специально написанным operator(), то мы можем просто сделать несколько перегрузок operator():

struct special_hash_t {    using is_transparent = void;    std::size_t    operator()(const full_key_t & k) const noexcept    {       return std::hash<std::size_t>{}(k.first) + 0x9e3779b9 +             std::hash<std::string>{}(second_key_part(k));    }    std::size_t    operator()(const light_key_t & k) const noexcept    {       return std::hash<std::size_t>{}(k.first) + 0x9e3779b9 +             std::hash<std::string>{}(second_key_part(k));    } };

Где second_part_key -- это вспомогательные функции вида:

[[nodiscard]] const std::string & second_key_part(const full_key_t & k) noexcept {    return k.second; } [[nodiscard]] const std::string & second_key_part(const light_key_t & k) noexcept {    return *(k.second); }

Внутри special_hash_t можно было обойтись и без них, но вот на следующем шаге они нам сильно помогут.

А следующим шагом будет определение собственного компаратора, который может сравнивать full_key_t и light_key_t на равенство. Этот компаратор мы подсунем std::unordered_map в качестве параметра шаблона KeyEqual. Для нашего примера компаратор может выглядеть так:

struct special_equal_to_t {    using is_transparent = void;    template<typename K1, typename K2>    bool    operator()(const K1 & k1, const K2 & k2) const noexcept    {       return (k1.first == k2.first) &&             (second_key_part(k1) == second_key_part(k2));    } };

За счет того, что в special_equal_to_t у нас operator() -- это шаблон метода, то он может принимать разные сочетания: как full_key_t с light_key_t, так и light_key_t с full_key_t. Здесь функции second_key_part помогают избежать дублирования кода.

Ключевой момент в этом всем -- это наличие определения is_transparent в special_key_t и special_equal_to_t. Без такого вложенного типа вся обсуждаемая машинерия с "новыми" find работать не будет. Причем, если забыть определить is_transparent, то компилятор может выдать такую простыню невнятных сообщений об ошибках, что причина проблемы будет совершенно непонятна (тут, конечно же от степени вменяемости компилятора зависит).

Далее остается просто определить тип нужного нам unordered_map:

using values_map_t = std::unordered_map<       full_key_t,       your_value_type,       special_hash_t,       special_equal_to_t>;

Какой же выигрыш дает этот трюк и дает ли вообще?

Если строковые ключи поиска короткие, т.е. срабатывает small string optimization (SSO), то практически не дает. Но вот если строчки достаточно длинные, чтобы SSO остался не у дел, то разница почти в два раза по моим замерам.

Под катом полнофункциональная программка, которая демонстрирует данный подход. Так вот, на i7-8550U с VC++ из VisualStudio 17.4.0 она выдает, например, следующие результаты:

*** find_by_full_key: 1512721us ***
values found: 10000000
*** find_by_light_key: 844164us ***
values found: 10000000

Тогда как MinGW 13.2.0 на той же машине показывает время чуть получше и все равно с почти что двухкратным разрывом:

*** find_by_full_key: 1137556us ***
values found: 10000000
*** find_by_light_key: 557952us ***
values found: 10000000

Так что трюк вполне себе рабочий. Но есть с ним две небольшие проблемки:

• про него легко забыть, особенно когда голова забита решением прикладных проблем, а глаз уже "замылился";
• нужно помнить про вложенный тип is_transparent, без него не работает, а компилятор своими сообщениями может только запутать.

Собственно, данный пост возник для того, чтобы зафиксировать этот трюк в склерознике (в особенности его часть про is_transparent).