Засада с эквивалентным ключом в std::unordered_map
От: Videoman Россия https://hts.tv/
Дата: 16.10.24 19:55
Оценка:
Вводные:
— С++ 17
снаружи приходят по умолчанию собранные std::unordered_map<std::string, SomeClass> (используют стандартный компаратор, это важно)

После кучи профилирования и оптимизаций бутылочного горла, сужение переместилось в место поиска по мапе, типа такого:
std::unordered_map<std::string, some_class> object; // 1
...
const auto& name = "constant string"sv; // 2
...
const auto it = object.find(std::string(name)); // 3
В строчке (3) приходится формировать строку, т.к. код создания unordered_map внешний по отношению к функции и мне не подвластен (std::less<void>, custom_allocator::is_transparent). При этом, name это всегда-всегда гарантированно константная строка. Обидно, что только для того, что бы вызвать метод поиска, приходится создавать полную строку std::string, на чем есть существенные потери тактов.

Может кто-то из спецов подскажет, можно тут что-то сделать не меняя сильно всё ?
Re: Засада с эквивалентным ключом в std::unordered_map
От: Великий Реверс google
Дата: 16.10.24 20:22
Оценка:
глобально ключ заменить ссылкой не?
ну как другой вариант делать move для find
Re[2]: Засада с эквивалентным ключом в std::unordered_map
От: Videoman Россия https://hts.tv/
Дата: 16.10.24 20:30
Оценка:
Здравствуйте, Великий Реверс, Вы писали:

ВР>глобально ключ заменить ссылкой не?

ВР>ну как другой вариант делать move для find

Если можно, приведи пример? Не понял ни первое ни второе предложение.
Re[3]: Засада с эквивалентным ключом в std::unordered_map
От: Великий Реверс google
Дата: 16.10.24 20:33
Оценка:
1)
у тебя ключ в контейнере стринг
сделай ключ стринг ссылка
стандартный или свой референс какой то придумай

2)
object.find(std::move(str));
Re[4]: Засада с эквивалентным ключом в std::unordered_map
От: Videoman Россия https://hts.tv/
Дата: 16.10.24 21:01
Оценка:
Здравствуйте, Великий Реверс, Вы писали:

ВР>1)

ВР>у тебя ключ в контейнере стринг
ВР>сделай ключ стринг ссылка
ВР>стандартный или свой референс какой то придумай

Я в условиях записал, что не могу, т.к. снаружи приходит std::unordered_map<std::string, some_class>, с std::string.

ВР>2)

ВР>object.find(std::move(str));

Этот код эквивалентен object.find(str), т.к. find на вход принимает константную ссылку.
Re: Засада с эквивалентным ключом в std::unordered_map
От: T4r4sB Россия  
Дата: 16.10.24 21:03
Оценка: +3 -1
Здравствуйте, Videoman, Вы писали:

V>Может кто-то из спецов подскажет, можно тут что-то сделать не меняя сильно всё ?


Ну такой вот калечный интерфейс у мапы, но ты не переживай, до комитета ВНИЗАПНА дошло, что они опять обосрались: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0919r2.html
Лет через 10 это войдёт в стандарт
Конкретно в твоём случае ключ всегда один и тот же , можно один раз создать строку и запомнить
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re: Засада с эквивалентным ключом в std::unordered_map
От: andyp  
Дата: 16.10.24 21:03
Оценка: +3
Здравствуйте, Videoman, Вы писали:

V>Вводные:

V>- С++ 17
V>- снаружи приходят по умолчанию собранные std::unordered_map<std::string, SomeClass> (используют стандартный компаратор, это важно)

V>После кучи профилирования и оптимизаций бутылочного горла, сужение переместилось в место поиска по мапе, типа такого:
V>std::unordered_map<std::string, some_class> object; // 1
V>...
V>const auto& name = "constant string"sv; // 2
V>...
V>const auto it = object.find(std::string(name)); // 3
V>
В строчке (3) приходится формировать строку, т.к. код создания unordered_map внешний по отношению к функции и мне не подвластен (std::less<void>, custom_allocator::is_transparent). При этом, name это всегда-всегда гарантированно константная строка. Обидно, что только для того, что бы вызвать метод поиска, приходится создавать полную строку std::string, на чем есть существенные потери тактов.


