Трудности с измерением производительности C / C ++
Я написал фрагмент кода на C, чтобы показать точку в обсуждении оптимизации и прогнозирования ветвлений. Тогда я заметил еще более разнообразный исход, чем ожидал. Моя цель состояла в том, чтобы написать его на языке, который является общим подмножеством между C ++ и C, который совместим со стандартами для обоих языков и который достаточно переносим. Он был протестирован на разных ПК с Windows:
#include <stdio.h>
#include <time.h>
/// @return - time difference between start and stop in milliseconds
int ms_elapsed( clock_t start, clock_t stop )
{
return (int)( 1000.0 * ( stop - start ) / CLOCKS_PER_SEC );
}
int const Billion = 1000000000;
/// & with numbers up to Billion gives 0, 0, 2, 2 repeating pattern
int const Pattern_0_0_2_2 = 0x40000002;
/// @return - half of Billion
int unpredictableIfs()
{
int sum = 0;
for ( int i = 0; i < Billion; ++i )
{
// true, true, false, false ...
if ( ( i & Pattern_0_0_2_2 ) == 0 )
{
++sum;
}
}
return sum;
}
/// @return - half of Billion
int noIfs()
{
int sum = 0;
for ( int i = 0; i < Billion; ++i )
{
// 1, 1, 0, 0 ...
sum += ( i & Pattern_0_0_2_2 ) == 0;
}
return sum;
}
int main()
{
clock_t volatile start;
clock_t volatile stop;
int volatile sum;
printf( "Puzzling measurements:\n" );
start = clock();
sum = unpredictableIfs();
stop = clock();
printf( "Unpredictable ifs took %d msec; answer was %d\n", ms_elapsed(start, stop), sum );
start = clock();
sum = unpredictableIfs();
stop = clock();
printf( "Unpredictable ifs took %d msec; answer was %d\n", ms_elapsed(start, stop), sum );
start = clock();
sum = noIfs();
stop = clock();
printf( "Same without ifs took %d msec; answer was %d\n", ms_elapsed(start, stop), sum );
start = clock();
sum = unpredictableIfs();
stop = clock();
printf( "Unpredictable ifs took %d msec; answer was %d\n", ms_elapsed(start, stop), sum );
}
Составлено с VS2010; / O2 оптимизации Intel Core 2, WinXP результаты:
Puzzling measurements:
Unpredictable ifs took 1344 msec; answer was 500000000
Unpredictable ifs took 1016 msec; answer was 500000000
Same without ifs took 1031 msec; answer was 500000000
Unpredictable ifs took 4797 msec; answer was 500000000
Редактировать: Полные переключатели компилятора:
/ Zi / nologo / W3 / WX- / O2 / Oi / Oy- / GL / D «WIN32» / D «NDEBUG» / D «_CONSOLE» / D «_UNICODE» / D «UNICODE» / Gm- / EHsc / GS / Gy / fp: точный / Zc: wchar_t / Zc: forScope /Fp»Release\Tiring.pch «/ Fa» Release \ «/ Fo» Release \ «/Fd»Release\vc100.pdb» / Gd / analysis- / errorReport: очереди
Другой человек написал такое … Скомпилировано с MinGW, g ++ 4.71, оптимизация -O1 Intel Core 2, WinXP:
Puzzling measurements:
Unpredictable ifs took 1656 msec; answer was 500000000
Unpredictable ifs took 0 msec; answer was 500000000
Same without ifs took 1969 msec; answer was 500000000
Unpredictable ifs took 0 msec; answer was 500000000
Также он опубликовал такие результаты для оптимизации -O3:
Puzzling measurements:
Unpredictable ifs took 1890 msec; answer was 500000000
Unpredictable ifs took 2516 msec; answer was 500000000
Same without ifs took 1422 msec; answer was 500000000
Unpredictable ifs took 2516 msec; answer was 500000000
Теперь у меня есть вопрос. Что здесь происходит?
Более конкретно … Как фиксированная функция может занимать так много времени? Что-то не так в моем коде? Есть ли что-то хитрое с процессором Intel? Компиляторы делают что-то странное? Может ли это быть из-за того, что 32-битный код работал на 64-битном процессоре?
Спасибо за внимание!
Редактировать:
Я принимаю, что g ++ -O1 просто повторно использует возвращенные значения в 2 других вызовах. Я также признаю, что g ++ -O2 и g ++ -O3 имеют дефект, который не учитывает оптимизацию. Значительное разнообразие измеренных скоростей (450% !!!) кажется все еще загадочным.
Я посмотрел на разборку кода, созданного VS2010. Это встроенный unpredictableIfs три раза. Встроенный код был довольно похож; петля была такая же. Не встроенный noIfs, Это действительно катилось noIfs немного. Это занимает 4 шага за одну итерацию. noIfs рассчитать как было написано в то время как unpredictableIfs использование jne перепрыгнуть через шаг.
Решение
С -O1, вызовы gcc-4.7.1 unpredictableIfs только один раз и повторно использует результат, поскольку он распознает, что это чистая функция, поэтому результат будет одинаковым при каждом вызове. (Мой сделал, проверил, посмотрев на сгенерированную сборку.)
При более высоком уровне оптимизации функции встроены, и компилятор больше не распознает, что это один и тот же код, поэтому он запускается каждый раз, когда в источнике появляется вызов функции.
Кроме того, мой gcc-4.7.1 лучше всего справляется с unpredictableIfs когда используешь -O1 или же -O2 (кроме проблемы повторного использования, оба производят один и тот же код), в то время как noIfs лечится много лучше с -O3, Времена между различными запусками одного и того же кода здесь согласованы — равны или различаются на 10 миллисекунд (гранулярность clock), поэтому я понятия не имею, что может вызвать существенно разные времена для unpredictableIfs вы сообщили для -O3,
С -O2петля для unpredictableIfs идентичен коду, созданному с -O1 (кроме замены регистра):
.L12:
movl %eax, %ecx
andl $1073741826, %ecx
cmpl $1, %ecx
adcl $0, %edx
addl $1, %eax
cmpl $1000000000, %eax
jne .L12
и для noIfs это похоже:
.L15:
xorl %ecx, %ecx
testl $1073741826, %eax
sete %cl
addl $1, %eax
addl %ecx, %edx
cmpl $1000000000, %eax
jne .L15
где это было
.L7:
testl $1073741826, %edx
sete %cl
movzbl %cl, %ecx
addl %ecx, %eax
addl $1, %edx
cmpl $1000000000, %edx
jne .L7
с -O1, Оба цикла работают в одинаковое время, с unpredictableIfs немного быстрее
С -O3петля для unpredictableIfs становится хуже,
.L14:
leal 1(%rdx), %ecx
testl $1073741826, %eax
cmove %ecx, %edx
addl $1, %eax
cmpl $1000000000, %eax
jne .L14
и для noIfs (включая установочный код здесь), он становится лучше:
pxor %xmm2, %xmm2
movq %rax, 32(%rsp)
movdqa .LC3(%rip), %xmm6
xorl %eax, %eax
movdqa .LC2(%rip), %xmm1
movdqa %xmm2, %xmm3
movdqa .LC4(%rip), %xmm5
movdqa .LC5(%rip), %xmm4
.p2align 4,,10
.p2align 3
.L18:
movdqa %xmm1, %xmm0
addl $1, %eax
paddd %xmm6, %xmm1
cmpl $250000000, %eax
pand %xmm5, %xmm0
pcmpeqd %xmm3, %xmm0
pand %xmm4, %xmm0
paddd %xmm0, %xmm2
jne .L18
.LC2:
.long 0
.long 1
.long 2
.long 3
.align 16
.LC3:
.long 4
.long 4
.long 4
.long 4
.align 16
.LC4:
.long 1073741826
.long 1073741826
.long 1073741826
.long 1073741826
.align 16
.LC5:
.long 1
.long 1
.long 1
.long 1
он вычисляет четыре итерации одновременно и, соответственно, noIfs работает почти в четыре раза быстрее.
Другие решения
Хорошо, глядя на код ассемблера от gcc в 64-битной Linux, первый случай, с -O1, функция UnpredictableIfs действительно вызывается только один раз, а результат используется повторно.
С -O2 и -O3 функции встроены, и время, которое требуется, должно быть идентичным. Также нет ни одной фактической ветви ни в одном бите кода, но перевод для двух битов кода несколько отличается, я вырезал строки, которые обновляют «сумму» [в %edx в обоих случаях]
UnpredictableIfs:
movl %eax, %ecx
andl $1073741826, %ecx
cmpl $1, %ecx
adcl $0, %edx
addl $1, %eax
NoIfs:
xorl %ecx, %ecx
testl $1073741826, %eax
sete %cl
addl $1, %eax
addl %ecx, %edx
Как видите, он не совсем идентичен, но делает очень похожие вещи.
Относительно диапазона результатов в Windows (от 1016 мс до 4797 мс): вы должны знать, что clock() в MSVC возвращается прошедшее время. Стандарт говорит clock() должен вернуть приближение Процессорное время, затраченное на процесс, и другие реализации лучше справляются с этой задачей.
Учитывая, что MSVC дает время простоя, если ваш процесс был перегружен во время выполнения одной итерации теста, он мог бы дать гораздо больший результат, даже если код выполнялся примерно с тем же количеством процессорного времени.
Также обратите внимание, что clock() на многих компьютерах с ОС Windows разрешение выглядит довольно паршивым, часто оно составляет 11-19 мс. Вы сделали достаточно итераций, и это всего лишь около 1%, поэтому я не думаю, что это является частью несоответствия, но это полезно знать при попытке написать эталонный тест. Я понимаю, что вы собираетесь на переносимость, но если вам нужно лучшее измерение на Windows, вы можете использовать QueryPerformanceCounter что почти наверняка даст вам гораздо лучшее разрешение, хотя до стены все еще остается время.
ОБНОВИТЬ: После того, как я узнал, что длительное время выполнения одного случая происходило последовательно, я запустил VS2010 и воспроизвел результаты. Я обычно получал около 1000 мс для одних прогонов, 750 мс для других и 5000+ мс для необъяснимых.
Замечания:
- Во всех случаях код unpredictableIfs () был встроен.
- Удаление кода noIfs () не оказало никакого влияния (поэтому долгое время не было побочным эффектом этого кода).
- Установка привязки потока к одному процессору не имела никакого эффекта.
- 5000 мс были неизменно поздними примерами. Я отметил, что более поздние экземпляры имели дополнительную инструкцию до начало цикла:
lea ecx,[ecx], Я не понимаю, почему это должно иметь значение в 5 раз. Кроме этого ранние и поздние экземпляры были идентичным кодом. - Удаление
volatileотstartа такжеstopпеременные дали меньше длинные пробеги, больше из 750 мс работает, и не 1000 мс работает. (Сгенерированный код цикла теперь выглядит одинаково во всех случаях, а неleaс.) - Удаление
volatileотsumпеременная (но сохраняя это для таймеров), длинные пробеги могут происходить в любой позиции. - Если вы удалите все
volatileквалификаторы, вы получаете последовательные, быстрые (750 мс) запуски. (Код выглядит идентично предыдущим, ноediбыл выбран дляsumвместоecx.)
Я не уверен, что делать вывод из всего этого, кроме того, что volatile имеет непредсказуемые последствия для производительности с MSVC, поэтому вы должны применять его только при необходимости.
ОБНОВЛЕНИЕ 2: Я вижу постоянные различия во время выполнения, связанные с использованием volatile, хотя разборка практически идентична.
С изменчивым:
Puzzling measurements:
Unpredictable ifs took 643 msec; answer was 500000000
Unpredictable ifs took 1248 msec; answer was 500000000
Unpredictable ifs took 605 msec; answer was 500000000
Unpredictable ifs took 4611 msec; answer was 500000000
Unpredictable ifs took 4706 msec; answer was 500000000
Unpredictable ifs took 4516 msec; answer was 500000000
Unpredictable ifs took 4382 msec; answer was 500000000
Разборка для каждого экземпляра выглядит следующим образом:
start = clock();
010D1015 mov esi,dword ptr [__imp__clock (10D20A0h)]
010D101B add esp,4
010D101E call esi
010D1020 mov dword ptr [start],eax
sum = unpredictableIfs();
010D1023 xor ecx,ecx
010D1025 xor eax,eax
010D1027 test eax,40000002h
010D102C jne main+2Fh (10D102Fh)
010D102E inc ecx
010D102F inc eax
010D1030 cmp eax,3B9ACA00h
010D1035 jl main+27h (10D1027h)
010D1037 mov dword ptr [sum],ecx
stop = clock();
010D103A call esi
010D103C mov dword ptr [stop],eax
Без летучих:
Puzzling measurements:
Unpredictable ifs took 644 msec; answer was 500000000
Unpredictable ifs took 624 msec; answer was 500000000
Unpredictable ifs took 624 msec; answer was 500000000
Unpredictable ifs took 605 msec; answer was 500000000
Unpredictable ifs took 599 msec; answer was 500000000
Unpredictable ifs took 599 msec; answer was 500000000
Unpredictable ifs took 599 msec; answer was 500000000
start = clock();
00321014 mov esi,dword ptr [__imp__clock (3220A0h)]
0032101A add esp,4
0032101D call esi
0032101F mov dword ptr [start],eax
sum = unpredictableIfs();
00321022 xor ebx,ebx
00321024 xor eax,eax
00321026 test eax,40000002h
0032102B jne main+2Eh (32102Eh)
0032102D inc ebx
0032102E inc eax
0032102F cmp eax,3B9ACA00h
00321034 jl main+26h (321026h)
stop = clock();
00321036 call esi
// The only optimization I see is here, where eax isn't explicitly stored
// in stop but is instead immediately used to compute the value for the
// printf that follows.
Кроме выбора регистра, я не вижу существенной разницы.