?

Log in

No account? Create an account

Previous Entry | Next Entry

Есть в программистском фольклоре два поверья:
1) хочешь скорости - пиши на Си
2) нет смысла писать на асме, компилятор и так умный
Столкнувшись в недавнем проекте с явным недостатком ума компилятора, решил по мотивам реального кода сделать микробенчмарк и посмотреть, как вообще разные компиляторы с ним справляются. Задачка очень простая: есть два массива 16-битных целых чисел, найти сумму квадратов разностей. В оригинале это были блоки 16х16, и проходить их надо было в двойном цикле. Такой вот код:
__declspec(align(16)) short a[256], b[256];
int sum = 0, j=0;
for(int y=0;y<16;y++)
    for(int x=0;x<16;x++) {		
        short v = a[j] - b[j];
        sum += v*v;
        j++;
    }

Данные в задаче таковы, что разность помещается в short, это не проблема. Цикл такой прогоняю 10 млн раз и смотрю время, а также смотрю, что за код сгенерировался.

MSVC6 (1998 год) делает все в лоб: два цикла по 16 итераций, внутри чтение слов из памяти с конвертацией в 32 бита, затем imul и сложение. 4 с лишним секунды.

Наступает 21 век, в 2001 году появляется набор инструкций SSE2, позволяющий ряд операций делать над 16 байтами сразу, в частности вычитать 8 short'ов за раз. С умножением сложнее: результат умножения short'ов - int, нельзя умножить 8 пар short'ов и получить 8 интов, т.к. в 128-битный регистр они не поместятся. Можно одной операцией либо перемножить и взять нижние 16 бит результатов, либо верхние 16 бит, либо 8 интов-результатов попарно сложить и получить 4 инта, уже помещающиеся в регистр.

Для использования команд SSE есть интринсики. Код с ними выглядит так:
int j = 0;
__m128i xsum = _mm_setzero_si128();
while(j<256) {
    __m128i a16 = _mm_load_si128((__m128i*)&a[j]);
    __m128i b16 = _mm_load_si128((__m128i*)&b[j]);
    __m128i diff16 = _mm_sub_epi16(a16, b16);
    __m128i madd = _mm_madd_epi16(diff16, diff16);
    xsum = _mm_add_epi32(xsum, madd);
    j += 8;
}
__m128i shft = _mm_srli_si128(xsum, 8);
xsum = _mm_add_epi32(xsum, shft);
shft = _mm_srli_si128(xsum, 4);
xsum = _mm_add_epi32(xsum, shft);
sum = _mm_cvtsi128_si32(xsum);

Отрабатывает те же 10 млн повторов за полсекунды. Но ручного написания интринсиков хочется избежать, у нас же есть умные компиляторы, да?

MSVC8 (2006 год). В опциях компилятора есть гордый пункт про SSE2. Включаем, компиляем. 3 с лишним секунды. Двойной цикл, внутренний unroll'ен по 4 итерации, внутри те же imul. SSE? Не, не слышал.

MSVC10 (2010 год). У студии новый WPFный интерфейс, но только не у окна настроек С++ проекта (настораживает?). Включаем нужные опции, компиляем. Тот же двойной цикл с разворачиванием внутреннего по 4 итерации, те же imul. Те же 3 секунды. SSE? Не, не слышал.

Intel Compiler 7.1 (2003 год). Полностью разворачивает внутренний цикл. 2 секунды. SSE? А что это?
Даем подсказку: вместо двойного цикла по 16 итераций делаем один на 256 итераций. Тут вдруг интеловский компилятор оживает и сам векторизует код ровно так же, как в примере с интринсиками. Укладывается в полсекунды.

Аналогичная подсказка MSVC всех версий ничего не дает, они продолжают разворачивать максимум по 4 итерации, никакого SSE.

Intel Compiler 11 (2009 год). Одинарный цикл векторизует так же хорошо, как 7-й. В двойном цикле на этот раз догадывается хотя бы векторизовать внутренний, но тупит с выравниваниями, вставляя ненужный и неиспользуемый код по краям. 1 секунда.

GCC 4.7.0 (2012 год). В двойном цикле полностью разворачивает внутренний, внутри imul, все как у intel 7. Те же 2 секунды. SSE? Не, не слышал. Если сделать цикл одинарным, сдюживает его векторизовать, но делает это плохо: вместо попарного сложения результатов умножения отдельно вычисляет верхние и нижние биты результатов, потом возится с перестановками и перепаковками байтов в регистрах. 1 секунда, вдвое хуже интела и варианта с ручной векторизацией.

