Вводные:
— С++ 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, на чем есть существенные потери тактов.

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

глобально ключ заменить ссылкой не?
ну как другой вариант делать move для find

Здравствуйте, Великий Реверс, Вы писали:

ВР>глобально ключ заменить ссылкой не?
ВР>ну как другой вариант делать move для find

Если можно, приведи пример? Не понял ни первое ни второе предложение.

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

2)
object.find(std::move(str));

Здравствуйте, Великий Реверс, Вы писали:

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

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

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

Этот код эквивалентен object.find(str), т.к. find на вход принимает константную ссылку.

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

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

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

Здравствуйте, 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.

Здравствуйте, 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;

понятно, что бред. Но если надо, значит надо.

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

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

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

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

Да там проблема в том, что интерфейс unordered_map пытались запилить такой же как у map. Чтобы была возможность легко заменять одно на другое в коде. А надо было для этих целей лишних адаптеров сделать имхо. Вот сейчас в с++20 введут прозрачные хешеры и компараторы, а проблема-то частично останется — ты для того, что ищешь, будешь всегда считать хеш. Платишь за то, что тебе не уперлось из-за кривого интерфейса.

Здравствуйте, 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 и выдернуть оттуда значения.

Здравствуйте, 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>, из-за чего её в общем случае нельзя вычислять от константных литералов во время компиляции (и не важно, что никто этой возможностью не пользуется) .

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

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



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

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

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

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

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

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

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

А вот с хэш-таблицами нужно ждать новых стандартов.

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

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

W>

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

Ну да, это плохо. У меня всегда есть опасения, что в контейнере окажется другой хешер

Здравствуйте, 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 и выдернуть оттуда значения.

В таком случае возникает закономерный вопрос — а существует ли оно, это бутылочное горлышко, на самом деле? Или видно исключительно в профайлере?

https://www.cppstories.com/2021/heterogeneous-access-cpp20/

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

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

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

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

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

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

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

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

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

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

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

W>·>А вообще, конечно, смешно. Парсим охрененно избыточный медленный json и экономим на спичках, считая байты... Хочешь перформанс — бери SBE или protobuf хотя бы.
W>Забавно, но если сравнивать самые быстрые парсеры, то simdjson выигрывает у protobuf, даже несмотря на то, что парсить ему приходится куда более объёмный сериализованный текст.
Вроде SBE затачивался под скорость и latency.

W>Бинарный формат protobuf отравлен varint'ами — в нём для чтения очередного поля нужно разобрать предыдущее — и ни у кого не получается это место хорошо на уровне инструкций распараллелить.
Любопытно. А чем json лучше в этом? Там вроде каждое поле таким образом "отравлено".

W>Но, совет всё равно хороший, так как и другое, скорее всего, будет работать на порядок быстрее чем самодельный парсер с std::unordered_map внутри.
Именно. И я почему-то уверен, что он перформанс микробенчмарком на map.find вместо замера общего перформанса обработки запроса включая парсинг и т.п.

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

W>>Бинарный формат protobuf отравлен varint'ами — в нём для чтения очередного поля нужно разобрать предыдущее — и ни у кого не получается это место хорошо на уровне инструкций распараллелить.
·>Любопытно. А чем json лучше в этом? Там вроде каждое поле таким образом "отравлено".

Тем что в нём структура документа описывается символами []{}",: , которые в любом контексте выглядят одинаково. И у CPU есть соответствующие инструкции, которые, например, берут длинную строку и возвращают битовую маску позиций, где в ней находятся эти символы.
После чего определение границ структур сводится к поиску парных скобок. То есть для '"' нужно найти парную '"' — и всё что между ними — это строка.
В современных архитектурах (x86,arm,risc-v) даже есть инструкция для таких операций с битами.
Конечно, есть случаи экранированных '\"' внутри строки, но это точно так же сводится к получению битовой маски вхождения символа '\' и нескольким побитовым операциям.

Можно примерно схему в https://arxiv.org/abs/1902.08318 почитать.


А в varint нужно каждый раз смотреть на старший бит в байте на предмет того, является ли продолжением предыдущего элемента или уже новым. Но при этом размеры сообщений, строк и packed-массивов кодируются длиной. То есть для них уже не работает трюк с выделением маски старших битов и нахождением в нём групп единиц, разделённых нулями через умножение полиномов, так как неизвестно находился ли бит внутри строки или нет. А чтобы это узнать — нужно прочитать длину строки. И мы вынуждены либо использовать последовательный разбор, либо пытаться сделать разбор со всех позиций сразу, чтобы потом выбрать настоящую. Но и то и другое скорости не добавляет.

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

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

Вообще JSON парсится влет и быстро, с ним нет проблем. Проблема в промежуточном слое, который был сделан в угоду гибкости (ну или из-за отсутствия до сих пор в C++ рефлексии) и тормозит уже десериализация во внутренние типы. Скорость сейчас устраивает, просто хотел подточить углы сделать запас.

Кстати по ходу обсуждения появился ещё один вопрос: если начать плавно переходить на С++20, то как с полнотой его поддержки в GCC сейчас обстоят дела?

Когда я фиксировал стандарт в прошлый раз на С+17, то обнаружил, что MSVC нормально поддерживал С++17, почти полностью, CLang — тоже, а вот с GCC были проблемы, приходилось ставить 10-ю или даже 11-ю версию. А как сейчас дела с 20-м стандартом?