Для сравнения строк внутри unordered_map используется равенство, а не меньше, так как ключи хешируются и поиск сначала идёт по хешам ключей, а затем по ключам с равным хешем линейным просмотром. У твоей строки сначала все равно считается хеш.

Чтобы сэкономить нужен c++20, прозрачный компаратор и хешер, что для std::string скорее всего выполняется. Так что, думаю у тебя не 20е плюсы.


V>Может кто-то из спецов подскажет, можно тут что-то сделать не меняя сильно всё ?


Не спец, но может, если есть контроль над (2), там статическую строку запилить? Будет только один вызов конструктора строки при первом входе в функцию, сэкономишь один вызов конструктора при вызове find.
Re: Засада с эквивалентным ключом в std::unordered_map
От: sergii.p  
Дата: 17.10.24 10:57
Оценка: 4 (1)
Здравствуйте, Videoman, Вы писали:

V>Вводные:

V>- С++ 17
V>- снаружи приходят по умолчанию собранные std::unordered_map<std::string, SomeClass> (используют стандартный компаратор, это важно)

вроде классический костыль — завести дублирующую мапу

using map_t = std::unordered_map<std::string, SomeClass>;
map_t object;
std::unordered_map<std::string_view, map_t::iterator> ref_object;


понятно, что бред. Но если надо, значит надо.
Re[2]: Засада с эквивалентным ключом в std::unordered_map
От: andyp  
Дата: 17.10.24 11:58
Оценка: 2 (1)
Здравствуйте, T4r4sB, Вы писали:

TB>Здравствуйте, Videoman, Вы писали:


V>>Может кто-то из спецов подскажет, можно тут что-то сделать не меняя сильно всё ?


TB>Ну такой вот калечный интерфейс у мапы, но ты не переживай, до комитета ВНИЗАПНА дошло, что они опять обосрались: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0919r2.html

TB>Лет через 10 это войдёт в стандарт

Да там проблема в том, что интерфейс unordered_map пытались запилить такой же как у map. Чтобы была возможность легко заменять одно на другое в коде. А надо было для этих целей лишних адаптеров сделать имхо. Вот сейчас в с++20 введут прозрачные хешеры и компараторы, а проблема-то частично останется — ты для того, что ищешь, будешь всегда считать хеш. Платишь за то, что тебе не уперлось из-за кривого интерфейса.
Re[2]: Засада с эквивалентным ключом в std::unordered_map
От: Videoman Россия https://hts.tv/
Дата: 17.10.24 12:12
Оценка:
Здравствуйте, sergii.p, Вы писали:

SP>Здравствуйте, Videoman, Вы писали:


V>>Вводные:

V>>- С++ 17
V>>- снаружи приходят по умолчанию собранные std::unordered_map<std::string, SomeClass> (используют стандартный компаратор, это важно)

SP>вроде классический костыль — завести дублирующую мапу


SP>
SP>using map_t = std::unordered_map<std::string, SomeClass>;
SP>map_t object;
SP>std::unordered_map<std::string_view, map_t::iterator> ref_object;
SP>


Идея понятна и вполне была бы оправдана, но боюсь, у меня не наберется столько поиска, что бы перекрыть затраты на создание дополнительного хеша.
У нас это некий кусок обобщенной десериализации, где всякие JSON подобные форматы сначала десериализуются в std::unordered_map<std::string, value_class>. В другом месте, в нужный момент из std::unordered_map<std::string, value_class> происходит выдергивание типов. Фактически мне нужно один раз пройти по std::unordered_map и выдернуть оттуда значения.
Отредактировано 17.10.2024 12:13 Videoman . Предыдущая версия . Еще …
Отредактировано 17.10.2024 12:13 Videoman . Предыдущая версия .
Re[3]: Засада с эквивалентным ключом в std::unordered_map
От: watchmaker  
Дата: 17.10.24 15:13
Оценка: 19 (2) +1
Здравствуйте, andyp, Вы писали:

A> Вот сейчас в с++20 введут прозрачные хешеры и компараторы, а проблема-то частично останется — ты для того, что ищешь, будешь всегда считать хеш. Платишь за то, что тебе не уперлось из-за кривого интерфейса.


