《深入理解计算机系统》（CSAPP）读书笔记 —— 第五章 优化程序性能

写程序最主要的目标就是使它在所有可能的情况下都正确工作。一个运行得很快但是给出错误结果的程序没有任何用处。程序员必须写出清晰简洁的代码，这样做不仅是为了自己能够看懂代码，也是为了在检査代码和今后需要修改代码时，其他人能够读懂和理解代码。另一方面，在很多情况下，让程序运行得快也是一个重要的考虑因素。本章主要介绍了循环展开，减小过程调用，消除不必要的内存引用等优化代码的方法，有助于我们写出高效的代码，提高代码的性能。

@[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×1094 \times {10^9}4×109个周期。每个时钟周期的时间是时钟频率的倒数。通常是以纳秒（ nanosecond，1纳秒等于10−8{10^{ - 8}}10−8秒）或皮秒（ picosecond，1皮秒等于10−12{10^{ - 12}}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的整体运行时间是字符串长度的二次项，正比于n2{n^2}n2。

  优化后的代码如下所示：

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.179.02combine4累积在临时变量中1.273.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×1K \times 1K×1循环展开次数和性能提升并不是正比关系，一般来讲，最多循环展开一次后，性能提升就不会很大了（主要原因是关键路径中n个mul操作，迭代次数减半，但是每次迭代中还是有两个顺序的乘法操作。具体参考P367）。

提高并行性

多个累积变量

  Pn{P_n}Pn​表示a0,a1⋯an{a_0},{a_1} \cdots {a_n}a0​,a1​⋯an​ 乘积：Pn=∑i=0n−1ai{P_n} = \sum\limits_{i = 0}^{n - 1} {{a_i}} Pn​=i=0∑n−1​ai​。假设n为偶数，我们还可以把它写成Pn=PEn×POn{P_n} = P{E_n} \times P{O_n}Pn​=PEn​×POn​,这里PEnP{E_n}PEn​是索引为偶数的元素的乘积，而POnP{O_n}POn​是索引值为奇数的元素的乘积。

  代码如下：

/*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个单精度浮点数，用a0,a1⋯an{a_0},{a_1} \cdots {a_n}a0​,a1​⋯an​表示，而%rcx包含8个单精度浮点数的内存地址，用b0,b1⋯bn{b_0},{b_1} \cdots {b_n}b0​,b1​⋯bn​表示，那么指令vmulps （%rcx）， %ymm0, %ymm1会从内存中读出8个值，并行地执行8个乘法，计算ai←aibi,0≤i≤7{a_i} \leftarrow {a_i}{b_i},0 \le i \le 7ai​←ai​bi​,0≤i≤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那些事”]