Comments 31
UFO just landed and posted this here
Да, код из той статьи компилируется у меня с оптимизациями (MSVC 11) 5 минут.
+5
UFO just landed and posted this here
Core i5 M 480 @ 2.67 GHz.
Точная версия (64-битного) компилятора 17.00.50727.1.
Жду результатов компиляции этим же компилятором с Вашего калькулятора.
Точная версия (64-битного) компилятора 17.00.50727.1.
Жду результатов компиляции этим же компилятором с Вашего калькулятора.
+13
UFO just landed and posted this here
Там у автора похоже две версии, одна с значительно увеличенным количеством комбинаций.
Я компилирую вот этот файл:
github.com/AlexeyAB/cpp_find_order/blob/ba568e1f9652ae106d4e50f978ff074269d16bc9/main.cpp
Я компилирую вот этот файл:
github.com/AlexeyAB/cpp_find_order/blob/ba568e1f9652ae106d4e50f978ff074269d16bc9/main.cpp
+5
Чуть-чуть статистики, кстати:
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 секунд
Мораль — мне пора обновить компиляторы!
+4
Попробуйте clang, он должен с отрывом обойти gcc.
0
В той статье писали, что clang на тех шаблонах вообще падает.
+4
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 секунд
0
У меня так (ноут 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
0
UFO just landed and posted this here
По поводу SoA — в данном случае (структура влазит в 64 бита) это заметно ухудшит производительность. Все-таки в этой статье все слишком хорошо упаковалось.
Кстати, по поводу кода, который компилируется 5 минут: там на самом деле можно гораздо красивше написать, чтобы генерировалось в 10 раз меньше функций.
Кстати, по поводу кода, который компилируется 5 минут: там на самом деле можно гораздо красивше написать, чтобы генерировалось в 10 раз меньше функций.
0
Мне не очень очевидно, почему так.
SoA с битовой упаковкой оставит количество данных тем же — но есть возможность часть данных не читать, если по данному полю фильтрации нет.
Конечно, надо *очень* аккуратно будет писать код который сравнивает каждое поле. Т.е. наверное быстрый код с SoA в данном случае написать заметно сложнее. Зато потом можно добавлять поля не меняя код :)
SoA с битовой упаковкой оставит количество данных тем же — но есть возможность часть данных не читать, если по данному полю фильтрации нет.
Конечно, надо *очень* аккуратно будет писать код который сравнивает каждое поле. Т.е. наверное быстрый код с SoA в данном случае написать заметно сложнее. Зато потом можно добавлять поля не меняя код :)
0
Смотря сколько полей. > 4 — просядет кеш.
0
Надо читать поля по одному для всего потока.
Т.е. отфильтровали целиком по первому полю, потом целиком по второму итп.
Т.е. отфильтровали целиком по первому полю, потом целиком по второму итп.
+1
Работа со списком отфильтрованных полей даст дополнительные накладные расходы, а чисто по производительности профит не так уж велик будет, если вообще. Так что зависит от специфики приложения, будет ли этот подход лучшим.
Битовая упаковка это кстати тоже потеря производительности, поэтому в контексте дискуссии не является преимуществом укладки по полям в отдельности.
Битовая упаковка это кстати тоже потеря производительности, поэтому в контексте дискуссии не является преимуществом укладки по полям в отдельности.
0
Список отфильтрованных полей — ну, есть разные варианты.
Есть вариант при котором последующие поля читаются с дырками — в зависимости от результатов фильтрации по предыдущим. Выглядит так что с битовой упаковкой такое точно не работает.
Есть вариант при котором все поля читают все объекты, и обновляют битовую/байтовую маску, а потом маску надо еще раз прочитать. Это читать больше данных в реальности, но все равно иногда меньше чем AoS.
Есть промежуточный вариант при котором мы обрабатываем объекты группами по например 128, и для каждого объекта последовательно обрабатываем все поля. Это скорее всего лучше предыдущих двух способов (первого — потому что можно все равно делать битовую упаковку; второго — потому что не тратим memory bandwidth на запись-чтение маски).
Но я согласен с тем что надо пробовать, не очевидно что лучше на данном примере.
Битовая упаковка не является преимуществом — просто если ее не делать то точно будет хуже (т.к. заметно больше данных читать), а если делать то непонятно.
Есть вариант при котором последующие поля читаются с дырками — в зависимости от результатов фильтрации по предыдущим. Выглядит так что с битовой упаковкой такое точно не работает.
Есть вариант при котором все поля читают все объекты, и обновляют битовую/байтовую маску, а потом маску надо еще раз прочитать. Это читать больше данных в реальности, но все равно иногда меньше чем AoS.
Есть промежуточный вариант при котором мы обрабатываем объекты группами по например 128, и для каждого объекта последовательно обрабатываем все поля. Это скорее всего лучше предыдущих двух способов (первого — потому что можно все равно делать битовую упаковку; второго — потому что не тратим memory bandwidth на запись-чтение маски).
Но я согласен с тем что надо пробовать, не очевидно что лучше на данном примере.
Битовая упаковка не является преимуществом — просто если ее не делать то точно будет хуже (т.к. заметно больше данных читать), а если делать то непонятно.
+3
Спасибо за оригинальную статью. Для данной задачи это намного проще.
Действительно у меня в статье есть избыточность во внешней раскрутке наличия полей, переехавшей без изменений из первой статьи, и используется избыточное число комбинаций в перестановке отсутствующих полей. Это сделано для упрощения понимания статьи, о чем там и написано. И то пришлось разделить на две.
Подобные оптимизации используются в 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.
+1
Если уж говорить о оптимизациях — простое изменение объявления структуры на
дает точно такой-же прирост скорости — почти в 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) )
И это без битовых операций.
+2
Речь об исходном C коде? У меня на msvc разницы нет. Возможно clang очень неэффективно компилирует доступ к bitfields? ;)
0
Да. Речь об исходном коде. Но ideone C++11 (gcc-4.7.2) показывает напротив, что так будет в полтора раза медленнее
+1
Зато у автора 'шаблонной' реализации есть отмазка
Но это меняет сути, что можно делать шаблонную write-only кашу, а можно подумать, и сделать правильно: просто и лаконично.
+1
Не успел…
Я тоже попробовал добавить «биты переноса», но проверял условие
Здесь 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-кодом (из самой первой статьи).
0
Sign up to leave a comment.
SIMD без SIMD, или ищем на С почти в два раза быстрее чем на С++