Вводные:
— С++ 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
Здравствуйте, Великий Реверс, Вы писали:
ВР>1) ВР>у тебя ключ в контейнере стринг ВР>сделай ключ стринг ссылка ВР>стандартный или свой референс какой то придумай
Я в условиях записал, что не могу, т.к. снаружи приходит std::unordered_map<std::string, some_class>, с std::string.
ВР>2) ВР>object.find(std::move(str));
Этот код эквивалентен object.find(str), т.к. find на вход принимает константную ссылку.
Re: Засада с эквивалентным ключом в std::unordered_map
Здравствуйте, Videoman, Вы писали:
V>Может кто-то из спецов подскажет, можно тут что-то сделать не меняя сильно всё ?
Ну такой вот калечный интерфейс у мапы, но ты не переживай, до комитета ВНИЗАПНА дошло, что они опять обосрались: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0919r2.html
Лет через 10 это войдёт в стандарт
Конкретно в твоём случае ключ всегда один и тот же , можно один раз создать строку и запомнить
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re: Засада с эквивалентным ключом в std::unordered_map
Здравствуйте, 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
Здравствуйте, 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
Идея понятна и вполне была бы оправдана, но боюсь, у меня не наберется столько поиска, что бы перекрыть затраты на создание дополнительного хеша.
У нас это некий кусок обобщенной десериализации, где всякие JSON подобные форматы сначала десериализуются в std::unordered_map<std::string, value_class>. В другом месте, в нужный момент из std::unordered_map<std::string, value_class> происходит выдергивание типов. Фактически мне нужно один раз пройти по std::unordered_map и выдернуть оттуда значения.
Здравствуйте, andyp, Вы писали:
A> Вот сейчас в с++20 введут прозрачные хешеры и компараторы, а проблема-то частично останется — ты для того, что ищешь, будешь всегда считать хеш. Платишь за то, что тебе не уперлось из-за кривого интерфейса.
Интерфейс, конечно, кривой. Но прозрачные хэши как раз уже сейчас позволяют не считать хэш повторно от констант.
В программе ты сам делаешь выбор: считать ли хэш от string_view каждый раз, либо посчитать его однажды и положить рядом:
Так потратишь несколько лишних байт, но зато вычисление хэша очень будет быстрым: return this->cached_hash;. Это бывает само по себе полезно, например, когда ключи большие и хэш от них считается медленно.
И в комбинации с прозрачным хэшированием такой класс отлично работает:
Хотя упрёк справедливый, потому из коробки не работает: В старом коде нужно включать поддержку прозрачности явно из-за параноидальной обратной совместимости;
Готового mixin-класса для кэширования хэшей в стандартной библиотеки нет;
Хэш функцию тоже нужно подставлять свою, из-за возможности рандомизации std::hash<string_view>, из-за чего её в общем случае нельзя вычислять от константных литералов во время компиляции (и не важно, что никто этой возможностью не пользуется) .Каждый пункт решается в одну-две строчки, но этого уже достаточно, чтобы куча кода так и оставалось работать с неэффективными значениями по умолчанию.
A>Да там проблема в том, что интерфейс unordered_map пытались запилить такой же как у map. Чтобы была возможность легко заменять одно на другое в коде.
Так у мапы тоже непонятно, почему нельзя делать поиск по стрингвью без конструирования строки.
А подсчет хеша на фоне лишних созданий строки — считай бесплатен.
Так что если это допустимо в проекте — то использовать альтернативную хешмапу. Если не требуется чтоб элементы сохраняли свой адрес, то наверное любая альтернативная мапа будет быстрее стдшной
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[4]: Засада с эквивалентным ключом в std::unordered_map
Здравствуйте, T4r4sB, Вы писали:
A>>Да там проблема в том, что интерфейс unordered_map пытались запилить такой же как у map. Чтобы была возможность легко заменять одно на другое в коде.
TB>Так у мапы тоже непонятно, почему нельзя делать поиск по стрингвью без конструирования строки.
Здравствуйте, 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);
Ещё как вариант: вместо создания новой строки — создать её один раз, зарезервировав размер по максимуму, и потом переприсваивать. Как я понимаю, основные тормоза обычно идут не на копирование байтов, а на выделение-удаление динамической памяти из кучи.
Здравствуйте, Videoman, Вы писали:
V>Идея понятна и вполне была бы оправдана, но боюсь, у меня не наберется столько поиска, что бы перекрыть затраты на создание дополнительного хеша. V>У нас это некий кусок обобщенной десериализации, где всякие JSON подобные форматы сначала десериализуются в std::unordered_map<std::string, value_class>. В другом месте, в нужный момент из std::unordered_map<std::string, value_class> происходит выдергивание типов. Фактически мне нужно один раз пройти по std::unordered_map и выдернуть оттуда значения.
В таком случае возникает закономерный вопрос — а существует ли оно, это бутылочное горлышко, на самом деле? Или видно исключительно в профайлере?
Здравствуйте, ·, Вы писали:
·>А зачем вообще тогда sv? Константы инициализируются только один раз, этим и пользуемся:
Получается, в рамках С++17, это единственный вариант без просадки производительности. Но пользоваться константами не очень удобно, думал может быть есть варианты получше.
Re[5]: Засада с эквивалентным ключом в std::unordered_map
Здравствуйте, Videoman, Вы писали:
V>·>А зачем вообще тогда sv? Константы инициализируются только один раз, этим и пользуемся: V>Получается, в рамках С++17, это единственный вариант без просадки производительности. Но пользоваться константами не очень удобно, думал может быть есть варианты получше.
А в чём недостатки этого варианта?
А вообще, конечно, смешно. Парсим охрененно избыточный медленный json и экономим на спичках, считая байты... Хочешь перформанс — бери SBE или protobuf хотя бы.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[6]: Засада с эквивалентным ключом в std::unordered_map
Здравствуйте, ·, Вы писали:
·>А вообще, конечно, смешно. Парсим охрененно избыточный медленный json и экономим на спичках, считая байты... Хочешь перформанс — бери SBE или protobuf хотя бы.
Забавно, но если сравнивать самые быстрые парсеры, то simdjson выигрывает у protobuf, даже несмотря на то, что парсить ему приходится куда более объёмный сериализованный текст.
Бинарный формат protobuf отравлен varint'ами — в нём для чтения очередного поля нужно разобрать предыдущее — и ни у кого не получается это место хорошо на уровне инструкций распараллелить.
Но, совет всё равно хороший, так как и другое, скорее всего, будет работать на порядок быстрее чем самодельный парсер с std::unordered_map внутри.