Сообщение Re[8]: Засада с эквивалентным ключом в std::unordered_map от 21.10.2024 16:47
Изменено 21.10.2024 21:01 watchmaker
Re[8]: Засада с эквивалентным ключом в std::unordered_map
Здравствуйте, ·, Вы писали:
W>>Бинарный формат protobuf отравлен varint'ами — в нём для чтения очередного поля нужно разобрать предыдущее — и ни у кого не получается это место хорошо на уровне инструкций распараллелить.
·>Любопытно. А чем json лучше в этом? Там вроде каждое поле таким образом "отравлено".
Тем что в нём структура документа описывается символами []{}",: , которые в любом контексте выглядят одинаково. И у CPU есть соответствующие инструкции, которые, например, берут длинную строку и возвращают битовую маску позиций, где в ней находятся эти символы.
После чего определение границ структур сводится к поиску парных скобок. То есть для '"' нужно найти парную '"' — и всё что между ними — это строка.
В современных архитектурах (x86,arm,risc-v) даже есть инструкция для таких операций с битами.
Конечно, есть случаи экранированных '\"' внутри строки, но это точно так же сводится к получению битовой маски вхождения символа '\t' и нескольким побитовым операциям.
Можно примерно схему в https://arxiv.org/abs/1902.08318 почитать.
А в varint нужно каждый раз смотреть на старший бит в байте на предмет того, является ли продолжением предыдущего элемента или уже новым. Но при этом размеры сообщений, строк и packed-массивов кодируются длиной. То есть для них уже не работает трюк с выделением маски старших битов и нахождением в нём групп единиц, разделённых нулями через умножение полиномов, так как неизвестно находился ли бит внутри строки или нет. А чтобы это узнать — нужно прочитать длину строки. И мы вынуждены либо использовать последовательный разбор, либо пытаться сделать разбор со всех позиций сразу, чтобы потом выбрать настоящую. Но и то и другое скорости не добавляет.
W>>Бинарный формат protobuf отравлен varint'ами — в нём для чтения очередного поля нужно разобрать предыдущее — и ни у кого не получается это место хорошо на уровне инструкций распараллелить.
·>Любопытно. А чем json лучше в этом? Там вроде каждое поле таким образом "отравлено".
Тем что в нём структура документа описывается символами []{}",: , которые в любом контексте выглядят одинаково. И у CPU есть соответствующие инструкции, которые, например, берут длинную строку и возвращают битовую маску позиций, где в ней находятся эти символы.
После чего определение границ структур сводится к поиску парных скобок. То есть для '"' нужно найти парную '"' — и всё что между ними — это строка.
В современных архитектурах (x86,arm,risc-v) даже есть инструкция для таких операций с битами.
Конечно, есть случаи экранированных '\"' внутри строки, но это точно так же сводится к получению битовой маски вхождения символа '\t' и нескольким побитовым операциям.
Можно примерно схему в https://arxiv.org/abs/1902.08318 почитать.
А в varint нужно каждый раз смотреть на старший бит в байте на предмет того, является ли продолжением предыдущего элемента или уже новым. Но при этом размеры сообщений, строк и packed-массивов кодируются длиной. То есть для них уже не работает трюк с выделением маски старших битов и нахождением в нём групп единиц, разделённых нулями через умножение полиномов, так как неизвестно находился ли бит внутри строки или нет. А чтобы это узнать — нужно прочитать длину строки. И мы вынуждены либо использовать последовательный разбор, либо пытаться сделать разбор со всех позиций сразу, чтобы потом выбрать настоящую. Но и то и другое скорости не добавляет.
Re[8]: Засада с эквивалентным ключом в std::unordered_map
Здравствуйте, ·, Вы писали:
W>>Бинарный формат protobuf отравлен varint'ами — в нём для чтения очередного поля нужно разобрать предыдущее — и ни у кого не получается это место хорошо на уровне инструкций распараллелить.
·>Любопытно. А чем json лучше в этом? Там вроде каждое поле таким образом "отравлено".
Тем что в нём структура документа описывается символами []{}",: , которые в любом контексте выглядят одинаково. И у CPU есть соответствующие инструкции, которые, например, берут длинную строку и возвращают битовую маску позиций, где в ней находятся эти символы.
После чего определение границ структур сводится к поиску парных скобок. То есть для '"' нужно найти парную '"' — и всё что между ними — это строка.
В современных архитектурах (x86,arm,risc-v) даже есть инструкция для таких операций с битами.
Конечно, есть случаи экранированных '\"' внутри строки, но это точно так же сводится к получению битовой маски вхождения символа '\' и нескольким побитовым операциям.
Можно примерно схему в https://arxiv.org/abs/1902.08318 почитать.
А в varint нужно каждый раз смотреть на старший бит в байте на предмет того, является ли продолжением предыдущего элемента или уже новым. Но при этом размеры сообщений, строк и packed-массивов кодируются длиной. То есть для них уже не работает трюк с выделением маски старших битов и нахождением в нём групп единиц, разделённых нулями через умножение полиномов, так как неизвестно находился ли бит внутри строки или нет. А чтобы это узнать — нужно прочитать длину строки. И мы вынуждены либо использовать последовательный разбор, либо пытаться сделать разбор со всех позиций сразу, чтобы потом выбрать настоящую. Но и то и другое скорости не добавляет.
W>>Бинарный формат protobuf отравлен varint'ами — в нём для чтения очередного поля нужно разобрать предыдущее — и ни у кого не получается это место хорошо на уровне инструкций распараллелить.
·>Любопытно. А чем json лучше в этом? Там вроде каждое поле таким образом "отравлено".
Тем что в нём структура документа описывается символами []{}",: , которые в любом контексте выглядят одинаково. И у CPU есть соответствующие инструкции, которые, например, берут длинную строку и возвращают битовую маску позиций, где в ней находятся эти символы.
После чего определение границ структур сводится к поиску парных скобок. То есть для '"' нужно найти парную '"' — и всё что между ними — это строка.
В современных архитектурах (x86,arm,risc-v) даже есть инструкция для таких операций с битами.
Конечно, есть случаи экранированных '\"' внутри строки, но это точно так же сводится к получению битовой маски вхождения символа '\' и нескольким побитовым операциям.
Можно примерно схему в https://arxiv.org/abs/1902.08318 почитать.
А в varint нужно каждый раз смотреть на старший бит в байте на предмет того, является ли продолжением предыдущего элемента или уже новым. Но при этом размеры сообщений, строк и packed-массивов кодируются длиной. То есть для них уже не работает трюк с выделением маски старших битов и нахождением в нём групп единиц, разделённых нулями через умножение полиномов, так как неизвестно находился ли бит внутри строки или нет. А чтобы это узнать — нужно прочитать длину строки. И мы вынуждены либо использовать последовательный разбор, либо пытаться сделать разбор со всех позиций сразу, чтобы потом выбрать настоящую. Но и то и другое скорости не добавляет.