在本章的第一部分,作者通过一个具体事例引出了代码调优的主题,也交代了调优的基本步骤:监视程序的性能-研究时间占用最多的代码段/函数-针对具体的代码段进行改进。在这个事例中，占用运行时间最多的是malloc函数，最终的改进方法是利用高速缓存优化。

　　在第二部分，作者通过连续4个问题进一步阐述了代码调优的具体做法。

　　问题1——整数取模。 这个问题来自第2章向量旋转的“杂技”算法：

　　k = ( j + rotdist ) % n;

C语言中取模运算开销较大，下面的代码可能会减少程序的运行时间：

　　k = j + rotdiat;
　　if (k > n)
　　    k -= n;

第一次运行时rotdist设为1，速度提升明显，第二次运行时设为10，却几乎没有影响。作者发现，当rotdist = 1时，算法的空间局部性很好，模运算决定了程序的运行时间，改动后局部性受到影响，这时候访存时间成了左右程序运行速度的关键因素，因此对模运算的优化没有表现出效果。

　　问题2——函数、宏和内联代码。 如下代码：

　　maxendinghere = max(maxendginghere, 0);
　　maxsofar = max(maxsofar, maxendinghere);

　　其中的max函数返回两个参数中的最大值：

　　float max(float a, float b){
　　    return a > b ? a : b;
　　}

　　有的C语言程序员可能下意识地采用宏来替换max函数：

　　#define max(a,b) ((a)>(b)?(a):(b))

这种改变可能会带来效率上的提升，但也可能适得其反。作者用在第8章（算法设计技术）的算法3中，却发现原本10毫秒的程序现在要运行100秒。这是因为宏那种按名称调用的语义导致算法3对自身的递归调用超过了两次，因此增加了其渐近运行时间。
　　C程序员经常需要在性能和正确性之间进行折中，而C++程序员却可以享受鱼与熊掌兼得的快乐。C++允许对某一函数进行内联编译，这就兼得了函数的简洁语义和宏的低廉开销。

　　问题3——顺序搜索。 顺序搜索的数组可能是未排序的。代码1：

　　int ssearch1(t)
　　    for i = [0, n)
　　        if x[i] == t
　　            return i
　　    return -1

　　代码2通过设置哨兵元素，去除了for循环中的条件判断：

　　int ssearch2(t)
　　    hold = x[n]
　　    x[n] = t
　　    for (i = 0; ; i++)
　　        if x[i] == t
　　            break
　　    x[n] = hold
　　    if i == n
　　        return -1
　　    else
　　        return i

　　很显然，这段代码的for循环两个分号之间的判断语句为空，也就减少了一次条件判断操作。
　　代码3采用循环展开的方法进一步加速程序，而且不再“小心翼翼地”将x[n]的值从哨兵元素重设回原来的值：

　　int ssearch3(t)
　　    x[n] = t
　　    for (i = 0; ; i += 8)
　　        if (x[i] == t) {  break }
　　        if (x[i+1] == t) { i += 1; break }
　　        if (x[i+2] == t) { i += 2; break }
　　        if (x[i+3] == t) { i += 3; break }
　　        if (x[i+4] == t) { i += 4; break }
　　        if (x[i+5] == t) { i += 5; break }
　　        if (x[i+6] == t) { i += 6; break }
　　        if (x[i+7] == t) { i += 7; break }
　　    if i == n
　　        return -1
　　    else
　　        return i

对现代计算机来说，将循环展开有助于避免管道阻塞、减少分支、增加指令级的并行性。

　　问题4——计算球面距离。这个问题中描述了一个具体的事例，通过增加额外的数据大大减少了运行时间。
　　在一个以经纬度为标准的系统中，程序要计算地球上已知的哪个点距离输入的经纬度最近。这个程序需要大量的计算，其中最耗费时间的当属其中反复执行的三角函数运算。经过改进后，将经纬度的表示法转化为x、y、z坐标表示的世界坐标系中的点，并且将这些数据存储起来。这样，在判断点的距离的时候，就改为采用坐标差的平方和而不再是三角函数运算。结果，程序获得了显著的加速（处理复杂地图的时间由几小时将为半分钟）。

　　在本章的第三部分，作者继续着眼于二分搜索算法，这次用了几种版本的代码对二分搜索进行持续的改进。

　　原来的二分搜索：

　　l = 0; u = n-1
　　loop
　　    /* invariant: if t is present, it is in x[l..u]*/
　　    if l > u
　　        p = -1; break
　　    m = (l + u)/2
　　    case
　　        x[m] < t: l = m+1
　　        x[m] == t: p = m; break
　　        x[m] > t: u = m-1