Может, другие языки лучше? Что у нас после С? D? DMD 2.059, 2012 год, двойной цикл по 16 итераций, imul, т.е. код на уровне vc6. Ожидаемые 4 секунды.

Ну это маргинальщина, на самом деле после С/С++ идет C#. Молва гласит, что якобы JIT позволяет генерить код под конкретный процессор, используя доступные наборы инструкций. В теории это действительно так. Переписываем код на C# собираем в VS10 под .NET4. 6 секунд двойной цикл, 5 секунд одинарный. SSE? Хз, но чота не похоже. О, сборка была для x86. Пробуем для x64: 4 секунды на двойной цикл, 2 с половиной на одинарный. Получше, но до нормального невекторизованного С++ кода не дотягивает.

Ладно, надоели си-подобные языки, вот на днях вышел Haskell Platform 2012.2. Там GHC 7.4.1, берем Data.Vector.Unboxed Int16. Если верить бенчмаркам criterion, 10 млн повторов будут работать 16 секунд. Ибо внутри внезапно часть вычислений делаются с плавающей точкой (если я правильно их нашел) (не правильно).

Мораль: со всей объективностью одного микробенчмарка :) можно заявить, что спустя 10 лет после появления SSE2 компиляторы - все еще говно, и авторы того же x264 не зря пишут на ассемблере.

Comments

( 66 comments — Leave a comment )
Page 1 of 2
<<[1] [2] >>
mr_st
Jun. 5th, 2012 02:08 pm (UTC)
Пару лет назад баловался с подобными тестами. Вывод был такой же: кроме интела никто толком векторизовать не умеет.
(Deleted comment)
thedeemon
Jun. 5th, 2012 02:53 pm (UTC)
Как-то так:
http://stuff.thedeemon.com/lj/vectest.zip
С++ варианты для GCC, там вместо declspec attribute.
(no subject) - soonts - Jun. 5th, 2012 07:46 pm (UTC) - Expand
(no subject) - thedeemon - Jun. 5th, 2012 11:03 pm (UTC) - Expand
(no subject) - thedeemon - Jun. 5th, 2012 11:05 pm (UTC) - Expand
xeno_by
Jun. 5th, 2012 03:02 pm (UTC)
В дотнетовском джите вроде бы SSE и нету. Попробуй на моно.
wizzard0
Jun. 5th, 2012 04:59 pm (UTC)
Дотнетовский джит, ЕМНИП, вообще на memory access optimization заточен, особенно х64.

Но SSE там действительно нету, увы.

Моно щас попробую, мне интересно.

2 thedeemon: а бенчмарк на memory access patterns или что-то такое сделать можешь?
(no subject) - thedeemon - Jun. 5th, 2012 10:58 pm (UTC) - Expand
(no subject) - stdray - Jul. 12th, 2012 03:34 pm (UTC) - Expand
(no subject) - wizzard0 - Jul. 12th, 2012 06:35 pm (UTC) - Expand
(no subject) - stdray - Jul. 13th, 2012 08:27 am (UTC) - Expand
potan
Jun. 5th, 2012 04:07 pm (UTC)
А такая штука с распараллеливанием на sse не справится?
thedeemon
Jun. 5th, 2012 10:56 pm (UTC)
Не знаю, надо пробовать. Кроме нее есть еще такая:
http://ispc.github.com/
(no subject) - helvegr - Jun. 6th, 2012 01:42 am (UTC) - Expand
(no subject) - thedeemon - Jun. 6th, 2012 03:10 am (UTC) - Expand
(no subject) - helvegr - Jun. 6th, 2012 03:13 am (UTC) - Expand
(no subject) - udpn - Jun. 6th, 2012 03:20 am (UTC) - Expand
(no subject) - thedeemon - Jun. 6th, 2012 04:23 am (UTC) - Expand
(no subject) - helvegr - Jun. 7th, 2012 08:43 am (UTC) - Expand
(no subject) - izard - Jun. 6th, 2012 02:43 pm (UTC) - Expand
(no subject) - thedeemon - Jun. 7th, 2012 02:02 am (UTC) - Expand
mr_aleph
Jun. 5th, 2012 04:38 pm (UTC)
это же все голимый паттерн-матчинг по существу, достаточно посмотреть на реализацию vect_recog_dot_prod_pattern в gcc и прослезится.
109
Jun. 5th, 2012 05:32 pm (UTC)
> Данные в задаче таковы, что разность помещается в short

