共计 12453 个字符,预计需要花费 32 分钟才能阅读完成。
写程序最次要的指标就是使它在所有可能的状况下都正确工作。一个运行得很快然而给出谬误后果的程序没有任何用途。程序员必须写出清晰简洁的代码,这样做不仅是为了本人可能看懂代码,也是为了在检査代码和今后须要批改代码时,其他人可能读懂和了解代码。另一方面,在很多状况下,让程序运行得快也是一个重要的思考因素。本章次要介绍了循环展开,减小过程调用,打消不必要的内存援用等优化代码的办法,有助于咱们写出高效的代码,进步代码的性能。
@[toc]
编写高效程序须要做到以下几点:
1. 适合的算法和数据结构
2. 编写出编译器可能无效优化以转换成高效可执行代码的源代码(例如,在 C 语言中,指针运算和强制类型转换使得编译器很难对它进行优化)。
3. 针对解决运算量特地大的计算,将一个工作分成多局部,即利用并行性。
优化编译器的能力和局限性
GCC 优化指令
-Og:默认配置,不优化。
-O1:编译器试图优化 代码大小和执行工夫 ,它次要对代码的 分支,常量以及表达式 等进行优化,但不执行任何会占用大量编译工夫的优化。
-O2:GCC 执行简直所有不蕴含工夫和空间衡量的优化(比方,尝试更多的 寄存器级的优化以及指令级的优化)。与 - O 相比,此选项减少了编译工夫,但进步了代码的效率。
-O3:比 -O2 更优化,对于 -O3 编译选项,在 -O2 的根底上,关上了更多的优化项(比方,应用伪寄存器网络,一般函数的内联,以及针对循环的更多优化)。不过可能导致编译进去的二级制程序不能 debug。
-Os:次要是对代码大小的优化,咱们根本不必做更多的关怀。通常各种优化都会打乱程序的构造,让调试工作变得无从着手。并且会打乱执行程序,依赖内存操作程序的程序须要做相干解决能力确保程序的正确性。
内存别名应用
两个指针可能指向同一个内存地位的状况成为内存别名应用。
void twiddle1 (long *xp,long*yp) { *xp+ = *yp; *xp+ = *yp; } void twiddle2(long *xp,long*yp) {*xp+ = 2 * *yp;}
twiddle1 它们都是将存储在由指针 yp 批示的地位处的值两次加到指针 xp 批示的地位处的值。twiddle2 须要 3 次内存援用(读 xp,读 yp,写 xp)。twiddle1 须要 6 次(2 次读 xp,2 次读 yp,2 次写 xp),个别,咱们认为 twiddle2 要优于 twiddle2。那么将 twiddle1 优化是不是就能产生相似 twiddle2 的代码了?
答案显然是不能够的。当 xp == yp 时,twiddle1 执行后的后果是:xp 的值减少 4 倍。而 twiddle2 的后果是 xp 的值减少 3 倍。因而,两个程序是有实质差异的。
以上这个例子就介绍了内存别名应用,编译器在优化时,并不知道xp 和 yp 是否相等,只能假如他们不相等,即 xp 和 yp 指针不会指向同一地位。
示意程序性能
程序性能度量规范:每元素的周期数(Cycles Per Element,CPE)。
处理器流动的程序是由时钟管制的,时钟提供了某个频率的法则信号,通常用千兆赫兹(GHz),即十亿周期每秒来示意。例如,当表明一个零碎有“4GHz”处理器,这示意处理器时钟运行频率为每秒 $4 \times {10^9}$ 个周期。每个时钟周期的工夫是时钟频率的倒数。通常是以纳秒(nanosecond,1 纳秒等于 ${10^{ – 8}}$ 秒)或皮秒(picosecond,1 皮秒等于 ${10^{ – 12}}$ 秒)为单位的。例如,一个 4GHz 的时钟其周期为 0.25 纳秒,或者 250 皮秒。从程序员的角度来看,用时钟周期来示意度量规范要比用纳秒或皮秒来示意有帮忙得多 。用时钟周期来示意, 度量值示意的是执行了多少条指令,而不是时钟运行得有多快。
程序示例
打消循环的低效率(Code Motion)
举个例子如下所示:
void lower1(char *s)
{
size_t i;
for (i = 0; i < strlen(s); i++)
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
<img src=”https://gitee.com/dongxingbo/Picture/raw/master//%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F/%E7%AC%AC%E4%BA%94%E7%AB%A0/strlen_%E9%95%BF%E5%BA%A6%E5%BD%B1%E5%93%8D%E6%95%88%E7%8E%87%E4%B8%BE%E4%BE%8B.png” alt=”image-20201201165824434″ style=”zoom: 80%;” />
程序看起来没什么问题,一个很平时的大小写转换的代码,然而为什么随着字符串输出长度的变长,代码的执行工夫会呈指数式增长呢?咱们把程序转换成 GOTO 模式看下。
void lower1(char *s)
{
size_t i = 0;
if (i >= strlen(s))
goto done;
loop:
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
i++;
if (i < strlen(s))
goto loop;
done:
}
咱们能够看到,在 C 语言中调用 strlen 一次,这个函数实际上会 执行两次 。还有一个重要的起因是: 字符串的长度并不会随着循环的进行而扭转,因而,咱们能够把 strlen 放在循环外,防止每次都调用 strlen 进行计算。
因为 C 语言中的字符串是以 null 结尾的字符序列,strlen 必须一步一步地查看这个序列,直到遇到 null 字符。对于一个长度为 n 的字符串,strlen 所用的工夫与 n 成正比。因为对 lower1 的 n 次迭代的每一次都会调用 strlen,所以 lower1 的整体运行工夫是字符串长度的二次项,反比于 ${n^2}$。
优化后的代码如下所示:
void lower2(char *s)
{
size_t i;
size_t len = strlen(s); /* 放在函数体外 */
for (i = 0; i < len; i++)
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
二者的执行效率比拟如下所示:
这种优化是常见的一类优化的办法,称为 代码移动(Code motion)。这类优化包含辨认要执行屡次(例如在循环里)然而计算结果不会扭转的计算。因此能够将计算挪动到代码后面不会被屡次求值的局部。
缩小过程调用
/* Move call to vec_length out of loop */
void combine2 (vec_ptr v, data_t *dest)
{
long i;
long length vec_length(v);
*dest = IDENT;
for (i=0;i< length;i++)
{
data_t val;
get_vec_element(v,i,&val);
*dest = *dest OP val;
}
}
从 combine2 的代码中咱们能够看出,每次循环迭代都会调用 get_vec_element 来获取下一个向量元素。对每个向量援用,这个函数要把向量索引 i 与循环边界做比拟,很显著会造成低效率。在解决任意的数组拜访时,边界查看可能是个很有用的个性,然而对 combine2 代码的简略分析表明所有的援用都是非法的。
data_t *get_vec_start(vec_ptr v)
{return v-data;}
/* Move call to vec_length out of loop */
void combine3 (vec_ptr v, data_t *dest)
{
long i;
long length vec_length(v);
data_t *data = get_vec_start(v);
*dest = IDENT;
for (i=0;i< length;i++)
{*dest = *dest OP data[i];
}
}
作为代替,假如为咱们的抽象数据类型减少一个函数 get_vec_start。这个函数返回数组的起始地址,而后就能写出此 combine3 所示的过程,其 内循环里没有函数调用 。它没有用函数调用来获取每个向量元素, 而是间接拜访数组。
事实上,通过这一步后,并没有使得性能有较大晋升,前面会具体讲到。这只是咱们优化路上的一步。
打消不必要的内存援用
#Inner loop of combines. data_t double, OP =
#dest in %rbx, data+i in %rdx, data+length in %rax
.L17:
vmovsd (%rbx),%xmm() # Read product from dest
vmulsd (%rdx),%xmm0,%xmm0 # Multiply product by data[i]
vmovsd %xmm, (%rbx)# Store product at dest
addq $8,%rdx # Increment data+i
cmp %rax,%rdx # Compare to data+length
jne .L17
在这段循环代码中,咱们看到,指针 dest 的地址寄存在寄存器 %rbx 中,它还扭转了代码,将第 i 个数据元素的指针保留在寄存器 %rdx 中,正文中显示为 data+i。每次迭代,这个指针都加 8。循环终止操作通过比拟这个指针与保留在寄存器各 ax 中的数值来判断。咱们能够看到每次迭代时,累积变量的数值都要从内存读出再写入到内存。这样的读写很节约,因为 每次迭代开始时从 dest 读出的值就是上次迭代最初写入的值。
咱们可能打消这种不必要的内存读写,combine4 所示的形式如下。引入一个长期变量 acc,它在循环中用来累积计算出来的值 。 只有在循环实现之后后果才寄存在 dest 中。正如上面的汇编代码所示,编译器当初能够用寄存器 %xmm0 来保留累积值。
#Inner loop of combines. data_t double, OP =
#dest in %rbx, data+i in %rdx, data+length in %rax
.L25:
vmulsd (%rdx),%xmm0,%xmm0 # Multiply product by data[i]
addq $8,%rdx # Increment data+i
cmp %rax,%rdx # Compare to data+length
jne .L25
void combine4 (vec_ptr v, data_t *dest)
{
long i;
long length vec_length(v);
data_t *data = get_vec_start(v);
*data acc = IDENT;
for (i=0;i< length;i++)
{acc = acc OP data[i];
}
*dest = acc;
}
把后果累积在长期变量中。将累积值寄存在局部变量 acc(累积器(accumulator)的简写)中,打消了每次循环迭代中从内存中读出并将更新值写回的须要。
程序性能如下(以 int 整数为例),单位为 CPE。
函数 | 办法 | + | * |
---|---|---|---|
combine3 | 间接数据拜访 | 7.17 | 9.02 |
combine4 | 累积在长期变量中 | 1.27 | 3.01 |
了解古代处理器
整体操作
基本概念
超标量(superscalar):在每个时钟周期执行多个操作
乱序(out-of-order):指令执行的程序不肯定要与它们在机器级程序中的程序统一
<img src=”https://gitee.com/dongxingbo/Picture/raw/master//%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F/%E7%AC%AC%E4%BA%94%E7%AB%A0/%E5%9B%BE5-11_%E4%B9%B1%E5%BA%8F%E5%A4%84%E7%90%86%E5%99%A8%E6%A1%86%E5%9B%BE.png” alt=”image-20201202111459465″ style=”zoom: 80%;” />
如上图所示,为一个乱序处理器的框图。整个设计有两个次要局部:指令管制单元 (Instruction Control Unit,ICU)和 执行单元(Execution Unit,EU)。前者负责从内存中读出指令序列,并依据这些指令序列生成一组针对程序数据的基本操作;而后者执行这些操作。
指令高速缓存(Instruction cache):一个非凡的高速存储器,它蕴含最近拜访的指令。
分支预测(branch prediction):处理器会猜想是否会抉择分支,同时还预测分支的指标地址。应用 投机执行(speculative execution)的技术,处理器会开始取出位于它预测的分支,会跳到的中央的指令,并对指令译码,甚至在它确定分支预测是否正确之前就开始执行这些操作。如果过后确定分支预测谬误,会将状态从新设置到分支点的状态,并开始取出和执行另一个方向上的指令。标记为取指管制的块包含分支预测,以实现确定取哪些指令的工作。
指令译码逻辑 :一条指令会被译码成多个操作。例如,addq %rax,8(%rdx),。这条指令会被译码成为三个操作:一个操作从内存中 加载 一个值到处理器中,一个操作将加载进来的值加上寄存器 %rax 中的值, 而一个操作将后果 存回 到内存。
读写内存是由加载和存储单元实现的 。加载单元解决从内存读数据到处理器的操作。这个单元有一个加法器来实现地址计算。相似,存储单元解决从处理器写数据到内存的操作。它也有一个加法器来实现地址计算。如图中所示,加载和存储单元通过 数据高速缓存(data cache)来拜访内存。数据高速缓存是一个高速存储器,寄存着最近拜访的数据值。
服役单元(retirement unit): 记录 正在进行 的解决,并确保它 恪守机器级程序的程序语义 。服役单元管制这些寄存器的更新。指令译码时,对于指令的信息被搁置在一个 先进先出的队列 中。这个信息会始终放弃在队列中,直到产生以下两个后果中的一个 。 首先 ,一旦一条指令的操作实现了,而且所有引起这条指令的分支点也都被确认为预测正确,那么这条指令就能够服役(retired)了,所有对程序寄存器的更新都能够被理论执行了。 另一方面 ,如果引起该指令的某个分支点预测谬误,这条指令会被清空(flushed),抛弃所有计算出来的后果。通过这种办法,预测谬误就不会改变程序的状态了。( 任何对程序寄存器的更新都只会在指令服役时才会产生)
寄存器重命名(register renaming):当一条更新寄存器 r 的指令译码时,产生标记 t,失去一个指向该操作后果的 惟一的标识符 。条目(r,t)被退出到一张表中,该表保护着每个程序寄存器 r 与会更新该寄存器的操作的标记 t 之间的关联。当随后以寄存器 r 作为操作数的指令译码时,发送到执行单元的操作会蕴含 t 作为操作数源的值。当某个执行单元实现第一个操作时, 会生成一个后果(v,t),指明标记为 t 的操作产生值 v。所有期待 t 作为源的操作都能应用 v 作为源值,这就是 一种模式的数据转发 。通过这种机制, 值能够从一个操作间接转发到另一个操作,而不是写到寄存器文件再读出来 ,使得第二个操作可能在第一个操作实现后尽快开始。重命名表只蕴含对于有未进行写操作的寄存器条目。当一条被译码的指令须要寄存器 r,而又没有标记与这个寄存器相关联,那么能够 间接从寄存器文件中获取这个操作数 。有了寄存器重命名, 即便只有在处理器确定了分支后果之后能力更新寄存器,也能够预测着执行操作的整个序列。
提早(latency):它示意实现运算所须要的总工夫。
发射工夫(Issue time):它示意两个间断的同类型的运算之间须要的最小时钟周期数。(发射工夫为 1:齐全流水线化)
浮点数加法器流水线化分为三个阶段:一个阶段解决指数值,一个阶段将小数相加,而另一个阶段对后果进行舍入。
容量(capacity):它示意可能执行该运算的性能单元的数量。
提早界线:实现合并运算的函数所须要的最小 CPE 值。
最大吞吐量:发射工夫的倒数。给出了 CPE 的最小界线。
循环展开
循环展开是一种程序变换,通过 减少 每次迭代计算的 元素的数量 , 缩小 循环的 迭代次数。循环展开可能从两个方面改良程序的性能。首先,它缩小了不间接有助于程序后果的操作的数量,例如循环索引计算和条件分支。第二,它提供了一些办法,能够进一步变动代码,缩小整个计算中要害门路上的操作数量。
/*2 * 1 loop unrolling*/
/* 应用 2×1 循环展开。这种变换能减小循环开销的影响 */
void combine5(vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(v);
long limit = length-1;
data_t *data = get_vec_start(v);
data_t acc = IDENT;
/* Combine 2 elements at a time */
for (i = 0; i < limit; i+=2) {acc = (acc OP data[i]) OP data[i+1];
}
/* Finish any remaining elements */
for (; i < length; i++) {acc = acc OP data[i];
}
*dest = acc;
}
上述代码是应用的”2 * 1 循环展开“的版本。第一个循环每次解决数组的两个元素。也就是每次迭代,循环索引 i 加 2,在一次迭代中,对数组元素 i 和 i + 1 应用合并运算。(留神拜访不要越界,正确设置 limit,n 个元素,个别设置界线 n -1)。
$K \times 1$ 循环展开次数和性能晋升并不是反比关系,一般来讲,最多循环展开一次后,性能晋升就不会很大了(次要起因是要害门路中 n 个 mul 操作,迭代次数减半,然而每次迭代中还是有两个程序的乘法操作。具体参考 P367)。
进步并行性
多个累积变量
${P_n}$ 示意 ${a_0},{a_1} \cdots {a_n}$ 乘积:${P_n} = \sum\limits_{i = 0}^{n – 1} {{a_i}} $。假如 n 为偶数,咱们还能够把它写成 ${P_n} = P{E_n} \times P{O_n}$, 这里 $P{E_n}$ 是索引为偶数的元素的乘积,而 $P{O_n}$ 是索引值为奇数的元素的乘积。
代码如下:
/*2 * 2 loop unrolling*/
/* 使用 2×2 循环展开。通过保护多个累积变量,这种办法利用了多个性能单元以及它们的流水线能力 */
void combine6(vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(v);
long limit = length-1;
data_t *data = get_vec_start(v);
data_t acc0 = IDENT;
data_t acc1 = IDENT;
/* Combine 2 elements at a time */
for (i = 0; i < limit; i+=2) {acc0 = acc0 OP data[i];
acc1 = acc1 OP data[i+1];
}
/* Finish any remaining elements */
for (; i < length; i++) {acc0 = acc0 OP data[i];
}
*dest = acc0 OP acc1;
}
上述代码用了 两次循环展开 ,以使每次迭代合并更多的元素,也应用了 两路并行,将索引值为偶数的元素累积在变量 acc0 中,而索引值为奇数的元素累积在变量 acc1 中。因而,咱们将其称为”2×2 循环展开”。同后面一样,咱们还包含了第二个循环,对于向量长度不为 2 的倍数时,这个循环要累积所有剩下的数组元素。而后,咱们对 acc0 和 acc1 利用合并运算,计算最终的后果。
事实上,combine6 比 combine5 性能晋升近 2 倍左右。
从新联合变换
/*2 * 1a loop unrolling*/
/* 使用 2×1a 循环展开,从新联合合并操作。这种办法减少了能够并行执行的操作数量 */
void combine7(vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(v);
long limit = length-1;
data_t *data = get_vec_start(v);
data_t acc = IDENT;
/* Combine 2 elements at a time */
for (i = 0; i < limit; i+=2) {acc = acc OP (data[i] OP data[i+1]);
}
/* Finish any remaining elements */
for (; i < length; i++) {acc = acc OP data[i];
}
*dest = acc;
}
咱们能够看到要害门路上只有 n / 2 个操作。每次迭代内的第一个乘法都不须要期待前一次迭代的累积值就能够执行。因而,最小可能的 CPE 缩小了 2 倍。这种改良形式简直达到了吞吐量的极限。
在执行从新联合变换时,咱们又一次扭转向量元素合并的程序。对于整数加法和乘法,这些运算是可联合的,这示意这种从新变换程序对后果没有影响。对于 浮点数 状况,必须再次评估这种从新联合是否有可能重大影响后果。咱们会说对大多数利用来说,这种差异不重要。
总的来说,从新联合变换可能缩小计算中要害门路上操作的数量,通过更好地利用性能单元的流水线能力失去更好的性能。大多数编译器不会尝试对浮点运算做从新联合,因为这些运算不保障是可联合的。以后的 GCC 版本会对整数运算执行从新联合,但不是总有好的成果。通常,咱们发现循环展开和并行地累积在多个值中,是进步程序性能的更牢靠的办法。
Intel 在 199 年引入了 SSE 指令,SSE 是“Streaming SIMD Extensions(流 SIMD 扩大)”的缩写,而 SIMD(读作“sim-dee”)是“Single-In-Struction, Multiple-Data(单指令多数据)”的缩写。SSE 性能历经几代,最新的版本为高级向量扩大(advanced vector extension)或 AVX。SIMD 执行模型是用 单条指令对整个向量数据进行操作 。这些向量保留在一组非凡的向量寄存器(vector register)中,名字为号 %ymm0~%ymm15。目前的 AVX 向量寄存器长为 32 字节,因而每一个都能够寄存 8 个 32 位数或 4 个 64 位数, 这些数据既能够是整数也能够是浮点数 。AVX 指令能够对这些寄存器执行向量操作,比方并行执行 8 组数值或 4 组数值的加法或乘法。例如,如果 YMM 寄存器 %ymm0 蕴含 8 个单精度浮点数,用 ${a_0},{a_1} \cdots {a_n}$ 示意,而 %rcx 蕴含 8 个单精度浮点数的内存地址,用 ${b_0},{b_1} \cdots {b_n}$ 示意,那么指令 vmulps(%rcx),%ymm0, %ymm1 会从内存中 读出 8 个值 ,并行地 执行 8 个乘法 ,计算 ${a_i} \leftarrow {a_i}{b_i},0 \le i \le 7$,并将失去的 8 个乘积保留 到向量寄存器 %ymm1。咱们看到,一条指令可能产生对多个数据值的计算,因而称为“SIMD”。(应用 SIMD 指令重写代码能够使程序性能取得上百倍晋升)
一些限度因素
寄存器溢出
咱们能够看到对这种循环展开水平的减少没有改善 CPE,有些甚至还变差了。古代 x86-64 处理器有 16 个寄存器,并能够应用 16 个 YMM 寄存器来保留浮点数。一旦循环变量的数量超过了可用寄存器的数量,程序就必须在栈上调配一些变量。
例如,上面的代码片段展现了在 10×10 循环展开的内循环中,累积变量 acc0 是如何更新的:
# Updating of accumulator acco in 10 x 10 unrolling
vmulsd (%rdx),%xmm,%xmm0 #acc0 *=data[i]
咱们看到该累积变量被保留在寄存器 %xmm0 中,因而程序能够简略地从内存中读取 data[i], 并与这个寄存器相乘。
与之相比,20×20 循环展开的相应局部十分不同:
# Updating of accumulator acco in 20 x 20 unrolling
vmovsd 40(%rsp),%xmm0
vmulsd (%rdx),%xmm0,%xmm0
vmovsd %xmmO,40(%rsp)
累积变量保留为 栈上的一个局部变量 ,其地位间隔栈指针偏移量为 40。程序必须从内存中读取两个数值:累积变量的值和 data[i] 的值,将两者相乘后,将后果保留回内存。
一旦编译器必须要诉诸寄存器溢出,那么保护多个累积变量的劣势就很可能隐没。侥幸的是,x86-64 有足够多的寄存器,大多数循环在呈现寄存器溢出之前就将达到吞吐量限度。
分支预测何预测谬误惩办
古代处理器的工作远远超前于以后正在执行的指令。
1. 不要过分关怀可预测的分支
咱们曾经看到谬误的分支预测的影响可能十分大,然而这并不意味着所有的程序分支都会减缓程序的执行。实际上,古代处理器中的分支预测逻辑十分长于分别不同的分支指令的有法则的模式和长期的趋势。例如,在合并函数中完结循环的分支通常会被预测为抉择分支,因而只在最初一次会导致预测谬误处罚。
2. 书写适宜用条件传送实现的代码
程序中的许多测试是齐全不可预测的,依赖于数据的任意个性,例如一个数是正数还是负数。对于这些测试,分支预测逻辑会解决得很蹩脚。对于实质上无奈预测的状况,如果编译器可能产生应用条件数据传送而不是应用条件管制转移的代码,能够极大地提高程序的性能。
咱们发现 GCC 可能为以一种更“功能性的 ”格调书写的代码产生 条件传送 ,在这种格调的代码中,咱们用 条件操作来计算值 ,而后用这些值来 更新程序状态 ,这种格调对抗于一种更“ 命令式的”格调,这种格调中,咱们用条件语句来有选择地更新程序状态。
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;
}
}
}
在随机数据上测试这个函数,失去的 CPE 大概为 13.50,而对于可预测的数据,CPE 为 2.5 其预测谬误惩办约为 20 个周期。
用性能式的格调实现这个函数是计算每个地位 i 的最大值和最小值,而后将这些值别离赋给 a[i]和 b[i]。
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;
}
}
对于这个函数的测试表明,无论数据是任意的,还是可预测的,CPE 都大概为 4.0。
了解内存性能
加载的性能
古代处理器有专门的性能单元来执行加载和存储操作,这些单元有外部的缓冲区来保留未实现的内存操作申请汇合。一个蕴含加载操作的程序的性能 既依赖于流水线的能力,也依赖于加载单元的提早。
要确定一台机器上加载操作的提早,咱们能够建设由一系列加载操作组成的一个计算,一条加载操作的后果决定下一条操作的地址。举例如下:
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 len;
}
.L3: #loop
addq $1,%rax #Increment len
moveq (%rdi),%rdi #ls = ls->next
tesatq %rdi,%rdi #Test ls
jne .L3 # if nonnull,goto loop
第 3 行上的 movq 指令是这个循环中要害的瓶颈。前面寄存器 %rdi 的每个值都依赖于加载操作的后果,而加载操作又以 %rdi 中的值作为它的地址。因而,直到前一次迭代的加载操作实现,下一次迭代的加载操作能力开始。这个函数的 CPE 等于 4.00,是由 加载操作的提早 决定的。
性能进步技术
尽管只思考了无限的一组应用程序,然而咱们能得出对于如何编写高效代码的很重要的经验教训。总结如下:
(1)高级设计
为遇到的问题抉择适当的算法和数据结构。要特地警惕,防止应用那些会渐进地产生蹩脚性能的算法或编码技术。
(2)根本编码准则
防止限度优化的因素,这样编译器就能产生高效的代码。
打消间断的函数调用。在可能时,将计算移到循环外。思考有选择地斗争程序的模块性以取得更大的效率。
打消不必要的内存援用。引入长期变量来保留两头后果。只有在最初的值计算出来时,才将后果寄存到数组或全局变量中。
(3)低级优化
结构化代码以利用硬件性能。
开展循环,升高开销,并且使得进一步的优化成为可能。
通过应用例如多个累积变量和从新联合等技术,找到办法进步指令级并行。
用功能性的格调重写条件操作,使得编译采纳条件数据传送。
(4)使用性能剖析工具
当解决大型程序时,将注意力集中在最耗时的局部变得很重要。代码分析程序和相干的工具能帮忙咱们系统地评估和改良程序性能。咱们形容了 GPROF,一个规范的 Unix 分析工具。还有更加简单欠缺的分析程序可用,例如 Intel 的 VTUNE 程序开发零碎,还有 Linux 零碎基本上都有的 VALGRIND。这些工具能够在过程级合成执行工夫,预计程序每个基本块(basic block)的性能。(基本块是外部没有管制转移的指令序列,因而基本块总是整个被执行的。)
最初要给读者一个忠告,要警觉,在为了提高效率重写程序时防止引入谬误。在引人新变量、扭转循环边界和使得代码整体上更简单时,很容易犯错误。一项有用的技术是在优化函数时,用 查看代码来测试函数的每个版本 ,以确保在这个过程没有引入谬误。查看代码对函数的新版本施行一系列的测试,确保它们产生与原来一样的后果。对于高度优化的代码,这组测试状况必须变得更加宽泛,因为要思考的状况也更多。例如, 应用循环展开的检査代码须要测试许多不同的循环界线,保障它可能解决最终单步迭代所须要的所有不同的可能的数字。
总结
本章中具体介绍了进步程序性能的一些通用办法和工具,在日常编写代码的过程中,应时刻留神代码的格调,养成良好的习惯。当解决大型程序时或者不晓得优化程序的那个局部时,咱们能够借助 GPROF,VTUNE,VALGRIND 等工具来进一步分析程序,剖析每个函数的性能,找到限度程序性能的因素,逐个解决。
如遇到排版错乱的问题,能够通过以下链接拜访我的 CSDN。
**CSDN:[CSDN 搜寻“嵌入式与 Linux 那些事”]