if 语句和 mod(SIZE) 之间的效率差异

Question

通过研究我发现 (i+1)mod(SIZE) 可以在元素数组中执行循环。所以我想知道这种方法是否比 if 语句更有效...

例如：

#define SIZE 15

int main(int argc, char *argv[]) {
    int items[SIZE];

    for(int i = 0; items[0] < 5; i = (i + 1) % SIZE) items[i] += 1;

    return 0;
}

比(?):

更有效率

#define SIZE 15

int main(int argc, char *argv[]) {
    int items[SIZE];

    for(int i = 0; items[0] < 5; i++) {
        if(i == SIZE) i = 0;
        items[i] += 1;
    }

    return 0;
}

感谢您的回答和抽出时间。

Answer 1

您可以在线查看程序集（即 here）。结果取决于体系结构和优化，但如果没有优化并且对于带有 GCC 的 x64，您将得到此代码（作为一个简单示例）。

示例 1：

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-68], edi
        mov     QWORD PTR [rbp-80], rsi
        mov     DWORD PTR [rbp-4], 0
.L3:
        mov     eax, DWORD PTR [rbp-64]
        cmp     eax, 4
        jg      .L2
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        mov     eax, DWORD PTR [rbp-64+rax*4]
        lea     edx, [rax+1]
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        mov     DWORD PTR [rbp-64+rax*4], edx
        mov     eax, DWORD PTR [rbp-4]
        add     eax, 1
        movsx   rdx, eax
        imul    rdx, rdx, -2004318071
        shr     rdx, 32
        add     edx, eax
        mov     ecx, edx
        sar     ecx, 3
        cdq
        sub     ecx, edx
        mov     edx, ecx
        mov     DWORD PTR [rbp-4], edx
        mov     ecx, DWORD PTR [rbp-4]
        mov     edx, ecx
        sal     edx, 4
        sub     edx, ecx
        sub     eax, edx
        mov     DWORD PTR [rbp-4], eax
        jmp     .L3
.L2:
        mov     eax, 0
        pop     rbp
        ret

示例 2：

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-68], edi
        mov     QWORD PTR [rbp-80], rsi
        mov     DWORD PTR [rbp-4], 0
.L4:
        mov     eax, DWORD PTR [rbp-64]
        cmp     eax, 4
        jg      .L2
        cmp     DWORD PTR [rbp-4], 15
        jne     .L3
        mov     DWORD PTR [rbp-4], 0
.L3:
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        mov     eax, DWORD PTR [rbp-64+rax*4]
        lea     edx, [rax+1]
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        mov     DWORD PTR [rbp-64+rax*4], edx
        add     DWORD PTR [rbp-4], 1
        jmp     .L4
.L2:
        mov     eax, 0
        pop     rbp
        ret

你看，对于 x86 的特定情况，没有模数的解决方案要短得多。

Answer 2

虽然您只询问 mod 与 branch，但根据 mod 和分支的实际实施情况，可能有更多的情况：

Modulus-based

Power-of-two

如果编译器知道SIZE的值并且是2的幂，那么mod会编译成一个andlike this and will be very efficient in performance and code size. The and is still part of the loop increment dependency chain though, putting a speed limit，性能上每次迭代 2 个周期，除非编译器足够聪明地展开它并将 and 排除在进位链之外（gcc 和 clang 不是）。

已知，不power-of-two

另一方面，如果 SIZE 的值已知但不是 2 的幂，那么您可能会得到固定模值 multiplication-based 的实现，like this.这通常需要 4-6 条指令，这些指令最终成为依赖链的一部分。因此，这会将您的性能限制为每 5-8 个周期进行 1 次迭代，具体取决于依赖链的延迟。

未知

在您的示例中，SIZE 是一个已知常量，但在编译时未知的更一般情况下，您将在支持它的平台上获得除法指令。东西 like this.

这对代码大小有利，因为它是一条指令，但对性能来说可能是灾难性的，因为现在你有一个缓慢的除法指令作为循环的进位依赖的一部分。根据您的硬件和 SIZE 变量的类型，您将看到每次迭代 20-100 个周期。

Branch-based

您在代码中放置了一个分支，但跳转编译器决定将其实现为条件跳转或条件移动。在 -O2、gcc decides on a jump and clang on a conditional move、

条件跳转

这是对你的代码的直接解释：使用条件分支来实现i == SIZE条件。

它的优点是使条件成为控制依赖性，而不是数据依赖性，因此当不采用分支时，您的循环将大部分运行全速运行。

但是，如果分支经常预测错误，性能可能会受到严重影响。这在很大程度上取决于 SIZE 的值和您的硬件。现代英特尔应该能够预测像这样的嵌套循环最多 20 次迭代，但除此之外，每次退出内部循环时它都会预测错误一次。当然，如果 SIZE 非常大，那么单个错误预测无论如何都无关紧要，所以最坏的情况是 SIZE 大到足以错误预测。

条件移动

clang 使用条件移动来更新 i。这是一个合理的选择，但它确实意味着 3-4 个周期的承载数据流依赖性。

¹要么实际上像你的例子那样的常量，要么由于内联和常量传播而实际上是一个常量。

if 语句和 mod(SIZE) 之间的效率差异

Efficiency difference between an if-statement and mod(SIZE)

c

performance

if-statement

processing-efficiency