Интерфейс, конечно, кривой. Но прозрачные хэши как раз уже сейчас позволяют не считать хэш повторно от констант.

В программе ты сам делаешь выбор: считать ли хэш от string_view каждый раз, либо посчитать его однажды и положить рядом:
// строка + хэш
struct hashed_string_view: std::string_view {
    constexpr hashed_string_view(std::string_view v);
    size_t cached_hash = 0;
};

Так потратишь несколько лишних байт, но зато вычисление хэша очень будет быстрым: return this->cached_hash;. Это бывает само по себе полезно, например, когда ключи большие и хэш от них считается медленно.

И в комбинации с прозрачным хэшированием такой класс отлично работает:
struct string_hash {
    using is_transparent = void;
    constexpr std::size_t operator()(const std::string_view str) const { return my_hash_impl(str); }   // вычисляем хэш динамически
    constexpr std::size_t operator()(const hashed_string_view& str) const { return str.cached_hash; }  // достаём предпосчитанное значение
};

consteval hashed_string_view operator""_svh(const char* str, size_t len) {
    return hashed_string_view{std::string_view{str, len}};
}


Теперь, если использовать string_hash в качестве хэшера для мапы, то от констант значение хэша будет посчитано сразу:
std::unordered_multimap<std::string, ValueType, string_hash, std::equal_to<>> map;

auto it = map.find("key"_svh);
Демо и сравнение.

A> проблема-то частично останется


Хотя упрёк справедливый, потому из коробки не работает:
  1. В старом коде нужно включать поддержку прозрачности явно из-за параноидальной обратной совместимости;
  2. Готового mixin-класса для кэширования хэшей в стандартной библиотеки нет;
  3. Хэш функцию тоже нужно подставлять свою, из-за возможности рандомизации std::hash<string_view>, из-за чего её в общем случае нельзя вычислять от константных литералов во время компиляции (и не важно, что никто этой возможностью не пользуется) .
Каждый пункт решается в одну-две строчки, но этого уже достаточно, чтобы куча кода так и оставалось работать с неэффективными значениями по умолчанию.
Отредактировано 17.10.2024 18:35 watchmaker . Предыдущая версия .
Re[3]: Засада с эквивалентным ключом в std::unordered_map
От: T4r4sB Россия  
Дата: 17.10.24 15:15
Оценка:
Здравствуйте, andyp, Вы писали:



A>Да там проблема в том, что интерфейс unordered_map пытались запилить такой же как у map. Чтобы была возможность легко заменять одно на другое в коде.


Так у мапы тоже непонятно, почему нельзя делать поиск по стрингвью без конструирования строки.
А подсчет хеша на фоне лишних созданий строки — считай бесплатен.

Так что если это допустимо в проекте — то использовать альтернативную хешмапу. Если не требуется чтоб элементы сохраняли свой адрес, то наверное любая альтернативная мапа будет быстрее стдшной
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[4]: Засада с эквивалентным ключом в std::unordered_map
От: so5team https://stiffstream.com
Дата: 17.10.24 16:30
Оценка: +1
Здравствуйте, T4r4sB, Вы писали:

A>>Да там проблема в том, что интерфейс unordered_map пытались запилить такой же как у map. Чтобы была возможность легко заменять одно на другое в коде.


TB>Так у мапы тоже непонятно, почему нельзя делать поиск по стрингвью без конструирования строки.


