Go语言中常见100问题-#93 Not taking into account instruction-level ...

不考虑指令级别并行

指令级别并行也是严重影响程序性能的一个原因。在理解什么是指令级并行之前，先来看一个具体的例子，并分析如何优化它。下面的函数接收一个长度为2的int64类型数组，函数内部将迭代一定次数，在每轮迭代时，执行如下操作：

• 对数组中的第一个元素+1
• 如果数组中的第一个元素值是偶数，则对数组中的第二个元素+1

const n = 1_000_000

func add(s [2]int64) [2]int64 {
 for i := 0; i < n; i++ {
  s[0]++
  if s[0]%2 == 0 {
   s[1]++
  }
 }
 return s
}

整个循环中执行的指令如下图，可以概括为一次加1操作需要一次读操作和一次写操作。指令的顺序是连续的：首先对s[0]递增，然后在对s[1]递增前，需要再次读取s[0]。

注意：上述指令序列与汇编指令并不是匹配的，这里只是为了更清晰的分析问题，进行了简化处理。

现在我们来花点时间讨论指令级并行（ILP）背后的理论。几十年前，CPU设计师不再仅仅通过提高时钟速度来提高CPU性能，他们也尝试了其他优化方法，包括ILP。允许程序开发人员并行执行一系列指令。在单个虚拟内核实现ILP的处理器称为超标量处理器。

下面描述的是CPU在执行一个由三条指令组成的应用，I1、I2和I3.执行指令时，CPU需要先解码指令然后执行，执行由执行单元负责，执行各种操作和计算。指令执行过程可以划分为更细的阶段，这样一系列指令可以并行执行。

如下图所示，尽管I1、I2和I3在程序中是按顺序的，但是在CPU执行层面是并行执行的。

注意，并非所有指令都必须在单个时钟周期内完成。例如，读取已经存在于寄存器中的值的指令可以在一个时钟周期内完成，但是读取从主存储器获取地址的指令可能需要几十个时钟周期才能完成。

如果顺序执行，I1、I2和I3花费的总时间如下。

total time = t(I1) + T(I2) + t(I3)

有了指令级并行，总时间为

total time = max(t(I1), t(I2), t(I3))

指令级并行也面临一些挑战，通常称这些挑战为冒险。举例说明，如果I3将一个变量设置为42，而I2是条件指令（例如 if foo == 1）怎么办，理论上应该防止并行执行I2和I3. 这种情况称为控制冒险或分支冒险，在实际中，CPU设计者使用分支预测来解决这种冒险。具体做法是，CPU可以计算出在过去的100次中有99次条件为真，所以将并行执行I2和I3。在预测错误的情况下（I2恰好为假), CPU将刷新当前执行流水线，确保一致性。这种刷新会导致10到20个时钟周期的性能损失。

还有其他类型的冒险（如数据冒险）也会阻止并行执行指令。作为开发人员，我们要有这个意识。现在考虑下面两条更新寄存器的指令：

• I1将寄存器A和B中的数字加到C中
• I2将寄存器C和D中的数字加到D中

因为I2取决于寄存器C的值，而该值依赖I1,所以两条指令不能同时执行。I1必须在I2前完成。这种情况称为数据冒险。为了处理数据冒险，CPU设计者想出了一种叫做转发的技巧，它绕过了对寄存器的写入。不过这种技术不能彻底解决问题，而是试图减轻影响。

现在回到最开始的程序，着力分析其中的循环内容：

s[0]++
if s[0]%2 == 0 {
    s[1]++
}

数据冒险会阻止指令同时运行，可以结合下图进一步理解指令序列存在的并行风险。

由于if语句，上述序列包含一个控制冒险，此外还有前面讨论的数据冒险，数据冒险会阻止并行执行指令。下图从指令序列角度反映了唯一独立的指令是s[0]检查和s[1]自增，归功于分支预测，这两个指令可以并行。

数据冒险呢？可以改进吗，见下面的add函数第二版本, add2中引入了一个临时变量，将s[0]的值保存到临时变量v中，然后对s[0]进行自增，add函数中s[0]自增后检查是否为偶尔，这里检查自增前的值是否为奇数。

func add2(s [2]int64) [2]int64 {
 for i := 0; i < n; i++ {
  v := s[0]
  s[0] = v + 1
  if v%2 !=0 {
   s[1]++
  }
 }
 return s
}

比较add2和add两个版代码，显著区别是检查步骤v的数据冒险，如下图所示。

通过add2中小小的改动，可以提高CPU并行度。s[0]和s[1]的自增操作可以并行运行。虽然两个版本有相同数量的执行步骤，但第二版本增加了可以并行执行的步骤数量。

现在对上面两个函数进行基准测试，实测结果如下。可以看到add2比add性能有显著提升，大约提高了15%，这要归功于指令级并行。

cpu: Intel(R) Core(TM) i5-7360U CPU @ 2.30GHz
BenchmarkAdd-4               795           1471355 ns/op
BenchmarkAdd2-4              952           1238269 ns/op

总结，本文讨论了CPU如何使用并行性来优化一组指令的执行时间，此外还讨论了各种冒险问题，像控制冒险和数据冒险。数据冒险会影响指令的并行化，并通过改进版本add2说明了并行化提升对程序性能影响。注意，对这种指令级微优化要小心谨慎，因为Go编译器一直在发展。当Go版本发生变化时，应用生成的程序集也可能发生变化。