Comments 15
А специальные инструкции для копирования строк, типа REP MOVSB, рассматривались?
Да, рассматривались. В старых реализациях memcpy именно они используются (а ещё используются в реализации копирования из ядра Linux в userspace — почему?). Казалось бы, это как раз то, что нужно — вся работа в одной инструкции.
Но в современных реализациях вместо этого написано куча кода с векторными инструкциями, разворачиванием цикла, duff device, prefetch, non-temporary stores. Почему-то так получается эффективнее. Хотя что мешает процессору делать так, чтобы REP MOVSB выполнялось так же эффективно?
Но в современных реализациях вместо этого написано куча кода с векторными инструкциями, разворачиванием цикла, duff device, prefetch, non-temporary stores. Почему-то так получается эффективнее. Хотя что мешает процессору делать так, чтобы REP MOVSB выполнялось так же эффективно?
Подозреваю что мешает общая сложность устройства. Поскольку x86 как бы RISC с CISC интерфейсом, то есть CISC команды транслируются в простые микрооперации, которые исполняются RISC ядром. Но аппаратно реализовать машину, которая REP MOVSB развернёт в соответствующие операции работающие сразу с многими байтами (аналог векторизации) не имеет большого смысла, поскольку оно будет выполняться практически с такой же скоростью как и чисто софтовый аналог (кэширование, префетчинг, предекодинг, предсказание ветвлений, конвееризация доступа к памяти и прочая). Сложность верификации (привет всякие уязвимости и баги) аппаратных реализаций намного выше, чем софтовых, а цена устранения аппаратных ошибок после запуска производства и вовсе космическая (даже при наличии микрокода).
Ну вот не скажите
Операция копирования используется очень часто, и городить кучу разных реализаций, для SSE1/2/3, AVX и т.д. и т.п., выжимая проценты производительности (и теряя их в других местах), внося потенциальные баги и дырки — разве это лучше, чем иметь пару-тройку специальных инструкций, которые раз и навсегда закроют вопрос максимально эффективного копирования для всех вариантов процессоров?
Операция копирования используется очень часто, и городить кучу разных реализаций, для SSE1/2/3, AVX и т.д. и т.п., выжимая проценты производительности (и теряя их в других местах), внося потенциальные баги и дырки — разве это лучше, чем иметь пару-тройку специальных инструкций, которые раз и навсегда закроют вопрос максимально эффективного копирования для всех вариантов процессоров?
www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf
Раздел 11.16.3 Data Movement Considerations
В реализации REP MOVSB были проведены улучшения (начиная с Haswell), так что есть смысл его потестировать.
Возможно, стоит весь декодер сделать на асме, максимально просто и дубово. Выравнивание в данном случае практически всегда отсутствует, и пытаться вручную оптимизировать смещения инструкций чтения — гиблое дело, имхо. 256-битные инструкции на таких случайных данных будут проигрывать из-за частого пересечения границы строки кеша.
Раздел 11.16.3 Data Movement Considerations
В реализации REP MOVSB были проведены улучшения (начиная с Haswell), так что есть смысл его потестировать.
Возможно, стоит весь декодер сделать на асме, максимально просто и дубово. Выравнивание в данном случае практически всегда отсутствует, и пытаться вручную оптимизировать смещения инструкций чтения — гиблое дело, имхо. 256-битные инструкции на таких случайных данных будут проигрывать из-за частого пересечения границы строки кеша.
Кстати, на ближайшей конференции Highload++ Siberia тоже будет доклад — про оптимизацию поиска строк. На первом скриншоте «VolnitskyBase» имеет некоторое отношение к этому докладу :)
Задача для внимательного читателя
Кол-во повторений чисел слишком велико, а длина последовательностей слишком мала и алгоритм сам себя нивелирует?
LZ4 умеет обнаруживать совпадения длиной минимум 4 байта. Но в последовательности чисел UInt32 0, 1, 2… (записанных в бинарном виде) нет повторяющихся подпоследовательностей такой длины, поэтому никаких совпадений не находится.
Для сравнения, если так записать числа UInt64, то они будут кое-как сжиматься (например, в начале повторяются фрагменты из 7 нулевых байт).
Более правильное решение — добавить кодек Delta перед LZ4. Недавно в ClickHouse появилась такая возможность — настраиваемые кодеки для отдельных столбцов, которые можно выстраивать в цепочки.
Для сравнения, если так записать числа UInt64, то они будут кое-как сжиматься (например, в начале повторяются фрагменты из 7 нулевых байт).
Более правильное решение — добавить кодек Delta перед LZ4. Недавно в ClickHouse появилась такая возможность — настраиваемые кодеки для отдельных столбцов, которые можно выстраивать в цепочки.
У меня есть сомнения, что возможно изобрести «максимально эффективный алгоритм» копирования для всех вариантов процессора (если посмотреть на разные реализации memcpy то можно слегка устать от разнообразия оптимизаций под разные поколения внутри одной архитектуры x86). Между ядром и физической памятью всякие кэши, таблицы трансляции и прочая. По сути, аппаратная реализация будет вызывать такую же последовательность операций на шине, что и в софтовой реализации.
Вижу, что в данном случае зашло очень неплохо, да и различия не радикальны, но интересно пофилософствовать на тему того, вещи, вроде многоруких бандитов все же зло, или благо в системном ПО?
С одной стороны, если СУБД работает быстрее на различных моделях процессоров, то однозначно благо. С другой, недетерминированность работы системного ПО может приводить к невозможности выполнять SLA на уровне прикладного ПО. Условно, если СУБД на определенный класс запросов всегда отвечает за 4-5 секунд, то это может быть лучше для конечного пользователя, чем если за 1-10 со средним в 2 сек, потому, что в первом случае можно ставить меньший таймаут на клиенте, и быстрее понимать, что система деградировала. С другой стороны, на практике, как правило запросов много, они накладываются друг на друга, и детерминированности не получить в принципе (а значит, и гнаться за ней не стоит). Может правильно иметь переключатель is_deterministic?)
С одной стороны, если СУБД работает быстрее на различных моделях процессоров, то однозначно благо. С другой, недетерминированность работы системного ПО может приводить к невозможности выполнять SLA на уровне прикладного ПО. Условно, если СУБД на определенный класс запросов всегда отвечает за 4-5 секунд, то это может быть лучше для конечного пользователя, чем если за 1-10 со средним в 2 сек, потому, что в первом случае можно ставить меньший таймаут на клиенте, и быстрее понимать, что система деградировала. С другой стороны, на практике, как правило запросов много, они накладываются друг на друга, и детерминированности не получить в принципе (а значит, и гнаться за ней не стоит). Может правильно иметь переключатель is_deterministic?)
В системе есть очень много источников недетерминированности: turbo boost, thermal и power throttling, page cache, memory layout, зависящий от аллокатора, page faults, фрагментация физической памяти, расположение данных на конкретном месте на HDD, многопоточное выполнение — когда результат всегда корректный, но скорость работы может меняться в широких пределах… Туда же можно отнести profile-guided optimizations, JIT и machine learned data structures. Всё это не так уж плохо, пока скорость работы меняется всего лишь в разы или меняется хотя бы предсказуемым образом.
Гораздо хуже например, если оптимизатор запроса из-за накопленной статистики стал выбирать один план запроса вместо другого, и скорость меняется в тысячу раз. Хотя в ClickHouse примитивный оптимизатор запросов, но похожие эффекты тоже могут иметь место.
Я слышал про специализированные базы данных для RTOS, но ничего про них не знаю.
Гораздо хуже например, если оптимизатор запроса из-за накопленной статистики стал выбирать один план запроса вместо другого, и скорость меняется в тысячу раз. Хотя в ClickHouse примитивный оптимизатор запросов, но похожие эффекты тоже могут иметь место.
Я слышал про специализированные базы данных для RTOS, но ничего про них не знаю.
а не пробовали смотреть на другие integer compression схемы, например github.com/lemire/FastPFor?
Да, смотрели. В самом начале в ClickHouse был тип данных VarInt, VarUInt. Но он использовал обычное кодирование по одному числу (такое же как в Protobuf). Оно работало не очень быстро, поэтому его удалили. Само собой напрашивается использование вариантов group-varint, которые обрабатывают блоки из некоторого количества чисел одновременно, как тот, что по ссылке. Мы этого довольно долго не могли сделать, так как не хватало фичи — возможность указывать отдельные кодеки для отдельных столбцов (всё-таки, это — специализированный алгоритм и тут лучше пользователю самому указать, для каких столбцов его использовать, а для каких — нет). В начале этого года возможность указания кодеков для отдельных столбцов появилась, но сам кодек ещё не добавили, хотя теперь этому ничего не мешает.
Sign up to leave a comment.
Как ускорить разжатие LZ4 в ClickHouse