Pull to refresh

Comments 31

UFO just landed and posted this here
Да, код из той статьи компилируется у меня с оптимизациями (MSVC 11) 5 минут.
UFO just landed and posted this here
Core i5 M 480 @ 2.67 GHz.
Точная версия (64-битного) компилятора 17.00.50727.1.

Жду результатов компиляции этим же компилятором с Вашего калькулятора.
UFO just landed and posted this here
Чуть-чуть статистики, кстати:

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 на тех шаблонах вообще падает.
Нет, clang version 3.2-1~exp9ubuntu3 не падает. У меня на Core2-ноуте вышеназванный файл компилируется за 3:19, съедая 1.27 ГБ RAМ. Только вот GCC 4.8.1-1ubuntu1 падает от жадности, съев 2 ГБ RAM, поэтому сравнить сам не могу.
Core i7 все тот же, но Linux и другие версии чуть-чуть.

gcc 4.7.3 — 1 минута 46 секунд (тайминг выше был из mingw-gcc 4.7.2)
clang 3.2.1 — 2 минуты 6 секунд
UFO just landed and posted this here
UFO just landed and posted this here
clang 3.4 (183617) — 2 минуты 15 секунд. Это svn trunk head.

clang 4.2 build 425 это старый clang из Xcode, как я понимаю.
UFO just landed and posted this here
У меня так (ноут 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
UFO just landed and posted this here
По поводу SoA — в данном случае (структура влазит в 64 бита) это заметно ухудшит производительность. Все-таки в этой статье все слишком хорошо упаковалось.

Кстати, по поводу кода, который компилируется 5 минут: там на самом деле можно гораздо красивше написать, чтобы генерировалось в 10 раз меньше функций.
Мне не очень очевидно, почему так.

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

Конечно, надо *очень* аккуратно будет писать код который сравнивает каждое поле. Т.е. наверное быстрый код с SoA в данном случае написать заметно сложнее. Зато потом можно добавлять поля не меняя код :)
Смотря сколько полей. > 4 — просядет кеш.
Надо читать поля по одному для всего потока.

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

Битовая упаковка это кстати тоже потеря производительности, поэтому в контексте дискуссии не является преимуществом укладки по полям в отдельности.
Список отфильтрованных полей — ну, есть разные варианты.

Есть вариант при котором последующие поля читаются с дырками — в зависимости от результатов фильтрации по предыдущим. Выглядит так что с битовой упаковкой такое точно не работает.

Есть вариант при котором все поля читают все объекты, и обновляют битовую/байтовую маску, а потом маску надо еще раз прочитать. Это читать больше данных в реальности, но все равно иногда меньше чем 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.
Если уж говорить о оптимизациях — простое изменение объявления структуры на
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) показывает напротив, что так будет в полтора раза медленнее
Как оказалось на ideone 32-битные машины, тогда понятно откуда замедление
Зато у автора 'шаблонной' реализации есть отмазка

Но это меняет сути, что можно делать шаблонную write-only кашу, а можно подумать, и сделать правильно: просто и лаконично.
Не успел…
Я тоже попробовал добавить «биты переноса», но проверял условие

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.

Articles