Pull to refresh

Про мнимые и реальные оптимизации в 10 раз, целительный SSE, и все такое

Reading time 6 min
Views 38K
По мотивам одного вчерашнего поста про оптимизацию условных переходов при расчете x=sign(a,b)*min(abs(a), abs(b)) якобы в 10 раз. Краткая сводка:

  • оптимизация налицо, но размер мнимый: не в 10 раз, а 2.5 раза;
  • бенчмарки надо делать правильно: не надо мерить CPU stalls, RAM bandwidth итп вместо исследуемой функции;
  • бенчмарки надо делать правильно: иначе могут дико дрожать;
  • выставлять только приоритет прикольно, но на коротких бенчмарках зря: +0.5% скорости, -15% дрожания;
  • нужно мерить исследуемую функцию и только ее, только так получаешь корректные данные;
  • нужно греть проц, нужно считать минимум из N прогонов/секунд, только так побеждаешь дрожание;
  • нужно пользовать SSE, с ним получилось 8.6 раз, причем код… читается.

В общем, опять пачка классических методологических ошибок при бенчмарке. Кому интересно, как такие ошибки НЕ делать, подробности, детальный разбор полетов, оптимизация в еще несколько раз и, главное, исходники под катом.

Прочитал вчера исходный пост, очень удивился ускорению в 10 раз за счет ликвидации переходов, даром, что на синтетике. Это слишком много, переходы дорогие, но не настолько. Попробовал повторить результаты, посмотрел внимательнее, и натурально: опять детсадовские ошибки в методике бенчмарка! Что же, пора их опять разобрать, пример хороший.

Ошибка #1 заключается в том, что приведенный исходный код тупо не мерит вообще ничего вменяемого. Сумма результатов llr() считается, и это хорошо. Но компилятор видит, что она не используется никак, и поэтому имеет полное право соптимизировать. У меня как раз соптимизировал. Вдобавок исходно опубликованные (теперь разобрались и исправили) варианты оптимизаций считали вообще не тот результат, и это было незаметно. Ох…

Мораль #1: пацаны, печатайте результаты, ВСЕГДА. И ошибки сразу поймаешь, и компилятор «ненужный» цикл не выкинет. Еще помогает объявить результат как volatile, но печатать его все равно надо.

Ошибка #2 заключается в том, что автор мерит цикл rand()+llr(), затем мерит цикл rand()+llr2(), затем рукой и на глазок вычитает время исполнения. Это плохая идея по двум причинам. rand очень тормозной, бенчмарк получается неоправданно долгий. ;) Это раз. В эксперименте измеряется производительность фарша из двух функций, а этот фарш заведомо ведет себя НЕ так, как только нужная функция. Это два.

В общем случае подход «давайте померим фарш из функций A+B» негоден потому, что компилятор того, может перемешать вычисления. Получится, что часть «измеряемой» функции B спряталась в функцию A, и на самом деле мы мерим неизвестную часть от B. Хорошо, когда A+B это боевая пара, использующаяся именно так. Плохо, когда вместо A тестовая синтетика типа rand().

В данном случае такого перемешивания не происходит, в дизасме call _rand() без всяких попыток его инлайнить, но явно происходит некая другая беда. Какая именно, я не понимаю, но рабочая гипотеза про CPU stalls. Гипотеза оттого, что немного оттянув начало вычислений llr(), которое начинается с инструкции test esi, esi, где esi почти что только что вернули из rand(), удается измеримо ускорить исходный бенчмарк. При этом просто повторить цикл 2 раза, понятное дело, эффекта не дает, надо именно разнести вычисления:

10.7 sec, rand()
13.3 sec, rand() + llr()
12.6 sec, rand() + llr() + 2x unroll

// 2x unroll без ускорения, 13.3 sec
int a = rand() - RAND_MAX / 2;
int b = rand() - RAND_MAX / 2;
x += LLR(a,b);
a = rand() - RAND_MAX / 2;
b = rand() - RAND_MAX / 2;
x += LLR(a,b);

// 2x unroll c ускорением, 12.6 sec
int a = rand() - RAND_MAX / 2;
int b = rand() - RAND_MAX / 2;
int a2 = rand() - RAND_MAX / 2;
int b2 = rand() - RAND_MAX / 2;
x += LLR(a,b);
x += LLR(a2,b2);


В одном из экспериментов, кстати, ускорение до 12.8 sec вообще давала тупо вставка asm { nop } перед x += LLR(a,b), однако уверенно повторить такое чудо не удалось. Какая-то случайная флуктуация. Но в общем и целом, наглядно видно, что мерить фарш из тяжелого rand() и легкого llr() это занятие, хм, нетривальное. Я предполагаю, что где-то в паре инструкций test/jxx возникают stalls из-за того, что выражение подсчитали вот только что. Может, кто-нибудь, у кого есть под руками VTune, сможет посмотреть поточнее, отчего так.

Мораль #2: пацаны, не мерьте фарш из исследуемой функции и синтетики, мерьте только нужную вам функцию. Как компилятор перемешает тот фарш и какие спецэффекты появятся на стыке, не угадать.

Избавляемся от тормозного rand(), выносим предрасчет достаточно большого блока случайных чисел за цикл, внутри цикла оставляем только вычисление и суммирование llr(). Итого мерим вдобавок к функции еще и оверхед на доступ к памяти, но при линейном чтении он минимальный. ВНЕЗАПНО, вместо мнимого ускорения в 10 раз наблюдаем реальное ускорение в скромные 2.5 раза.