а компилятор-то это откуда знает?
thedeemon
Jun. 5th, 2012 10:52 pm (UTC)
Отсюда:
short v = a[j] - b[j];
Vadim Kantorov
Jun. 5th, 2012 05:59 pm (UTC)
Практически интересный вопрос: MATLAB за сколько такую операцию выполнит?
thedeemon
Jun. 5th, 2012 10:53 pm (UTC)
У меня его нет. Попробуйте, мне тоже интересно.
helvegr
Jun. 5th, 2012 07:56 pm (UTC)
> Ибо внутри внезапно часть вычислений делаются с плавающей точкой (если я правильно их нашел).

Я посмотрел core, и таких вычислений там не увидел. Вот релевантный кусок.
Видно следующее: а) лишняя проверка на завершение, т.к. zipWith не знает, что векторы одного размера; б) проверка того, что результат разности влезает в 16 бит (narrow16Int#) внутри цикла (16-битные операции в GHC реализованы через 32-битные).

Вот оптимизированная версия:

calc_low_level :: V.Vector Int16 -> V.Vector Int16 -> Int
calc_low_level a b = go 0 0
  where
    end = V.length a

    go i acc | i >= end  = acc
             | otherwise =
               let a_i = fromIntegral (V.unsafeIndex a i)
                   b_i = fromIntegral (V.unsafeIndex b i)

                   d :: Int
                   d = a_i - b_i
               in go (i+1) (acc + d*d)


Поддержки SSE в GHC нет даже на уровне интринсиков (хотя планируется добавить).
nponeccop
Jun. 6th, 2012 12:50 am (UTC)
> Поддержки SSE в GHC нет

Кстати она вроде бы есть в ATS и thedeemon вроде как гуру ATS. Реквестирую версию с интринсиками на ATS!
(no subject) - thedeemon - Jun. 6th, 2012 01:44 am (UTC) - Expand
(no subject) - helvegr - Jun. 6th, 2012 01:55 am (UTC) - Expand
(no subject) - thedeemon - Jun. 6th, 2012 02:51 am (UTC) - Expand
(no subject) - helvegr - Jun. 6th, 2012 02:58 am (UTC) - Expand
(no subject) - thedeemon - Jun. 6th, 2012 03:06 am (UTC) - Expand
(no subject) - helvegr - Jun. 6th, 2012 03:20 am (UTC) - Expand
nivanych
Jun. 6th, 2012 01:40 am (UTC)
10 лет прошло, как я x86-оптимизацией закончил заниматьася.
С тех пор, почти ничего не изменилось. Печально.
Но вот напомнили про ATS.
Что там, как там? :-)
thedeemon
Jun. 6th, 2012 01:46 am (UTC)
Он же Си генерит, так что не лучше, чем в GCC.
(no subject) - thedeemon - Jun. 6th, 2012 01:49 am (UTC) - Expand
diam_2003
Jun. 6th, 2012 02:10 am (UTC)
В таких случаях ещё принято писать, с какими ключиками запускался компилятор.
thedeemon
Jun. 6th, 2012 03:00 am (UTC)
Для GCC
g++ madd.cpp -O3 -msse2 -ftree-vectorize -o madd.exe

Для msvc там ключей дофига, но в опциях были maximize speed, inline any suitable, use SSE2, no RTTI, favor fast code over size.

Для интела еще добавляются -QaxW -Qip

Для DMD: -release -O