если как марти будешь сидеть на каком нибудь старом гцц 7.2
то да
проблем много
начиная с самой главной
с++20 он в этой версии только начинал поддерживать

а если поставить самый последний гцц
то проблем нет
с++26 по чуть чуть добавляют

Здравствуйте, Великий Реверс, Вы писали:

ВР>если как марти будешь сидеть на каком нибудь старом гцц 7.2

Не знаю как там с 7.2, но на 9-м я столкнулся с тем, что не были реализованы некоторые части стандартной библиотеки 17-го стандарта.

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

w> Конечно, есть случаи экранированных '\"' внутри строки, но это точно так же сводится к получению битовой маски вхождения символа '\t' и нескольким побитовым операциям.
Спасибо, интересно.
А как с числами быть? Надо уметь конвертировать десятичное представление в int, да ещё и 1000000 может быть записано как 1.0E6.

w> Можно примерно схему в https://arxiv.org/abs/1902.08318 почитать.
Гы, деньги хотят.

w> А чтобы это узнать — нужно прочитать длину строки. И мы вынуждены либо использовать последовательный разбор, либо пытаться сделать разбор со всех позиций сразу, чтобы потом выбрать настоящую. Но и то и другое скорости не добавляет.
Прикольно. Т.е. я правильно понял, что закрывающий символ, даже с учётом экранирования, можно найти быстрее, чем сразу же прочитать длину?! Совершенно контринтуитивно.

https://en.cppreference.com/w/cpp/compiler_support/17
https://en.cppreference.com/w/cpp/compiler_support/20

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

W>Можно примерно схему в https://arxiv.org/abs/1902.08318 почитать.

Спасибо, интересно.

Правда, я не уверен, что так уж корректно измерять скорость работы парсера в гигабайтах в секунду.

Согласен с тем, что varint может быть проблемой. Но, для пересылки одного 32-битного int потребуется 6 байтов максимум. В случае json — это до десяти байтов плюс разделители, итого 11 или 12. В два раза больше.
Но это вырожденный случай, число "800" (16-битный int) потребует 3 байтов в protobuf и тех же трех в json плюс один или два разделителя.
но в случае с protobuf, это уже включает идентификатор поля, а в случае в json идентификатор поля — это отдельная строка черт его знает какой длины, для которой еще нужно будет посчитать хеш...

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

w>> Можно примерно схему в https://arxiv.org/abs/1902.08318 почитать.
·>Гы, деньги хотят.

У меня получилось PDF скачать.

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


L>Правда, я не уверен, что так уж корректно измерять скорость работы парсера в гигабайтах в секунду.

Да нормально — это же метрика для сравнения разных реализаций json парсеров между собой. У них цель быстрее распарсить готовый json-документ, а не соревноваться с парсерами альтернативных форматов сериализации.



L> Но, для пересылки одного 32-битного int потребуется 6 байтов максимум. В случае json — это до десяти байтов плюс разделители, итого 11 или 12. В два раза больше.
L>Но это вырожденный случай

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

L>но в случае с protobuf, это уже включает идентификатор поля, а в случае в json идентификатор поля — это отдельная строка черт его знает какой длины

Понятно, что в среднем json более «рыхлый».
Тем удивительнее, что simdjson умудряется оказываться быстрее даже при пересчёте на размер исходных данных. Выигрыш сильно меньше, но парадоксально, что он вообще есть.

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

·>А как с числами быть?

Конвертировать медленно и мучительно. Какие-то части парсера будут медленнее работать из-за текстовой природы формата.

w>> А чтобы это узнать — нужно прочитать длину строки. И мы вынуждены либо использовать последовательный разбор, либо пытаться сделать разбор со всех позиций сразу, чтобы потом выбрать настоящую. Но и то и другое скорости не добавляет.
·>Т.е. я правильно понял, что закрывающий символ, даже с учётом экранирования, можно найти быстрее, чем сразу же прочитать длину?!

Скорее выигрышь в том, что одной операцией можно найти все открывающие и закрывающие символы в целом блоке данных, где таких последовательностией может быть больше одной.
А с явной длиной нужно сначала её прочитать, и лишь потом сместиться в потоке на указанное смещение к началу следующей последовательности. Тут между ними возникает зависимость, мешающая параллелизму.
Ну и свою роль ещё играет не самый удачный выбор способа записи самих varint'ов и тегов в protobuf.

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

L>>Правда, я не уверен, что так уж корректно измерять скорость работы парсера в гигабайтах в секунду.
W>Да нормально — это же метрика для сравнения разных реализаций json парсеров между собой. У них цель быстрее распарсить готовый json-документ, а не соревноваться с парсерами альтернативных форматов сериализации.

Для сравнения json парсеров между собой — да. Но подобная метрика не подходит, если хочется проверить, не выгоднее ли использовать simdjson, нежели protobuf.

W>Понятно, что в среднем json более «рыхлый».
W>Тем удивительнее, что simdjson умудряется оказываться быстрее даже при пересчёте на размер исходных данных. Выигрыш сильно меньше, но парадоксально, что он вообще есть.

Понятное дело, что в целом нужно рассматривать не только производительность парсера, но и в целом размер данных, пересылаемых по сети. Тут в общем binary протоколы будут в выигрыше