Comments 31
Да, код из той статьи компилируется у меня с оптимизациями (MSVC 11) 5 минут.
Core i5 M 480 @ 2.67 GHz.
Точная версия (64-битного) компилятора 17.00.50727.1.
Жду результатов компиляции этим же компилятором с Вашего калькулятора.
Точная версия (64-битного) компилятора 17.00.50727.1.
Жду результатов компиляции этим же компилятором с Вашего калькулятора.
Там у автора похоже две версии, одна с значительно увеличенным количеством комбинаций.
Я компилирую вот этот файл:
github.com/AlexeyAB/cpp_find_order/blob/ba568e1f9652ae106d4e50f978ff074269d16bc9/main.cpp
Я компилирую вот этот файл:
github.com/AlexeyAB/cpp_find_order/blob/ba568e1f9652ae106d4e50f978ff074269d16bc9/main.cpp
Чуть-чуть статистики, кстати:
cl /Ox /EHsc /bigobj
g++ -O3
Core i5 @ 2.6 (мой), cl 17.00.50727.1 — время 7 минут 11 секунд
Core i5 @ 2.6 (мой), gcc 4.6.1 — падает :(
Core i7 @ 3.3, cl 17.00.60315.1 — время 3 минуты 2 секунды
Core i7 @ 3.3, gcc 4.7.2 — время 2 минуты 30 секунд
Мораль — мне пора обновить компиляторы!
cl /Ox /EHsc /bigobj
g++ -O3
Core i5 @ 2.6 (мой), cl 17.00.50727.1 — время 7 минут 11 секунд
Core i5 @ 2.6 (мой), gcc 4.6.1 — падает :(
Core i7 @ 3.3, cl 17.00.60315.1 — время 3 минуты 2 секунды
Core i7 @ 3.3, gcc 4.7.2 — время 2 минуты 30 секунд
Мораль — мне пора обновить компиляторы!
Попробуйте clang, он должен с отрывом обойти gcc.
В той статье писали, что clang на тех шаблонах вообще падает.
Core i7 все тот же, но Linux и другие версии чуть-чуть.
gcc 4.7.3 — 1 минута 46 секунд (тайминг выше был из mingw-gcc 4.7.2)
clang 3.2.1 — 2 минуты 6 секунд
gcc 4.7.3 — 1 минута 46 секунд (тайминг выше был из mingw-gcc 4.7.2)
clang 3.2.1 — 2 минуты 6 секунд
У меня так (ноут Core 2 Duo P8600 2.4 GHz):
gcc (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3:
3m56.371s
Ubuntu clang version 3.2-1~exp9ubuntu1:
3m5.207s
gcc (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3:
3m56.371s
Ubuntu clang version 3.2-1~exp9ubuntu1:
3m5.207s
По поводу SoA — в данном случае (структура влазит в 64 бита) это заметно ухудшит производительность. Все-таки в этой статье все слишком хорошо упаковалось.
Кстати, по поводу кода, который компилируется 5 минут: там на самом деле можно гораздо красивше написать, чтобы генерировалось в 10 раз меньше функций.
Кстати, по поводу кода, который компилируется 5 минут: там на самом деле можно гораздо красивше написать, чтобы генерировалось в 10 раз меньше функций.
Мне не очень очевидно, почему так.
SoA с битовой упаковкой оставит количество данных тем же — но есть возможность часть данных не читать, если по данному полю фильтрации нет.
Конечно, надо *очень* аккуратно будет писать код который сравнивает каждое поле. Т.е. наверное быстрый код с SoA в данном случае написать заметно сложнее. Зато потом можно добавлять поля не меняя код :)
SoA с битовой упаковкой оставит количество данных тем же — но есть возможность часть данных не читать, если по данному полю фильтрации нет.
Конечно, надо *очень* аккуратно будет писать код который сравнивает каждое поле. Т.е. наверное быстрый код с SoA в данном случае написать заметно сложнее. Зато потом можно добавлять поля не меняя код :)
Смотря сколько полей. > 4 — просядет кеш.
Надо читать поля по одному для всего потока.
Т.е. отфильтровали целиком по первому полю, потом целиком по второму итп.
Т.е. отфильтровали целиком по первому полю, потом целиком по второму итп.
Работа со списком отфильтрованных полей даст дополнительные накладные расходы, а чисто по производительности профит не так уж велик будет, если вообще. Так что зависит от специфики приложения, будет ли этот подход лучшим.
Битовая упаковка это кстати тоже потеря производительности, поэтому в контексте дискуссии не является преимуществом укладки по полям в отдельности.
Битовая упаковка это кстати тоже потеря производительности, поэтому в контексте дискуссии не является преимуществом укладки по полям в отдельности.
Список отфильтрованных полей — ну, есть разные варианты.
Есть вариант при котором последующие поля читаются с дырками — в зависимости от результатов фильтрации по предыдущим. Выглядит так что с битовой упаковкой такое точно не работает.
Есть вариант при котором все поля читают все объекты, и обновляют битовую/байтовую маску, а потом маску надо еще раз прочитать. Это читать больше данных в реальности, но все равно иногда меньше чем AoS.
Есть промежуточный вариант при котором мы обрабатываем объекты группами по например 128, и для каждого объекта последовательно обрабатываем все поля. Это скорее всего лучше предыдущих двух способов (первого — потому что можно все равно делать битовую упаковку; второго — потому что не тратим memory bandwidth на запись-чтение маски).
Но я согласен с тем что надо пробовать, не очевидно что лучше на данном примере.
Битовая упаковка не является преимуществом — просто если ее не делать то точно будет хуже (т.к. заметно больше данных читать), а если делать то непонятно.
Есть вариант при котором последующие поля читаются с дырками — в зависимости от результатов фильтрации по предыдущим. Выглядит так что с битовой упаковкой такое точно не работает.
Есть вариант при котором все поля читают все объекты, и обновляют битовую/байтовую маску, а потом маску надо еще раз прочитать. Это читать больше данных в реальности, но все равно иногда меньше чем AoS.
Есть промежуточный вариант при котором мы обрабатываем объекты группами по например 128, и для каждого объекта последовательно обрабатываем все поля. Это скорее всего лучше предыдущих двух способов (первого — потому что можно все равно делать битовую упаковку; второго — потому что не тратим memory bandwidth на запись-чтение маски).
Но я согласен с тем что надо пробовать, не очевидно что лучше на данном примере.
Битовая упаковка не является преимуществом — просто если ее не делать то точно будет хуже (т.к. заметно больше данных читать), а если делать то непонятно.
Спасибо за оригинальную статью. Для данной задачи это намного проще.
Действительно у меня в статье есть избыточность во внешней раскрутке наличия полей, переехавшей без изменений из первой статьи, и используется избыточное число комбинаций в перестановке отсутствующих полей. Это сделано для упрощения понимания статьи, о чем там и написано. И то пришлось разделить на две.
Подобные оптимизации используются в production, но конкретно эта задача не из production, а из каких-то тестовых задач на просторах интернета. Если постановка задачи отойдет от оригинальной, то:
Мой вариант не подойдет для большого количества полей. Съест всю память и загнется на компиляции.
Ваш вариант не подойдет для типов long long, double, и других пользовательских типов (статических строк и т.д.).
При использовании разных типов будет проблематично использовать и SSE, хотя в случае SoA можно.
Почему я не использую аппаратно-зависимые CPU SIMD-инструкции? Если есть условия для использования SIMD — нам не критична аппаратная независимость, и задача действительно хорошо ложиться на SIMD, как например в сравнениях при использовании SoA, то она реализуется на CUDA GPU.
Выбор между SOA-AOS (в терминах СУБД это DSM-NSM) многократно подробно описан. Если совсем упрощенно то:
— SOA(DSM) используется при доступе к большому проценту строк и малому проценту полей, например в аналитике на Bigdata
— AOS(NSM) используется при доступе ко всем полям (или большому проценту полей) и к малому проценту строк остающимся после Index Seek/Index Range Scan, например в Highload веб-сервисах
Т.е. выбор будет зависеть от селективности посылаемых поисковых запросов.
В моем примере показана лишь малая часть реализации поиска, только та, что касается аппаратно-независимой оптимизации на шаблонах. В реальности дополнительно используются индексы и много чего ещё.
Насколько я понял под промежуточным вы имели вариант PAX, который используется в Oracle ExadataV2. Там он используется в первую очередь для улучшения сжатия, и во-вторую для улучшения cache-friendly.
Действительно у меня в статье есть избыточность во внешней раскрутке наличия полей, переехавшей без изменений из первой статьи, и используется избыточное число комбинаций в перестановке отсутствующих полей. Это сделано для упрощения понимания статьи, о чем там и написано. И то пришлось разделить на две.
Подобные оптимизации используются в production, но конкретно эта задача не из production, а из каких-то тестовых задач на просторах интернета. Если постановка задачи отойдет от оригинальной, то:
Мой вариант не подойдет для большого количества полей. Съест всю память и загнется на компиляции.
Ваш вариант не подойдет для типов long long, double, и других пользовательских типов (статических строк и т.д.).
При использовании разных типов будет проблематично использовать и SSE, хотя в случае SoA можно.
Почему я не использую аппаратно-зависимые CPU SIMD-инструкции? Если есть условия для использования SIMD — нам не критична аппаратная независимость, и задача действительно хорошо ложиться на SIMD, как например в сравнениях при использовании SoA, то она реализуется на CUDA GPU.
Выбор между SOA-AOS (в терминах СУБД это DSM-NSM) многократно подробно описан. Если совсем упрощенно то:
— SOA(DSM) используется при доступе к большому проценту строк и малому проценту полей, например в аналитике на Bigdata
— AOS(NSM) используется при доступе ко всем полям (или большому проценту полей) и к малому проценту строк остающимся после Index Seek/Index Range Scan, например в Highload веб-сервисах
Т.е. выбор будет зависеть от селективности посылаемых поисковых запросов.
В моем примере показана лишь малая часть реализации поиска, только та, что касается аппаратно-независимой оптимизации на шаблонах. В реальности дополнительно используются индексы и много чего ещё.
Насколько я понял под промежуточным вы имели вариант PAX, который используется в Oracle ExadataV2. Там он используется в первую очередь для улучшения сжатия, и во-вторую для улучшения cache-friendly.
Если уж говорить о оптимизациях — простое изменение объявления структуры на
дает точно такой-же прирост скорости — почти в 2 раза на моем 1,7ГГц Core i7 (LLVM version 4.2 (clang-425.0.28) )
И это без битовых операций.
struct T_cash_account_row {
...
int32_t code;
int32_t amount_of_money;
int16_t height;
int16_t age:7;
int16_t gender:1;
...дает точно такой-же прирост скорости — почти в 2 раза на моем 1,7ГГц Core i7 (LLVM version 4.2 (clang-425.0.28) )
И это без битовых операций.
Речь об исходном C коде? У меня на msvc разницы нет. Возможно clang очень неэффективно компилирует доступ к bitfields? ;)
Да. Речь об исходном коде. Но ideone C++11 (gcc-4.7.2) показывает напротив, что так будет в полтора раза медленнее
Зато у автора 'шаблонной' реализации есть отмазка
Но это меняет сути, что можно делать шаблонную write-only кашу, а можно подумать, и сделать правильно: просто и лаконично.
Не успел…
Я тоже попробовал добавить «биты переноса», но проверял условие
Здесь int test[2] — два слова, которые соддержат проверяемую структуру, int begin[2],end[2] — границы фильтров, mask_0 и mask_1 — знаки битов переполнения. Итог — 32-битный код даёт 5-кратный выигрыш по сравнению с исходным C-кодом (из самой первой статьи).
Я тоже попробовал добавить «биты переноса», но проверял условие
return (( ((test[0]-begin[0])|(end[0]-test[0])) & mask_0) | ( ((test[1]-begin[1])|(end[1]-test[1])) & mask_1))==0 ? 1 : 0;
Здесь int test[2] — два слова, которые соддержат проверяемую структуру, int begin[2],end[2] — границы фильтров, mask_0 и mask_1 — знаки битов переполнения. Итог — 32-битный код даёт 5-кратный выигрыш по сравнению с исходным C-кодом (из самой первой статьи).
Sign up to leave a comment.
SIMD без SIMD, или ищем на С почти в два раза быстрее чем на С++