　　改进1：多个t也能返回第1个。

　　l = -1; u = n
　　while l+1 != u
　　    /* invariant: x[l] < t && x[u] >= t && l < u */
　　    m = (l + u) / 2
　　    if x[m] < t
　　        l = m
　　    else
　　        u = m;
　　/* assert l+1 = u && x[l] < t && x[u] >= t */
　　p = u
　　if p >= n || x[p] != t
　　    p = -1

　　虽然这个二分搜索解决的问题要比原先的程序所解决的问题更难，但却可能更高效：在每次循环迭代中，它只对t和x中的元素作一次比较，而原先的程序有时必须比较两次。
　　改进2：利用n=1000的已知条件，使用下限值l和增量i来表示区间，使得l+i=u。

　　i = 512
　　l = -1
　　if x[511] < t
　　    l = 1000 - 512
　　while i != 1
　　    /* invariant: x[l] < t && x[l+i] >= t && i = 2^j */
　　    nexti = i / 2
　　    if x[l+nexti] < t
　　        l = l + nexti
　　        i = nexti
　　    else
　　        i = nexti
　　/* assert i == 1 && x[l] < t && x[l+i] >= t */
　　p = l+1
　　if p > 1000 || x[p] != t
　　    p = -1

　　这段代码通常要比前一个程序慢一些，但它为将来的加速打开了方便之门。
　　改进3是对改进2的简化：

　　i = 512
　　l = -1
　　if x[511] < t
　　    l = 1000 - 512
　　while i != 1
　　    /* invariant: x[l] < t &&x[l+i] >= t && i = 2^j*/
　　    i = i / 2
　　    if x[l+i] < t
　　        l = l + i
　　/* assert i == 1 && x[l] < t && x[l+i] >= t*/
　　p = l + i
　　if p > 1000 || x[p] != t
　　    p = -1

　　改进4直接进行循环展开，消除了循环控制和i/2的开销。

　　l = -1
　　if (x[511] < t) l = 1000 - 512
　　    /* assert x[l] < t && x[l+512] >= t */
　　if (x[l+256] < t) l += 256
　　    /* assert x[l] < t && x[l+256] >= t */
　　if (x[l+128] < t) l += 128
　　if (x[l+64] < t) l += 64
　　if (x[l+32] < t) l += 32
　　if (x[l+16] < t) l += 16
　　if (x[l+8] < t) l += 8
　　if (x[l+4] < t) l += 4
　　if (x[l+2] < t) l += 2
　　if (x[l+1] < t) l += 1
　　    /* assert x[l] < t && x[l+1] >= t */
　　p = l + 1
　　if p > 1000 || x[p] != t
　　    p = -1

• 原理总结

　　代码调优的最重要原理就是尽量少用它。
　　效率的角色。 Don Knuth观察发现，不成熟的优化是大量编程灾难的根源，它会危及程序的正确性、功能性以及可维护性。当可能的危害影响较大时，请考虑适当将效率放一放。
　　度量工具。 第一步是对系统进行性能监视以确定代码的关键部分，对其他部分而言，应当遵循“没有坏的话就不要修”的格言。
　　设计层面。 效率问题可以由多种方法来解决，只有在确信没有更好的解决方案时才考虑进行代码调优。
　　双刃剑。 使用if语句替换模运算有时候可以使速度加倍，有时候却对运行时间没什么影响。将函数转换为宏可以使某个函数速度加倍，却也可能使另一个函数的速度减慢为原来的万分之一。用具有代表性的输入来度量程序的效果是至关重要的。

　　下面是本章中体现到的调优法则。
　　第一部分所举高速缓存的示例体现了高效处理常见情况。
　　问题1——整数取模。利用等价的代数表达式，使用低开销的比较取代了高开销的取模运算。
　　问题2——函数、宏和内联代码。打破函数层次。
　　问题3——顺序搜索。使用哨兵来合并测试条件，展开循环。
　　问题4——计算球面距离。修改数据结构，利用等价的代数表达式。
　　二分搜索。合并测试条件，利用等价的代数表达式，展开循环。

　　（习题12）人们在调优程序时有时会从数学的角度考虑而不是从代码的角度考虑。为计算下面的多项式：

y=anxn+an-1xn-1+...a1x1+a0

　　如下代码使用了2n次乘法，请写一个更快的。

　　y = a[0]
　　xi = 1
　　for i = [1, n]
　　    xi = x * xi
　　    y = y + a[i] * xi

　　一种n次乘法的方法：

　　y = a[n]
　　for (i = n-1; i >= 0; i--)
　　    y = x * y + a[i]