В шарпе вроде всего одна галка "optimize".
(no subject) - permea_kra - Jun. 14th, 2012 03:19 am (UTC) - Expand
kiryl
Jun. 6th, 2012 02:28 am (UTC)
На AVX ещё не смотрел? С 256-и битными регистрами будет веселее. Может и компилятору векторизовать будет проще (хотя я б не сильно надеялся).
thedeemon
Jun. 6th, 2012 03:04 am (UTC)
Не, у меня пока под рукой даже нет процессора, его поддерживающего. И у большинства пользователей тоже.
(no subject) - izard - Jun. 6th, 2012 02:44 pm (UTC) - Expand
qehgt
Jun. 6th, 2012 11:53 am (UTC)
Непонятно, что происходит в последних пяти строчках SSE кода. Можно как-то подробнее расписать? (непонятно, куда квадраты делись)
thedeemon
Jun. 6th, 2012 12:08 pm (UTC)
В цикле в a16 и b16 загружается по 8 16-битных значений. Вычитаем:
__m128i diff16 = _mm_sub_epi16(a16, b16);
в diff16 - 8 16-битных разностей. Дальше
__m128i madd = _mm_madd_epi16(diff16, diff16);
вот тут разности умножаются поэлементно на себя, а затем первый результат складывается со вторым, третий с четвертым, пятый с шестым и седьмой с восьмым, в переменной madd теперь 4 32-битных инта. Они поэлементно добавляются в xsum - вектор из 4 интов.

После цикла 4 инта в xsum нужно сложить и получить окончательный ответ. Для этого сдвигаем их на 8 байт вправо и прибавляем, получаем 2 инта-суммы (первый + третий, второй + четвертый) в нижних 8 байтах xsum. Потом аналогично сдвигаем на 4 байта вправо и прибавляем, получаем искомую сумму в одном нижнем инте xsum. Ее и записываем в интовую переменную.
(no subject) - qehgt - Jun. 6th, 2012 01:58 pm (UTC) - Expand
sleepy_drago
Jun. 6th, 2012 03:41 pm (UTC)
ко намекает что вы хотите странного. Наверное единственный компилятор, который "должен по идее уметь колбасить двойные циклы" это intel fortran :D Но я проверять это не буду никогда.

Что касается с++ то альтернативы интринсикам никогда не было. Если за последние 3 года не случилось чуда то intel c++ умудряется просрать все что он выиграл на одиночных циклах msvc практически на любой программе разумного размера. И этому есть хорошее объяснение так как мс оптимизирует кучу уровней абстракции в очень сложном коде - это их конек.

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

счастье всех в том что иерархия памяти сглаживает это все почти в 0 так как пара штрафов (кэш-промахов) и про то сколько там вычислялась та ерунда можно забыть.

имхо^2 мечтать о новых языках на которых можно будет специфицировать до железа можно но практически бессмысленно. Коробочные продукты на них не появятся при нашей жизни. увы. А то чем занимаются авторы golang/llvm/... и тп это печаль./имхо^2
thedeemon
Jun. 6th, 2012 10:29 pm (UTC)
В исходной задаче, по мотивам которой был сделан этот бенчмарк, брался один блок 16х16 и к нему примерялся десяток способов внутриблочного предсказания, с оценкой в виде как раз суммы квадратов ошибки. Там все очень хорошо в кэше сидело, и векторизация дала многократное ускорение. И то, что для этого приходится писать интринсики, удручает. И вообше, хочется поручить это машине, т.к. человек не всегда видит оптимальное решение.
(no subject) - sleepy_drago - Jun. 7th, 2012 05:16 am (UTC) - Expand
(no subject) - tramsm - Jul. 1st, 2012 07:11 pm (UTC) - Expand
mpd
Jun. 7th, 2012 01:19 am (UTC)
Re: компиляторы и SSE, или веселые микробенчмарки
Кстати, может заинтересует, не увидел у вас в друзьях Алексея Тутубалина:
http://alextutubalin.livejournal.com/tag/sse
thedeemon
Jun. 7th, 2012 02:05 am (UTC)
Re: компиляторы и SSE, или веселые микробенчмарки
О, спасибо, не видел раньше этого блога.
permea_kra
Jun. 14th, 2012 04:17 pm (UTC)
Не знаю, за счет чего, но если в строку опций для gcc -O3 -msse2 madd.cpp добавить -floop-strip-mine , появляется ~10% выигрышь времени. За счет чего?
thedeemon
Jun. 15th, 2012 06:58 am (UTC)
У меня наоборот на 5-10% медленнее получилось с этим ключом.
(no subject) - thedeemon - Jun. 15th, 2012 07:01 am (UTC) - Expand
(no subject) - permea_kra - Jun. 15th, 2012 01:13 pm (UTC) - Expand
(no subject) - thedeemon - Jun. 15th, 2012 01:54 pm (UTC) - Expand
Page 1 of 2
<<[1] [2] >>
( 66 comments — Leave a comment )