本文为学习 Computer Enhance - Instructions Per Clock 的整理。

问题引入

有如下代码：

1
2
3
4
5
6
7
8
9
10
11
typedef unsigned int u32;

u32 SingleScalar(u32 Count, u32 *Input)
{
    u32 Sum = 0;
    for (u32 Index = 0; Index < Count; ++Index)
    {
        Sum += Input[Index];
    }
    return Sum;
}

每颗 CPU 在理论上每个时钟周期都能执行一定数量的指令，而我们的工作负载越接近这个数量，就越能发挥这颗 CPU 的全部潜力。

上述代码中，可以认为 加法是工作负载，而 循环是一种”浪费”。下面是上述代码生成的汇编：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SingleScalar:
    test    ecx, ecx                ; if (Count == 0)
    je      .L4                     ;   return 0
    mov     r8, rdx                 ; r8 = Input
    mov     eax, ecx                
    lea     rdx, [rdx+rax*4]        ; rdx = Input + Count (结束地址)
    mov     eax, 0                  ; Sum = 0
.L3:                                ; === 循环开始 ===
    add     eax, DWORD PTR [r8]     ; Sum += *Input
    add     r8, 4                   ; Input++
    cmp     r8, rdx                 ; if (Input != end)
    jne     .L3                     ;   继续循环
.L1:
    ret
.L4:
    mov     eax, ecx
    jmp     .L1

可以看到每个循环中，执行加法的指令只有 add eax, DWORD PTR [r8] 一条，会造成浪费。

循环展开 (Loop Unrolling)

如何优化这个代码呢？可以使用一种应用于循环的经典技巧：循环展开。

展开 2 次

1
2
3
4
5
6
7
8
9
10
u32 Unroll2Scalar(u32 Count, u32 *Input)
{
    u32 Sum = 0;
    for (u32 Index = 0; Index < Count; Index += 2)
    {
        Sum += Input[Index];
        Sum += Input[Index + 1];
    }
    return Sum;
}

我们在一次循环中处理了两次加法，把循环写成这样，CPU 就不必频繁地进行比较了。

展开 4 次

这种做法的次数没有上限。我们可以在循环体里做四次累加，并把索引每次加四：

1
2
3
4
5
6
7
8
9
10
11
12
u32 Unroll4Scalar(u32 Count, u32 *Input)
{
    u32 Sum = 0;
    for (u32 Index = 0; Index < Count; Index += 4)
    {
        Sum += Input[Index];
        Sum += Input[Index + 1];
        Sum += Input[Index + 2];
        Sum += Input[Index + 3];
    }
    return Sum;
}

性能测试结果

用 数组大小 / CPU 周期数 可以计算出每一个周期可以计算多少个 add 操作，上面三个循环的结果如下：

函数 周期数 adds/cycle
SingleScalar 2666 1.536
Unroll2Scalar 2588 1.583
Unroll4Scalar 1686 2.429

问题分析

数据看起来好像是符合预期的？

但它其实是 不合理的。Unroll2Scalar 到 Unroll4Scalar 的提升太明显了！

从 SingleScalar 到 Unroll2Scalar 可以看到，循环展开的优化能力其实是很有限的。Unroll2Scalar 到 Unroll4Scalar 明显出现了其他的优化因素。

真正的原因：依赖链

其实在之前的代码中出现了一个很影响性能的操作：

1
2
3
4
Sum += Input[Index];
Sum += Input[Index + 1];
Sum += Input[Index + 2];
Sum += Input[Index + 3];

这是一个 串行依赖链——每一个 add 的参数都依赖于上一条指令的结果，导致 CPU 无法并行执行它们，只能一条一条串行执行。

编译器在编译 Unroll4Scalar 时，生成了 临时变量 来替换 Sum，最后将临时变量加起来。这样就有效地打破了依赖链，使得代码可以并行执行。

这才是出现较大提升的关键，我们在下一篇博客中继续说明。