性能：Mod 和赋值 vs 条件和赋值

Question

我在 ISR 中有一个计数器（由 50us 的外部 IRQ 触发）。计数器递增并环绕 MAX_VAL (240).

我有以下代码：

if(condition){
  counter++;
  counter %= MAX_VAL;
  doStuff(table[counter]);
}

我正在考虑替代实施：

if(condition){
  //counter++;//probably I would increment before the comparison in production code
  if(++counter >= MAX_VAL){
    counter=0;
  }
  doStuff(table[counter]);
}

我知道人们建议不要尝试像这样进行优化，但这让我感到疑惑。在 x86 上什么更快？ MAX_VAL 的什么值可以证明第二次实施是合理的？

这大约每 50 微秒被调用一次，因此减少指令集是个不错的主意。 if(++counter >= MAX_VAL) 将被预测为假，因此在绝大多数情况下它会删除对 0 的赋值。出于我的目的，id 更喜欢 %= 实现的一致性。

Answer 1

正如@RossRidge 所说，在现代 x86 上服务中断的噪音中，开销大部分会丢失（可能至少 100 个时钟周期，如果很多更多这是具有 Meltdown + Spectre 缓解设置的现代 OS 的一部分。

如果 MAX_VAL 是 2 的幂，counter %= MAX_VAL 非常好，特别是如果 counter 是无符号的（在这种情况下只是一个简单的 and，或者在这个case a movzx byte to dword which can have had zero latency on Intel CPU. 当然它仍然有吞吐量成本：)

是否可以用无害的东西或重复的东西填充最后 255-240 个条目？

只要 MAX_VAL 是一个 编译时 常量，counter %= MAX_VAL 将有效地编译成几个乘法、移位和加法. （同样，无符号更有效。）Why does GCC use multiplication by a strange number in implementing integer division?

但是检查回绕会更好。无分支检查（使用 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]);
    }
}

我用最近的 gcc 和 clang 编译了这个 on the Godbolt compiler explorer 的许多版本。

（有关 x86 asm 短块的吞吐量和延迟的静态性能分析的更多信息，请参阅 What considerations go into predicting latency for operations on modern superscalar processors and how can I calculate them by hand?, and other links in the x86 tag wiki, especially Agner Fog's guides。）

clang 对两个版本都使用无分支 cmov。我用 -fPIE 编译，以防你在你的内核中使用它。如果你可以使用 -fno-pie，那么编译器可以保存一个 LEA 并使用 mov edi, [table + 4*rcx]，假设你在一个目标上，其中位置相关代码中的静态地址适合 32 位符号扩展常量（例如，在 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 个额外的周期，其中 cmov 是 2 微指令。

相比之下，使用模数的版本对于带有 gcc 的块是 14 微指令，包括 3 微指令 mul r32。延迟至少是8个周期，我没数清楚。（不过，对于吞吐量来说，情况只会更糟一点，除非更高的延迟会降低乱序执行重叠执行依赖于计数器的内容的能力。）

其他优化

使用counter的旧值，并为下次准备一个值（计算脱离关键路径。）
使用指针代替计数器。节省几条指令，代价是使用 8 个字节而不是变量的 1 或 4 个缓存空间。（uint8_t counter 可以很好地编译某些版本，只需使用 movzx 到 64 位）。

这样往上数，所以table可以是有序的。它在加载后递增 ，使该逻辑脱离关键路径依赖链以进行乱序执行。

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 所以编译器无论如何都需要寄存器中的 table 地址。

# 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 微指令）。这可能比计数器版本具有更低的延迟，因为在 Sandybridge 系列上，[rax] 寻址模式（RAX 来自负载）的延迟比索引寻址模式低 1 个周期。没有位移，它永远不会受到
中描述的惩罚

或（使用计数器）向零计数向下：如果编译器可以使用减量设置的标志来检测值变为，则可能会保存一条指令消极的。或者我们总是可以使用递减后的值，然后进行回绕：所以当 counter 为 1 时，我们将使用 table[--counter] (table[0])，但存储 counter=MAX_VAL.同样，从关键路径上取下包装检查。

如果你想要一个分支版本，你希望它在进位标志上分支，因为 sub eax,1 / jc 可以宏融合为 1 微指令，但是 sub eax,1 / js 无法在 Sandybridge 系列上进行宏融合。。但是有了无分支，就没问题了。 cmovs（如果设置了符号标志则移动，即如果最后的结果为负）与 cmovc（如果设置进位标志则移动）一样有效。

让 gcc 使用 dec 或 sub 的标志结果而不做 cdqe 将索引符号扩展到指针宽度是很棘手的。我想我可以使用 intptr_t 计数器，但这很愚蠢；还不如只使用一个指针。对于未签名的计数器，gcc 和 clang 都想在递减后执行另一个 cmp eax, 239 或其他操作，即使标志已经从递减中设置得很好。但是我们可以通过检查 (int)counter < 0:
让 gcc 使用 SF
// 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），但关键路径上没有额外的延迟。因此，所有额外的递减和换行指令都是用于乱序执行的多汁指令级并行。

性能：Mod 和赋值 vs 条件和赋值

Performance: Mod and assignment vs conditional and assignment

c

x86

assembly

micro-optimization