Ylin's Blog
0%

62:程序性能优化(3)

发表于 分类于 ，
本文字数： 4.6k 阅读时长 ≈ 4 分钟

我们已经尽可能的实现各种程度的优化了，但所谓知己知彼，百战不殆。我们不仅要了解程序的性能怎么去优化，同时也要了解制约程序进一步优化的因素是什么。

限制因素

关键路径指明了执行程序所需时间的基本下界。如果程序中有某条数据相关链，这条链上的所有的延迟之和等于T，那么程序至少需要T个周期才能执行完。我们还看到功能单元的吞吐量界限也是程序执行的一个下界。也就是说，假设一个程序一共需要N个某种运算的计算，而微处理器只有C个能执行这个操纵的功能单元，并且这些单元的发射时间为I，那么这个程序的执行至少需要N*I/C个周期。

不过以上是理想状态，实际过程中，我们仍然需要考虑其他的制约因素。

寄存器溢出

循环并行性的好处受汇编代码描述计算的能力限制（如果代码描述不出来，说明寄存器不够用了）。如果并行度p超过了可用的寄存器数量，那么编译器就会溢出。将某些临时值放到内存中，在堆栈上分配空间。比如下面的例子：

image.png

为啥20*20的循环展开反而不如10*10呢？现代x86-64处理器可以使用16个YMM寄存器来保存浮点数。一旦数量超过了可用的寄存器的数量，程序就必须在栈上分配变量。内存写入读取的过程会造成不必要的开销。不过大多数循环会在出现寄存器溢出之前就会达到吞吐量的极限。

分支预测和预测错误处罚

指令在进行分支预测时，往往会使用投机执行的机制，但是预测错误意味着很大的代价。虽然代价是无法避免的，但是我们是否可以减少这个代价呢？在x86-64的程序处理中有条件传送的指令。我们可以在进行分支跳转的时候，通过将条件转移编译成条件传送来，减少这个代价。我们直接结算出两个方向上的可能的值，然后根据条件传送选择期望的值。这样，我们就不用考虑条件是否满足了，因为没有代价。

抛开编译器的优化，我们又该如何编写能够减少分支预测处罚的代码呢?

不要过分关心可以预测的分支

错误的分支预测影响可能很大，但是并不意味着所有的程序分支都会减缓程序的运行。现代处理器的分支预测逻辑十分先进，对于循环语句的分支，往往会被预测为选择分支，这样只有最后一次才会导致预测错误。

所以在程序性能优化（1）中的这个现象可以解释：

image.png

我们为了减少get_vec_element中的边界检测的延迟，改进成了combine3，发现程序性能几乎没什么改变，这是因为对于i的边界检测，是高度可预测的，对于计算机而言影响微乎其微。这些检测并不会影响程序的关键路径，或是起不到决定性作用。

书写适合用条件传送实现的代码

分支预测对于循环这种有规律的模式还行，但是程序中的大多数测试时完全不可预测的，依赖于数据的任意性，分支预测逻辑会表现得很糟糕。我们无法保证编译器会在编译中使用条件数据传送而不是条件控制转移，但是我们可以引导编译器进行我们想要的编译。

以一个程序为例，给定两个整数数组a和b，对于每个位置i，我们想要将a[i]设置为a[i]和b[i]中较小的那个，将b[i]设置成较大的那个。

首先是我们常用的风格：

1
2
3
4
5
6
7
8
9
10
void minmax1(long a[],long b[],long n){
    long i;
    for(i=0;i<n;i++){
        if(a[i]>b[i]){
            long t = a[i];
            a[i] = b[i];
            b[i] = t;
        }
    }
}

在这里可以看到，我们是在分支预测之后才执行交换的过程。这会扩大分支预测的代价。可是我们尝试另一种写法：

