5.6 消除不必要的内存引用

combine3 的代码将合并运算计算的值累积在指针 dest 指定的位置。通过检查编译出来的为内循环产生的汇编代码，可以看出这个属性。在此我们给出数据类型为 double，合并运算为乘法的 x86-64 代码：

# Inner loop of combine3. data_t = double, OP = *
# dest in %rbx, data+i in %rdx, data+length in %rax
.L17:                              # loop:
    vmovsd  (%rbx), %xmm0          # Read product from dest
    vmulsd  (%rdx), %xmm0, %xmm0   # Multiply product by data[i]
    vmovsd  %xmm0, (%rbx)          # Store product at dest
    addq    $8, %rdx               # Increment data+i
    cmpq    %rax, %rdx             # Compare to data+length
    jne     .L17                   # If !=, goto loop

在这段循环代码中，我们看到，指针 dest 的地址存放在寄存器 %rbx 中，它还改变了代码，将第 i 个数据元素的指针保存在寄存器 %rdx 中，注释中显示为 data+i。每次迭代，这个指针都加 8。循环终止操作通过比较这个指针与保存在寄存器 %rax 中的数值来判断。我们可以看到每次迭代时，累积变量的数值都要从内存读出再写入到内存。这样的读写很浪费，因为每次迭代开始时从 dest 读出的值就是上次迭代最后写入的值。

我们能够消除这种不必要的内存读写，按照图 5-10 中 combine4 所示的方式重写代码。引入一个临时变量 acc，它在循环中用来累积计算出来的值。只有在循环完成之后结果才存放在 dest 中。正如下面的汇编代码所示，编译器现在可以用寄存器 %xmm0 来保存累积值。与 combine3 中的循环相比，我们将每次迭代的内存操作从两次读和一次写减少到只需要一次读。

# Inner loop of combine4. data_t = double, OP = *
# acc in %xmm0, data+i in %rdx, data+length in %rax
.L25:                              # loop:
    vmulsd  (%rdx), %xmm0, %xmm0   # Multiply acc by data[i]
    addq    $8, %rdx               # Increment data+i
    cmpq    %rax, %rdx             # Compare to data+length
    jne     .L25                   # If !=, goto loop

