компиляторы и SSE, или веселые микробенчмарки

[thedeemon]

Есть в программистском фольклоре два поверья:
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

[mr-st.livejournal.com]

Пару лет назад баловался с подобными тестами. Вывод был такой же: кроме интела никто толком векторизовать не умеет.

[stepancheg.livejournal.com]

Выложи куда-нибудь код тестов.

[thedeemon.livejournal.com]

Как-то так:
http://stuff.thedeemon.com/lj/vectest.zip
С++ варианты для GCC, там вместо declspec attribute.

[xeno-by.livejournal.com]

В дотнетовском джите вроде бы SSE и нету. Попробуй на моно.

[potan.livejournal.com]

А такая штука с распараллеливанием на sse не справится?

[mr-aleph.livejournal.com]

это же все голимый паттерн-матчинг по существу, достаточно посмотреть на реализацию vect_recog_dot_prod_pattern в gcc и прослезится.

[wizzard]

Дотнетовский джит, ЕМНИП, вообще на memory access optimization заточен, особенно х64.

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

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

2 thedeemon: а бенчмарк на memory access patterns или что-то такое сделать можешь?

[109.livejournal.com]

> Данные в задаче таковы, что разность помещается в short

а компилятор-то это откуда знает?

[vadim kantorov (from livejournal.com)]

Практически интересный вопрос: MATLAB за сколько такую операцию выполнит?

[soonts.livejournal.com]

Попробовал на C# этот же код.

На моей машине i5-5410M результаты следующие:

Visual Studio 11 developer preview - 4.9 секунд
Visual Studio 2010 - 3.8 секунд.
Visual Studio 2008 - 3.7 секунд.

Во всех случаях - C#, release, Any CPU (т.е. на моей машине x64 код), консольное приложение.

Версия .NET Framework соответственно 4.5 client profile, 4.0 client profile и 3.5 (это были конфигурации по умолчанию при создании консольного C# проекта).

Запускал каждую из трёх версий раз по 10, разброс небольшой, сильно меньше чем разница между студиями.

Время засекал при помощи класса System.Diagnostics.Stopwatch, измерял только время исполнения внутреннего цикла.

А у тебя какой камень был, и время чего именно ты измерял?

[helvegr.livejournal.com]

> Ибо внутри внезапно часть вычислений делаются с плавающей точкой (если я правильно их нашел).

Я посмотрел core, и таких вычислений там не увидел. Вот релевантный кусок (http://hpaste.org/69574).
Видно следующее: а) лишняя проверка на завершение, т.к. 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 нет даже на уровне интринсиков (хотя планируется добавить (http://hackage.haskell.org/trac/ghc/wiki/SIMD/Implementation/Status)).

[thedeemon.livejournal.com]

Отсюда:
short v = a[j] - b[j];

[thedeemon.livejournal.com]

У меня его нет. Попробуйте, мне тоже интересно.

[thedeemon.livejournal.com]

Не знаю, надо пробовать. Кроме нее есть еще такая:
http://ispc.github.com/

[thedeemon.livejournal.com]

Тут мне не очень понятно, как он должен быть устроен.

[thedeemon.livejournal.com]

Если не ошибаюсь, Core 2 Quad Q8200.
Мерял аналогично сам цикл стопвотчем. Забыл в архив .cs положить, сейчас добавил, ссылка та же.

[thedeemon.livejournal.com]

А тенденция очень занятная. Чем можно такую деградацию объяснить?

[nponeccop.livejournal.com]

> Поддержки SSE в GHC нет

Кстати она вроде бы есть в ATS и thedeemon вроде как гуру ATS. Реквестирую версию с интринсиками на ATS!

[nivanych.livejournal.com]

10 лет прошло, как я x86-оптимизацией закончил заниматьася.
С тех пор, почти ничего не изменилось. Печально.
Но вот напомнили про ATS.
Что там, как там? :-)

[helvegr.livejournal.com]

Я попробовал задействовать ispc; получилось в 10 раз медленнее, чем с интринсиками (https://gist.github.com/2880011).

[thedeemon.livejournal.com]

SSE есть для скалярных вещественных операций.
http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/options-platform.html
Даже активно используется.
Чуть позже подробнее посмотрю, в том ли месте я увидел плавучку.

[thedeemon.livejournal.com]

Он же Си генерит, так что не лучше, чем в GCC.

[thedeemon.livejournal.com]

Основные изменения на x86 - теперь часто главное не какие вычисления делать, а как к памяти обращаться. Кэш-миссы слишком дороги.

[helvegr.livejournal.com]

> SSE есть для скалярных вещественных операций.

Да, точно. s/SSE/SIMD/.

[diam-2003.livejournal.com]

В таких случаях ещё принято писать, с какими ключиками запускался компилятор.