Ок, это уже согласуется с ожиданиями, но теперь недостаточно быстро и хорошо ;)

На помощь приходит SSE. У меня на десктопе неновый Core2Duo E8500, но даже он умеет SSE4. Разворачиваем цикл в 4 раза, считаем по 4 пары зараз. Прямо в лоб пользуемся специнструкциями для вычисления sign, abs.

1.073 sec, llr() baseline
0.438 sec, llr2() optimized, 2.5x
0.125 sec, llr4() sse + 4x unroll, 8.6x

Что интересно, код довольно читаем. Единственно что, надо аккуратно откомментировать _mm_sign_epi32(). Первое, он внезапно берет еще и 2й аргумент, и как бы умножает его на знак 1го аргумента. То, что надо. Второе, при этом _mm_sign(0)=0, а не 1, как для каких-то задач могло бы хотеться. Однако для наших целей разницы нет, тк. если abs(a) либо abs(b) равны 0, то sign*min(abs)=0, поэтому ошибки нет.

static inline __m128i LLR4(const int * pa, const int * pb)
{
	__m128i a = *(__m128i*)pa;
	__m128i b = *(__m128i*)pb;

	// sign(a,b)*min(abs(a),abs(b))
	__m128i absa = _mm_abs_epi32(a);
	__m128i absb = _mm_abs_epi32(b);
	__m128i absm = _mm_min_epi32(absa, absb);
	__m128i ab = _mm_mullo_epi32(a, b);
	__m128i rr = _mm_sign_epi32(absm, ab);
	return rr;
}


Заметка на полях: что интересно, суммирование компонент регистра через _mm_hadd_epi32 вместо выгрузки регистра в память и суммирования затем 4 обычных int результатов не дает. Вот бы уже увидеть эффект от hadd наконец хоть где-нибудь, давно хочу.

Еще заметка: что интересно, дальнейшее разворачивание цикла тоже результатов не дает. Видимо, уже упирается в скорость чтения памяти, там около 6.4 GB/sec выходит.

Ошибка #3, значится, в том, что давно доступные SSE расширения не задействованы, все доблестные оптимизации зачем-то выполнены под платформу, по существу, i386.

Это спорный вывод, долго думал, писать его или как. «Ошибка» это или нет? Я лично считаю, что да. Потому что если уж оптимизировать, так по-большому! Схоласты в каментах наверняка завоют, что таки нет. Ведь эта версия векторизована и работает по 4 пары чисел зараз, а это решительно несовместимое изменение исходной функции. Плюс оптимизации под i386 тоже очень ценны, вдруг программу запустят не на i7, а на памятнике IT археологии. Однако в любом случае, мораль уж точно одинакова.

Мораль #3: пацаны, нынче 2013 год, SSE4 есть почти везде, SSE2 уаабще везде, поступайте соответственно, оптимизируйте (по возможности) под 99% пользователей, а не 1% fallback.

Получившаяся SSE версия теперь уже достаточно бодра, чтобы наблюдать, как время на разных запусках пляшет от 0.125 до 0.145 секунд. Почти 20% разницы. Ох…

Ошибка #4 только что появилась за счет оптимизации ;) Выставление высоких приоритета треда и процесса дает около 0.5% производительности, но никак спасает от дрожания измерений. Первое, простаивающий процессор сбрасывает частоту, а обратно ее набирает не сразу. За 10+ сек успевает, за 0.1 сек нет. Второе, даже если прогнать коротенький тест 100 раз, время каждой отдельной итерации все равно будет плясать. И в начале, и в конце этих 100 прогонов. Мало ли, что там в якобы простаивающей системе с 99% idle таки себе фоном работает и как влияет.

Процессор надо «греть» и даже после этого результаты (достаточно коротеньких) прогонов надо фильтровать. Просто сделать чуть побольше итераций и усреднять недостаточно, общее время все равно заметно дрожит. Выкинуть первые «холодные» итерации недостаточно тоже, результат дрожит. Можно считать среднее и дисперсию, выкидывать outliers, где abs(value-mean)>=k*stddev, затем пересчитывать среднее, я попробовал, но и это дрожит!

А менее всего дрожит такой нехитрый метод: делаем несколько прогонов (я делаю 10) и выбираем из них минимальное время одного прогона. Оказывается, что такой минимум стоит как вкопанный, отличия по нескольким запускам максимум на 0.5%.

Обратите внимание: прогоны эти надо делать вдобавок к первоначальному разогреву в течение 3-10 сек, иначе 10*0.1 = 1 сек опять не хватит для набора эшелона и несмотря на фокус с минимумом, время все равно будет дрожать. Либо же прогонов надо делать (сильно) более 10. В нашем примере самая первая референсная реализация заодно работает как такой разогрев. Но если строчку Bench(Test1) закомментировать, опять начнутся пляски им.тов.св.Витта. Опа, throttling style!

Мораль #4: пацаны, грейте проц не менее 3 сек, а лучше 10 сек и вдобавок считайте минимум по N прогонов.

При бенчмарках можно допустить еще кучу ошибок, и наверняка в итоговом коде (кстати, вот он: gist.github.com/anonymous/5605201) еще что-нибудь пропущено, но сегодня мы разбирали вот эти. Надеюсь, не совершенно бесполезно.

Будьте бдительны, мерьте правильно, оптимизируйте без пощады и до конца ;)
Tags:
Hubs:
+140
Comments 60
Comments Comments 60

Articles