Трудности измерения производительности 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: exact/Zc: wchar_t/Zc: forScope/Fp "Release\Trying.pch" /Fa "Release\" /Fo "Release\" /Fd "Release\vc100.pdb" /Gd/analysis -/errorReport: queue
Другое лицо опубликовано такое... Скомпилировано с 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-битном процессоре?
Спасибо за внимание!
Edit:
Я принимаю, что g++ -O1 просто повторно использует возвращаемые значения в двух других вызовах. Я также согласен с тем, что g++ -O2 и g++ -O3 имеют дефект, который оставляет оптимизацию. Значительное разнообразие измеренных скоростей (450%!!!) кажется загадочным.
Я посмотрел на разборку кода, созданного VS2010. Он сделал inline unpredictableIfs 3 раза. Встроенный код был довольно схожим; петля была такой же. Он не встроил noIfs. Он немного отбросил noIfs. Для одной итерации требуется 4 шага. noIfs вычислить, как было написано, а unpredictableIfs использовать jne для перехода через приращение.
Ответы
Ответ 1
С -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 выполняется почти в четыре раза быстрее.
Ответ 2
Правильно, глядя на код ассемблера из 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
Как вы можете видеть, это не совсем идентично, но это очень похоже на вещи.
Ответ 3
Относительно диапазона результатов в Windows (от 1016 мс до 4797 мс): вы должны знать, что clock() в MSVC возвращает прошедшее время стены. В стандарте указано, что clock() должен возвращать приблизительное время процессора, затрачиваемое процессом, а другие реализации лучше справляются с этим.
Учитывая, что MSVC дает время на стене, если ваш процесс получил предварительную утилизацию при выполнении одной итерации теста, это может дать гораздо больший результат, даже если код работает примерно с таким же количеством процессорного времени.
Также обратите внимание, что clock() на многих ПК с ОС Windows имеет довольно паршивое разрешение, часто как 11-19 мс. Вы сделали достаточно итераций, что только около 1%, поэтому я не думаю, что это часть несоответствия, но хорошо знать, когда вы пытаетесь написать бенчмарк. Я понимаю, что вы идете на переносимость, но если вам нужны лучшие измерения в Windows, вы можете использовать QueryPerformanceCounter, что почти наверняка даст вам гораздо лучшее разрешение, хотя оно все еще только истекло, настенное время.
ОБНОВЛЕНИЕ: После того, как я узнал, что длительное время выполнения в одном случае происходит последовательно, я запускал VS2010 и воспроизводил результаты. Обычно я получаю что-то около 1000 мс для некоторых прогонов, 750 мс для других и 5000+ мс для необъяснимых.
замечания:
- Во всех случаях код incredictableIfs() был встроен.
- Удаление кода noIfs() не повлияло (поэтому долгое время не было побочным эффектом этого кода).
- Настройка привязки потоков к одному процессору не имела эффекта.
- Времена 5000 мс неизменно были более поздними. Я отметил, что более поздние экземпляры имели дополнительную инструкцию перед началом цикла:
lea ecx,[ecx]. Я не понимаю, почему это должно сделать разницу в 5 раз. Кроме того, ранние и более поздние экземпляры были идентичными.
- Удаление
volatile из переменных start и stop дало меньше длинных прогонов, больше пробега 750 мс и не работает 1000 мс. (Созданный код цикла во всех случаях выглядит точно таким же, а не lea s.)
- Удаляя
volatile из переменной sum (но сохраняя ее для таймеров синхронизации), длинные прогоны могут выполняться в любой позиции.
- Если вы удалите все квалификаторы
volatile, вы получите последовательные, быстрые (750 мс) прогоны. (Код выглядит идентичным предыдущим, но edi был выбран для sum вместо ecx.)
Я не уверен, что заключить из всего этого, за исключением того, что volatile имеет непредсказуемые последствия производительности с MSVC, поэтому вы должны применять его только при необходимости.
ОБНОВЛЕНИЕ 2: Я вижу согласованные различия во времени выполнения, связанные с использованием летучих, даже несмотря на то, что разборка почти идентична.
С изменчивым:
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.
Помимо выбора регистра, я не вижу существенной разницы.
