如何使用高级语言在机器语言层面提高程序运行效率

==基础编码原则==利用局部性原理减少过程调用利用局部性原理消除不必要的内存引用 ==低级优化==指令级并行寄存器重命名 循环展开利用多个累计变量重新结合变换 触发条件传输

下面我将对一个示例程序进行一系列的优化带各位走过利用高级语言【C语言】指导编译器编译高效率代码的路程。

本文分为两章。

第一章《基础编码原则》利用局部性原理编码提高程序效率。

第二章《低级优化》利用编码手段最大化利用处理器资源。

本文没有具体的汇编代码【本来想写，但嫌麻烦】，大家放心食用

基础编码原则

本章我们将利用局部性原理，最大化利用寄存器来编码，使程序减少内存访问读写，以及减少过程【函数】调用来减轻处理器由分配资源和ret指令引起的处理器时钟周期浪费。

利用局部性原理减少过程调用

下面是一段计算向量元素和的代码

对向量内元素求和利用这个宏定义

#define IDENT 0#define OP +

对向量内元素求积利用这个宏定义

#define IDENT 1#define OP *

下面的代码是对向量的各个操作：【下面示例函数中会调用这两个函数】

/**定义一个向量结构体**/typedef struct{long len;data_t *data;} vec_rec, *vec_ptr;/**程序中各函数的定义**///获取向量中下标为index的元素，返回结果给dest所指向的内存单元int get_vec_element(vec_ptr v, long index, data_t* dest){if(index < 0 || index >= v->len) return 0;*dest = v->data[index];return 1;}//返回向量长度long vec_length(vec_ptr v){return v->len;}

待优化示例代码：

void combine1(vec_ptr v , data_t* dest){long i;*dest = IDENT;for(i = 0; i < vec_length( v ); i++){data_t val;get_vec_element( v , i , &val);*dest = *dest OP val;}}

上面给出的代码中，for循环每次循环都会调用一次vec_length( )函数来访问向量元素个数，而每次调用vec_length( )都会对内存进行一次访存操作，并且还面临对程序栈的各项修改，还有ret带来的处理器三个周期的浪费^{1。但由于向量长度不会因为访问一次向量元素就发生改变，而每次for循环都要进行一次vec_length( )函数调用，带来大量不必要的处理器周期浪费。}

下面给出经过修改的代码：