/* Accumulate result in local variable */
void combine4(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    for (i = 0; i < length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

图 5-10 把结果累积在临时变量中。将累积值存放在局部变量 acc（累积器（accumulator）的简写）中，消除了每次循环迭代中从内存中读出并将更新值写回的需要。

我们看到程序性能有了显著的提高，如下表所示：

函数	方法	整数 `+`	整数 `*`	浮点数 `+`	浮点数 `*`
`combine3`	直接数据访问	7.17	9.02	9.02	11.03
`combine4`	累积在临时变量中	1.27	3.01	3.01	5.01

所有的时间改进范围从 2.2× 到 5.7×，整数加法情况的时间下降到了每元素只需 1.27 个时钟周期。

可能又有人会认为编译器应该能够自动将图 5-9 中所示的 combine3 的代码转换为在寄存器中累积那个值，就像图 5-10 中所示的 combine4 的代码所做的那样。然而实际上，由于内存别名使用，两个函数可能会有不同的行为。例如，考虑整数数据，运算为乘法，标识元素为 1 的情况。设 v=[2, 3, 5] 是一个由 3 个元素组成的向量，考虑下面两个函数调用：

combine3(v, get_vec_start(v) + 2);
combine4(v, get_vec_start(v) + 2);

也就是在向量最后一个元素和存放结果的目标之间创建一个别名。那么，这两个函数的执行如下：

函数	初始值	循环之前	i=0	i=1	i=2	最后
`combine3`	[2, 3, 5]	[2, 3, 1]	[2, 3, 2]	[2, 3, 6]	[2, 3, 36]	[2, 3, 36]
`combine4`	[2, 3, 5]	[2, 3, 5]	[2, 3, 5]	[2, 3, 5]	[2, 3, 5]	[2, 3, 30]

正如前面讲到过的，combine3 将它的结果累积在目标位置中，在本例中，目标位置就是向量的最后一个元素。因此，这个值首先被设置为 1，然后设为 2·1=2，然后设为 3·2=6。最后一次迭代中，这个值会乘以它自己，得到最后结果 36。对于 combine4 的情况来说，直到最后向量都保持不变，结束之前，最后一个元素会被设置为计算出来的值 1·2·3·5=30。

当然，我们说明 combine3 和 combine4 之间差别的例子是人为设计的。有人会说 combine4 的行为更加符合函数描述的意图。不幸的是，编译器不能判断函数会在什么情况下被调用，以及程序员的本意可能是什么。取而代之，在编译 combine3 时，保守的方法是不断地读和写内存，即使这样做效率不太高。

练习题 5.4

当用带命令行选项 -O2 的 GCC 来编译 combine3 时，得到的代码 CPE 性能远好于使用 -O1 时的：

函数方法整数 + 整数 * 浮点数 + 浮点数 *

combine3 用 -O1 编译 7.17 9.02 9.02 11.03

combine3 用 -O2 编译 1.60 3.01 3.01 5.01

combine4 累积在临时变量中 1.27 3.01 3.01 5.01

由此得到的性能与 combine4 相当，不过对于整数求和的情况除外，虽然性能已经得到了显著的提高，但还是低于 combine4。在检查编译器产生的汇编代码时，我们发现对内循环的一个有趣的变化：
# Inner loop of combine3. data_t = double, OP = *
# dest in %rbx, data+i in %rdx, data+length in %rax
# Accumulated product in %xmm0
# Compiled -O2
.L22:                              # loop:
    vmulsd  (%rdx), %xmm0, %xmm0   # Multiply product by data[i]
    addq    $8, %rdx               # Increment data+i
    cmpq    %rax, %rdx             # Compare to data+length
    vmovsd  %xmm0, (%rbx)          # Store product at dest
    jne     .L22                   # If !=, goto loop
把上面的代码与用优化等级 1 产生的代码进行比较：
# Inner loop of combine3. data_t = double, OP = *
# dest in %rbx, data+i in %rdx, data+length in %rax
# Compiled -O1
.L17:                              # loop:
    vmovsd  (%rbx), %xmm0          # Read product from dest
    vmulsd  (%rdx), %xmm0, %xmm0   # Multiply product by data[i]
    vmovsd  %xmm0, (%rbx)          # Store product at dest
    addq    $8, %rdx               # Increment data+i
    cmpq    %rax, %rdx             # Compare to data+length
    jne     .L17                   # If !=, goto loop
我们看到，除了指令顺序有些不同，唯一的区别就是使用更优化的版本不含有 vmovsd 指令，它实现的是从 dest 指定的位置读数据（第 2 行）。

A. 寄存器 %xmm0 的角色在两个循环中有什么不同？

B. 这个更优化的版本忠实地实现了 combine3 的 C 语言代码吗（包括在 dest 和向量数据之间使用内存别名的时候）？

C. 解释为什么这个优化保持了期望的行为，或者给出一个例子说明它产生了与使用较少优化的代码不同的结果。

函数	方法	整数 `+`	整数 `*`	浮点数 `+`	浮点数 `*`
`combine3`	用 `-O1` 编译	7.17	9.02	9.02	11.03
`combine3`	用 `-O2` 编译	1.60	3.01	3.01	5.01
`combine4`	累积在临时变量中	1.27	3.01	3.01	5.01

使用了这最后的变换，至此，对于每个元素的计算，都只需要 1.25～5 个时钟周期。比起最开始采用优化时的 9～11 个周期，这是相当大的提高了。现在我们想看看是什么因素在制约着代码的性能，以及可以如何进一步提高。