Как говорит @RossRidge, накладные расходы будут в основном потеряны из-за шума обслуживания прерывания на современном x86 (возможно, по крайней мере, 100 тактов, и много много больше, если это является частью современногоОперационная система с настроенным устранением Meltdown + Spectre).
Если MAX_VAL - это степень 2, counter %= MAX_VAL отлично, особенно если counter без знака (в этом случае просто and, или, в данном случае, movzx байт на слово, которое может иметь нулевую задержку на процессорах Intel. Конечно, при этом у него все равно есть пропускная способность: Может ли MOV x86 действительно быть "свободным"? Почему я не могу воспроизвестиэто вообще? )
Можно ли заполнить последние 255-240 записями чем-то безобидным или повторять что-то?
Пока MAX_VALконстанта времени компиляции , тем не менее, counter %= MAX_VAL будет эффективно компилироваться до пары умножений, сдвигов и сложений.(Опять же, более эффективно для неподписанных.) Почему GCC использует умножение на странное число при реализации целочисленного деления?
Но проверка на повторение еще лучше.Проверка без ответвлений (с использованием cmov) имеет меньшую задержку, чем остаток с использованием мультипликативного обратного, и обходится меньше пропускной способности для пропускной способности.
Как вы говорите, проверка с ветвлением может снять проверку с критическойпуть полностью, иногда ценой ошибочного прогноза.
// simple version that works exactly like your question
// further optimizations assume that counter isn't used by other code in the function,
// e.g. making it a pointer or incrementing it for the next iteration
void isr_countup(int condition) {
static unsigned int counter = 0;
if(condition){
++counter;
counter = (counter>=MAX_VAL) ? 0 : counter; // gcc uses cmov
//if(counter >= MAX_VAL) counter = 0; // gcc branches
doStuff(table[counter]);
}
}
Я скомпилировал много версий этого в проводнике компилятора Godbolt , с последними версиями gcc и clang.
(Подробнее о статическом анализе производительности и пропускной способности для коротких блоков x86 asm см. Какие соображения относятся к прогнозированию задержки для операций на современных суперскалярных процессорах и как их можно вычислить вручную? и другие ссылки в x86 wiki , особенно Руководства Agner Fog .)
clang использует без ветвей cmov для обеих версий.Я скомпилировал с -fPIE на случай, если вы используете это в своих ядрах.Если вы можете использовать -fno-pie, то компилятор может сохранить LEA и использовать mov edi, [table + 4*rcx], предполагая, что вы находитесь на цели, где статические адреса в позиционно-зависимом коде вписываются в 32-битные константы с расширенными знаками (например, true вЯдро Linux, но я не уверен, что они компилируются с -fPIE или делают ASLR ядра с перемещениями при загрузке ядра.)
# clang7.0 -O3 -march=haswell -fPIE.
# gcc's output is the same (with different registers), but uses `mov edx, 0` before the cmov for no reason, because it's also before a cmp that sets flags
isr_countup: # @isr_countup
test edi, edi
je .LBB1_1 # if condition is false
mov eax, dword ptr [rip + isr_countup.counter]
add eax, 1 # counter++
xor ecx, ecx
cmp eax, 239 # set flags based on (counter , MAX_VAL-1)
cmovbe ecx, eax # ecx = (counter <= MAX_VAL-1) ? 0 : counter
mov dword ptr [rip + isr_countup.counter], ecx # store the old counter
lea rax, [rip + table]
mov edi, dword ptr [rax + 4*rcx] # index the table
jmp doStuff@PLT # TAILCALL
.LBB1_1:
ret
Блок из 8 инструкций, начинающийся с загрузки старойзначение счетчика составляет всего 8 моп (для AMD или Intel Broadwell и более поздних версий, где cmov - только 1 моп)Задержка критического пути от готовности counter к готовности table[++counter % MAX_VAL] составляет 1 (сложение) + 1 (cmp) + 1 (cmov) + задержка использования нагрузки для нагрузки.т.е. 3 дополнительных цикла.Это задержка инструкции 1 mul.Или 1 дополнительный цикл на старом Intel, где cmov равен 2 моп.
Для сравнения, версия с использованием модуля по модулю составляет 14 моп для этого блока с gcc, включая 3-моп mul r32.Задержка составляет не менее 8 циклов, я точно не считал.(Для пропускной способности это только немного хуже, хотя, если более высокая задержка не уменьшает способность неупорядоченного выполнения перекрывать выполнение материала, который зависит от счетчика.)
Другоеоптимизации
Используйте старое значение counter и подготовьте значение для следующего раза (снимая вычисления с критического пути.)
Используйте указатель вместо счетчика.Сохраняет пару инструкций за счет использования 8 байтов вместо 1 или 4 места в кэше для переменной.(uint8_t counter прекрасно компилируется с некоторыми версиями, просто используя movzx в 64-битную версию).
Это считается в сторону увеличения, поэтому таблица может быть в порядке.Он увеличивает после загрузки, убирая эту логику из цепочки зависимостей критического пути для выполнения вне порядка.
void isr_pointer_inc_after(int condition) {
static int *position = table;
if(condition){
int tmp = *position;
position++;
position = (position >= table + MAX_VAL) ? table : position;
doStuff(tmp);
}
}
Это очень хорошо компилируется как с gcc, так и с clang, особенно если вывы используете -fPIE, поэтому компилятору в любом случае нужен адрес таблицы в регистре.
# gcc8.2 -O3 -march=haswell -fPIE
isr_pointer_inc_after(int):
test edi, edi
je .L29
mov rax, QWORD PTR isr_pointer_inc_after(int)::position[rip]
lea rdx, table[rip+960] # table+MAX_VAL
mov edi, DWORD PTR [rax] #
add rax, 4
cmp rax, rdx
lea rdx, -960[rdx] # table, calculated relative to table+MAX_VAL
cmovnb rax, rdx
mov QWORD PTR isr_pointer_inc_after(int)::position[rip], rax
jmp doStuff(int)@PLT
.L29:
ret
Снова 8 моп (при условии, что cmov - 1 моп).Это имеет даже более низкую задержку, чем, возможно, могла бы иметь версия счетчика, потому что режим адресации [rax] (с RAX, приходящимся на нагрузку) имеет на 1 цикл меньшую задержку, чем индексированный режим адресации, в семействе Sandybridge.Без смещения он никогда не переносит штраф, описанный в Существует ли штраф, если база + смещение находятся на странице, отличной от базы?
Или (сcounter) count down к нулю: потенциально сохраняет инструкцию, если компилятор может использовать флаги, установленные декрементом, для обнаружения отрицательного значения.Или мы всегда можем использовать уменьшенное значение и выполнить перенос после этого: поэтому, когда counter равен 1, мы будем использовать table[--counter] (table[0]), но хранить counter=MAX_VAL.Опять же, снимает проверку обтекания критического пути.
Если вы хотели версию ветвления, вы бы хотели, чтобы она разветвлялась на флаге переноса, потому что sub eax,1 / jc может слиться макросом в 1упс, но sub eax,1 / js не может слиться с макросами в семействе Сэндибридж. x86_64 - Сборка - условия цикла и выход из строя .Но с без филиалов, это нормально.cmovs (MOV, если установлен флаг знака, т. Е. Если последний результат был отрицательным), так же эффективен, как cmovc (MOV, если установлен флаг переноса).
Было сложно получить gcc, чтобы использоватьПометить результаты из dec или sub, не делая также cdqe, чтобы расширить индекс до ширины указателя.Думаю, я мог бы использовать счетчик intptr_t, но это было бы глупо;может также просто использовать указатель.С неподписанным счетчиком gcc и clang оба хотят сделать еще один cmp eax, 239 или что-то после декремента, даже если флаги уже установлены очень хорошо из декремента.Но мы можем заставить gcc использовать SF, проверив (int)counter < 0:
// Counts downward, table[] entries need to be reversed
void isr_branchless_dec_after(int condition) {
static unsigned int counter = MAX_VAL-1;
if(condition){
int tmp = table[counter];
--counter;
counter = ((int)counter < 0) ? MAX_VAL-1 : counter;
//counter = (counter >= MAX_VAL) ? MAX_VAL-1 : counter;
//counter = (counter==0) ? MAX_VAL-1 : counter-1;
doStuff(tmp);
}
}
# gcc8.2 -O3 -march=haswell -fPIE
isr_branchless_dec_after(int):
test edi, edi
je .L20
mov ecx, DWORD PTR isr_branchless_dec_after(int)::counter[rip]
lea rdx, table[rip]
mov rax, rcx # stupid compiler, this copy is unneeded
mov edi, DWORD PTR [rdx+rcx*4] # load the arg for doStuff
mov edx, 239 # calculate the next counter value
dec eax
cmovs eax, edx
mov DWORD PTR isr_branchless_dec_after(int)::counter[rip], eax # and store it
jmp doStuff(int)@PLT
.L20:
ret
по-прежнему 8 мопов (должно быть 7), но без дополнительной задержки на критическом пути.Таким образом, все дополнительные инструкции декремента и переноса представляют собой сочный параллелизм на уровне команд для выполнения не по порядку.