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

По мотивам вчерашнего поста про оптимизацию условных переходов при расчете 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(), затем рукой и на глазок вычитает время исполнения. Это плохая идея по двум причинам. Во1х, rand очень тормозной, бенчмарк получается неоправданно долгий. 😉 Во2х, в эксперименте измеряется производительность фарша из двух функций, а этот фарш заведомо ведет себя НЕ так, как только нужная функция.

В общем случае подход «давайте померим фарш из функций A+B» негоден потому, что компилятор того, может перемешать вычисления. Получится, что часть «измерямой» функции B спряталась в функцию A. Хорошо, когда 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(). Во1х, он внезапно берет еще и 2й аргумент, и как бы умножает его на знак 1го аргумента. То, что надо. Во2х, при этом _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 чисел результатов не дает. Вот бы уже увидеть эффект от hadd наконец хоть где-нибудь, давно хочу.

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

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

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

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

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

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

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

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

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

Будьте бдительны, мерьте правильно, оптимизируйте без пощады и до конца 😉