void combine2(vec_ptr v , data_t* dest){long i;*dest = IDENT;long length = vec_length(v);//在此处加入一个局部变量lengthfor(i = 0; i < length; i++){data_t val;get_vec_element( v , i, &val);*dest = *dest OP val;}}

经过修改的代码中，在combine1函数内增加了一个局部变量length用来记录向量长度，这样就不必每次for循环都调用一次vec_length( )函数，避免了反复调用函数带来的处理器不必要消耗。

局部变量，在处理器执行过程中一般处于程序栈中或者处理器更愿意利用寄存器存储局部变量，这是由编译器决定的，一般当没有空闲的寄存器的时候才会用栈来存储局部变量，因为这个局部变量【length】被反复访问，因此编译器会将其用更加高速的寄存器存储。于此，提高了代码的局部性。

我们发现，combine2中还有一个函数，get_vec_element( v , i, &val)，其反复访问内存，给出以下优化代码

//函数返回向量的首地址data_t* get_vec_start(v){return v->data;}void combine3(vec_ptr v , data_t* dest){long i;*dest = IDENT;long length = vec_length(v);data_t* data = get_vec_start(v);//创建一个局部变量data指针指向 向量首地址，利用直接访存操作代替通过函数访问向量元素for(i = 0; i < length; i++){*dest = *dest OP data[i];}}

如此，我们利用一个指向向量首地址的指针，使用指针直接访存的方法，消除了反复调用get_vec_element( )函数的处理器浪费。

利用局部性原理消除不必要的内存引用

上面优化到combine3，我们利用局部性原理，减少了函数调用带来的处理器浪费。

接下来我们将学习如何利用局部性消除不必要的内存引用。

重点：我们观察combine3，发现for循环中，dest指针指向的地址被反复读取与写入，我们需要减少内存读写，因为每次内存读写都需要使用非常多的时钟周期，从而降低程序运行效率，哪怕是高速缓存也至少需要4个时钟周期，下图展示了处理器使用内存的顺序。

我们知道，处理器访存顺序为：寄存器 === 》L1缓存 ===》L2缓存 ===》L3缓存 ===》内存 ===》固态硬盘/机械硬盘 ===》网络磁盘

如下图所示：

下一级存储作为上一级存储的缓存。所以当高速缓存不命中的时候缓存会往内存提取一个数据块，因为局部性原理，往往访问的都是刚刚访问的内存附近的内存，所以直接传入数据块可以提高缓存命中率并且降低访问内存的次数。

那么，combine3的代码中，dest指针的内存读写如何消除呢？

示例代码：

data_t* get_vec_start(v){return v->data;}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;//创建一个局部变量acc用于累计计算结果for(i = 0; i < length; i++){acc = acc OP data[i];}*dest = acc;//最后将累计的结果赋值给dest指针指向的内存}

combine4使用一个局部变量acc累积计算结果，跟局部变量length一样，编译器会利用一个寄存器来表示acc，这样就降低了访存次数，只在函数的最后 将累积结果返回给dest指向的内存单元。

那data[i]这个访存次数怎么降低呢？【请看低级优化章】

低级优化

本章我们将从处理器最底层硬件走入最大化利用处理器资源的康庄大道。

主要分为：1.突破延迟界限，2.接近吞吐量界限

我们的目标：使程序接近吞吐量界限

首先，我们预普及一下处理器资源：【参考处理机：Intel Core i7 Haswell】

处理器分为指令控制单元和指令执行单元

指令控制单元：负责从内存中读出指令序列，并根据指令序列生成一组针对程序数据的基本操作

指令执行单元：负责执行指令控制单元生成的基本操作

我们这里讨论的是执行单元中的功能单元部分，因为利用的处理器资源主要是功能单元的算数运算单元和加载单元

指令执行单元= 功能单元 + 缓存

功能单元可以并行的执行多个操作，而不必顺序执行，并且执行结果严格遵循顺序执行的结果

功能单元分为以下八个单元：

整数运算、浮点乘、整数和浮点除、分支 整数运算、浮点加、整数乘、浮点乘 加载、地址计算 加载、地址计算 存储 整数运算 整数运算、分支 存储，地址计算

读写内存是由加载、存储单元实现的，加载单元负责读取，存储单元负责写入。

处理器利用分支单元实现：检查分支预测是否正确，若发现分支预测错误，那么该单元则广播给其他单元预测错误的信息，并命令其他正在运算的单元清空已经运算的错误的内容。

整数运算包括：整数加、位级操作、移位运算

我们看到，功能单元的这种组合具有同时执行多同类型操作的能力，如：

同时执行四个整数加同时执行两个浮点乘同时加载两个内存数据

有了以上的处理器功能单元基础，我们就可以充分利用处理器资源来编写代码了

指令级并行

我们发现，跟更新寄存器的操作是在执行单元执行结束了之后的操作，那么当连续多次写同一个寄存器的时候就可以在经过多个执行单元的操作的最后再将寄存器更新了，这就是实现指令级并行的方法之一。控制操作数在执行单元间传送的机制叫“寄存器重命名”。

寄存器重命名

当一条更新寄存器 r 指令译码时，产生标记 t ，得到一个指向该操作结果的唯一标识符。

条目( r , t )被加入到一张表中，该表维护每个程序寄存器 r 与会更新该寄存器的操作的标记 t 之间的关联。

当随后以寄存器 r 作为操作数的指令译码时，发送到执行单元的操作包含 t 作为操作数源的值。

当某个执行单元完成第一个操作时，会产生一个结果 （v ， t ），其指明标记为 t 的操作产生值 v 。

所有等待 t 作为源的操作都能够使用 v 作为源值，这也是一种形式的数据转发。

通过寄存器重命名这一机制，寄存器值可以从一个操作直接转发到另一个操作，而不是写入寄存器再读出来，这使得第二个对同一寄存器的操作能够再第一个操作完成后马上开始。

循环展开

我们看看如何用循环展开消除对内存多次访问产生的延迟

通过增加每次迭代计算的元素的数量，减少循环的次数。

void combine5(vec_ptr v , data_t* dest){long i;long length = vec_length(v);data_t* data = get_vec_start(v);data_t acc = IDENT;//创建一个局部变量acc用于累计计算结果long limit = length - 1 ;for(i = 0; i < limit; i+=2){acc = (acc OP data[i]) OP data[i+1];}//完成剩余元素for(;i<length;i++){acc = acc OP data[i];}*dest = acc;//最后将累计的结果赋值给dest指针指向的内存}

循环展开从两个方面改进程序性能：

它减少了不直接有助于程序结果的操作数量，如【循环索引计算】和【条件分支】。它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量。

在本次优化中，原本需要两个循环的操作在一个循环内完成，减少了不必要的循环索引计算和条件分支。

到此，程序仅受单运算单元带来的吞吐量限制。

这被称为2X1的循环展开

利用多个累计变量

我们发现代码acc = (acc OP data[i]) OP data[i+1];实际上只有一个运算单元在执行，但是我们拥有多个执行同一操作的硬件，并非是处理器达到上限，是我们的程序没办法调用其他的相同运算单元。

此处我们提出一种新的方法突破单运算单元限制：使用多累计变量

void combine6(vec_ptr v , data_t* dest){long i;long length = vec_length(v);data_t* data = get_vec_start(v);data_t acc1 = IDENT;//累计变量1data_t acc2 = IDENT;//累计变量2long limit = length - 1 ;for(i = 0; i < limit; i+=2){acc1 = acc1 OP data[i];acc2 = acc2 OP data[i+1];}//完成剩余元素for(;i<length;i++){acc1 = acc1 OP data[i];}*dest = acc1 OP acc2;//将两个累计变量通过 OP 运算的结果存入dest指向的内存单元}

如此，如果 OP 是“ + ”，那么我们调用了两个加法单元执行运算，实现了指令级并行，如果 OP 是 “ * ”， 并且data_t是double ，那么我们调用了两个乘法单元【处理机仅有的两个乘法单元】。

这被称为2X2的循环展开

重新结合变换

上承combine5，我们从根本上改变合并执行的方式，也可以极大提高程序效率.

上面给出的combine5中：acc = (acc OP data[i]) OP data[i+1];

此处给出的combine7中：acc = acc OP (data[i] OP data[i+1]);

void combine7(vec_ptr v , data_t* dest){long i;long length = vec_length(v);data_t* data = get_vec_start(v);data_t acc = IDENT;//创建一个局部变量acc用于累计计算结果long limit = length - 1 ;for(i = 0; i < limit; i+=2){acc = acc OP (data[i] OP data[i+1]);}//完成剩余元素for(;i<length;i++){acc = acc OP data[i];}*dest = acc;//最后将累计的结果赋值给dest指针指向的内存}

这样做的优势在哪里呢？因为括号改变了向量元素与累计值的合并顺序，一次调动两个加载单元，加载自内存的值直接运算，并将运算结果直接与寄存器运算，这样就消除了加载单元限制的延迟界限，靠近了加载单元的吞吐量界限。

combine5中，运算第一个 OP 完成后，运算第二个 OP 之前需要等待加载单元加载的数据才能运算第二个 OP。

combine7中，直接调动两个加载单元加载内存数据，而后直接调动乘法单元运算结果，再将结果与寄存器内的数据运算，最后将运算结果传送至寄存器内部。

触发条件传输

对以下代码：

for(i = 0;i < n; i++){if(a[i] > b[i]){long t = a[i];a[i] = b[i];b[i] = t;}}

我们发现，在运算结果之前要进行分支预测，一旦分支预测则可能会导致分支预测错误，实际上，我们可以通过编写触发条件传送的代码来避免分支预测。改进如下：

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;}

由此，我们避免了不必要的分支预测错误可能引发的处理器性能浪费。

小白水平有限，有错误的地方还望大佬不吝指正！

[1] 本文示例和代码引用自《深入理解计算机系统》-Randal E.Bryant

[2] 图片1引用自：/p/265776590#:~:text=%E5%AF%84%E5%AD%98%E5%99%A8%E7%9A%84%E8%AE%BF%E9%97%AE%E9%80%9F%E5%BA%A6%E9%9D%9E%E5%B8%B8%E5%BF%AB%EF%BC%8C%E4%B8%80%E8%88%AC%E8%A6%81%E6%B1%82%E5%9C%A8%E5%8D%8A%E4%B8%AA%20CPU%20%E6%97%B6%E9%92%9F%E5%91%A8%E6%9C%9F%E5%86%85%E5%AE%8C%E6%88%90%E8%AF%BB%E5%86%99%EF%BC%8CCPU%20%E6%97%B6%E9%92%9F%E5%91%A8%E6%9C%9F%E8%B7%9F%20CPU%20%E4%B8%BB%E9%A2%91%E6%81%AF%E6%81%AF%E7%9B%B8%E5%85%B3%EF%BC%8C%E6%AF%94%E5%A6%82,2%20GHz%20%E4%B8%BB%E9%A2%91%E7%9A%84%20CPU%EF%BC%8C%E9%82%A3%E4%B9%88%E5%AE%83%E7%9A%84%E6%97%B6%E9%92%9F%E5%91%A8%E6%9C%9F%E5%B0%B1%E6%98%AF%201%2F2G%EF%BC%8C%E4%B9%9F%E5%B0%B1%E6%98%AF%200.5ns%EF%BC%88%E7%BA%B3%E7%A7%92%EF%BC%89%E3%80%82

[3] 图片引用自哈尔滨工业大学计算机系统课程。

1 ↩︎