1
2
3
4
5
6
7
8
9
void minmax2(long a[],long b[],long n){
    long i;
    for(i=0;i<n;i++){
        long min = a[i] < b[i] ? a[i] : b[i];
        long max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}

这里的话相当于去除了条件分支，先把每个位置的最大值和最小值计算出来，然后分别赋值给a[i]和b[i]。通过合理的安排代码，我们也可以更好的帮助编译器优化代码。

理解内存性能

内存性能实际上也是很重要的决定性因素，在之前的测试中，实际上访问的内存都十分少量。所有的现代处理器都包含一个或多个高速缓存存储器，以对少量的存储器提供快速的访问。接下来我们要进一步讨论加载和存储操作的程序的性能印象。不过我们默认所有的数据都是存放在高速缓存中的情况。

加载的性能

一个包含加载操作的程序性能既依赖于流水线的能力，也依赖于加载单元的延迟。在之前的合并函数中，无论什么数据类型和合并操作都无法让CPE下降到0.5以下。这是因为，每一个被计算的元素，所有的示例都需要熊内存中独一个值，对于两个加载单元而言，其每个时钟周期都只能启动一条加载操作，所以CPE不可能小于0.5

到目前为止我们并没有在示例中看到加载操作的延迟产生的影响。加载操作的地址只依赖于循环索引i，所以加载操作不会称为限制性能的关键路径的一部分。

但是我们可以手动构造一个由一系列加载操作构成的计算，一个加载操作的结果决定下一条操作的地址：

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct ELE{
    struct ELE* next;
    long data;
}list_ele,*list_ptr;

long list_len(list_ptr ls){
 	long len = 0;
    while (ls){
        len ++;
        ls = ls->next;
    }
    return;
}

在这里变量ls的每个后续只依赖于指针引用ls->next读出的值。我们可以关键部分的汇编代码：

1
2
3
4
5
.L3:
	addq $1,%rax
	movq (%rdi),%rdi	;ls = ls->next
	testq %rdi,%rdi
	jne .L3

我们可以可以看到movq是整个循环中关键的瓶颈，且每次循环都会依赖加载出来的%rdi的值，此时的程序的CPE是由加载操作的延迟决定的。我们之后在存储器部分会详细讨论。

存储的性能

和其他的操作不一样，存储操作不会影响任何寄存器的值。一系列的存储操作并不会产生数据相关。只有加载操作会受存储操作结果的影响，因为只有加载操作才能从由存储操作写的那个位置读回值。

我们可以做一个实验来体现这种影响：

1
2
3
4
5
6
7
8
9
void write_read(long* src,long* dst,long n){
    long cnt = n;
    long val = 0;
    while (cnt){
        *dst = val;
        val = (*src)+1;
        cnt--;
    }
}

然后我们分别使用两种不同的调用方式：

image.png

最终的结果是示例A的CPE=1.3远快于示例B的CPE = 7.3。这背后的原因就是因为在调用write_read时，参数src和dst指向了同一个内存位置，导致产生了写/读相关——一个内存读的结果依赖于一个最近的内存写。

为了理解这背后具体的原理，我们需要更加仔细的看看加载和存储执行单元：

image.png

存储单元实际上会包含一个存储缓冲区，它包含已经被发射到存储单元而又还没完成的存储操作（这里的完成包括更新数据高速缓存）的地址和数据。提供这么一个缓冲区，使得一系列存储操作不必等待每个操作都更新高速缓存就能执行。当一个加载操作发生时，它必须检查存储缓存区中的条目，看看有没有地址匹配。如果有就取出相应的数据条目作为加载操作的结果。

其机器代码形式如下：

1
2
3
4
5
6
7
; src in %rdi , dst in %rsi , val in %rax
.L3:				; loop:
	movq %rax,(%rsi)	;write val to dst
	movq (%rdi),%rax	;t = *src
	addq $1,%rax		; val = t+1
	subq $1,%rdx		;cnt--
	jne .L3				;if != 0,goto loop

这里的movq (%rdi),%rax在实际的过程中被翻译成了两个操作：

  • s_addr指令计算存储操作的地址，在存储缓冲区创建一个条目，并设置该条目的地址字段
  • s_data操作设置该条目的数据字段。
image.png

这两个计算时独立执行的，不过它们之间有隐含的相关，实际上s_addr的操作必须在s_data之前。同时由于load操作需要检查所有未完成的存储操作的地址，所以s_addr到load之间也会存在数据相关。还有一个有条件的数据相关，存在于s_data和load之间（当%rsi和%rdi相等，即读写的地址相同），此时load操作必须等待直到s_data将它的结果存放到存储缓冲区中。反之，则继续进行。

我们依旧可以图形化抽象write_read的操作，来分析它的关键路径：

image.png

右边是最简情况，只保留了使用一次迭代中的值为下一次迭代产生的值的操作。

现在我们可以理解函数write_read的性能特征了，下面是内循环多次迭代形成的数据相关：

image.png

在示例A的情况下，有不同的源和目的地址，加载和存储操作都可以独立进行，因此唯一的关键路径是减少变量造成的，因此这个程序的CPE为1.0。对于示例B的情况下，源地址和目的地址相同，导致s_data和load指令之间的数据相关使得关键路径形成。其中包括了存储，加载，增加数据等操作，导致程序的CPE为7.0。

这个例子说明了，内存操作的细微之处。对于寄存器操作，在指令被译码成操作的时候，处理器就可以确定哪些指令会影响那些指令了。但是对于内存操作，只有到计算出加载和存储的地址被计算出来后，处理器才能确定那些指令会影响哪些。

我们可以通过设置中间变量的方式来避免写/读相关。例如：

我们有a，p两个数组，令p[0] = a[0]，p[i] = p[i-1] + a[i]，我们正常写出来的程序会是这样：

1
2
3
4
5
6
void psum1(long a[],long p[],long n){
    long i;
    p[0] = a[0];
    for (i=1;i<n;i++)
        p[i] = p[i-1] + a[i];
}

但是这里的p[i]=p[i-1] + a[i]存在着读/写相关。我们可以引入一个中间的存储变量，来避免这种数据上的依赖：

1
2
3
4
5
6
7
8
9
10
void psum1(long a[],long p[],long n){
    long i;
    long last_val,val;
    last_val = p[0] = a[0];
    for (i=1;i<n;i++){
        val = last_val + a[i];
        p[i] = val;
        last_val = val;
    }
}

总结：性能提高技术

  • 高效设计：为遇到问题选择适当的算法和数据结构，避免使用会渐进的产生糟糕性能的算法或编码技术。
  • 基本编码原则：避免限制优化的因素，这样编译器就能产生高效的代码。
    • 消除连续的函数引用：必要时，将计算移到循环外面。
    • 消除不必要的内存引用：引入临时变量来保存中间结果。只有在最后的值计算出来时，才将结果存放到数组或全局变量中
  • 低级优化：结构化代码以利用硬件功能。
    • 展开循环，降低开销，并且使得进一步的优化称为可能
    • 通过使用例如多个累计变量和重新结合等技术，提高指令的并行性
    • 用功能性的风格重写条件操作，使得编译采用条件数据传送