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

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 的什么值可以证明第二个实现是合理的？

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

Answer 1

正如 @RossRidge 所说，开销大部分会消失在现代 x86 上服务中断的噪音中（可能至少 100 个时钟周期，如果这是设置了 Meltdown + Spectre 缓解措施的现代操作系统的一部分，则需要更多时钟周期）。

如果MAX_VAL是 2 的幂，counter %= MAX_VAL则非常好，特别是如果counter是无符号的（在这种情况下只是一个简单的and，或者在这种情况下是一个movzx字节到双字，在 Intel CPU 上可以具有零延迟。当然，它仍然有吞吐量成本：可以 x86 的MOV真的是“免费”的吗？为什么我根本无法复制这个？）

是否可以用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中的其他链接，尤其是阿格纳·福格的指南。）

cmovclang的两个版本都使用branchless 。我编译了-fPIE以防你在内核中使用它。如果您可以使用-fno-pie，那么编译器可以保存 LEA 并使用mov edi, [table + 4*rcx]，假设您所在的目标位置相关代码中的静态地址适合 32 位符号扩展常量（例如，在 Linux 内核中为 true，但我'我不确定它们是否使用-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 (add) + 1 (cmp) + 1 (cmov) + 负载的加载使用延迟。即3个额外的周期。这是 1 条指令的延迟mul。或者在较旧的 Intel 上有 1 个额外周期，即cmov2 uop。

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

其他优化

• 使用 的旧值counter，并为下次准备一个值（使计算脱离关键路径。）

• 使用指针而不是计数器。节省了几条指令，代价是使用 8 个字节而不是变量的 1 或 4 个缓存占用空间。（uint8_t counter某些版本可以很好地编译，仅用于movzx64 位）。

这是向上计数的，因此表格可以是有序的。它在加载后递增，将该逻辑从关键路径依赖链中移出，以实现无序执行。

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 uop（假设cmov是 1 uop）。这比计数器版本的延迟甚至更低，因为[rax]在 Sandybridge 系列上，寻址模式（RAX 来自负载）的延迟比索引寻址模式低 1 个周期。由于没有位移，它永远不会遭受当基点+偏移量与基点位于不同页面时是否有惩罚中描述的惩罚？

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

  如果你想要一个分支版本，你会希望它在进位标志上分支，因为sub eax,1/jc可以宏融合到 1 uop，但sub eax,1/js不能在 Sandybridge 系列上宏融合。 x86_64 - 汇编循环条件和乱序。但对于无分支来说，那就没问题了。 (mov 如果设置了符号标志，即如果最后的结果为负) 与(mov 如果设置了进位标志)cmovs一样有效。cmovc

  让 gcc 使用 dec 或 sub 的标志结果而不同时执行 acdqe将索引符号扩展为指针宽度是很棘手的。我想我可以使用intptr_t计数器，但这很愚蠢；不妨只使用指针。cmp eax, 239对于无符号计数器，gcc 和 clang 都希望在减量之后执行其他操作或某些操作，即使标志已经从减量中设置得很好。但我们可以通过检查让 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 uop（应该是 7），但关键路径上没有额外的延迟。因此，所有额外的递减和换行指令都是无序执行的有趣的指令级并行性。