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

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

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

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

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

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


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

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

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

Здравствуйте, 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 введут прозрачные хешеры и компараторы, а проблема-то частично останется — ты для того, что ищешь, будешь всегда считать хеш. Платишь за то, что тебе не уперлось из-за кривого интерфейса.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здравствуйте, 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>Да там проблема в том, что интерфейс unordered_map пытались запилить такой же как у map. Чтобы была возможность легко заменять одно на другое в коде.

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

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

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

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

W>

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

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

Здравствуйте, 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, это единственный вариант без просадки производительности. Но пользоваться константами не очень удобно, думал может быть есть варианты получше.

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

·>А вообще, конечно, смешно. Парсим охрененно избыточный медленный 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 вместо замера общего перформанса обработки запроса включая парсинг и т.п.

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

·>А вообще, конечно, смешно. Парсим охрененно избыточный медленный 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 идентификатор поля — это отдельная строка черт его знает какой длины, для которой еще нужно будет посчитать хеш...

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


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

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



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

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

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

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