《编程珠玑》第9、10章学习笔记

第九章 代码调优

提高效率的高层次方法：问题定义、系统结构、算法设计、数据结构。本章讨论了低层次的方法：代码调优，首先要确定程序中开销较大的部分，然后进行少量修改，以提高其运行速度。

1、典型例子：关于一个复杂图像处理程序的调优。首先监视程序性能，发现程序的大部分运行时长花在对某一类型malloc分配空间上 ——>应用高速缓存原理解决问题：将常见类型的空闲记录缓存在一个链表中，因此可以直接快速访问链表来处理常见的请求而无需调用通用的分配程序——>时间缩短为45%，且减少了内存碎片。

2、调优技巧：

a:整数取模，利用等价的代数表达式，如下所示，使用低开销的比较取代高开销的取模运算。

原代码：k = ( j + rotdist )%n

替换代码：k = j + rotdist;

          if (k >= n)   

k -= n;

b:函数、宏和内联代码，通过使用宏替换函数来打破函数层次，可以使速度提高一倍，但进一步将代码改成内联形式却看不到明显改善。

C:顺序搜索：使用哨兵来合并测试条件可以获得大约5%的加速。循环展开则可以得到大约56%的额外加速。循环展开有助于避免管道阻塞、减少分支、增加指令级的并行性。

d:计算球面距离，修改数据结构（将笛卡尔坐标和经度、维度存储在一起），利用等价的代数表达式（使用开销较低的欧氏距离代替角度距离）。

3、极端例子：二分搜索

l = -1

if ( x[511] < t )   l = 1000-512

if ( x[l+256] < t )  l += 256

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

p = l + 1

if p > 1000 || x[p] !=t

p = -1

【展开了整个循环，消除了循环控制和i被2除的开销】

首先合并测试条件将每次内循环的数组比较次数从两次减少为一次；利用等价的代数表达式使得将上下限的表示方法转换为下限与增量表示法；循环展开将程序展开以消除所有的循环开销。

4、原理：代码调优的最重要的原则就是尽量少用它。

a: 效率的角色。不成熟的优化是大量编程灾害的根源。

b: 度量工具。性能工具进行监视找到程序中的关键位置，对于其他区域——没有坏就不要修

C:设计层面。

d:双刃剑。使用if语句替换模运算有时会对速度加倍，有时却对运行时间没有影响。将函数转换为宏可以使某个函数运行速度加倍，却也可能使另一个函数速度减慢。在进行改进后，用具有代表性的输入来度量程序的效果至关重要。

5、小结：进行代码调优的目的是减少CPU时间，同时也可以减少分页或者增加高速缓存命中率。除了减少运行时间之外，代码调优的另一目的或许就是减少程序所需要的空间了。

1、实例问题：在地理数据库中存储邻居的系统，使用稀疏矩阵实现：使用数组表示所有列，使用链表表示给定列中的活跃元素。具体优化过程如下：

问题描述：用最少的存储空间表示一个具有2000个活跃点的200X200的矩阵。

解决方法一：稀疏矩阵（使用数组表示所有的列，使用链来表示给定列中的活跃元素）

for （p = colhead[i]; p != NULL; p = p->next ）

     if p->row == j

          return p->pointnum

return -1

空间分析：该结构使用了具有200个指针以及2000条记录的数组，每条记录都具有一个整数和两个指针。空间模型800字节，每条记录12字节，共需要12X2000+800=24800字节。

若使用malloc，每条记录48字节，共计需要96.8KB。

解决方法二：201元的数组表示列，并且用两个2000元的并行数组表示这些点。

for k = (firstincol[i], firstincol[i+1])

if row[k] ==j

    return pointnum[k]

return -1

空间分析：(2000X2+201)X2=8402字节

解决方三：因为row数组的全部元素都小于200，可用单字节无符号char表示，

空间分析：2000X2+2000X1+201X2=6402字节

解决方案四：如果点本身已经存储了行信息，可以删除row数组

for k = (firstincol[i], firstincol[i+1])

if point [pointnum[k]].row == j

    return pointnum[k]

return -1

2、数据空间技术：

a:不存储，重新计算，只适用于需要“存储”的对象可以根据其描述重新计算得到的情况。

b:稀疏矩阵结构：引入关键字索引。

c:数据压缩：根据信息理论，对对象进行编码，减少存储空间。

d:分配策略：动态分配。

e:垃圾回收：共享空间技术。

3、代码空间技术：（程序本身规模所限）

a:函数定义：用函数替换代码中常见模式简化程序同时减少空间需求。

 b：解释程序：使编程和维护更简单，增加清晰度。“自底向上”。

 C:编译成机器语言：使用汇编语言进行手工编码。常用于数字信号处理。

小结：了解空间开销 ——> 找到空间热点 ——> 观察空间度量（性能监视器）——> 折中平衡性能和内存 ——> 预编译环境协作（内存分配策略，分页策略等） ——> 使用适合任务的正确工具。（我们已经学习过四中节省数据空间的技术：重新计算、稀疏结构、信息理论及分配策略和三中节省代码空间的技术:函数定义、解释程序以及翻译）和一条最重要的原则：简单性。因此在内存很重要时，要注意考虑所有可能的选项）