Цикл с вызовом функции быстрее, чем пустой цикл
Я связал некоторую сборку с некоторым c для проверки стоимости вызова функции со следующей сборкой и исходным кодом c (используя fasm и gcc соответственно)
монтаж:
format ELF
public no_call as "_no_call"
public normal_call as "_normal_call"
section '.text' executable
iter equ 100000000
no_call:
mov ecx, iter
@@:
push ecx
pop ecx
dec ecx
cmp ecx, 0
jne @b
ret
normal_function:
ret
normal_call:
mov ecx, iter
@@:
push ecx
call normal_function
pop ecx
dec ecx
cmp ecx, 0
jne @b
ret
c источник:
#include <stdio.h>
#include <time.h>
extern int no_call();
extern int normal_call();
int main()
{
clock_t ct1, ct2;
ct1 = clock();
no_call();
ct2 = clock();
printf("\n\n%d\n", ct2 - ct1);
ct1 = clock();
normal_call();
ct2 = clock();
printf("%d\n", ct2 - ct1);
return 0;
}
Результаты, которые я получил, были удивительными. Прежде всего, скорость зависела от порядка, в котором я имел значение. Если бы я связал как gcc intern.o extern.oтипичный вывод
162
181
Но ссылки в обратном порядке gcc extern.o intern.oЯ получил вывод больше как:
162
130
То, что они разные, было очень удивительно, но это не тот вопрос, который я задаю. ( соответствующий вопрос здесь)
Вопрос, который я задаю, состоит в том, как во время второго цикла цикл с вызовом функции был быстрее, чем без цикла, как стоимость вызова функции, по-видимому, была отрицательной.
Изменить: просто чтобы упомянуть некоторые вещи, которые пытались в комментариях:
- В скомпилированном байт-коде вызовы функций не были оптимизированы.
- Корректировка выравнивания функций и циклов по всем границам от 4 до 64 байтов не ускорила no_call, хотя некоторые выравнивания замедлили normal_call
- Предоставление процессору / ОС возможности разогреваться, вызывая функции несколько раз, а не один раз, не оказало заметного влияния на измеренную продолжительность, а также не изменило порядок вызовов или не выполнило их отдельно.
- Запуск в течение более длительного времени не влияет на соотношение, например, в 1000 раз дольше я получил
162.168а также131.578секунды для моих пробежек
Кроме того, после изменения кода ассемблера для выравнивания по байтам я протестировал добавление набора функций к дополнительному смещению и пришел к более странным выводам. Вот обновленный код:
format ELF
public no_call as "_no_call"
public normal_call as "_normal_call"
section '.text' executable
iter equ 100000000
offset equ 23 ; this is the number I am changing
times offset nop
times 16 nop
no_call:
mov ecx, iter
no_call.loop_start:
push ecx
pop ecx
dec ecx
cmp ecx, 0
jne no_call.loop_start
ret
times 55 nop
normal_function:
ret
times 58 nop
normal_call:
mov ecx, iter
normal_call.loop_start:
push ecx
call normal_function
pop ecx
dec ecx
cmp ecx, 0
jne normal_call.loop_start
ret
Мне пришлось вручную (и не переносить) принудительное выравнивание 64 байтов, поскольку FASM не поддерживает выравнивание более 4 байтов для исполняемого раздела, по крайней мере, на моей машине. Смещение программы по offset байты, вот что я нашел.
if (20 <= offset mod 128 <= 31) then we get an output of (approximately):
162
131
else
162 (+/- 10)
162 (+/- 10)
Не знаю, что с этим делать, но это то, что я обнаружил до сих пор.
Изменить 2:
Еще одна вещь, которую я заметил, что если вы удалите push ecx а также pop ecx из обеих функций вывод становится
30
125
что указывает на то, что это самая дорогая часть этого. Выравнивание стека в обоих случаях одинаково, так что это не является причиной несоответствия. Я думаю, что аппаратное обеспечение каким-то образом оптимизировано для ожидания вызова после пуша или чего-то подобного, но я не знаю ничего подобного
2 ответа
Обновление: задержка хранения / перезагрузки Skylake составляет всего 3с, но только если время выбрано правильно. Последовательные нагрузки, включенные в цепочку зависимостей пересылки магазина, которые естественным образом распределены на 3 или более циклов, будут испытывать более быстрое время ожидания (например, с 4 imul eax,eax в петле, mov [rdi], eax / mov eax, [rdi] только увеличивает количество циклов от 12 до 15 циклов за итерацию.) но когда нагрузкам разрешено выполнять более плотно, это приводит к некоторому типу конкуренции, и вы получаете около 4,5 циклов за итерацию. Нецелая средняя пропускная способность также является большим признаком того, что есть что-то необычное.
Я наблюдал тот же эффект для векторов 32B (в лучшем случае 6.0c, от 6 до 6.9c), но векторы 128b всегда были около 5.0c. Смотрите подробности на форуме Agner Fog.
Обновление 2. Добавление избыточного назначения ускоряет код при компиляции без оптимизации, а сообщение в блоге 2013 года указывает на то, что этот эффект присутствует на всех процессорах семейства Sandybridge.
Задержка пересылки магазина (в худшем случае) на Skylake на 1 такт лучше, чем на предыдущих версиях, но изменчивость, когда нагрузка не может быть выполнена сразу же, аналогична.
При правильном (неправильном) выравнивании call в цикле может фактически помочь Skylake наблюдать более низкую задержку пересылки магазина от push до pop. Я смог воспроизвести это с помощью счетчиков перфорации (Linux perf stat -r4), используя YASM. (Я слышал, что в Windows менее удобно использовать счетчики перфектов, и у меня все равно нет машины для разработки под Windows. К счастью, ОС на самом деле не имеет отношения к ответу; каждый должен иметь возможность воспроизвести результаты моего перфронтера на Windows с VTune или что-то.)
Я видел более быстрые времена со смещением = 0,10, 37, 63-74, 101 и 127 послеalign 128 в месте, указанном в вопросе. Кэши L1I имеют размер 64B, а uop-кеш заботится о границах 32B. Похоже, выравнивание относительно границы 64B - это все, что имеет значение.
Цикл без вызова всегда 5 циклов, но call цикл может опуститься до 4с за итерацию от своих обычных почти ровно 5 циклов. Я видел более медленную, чем обычно, производительность со смещением =38 (5,68 +- 8,3% циклов на итерацию). В других точках есть небольшие глюки, такие как 5.17c +- 3.3%, согласно perf stat -r4 (который делает 4 прогона и усреднения).
Кажется, это взаимодействие между интерфейсом, не стоящим в очереди на столько мопов впереди, в результате чего фоновый период имеет меньшую задержку для пересылки из магазина от push к pop.
IDK, если многократное повторное использование одного и того же адреса для пересылки в хранилище делает его медленнее (с несколькими выполненными миссиями хранилища, уже выполненными перед соответствующими мерами хранилища данных), или чем.
Тестовый код: bashОболочка цикла для создания и профилирования asm с каждым другим смещением:
(set -x; for off in {0..127};do
asm-link -m32 -d call-tight-loop.asm -DFUNC=normal_call -DOFFSET=$off &&
ocperf.py stat -etask-clock,context-switches,cpu-migrations,page-faults:u,cycles,instructions,uops_issued.any,uops_executed.thread,idq.mite_uops,dsb2mite_switches.penalty_cycles -r4 ./call-tight-loop;
done ) |& tee -a call-tight-loop.call.offset-log
(set -x)в подоболочке это удобный способ регистрировать команды вместе с их выводом при перенаправлении в файл журнала.
asm-link это скрипт, который запускается yasm -felf32 -Worphan-labels -gdwarf2 call-tight-loop.asm "$@" && ld -melf_i386 -o call-tight-loop call-tight-loop.o, затем бежит objdumps -drwC -Mintel на результат.
Тестовая программа NASM / YASM для Linux (собирается в полный статический двоичный файл, который запускает цикл, а затем завершает работу, поэтому вы можете профилировать всю программу.) Прямой порт источника FASM OP, без оптимизации в asm.
CPU p6 ; YASM directive. For NASM, %use smartalign.
section .text
iter equ 100000000
%ifndef OFFSET
%define OFFSET 0
%endif
align 128
;;offset equ 23 ; this is the number I am changing
times OFFSET nop
times 16 nop
no_call:
mov ecx, iter
.loop:
push ecx
pop ecx
dec ecx
cmp ecx, 0
jne .loop
ret
times 55 nop
normal_function:
ret
times 58 nop
normal_call:
mov ecx, iter
.loop:
push ecx
call normal_function
pop ecx
dec ecx
cmp ecx, 0
jne .loop
ret
%ifndef FUNC
%define FUNC no_call
%endif
align 64
global _start
_start:
call FUNC
mov eax,1 ; __NR_exit from /usr/include/asm/unistd_32.h
xor ebx,ebx
int 0x80 ; sys_exit(0), 32-bit ABI
Пример вывода из быстрого call бежать:
+ asm-link -m32 -d call-tight-loop.asm -DFUNC=normal_call -DOFFSET=3
...
080480d8 <normal_function>:
80480d8: c3 ret
...
08048113 <normal_call>:
8048113: b9 00 e1 f5 05 mov ecx,0x5f5e100
08048118 <normal_call.loop>:
8048118: 51 push ecx
8048119: e8 ba ff ff ff call 80480d8 <normal_function>
804811e: 59 pop ecx
804811f: 49 dec ecx
8048120: 83 f9 00 cmp ecx,0x0
8048123: 75 f3 jne 8048118 <normal_call.loop>
8048125: c3 ret
...
Performance counter stats for './call-tight-loop' (4 runs):
100.646932 task-clock (msec) # 0.998 CPUs utilized ( +- 0.97% )
0 context-switches # 0.002 K/sec ( +-100.00% )
0 cpu-migrations # 0.000 K/sec
1 page-faults:u # 0.010 K/sec
414,143,323 cycles # 4.115 GHz ( +- 0.56% )
700,193,469 instructions # 1.69 insn per cycle ( +- 0.00% )
700,293,232 uops_issued_any # 6957.919 M/sec ( +- 0.00% )
1,000,299,201 uops_executed_thread # 9938.695 M/sec ( +- 0.00% )
83,212,779 idq_mite_uops # 826.779 M/sec ( +- 17.02% )
5,792 dsb2mite_switches_penalty_cycles # 0.058 M/sec ( +- 33.07% )
0.100805233 seconds time elapsed ( +- 0.96% )
Старый ответ, прежде чем заметить переменную задержку пересылки магазина
Вы нажимаете / выдвигаете свой счетчик циклов, так что все, кроме call а также ret инструкции (и cmp/jcc) являются частью цепочки зависимостей переноса по критическому пути, включающей счетчик цикла.
Вы ожидаете, что pop придется ждать обновления указателя стека call/ret, но механизм стека обрабатывает эти обновления с нулевой задержкой. (Intel, начиная с Pentium-M, AMD, начиная с K10, согласно микроархиву pdf Агнера Фога, поэтому я предполагаю, что у вашего ЦП он есть, даже если вы ничего не сказали о том, на какой микроархитектуре ЦП вы выполняли свои тесты.)
Экстра call/ret все еще нужно выполнить, но выполнение не по порядку может поддерживать выполнение инструкций критического пути с максимальной пропускной способностью. Так как это включает в себя задержку магазина-> пересылка нагрузки из цикла push/pop + 1 для decЭто не высокая пропускная способность на любом процессоре, и это удивительно, что интерфейс может стать узким местом при любом выравнивании.
push->pop По словам Агнера Фога, задержка на Skylake составляет 5 циклов, поэтому при таком подходе ваш цикл может выполняться в лучшем случае только одну итерацию на 6 циклов. Это достаточно времени для выполнения не по порядку выполнения call а также ret инструкции. Агнер перечисляет максимальную пропускную способность для call по одному на 3 цикла, и ret по одному на 1 цикл. Или на AMD Bulldozer, 2 и 2. В его таблицах ничего не говорится о пропускной способности call/ret пара, так что ИДК, могут ли они перекрываться или нет. На AMD Bulldozer сохраните / перезагрузите время ожидания с mov это 8 циклов. Я предполагаю, что это примерно то же самое с push/pop.
Кажется, что разные выравнивания для верхней части цикла (т.е. no_call.loop_start:) вызывают узкие места переднего плана. call Версия имеет 3 ветви на одну итерацию: call, ret и loop-branch. Обратите внимание, что retЦель ветки - это инструкция сразу после call, Каждый из них потенциально нарушает работу внешнего интерфейса. Поскольку на практике вы наблюдаете реальное замедление, мы должны видеть более чем 1 задержку цикла на ветвь. Или для версии no_call - один пузырь выборки / декодирования, который хуже, чем около 6 циклов, что приводит к фактическому потраченному впустую циклу выдачи мопов в неупорядоченную часть ядра. Это странно.
Слишком сложно догадаться о том, каковы фактические детали микроархитектуры для каждого возможного uarch, поэтому дайте нам знать, на каком процессоре вы тестировали.
Я упомяну, хотя, что push/pop внутри цикла на Skylake прекращается его выдача из детектора Loop Stream Detector, и его приходится каждый раз заново извлекать из кэша UOP. Руководство по оптимизации Intel гласит, что для Sandybridge несоответствующий push / pop внутри цикла не позволяет использовать LSD. Это означает, что он может использовать LSD для циклов со сбалансированным push/pop. В моем тестировании это не относится к Skylake (используя lsd.uops счетчик производительности), но я не видел никаких упоминаний о том, было ли это изменение, или SnB на самом деле тоже так.
Кроме того, безусловные ветви всегда заканчивают строку uop-cache. Возможно, что с normal_function: в том же естественно выровненном фрагменте 32B машинного кода, что и call а также jne, возможно, блок кода не помещается в кэш UOP. (Только 3 строки UOP-кэша могут кэшировать декодированные UOP для одного 32-битного фрагмента кода x86). Но это не объясняет возможности проблем для цикла no_call, поэтому вы, вероятно, не работаете на микроархитектуре семейства Intel SnB.
(Обновление, да, цикл иногда запускается в основном из устаревшего декодирования (idq.mite_uops), но обычно не исключительно. dsb2mite_switches.penalty_cycles обычно ~8k, и, вероятно, происходит только при прерываниях по таймеру. Беги, где call цикл работает быстрее, кажется, коррелирует с более низким idq.mite_uops, но это все еще 34M +- 63% для случая смещения =37, где итерации 100M заняли 401M циклов.)
Это действительно один из тех случаев "не делай этого": встроенные крошечные функции вместо вызова их из очень узких циклов.
Вы можете увидеть другие результаты, если вы push/pop регистр, отличный от вашего счетчика цикла. Это отделяет push / pop от счетчика цикла, поэтому будет 2 отдельных цепочки зависимостей. Это должно ускорить обе версии: call и no_call, но, возможно, не одинаково. Это может сделать внешнее узкое место более очевидным.
Вы должны увидеть огромное ускорение, если вы push edx но pop eaxтаким образом, инструкции push / pop не образуют цепочку зависимостей, переносимых циклом. Тогда экстра call/ret определенно будет узким местом.
Примечание: dec ecx уже устанавливает ZF так, как вы хотите, чтобы вы могли просто использовать dec ecx / jnz, Также, cmp ecx,0 менее эффективен, чемtest ecx,ecx (больший размер кода и не может слиться макрос на столько процессоров). Во всяком случае, совершенно не имеет отношения к вопросу об относительной производительности ваших двух циклов. (Ваше отсутствие ALIGN Директива между функциями означает, что изменение первой изменило бы выравнивание ветви цикла во второй, но вы уже исследовали различные выравнивания.)
Вызов функции normal_function и ее возврат будут правильно прогнозироваться каждый раз, кроме первого, поэтому я не ожидаю увидеть разницу во времени из-за наличия вызова. Таким образом, все различия во времени, которые вы видите (быстрее или медленнее), связаны с другими эффектами (например, упомянутыми в комментариях), а не с различием в коде, который вы фактически пытаетесь измерить.