Можно начиная с С++14 (https://en.cppreference.com/w/cpp/container/map/find).
Нужно только std::less<> в качестве компаратора не забывать явно вписывать.

А вот с хэш-таблицами нужно ждать новых стандартов.
Re[4]: Засада с эквивалентным ключом в std::unordered_map
От: andyp  
Дата: 17.10.24 17:42
Оценка:
Здравствуйте, watchmaker, Вы писали:

со всем согласен!

W>
  • Готового mixin-класса для кэширования хэшей в стандартной библиотеки нет;

    Ну да, это плохо. У меня всегда есть опасения, что в контейнере окажется другой хешер
  • Re[3]: Засада с эквивалентным ключом в std::unordered_map
    От: · Великобритания  
    Дата: 17.10.24 21:50
    Оценка: +2
    Здравствуйте, Videoman, Вы писали:

    V> У нас это некий кусок обобщенной десериализации, где всякие JSON подобные форматы сначала десериализуются в std::unordered_map<std::string, value_class>. В другом месте, в нужный момент из std::unordered_map<std::string, value_class> происходит выдергивание типов. Фактически мне нужно один раз пройти по std::unordered_map и выдернуть оттуда значения.

    А зачем вообще тогда sv? Константы инициализируются только один раз, этим и пользуемся:
    const auto& name = std::string("constant string");
    ...
    const auto it = object.find(name);


    Ещё как вариант: вместо создания новой строки — создать её один раз, зарезервировав размер по максимуму, и потом переприсваивать. Как я понимаю, основные тормоза обычно идут не на копирование байтов, а на выделение-удаление динамической памяти из кучи.
    avalon/3.0.0
    но это не зря, хотя, может быть, невзначай
    гÅрмония мира не знает границ — сейчас мы будем пить чай
    Re[3]: Засада с эквивалентным ключом в std::unordered_map
    От: landerhigh Пират  
    Дата: 18.10.24 14:46
    Оценка:
    Здравствуйте, Videoman, Вы писали:

    V>Идея понятна и вполне была бы оправдана, но боюсь, у меня не наберется столько поиска, что бы перекрыть затраты на создание дополнительного хеша.

    V>У нас это некий кусок обобщенной десериализации, где всякие JSON подобные форматы сначала десериализуются в std::unordered_map<std::string, value_class>. В другом месте, в нужный момент из std::unordered_map<std::string, value_class> происходит выдергивание типов. Фактически мне нужно один раз пройти по std::unordered_map и выдернуть оттуда значения.

    В таком случае возникает закономерный вопрос — а существует ли оно, это бутылочное горлышко, на самом деле? Или видно исключительно в профайлере?
    www.blinnov.com
    Re: Засада с эквивалентным ключом в std::unordered_map
    От: Ip Man Китай  
    Дата: 20.10.24 14:45
    Оценка:
    https://www.cppstories.com/2021/heterogeneous-access-cpp20/
    Re[4]: Засада с эквивалентным ключом в std::unordered_map
    От: Videoman Россия https://hts.tv/
    Дата: 20.10.24 17:36
    Оценка:
    Здравствуйте, ·, Вы писали:

    ·>А зачем вообще тогда sv? Константы инициализируются только один раз, этим и пользуемся:


    Получается, в рамках С++17, это единственный вариант без просадки производительности. Но пользоваться константами не очень удобно, думал может быть есть варианты получше.
    Re[5]: Засада с эквивалентным ключом в std::unordered_map
    От: · Великобритания  
    Дата: 21.10.24 09:40
    Оценка: +1
    Здравствуйте, Videoman, Вы писали:

    V>·>А зачем вообще тогда sv? Константы инициализируются только один раз, этим и пользуемся:

    V>Получается, в рамках С++17, это единственный вариант без просадки производительности. Но пользоваться константами не очень удобно, думал может быть есть варианты получше.
    А в чём недостатки этого варианта?

    А вообще, конечно, смешно. Парсим охрененно избыточный медленный json и экономим на спичках, считая байты... Хочешь перформанс — бери SBE или protobuf хотя бы.
    но это не зря, хотя, может быть, невзначай
    гÅрмония мира не знает границ — сейчас мы будем пить чай
    Re[6]: Засада с эквивалентным ключом в std::unordered_map
    От: watchmaker  
    Дата: 21.10.24 14:51
    Оценка:
    Здравствуйте, ·, Вы писали:

    ·>А вообще, конечно, смешно. Парсим охрененно избыточный медленный json и экономим на спичках, считая байты... Хочешь перформанс — бери SBE или protobuf хотя бы.


    Забавно, но если сравнивать самые быстрые парсеры, то simdjson выигрывает у protobuf, даже несмотря на то, что парсить ему приходится куда более объёмный сериализованный текст.
    Бинарный формат protobuf отравлен varint'ами — в нём для чтения очередного поля нужно разобрать предыдущее — и ни у кого не получается это место хорошо на уровне инструкций распараллелить.

    Но, совет всё равно хороший, так как и другое, скорее всего, будет работать на порядок быстрее чем самодельный парсер с std::unordered_map внутри.
    Подождите ...
    Wait...
    Пока на собственное сообщение не было ответов, его можно удалить.