0898-08980898 13876453617
0898-08980898 13876453617
原著：Optimization of Computer Programs in C
一个知识工作者的一生的大部分时间都花在等待计算机持续产生结果上。用户和组织通过购买更快的计算机，添加内存，使用更快的网络来控制他们的等待时间。应用程序开发者有责任去设计他们的程序，以便更好的利用他们手里有限而昂贵的资源。
本文论述了一些优化(提升速度)c计算机编程语言的技术。主要聚焦在最小化CPU运行程序所耗费时间，并附有一些简单的可以获得性能提升的示例代码。内存和I/O速度优化亦进行了讨论。
一般选择的有效的性能优化技术是，使用分析器去标识性能额瓶颈。通常猜测程序的哪部分消耗了最多的资源是很困难的，如果你将优化的努力建立在投机而不是真实数据上，你将可能在提高已经运行的很快的代码速度上浪费了很多时间，而忽略了主要问题代码之所在。
一旦你定位了一个瓶颈所在，比如一个执行了上千次的循环，最好的办法就是重新设计程序。这比将该循环运行速度提高百分之十更有效，而后者往往由编译器的优化就可做到。优化仅仅是浪费时间，如果符合下面的论述：
当然也要把程序的应用场景考虑在内。如果是一个一天运行一次的报告生成程序，使用者可能在去吃午饭之前打开它，事实上确保他回来之前运行完毫无意义。如果它被一个比你的程序更慢的程序调用，用户也毫无感觉。但如果它是跟踪GUI的鼠标事件代码，用户将对可感知的延迟进行产生抱怨。
给出那些优化是合理的，编译在全优化模式并且在真实的输入数据上运行你的程序。如果你不能访问到真实的输入数据，仔细选择你的测试输入数据：程序员趋向于使用一个小的输入数据集合，而在程序用户手里可能会遇见五花八门的各种情况。
使用time命令查看程序是cpu密集，内存密集，还是IO密集，或者兼而有之。即使你的代码“看上去”运行花费了好长时间，它可能仅仅只有几秒钟。在你的计算机上可能有比你认知的更多的time命令：有时可能是内建到shell中，并且含有很多选项。你也可以使用getusage()来获得性能信息，也可以从性能分析工具获得，比如gprog,prof,和tcov。
使能分析器和只要和它兼容的任何优化选项，重新编译你的代码。使用真实数据运行你的程序，生成剖析报告。绘出哪个函数消耗了最多的CPU时间，然后仔细将它检查一遍。一次改变一处重复直到没有明显的瓶颈或者程序可以高效运行为止。
前四个是非常重要的，其余的没有特别的顺序。
思考代码真正是如何工作的。熟悉文献的内容，学习使用最合适的算法，即使它不是你提出的。熟悉大多数计算机科学使用的O(n)记法。
一些明显的替代方案:
| 慢的算法 | 替代方案 |
|---|---|
| 顺序搜索 | 二叉搜索 或者 哈希查找 |
| 插入 或者 冒泡排序 | 快排 归并 或者 基数排序 |
选择合适的数据结构，如果你将会执行大量的随机插入和删除，那么链表是比较好的选择，如果你将会执行一些二叉搜索，那么数组较为妥当。
任何对人类简洁可读的代码，对编译器也简洁可读。复杂的表达不仅难以优化，而且容易引起编译器优化热情退却。我曾经见到一个编译器拥有翻译单元限制，当一级超限时将会引起所有的模块反优化；
可以使得代码简洁的手段：比如使得函数内部代码更加精壮。现代机器的函数调用开销通常都很小，因此优化不是编写一个十页函数的有效借口；
如果你编写清晰，轻便的代码，你可以快速部署到最新最快的机器上，并其提供给对速度感兴趣的客户。
学会对某个操作需要的时长进行权衡。其中最慢的是打开文件，读写大量数据，开启新线程，查找，排序，数组的整体操作，拷贝大量的数据等。最快的操作一般是编程语言基础元素比如，变量赋值，解引用指针，整数加法等。这些操作没有一个会耗费大量的时间，但是计算机允许代码段重复执行。如果你执行了最快的操作一千万次，它也将花去可观的时间。在真实的程序中，很多事情发生很多次，拥有常识将助你理解你的分析器的输出。
一个容易误解的片段：
此处的目的是通过如果它也将为0则不进行初始化来节约时间。实际上，检测它是否为0，将会和将它赋值为0所花费的时相差无几
x=0有相同的效果，甚至可能更快。
对于一个勇敢的黑客，检查编译器产生的汇编级别的输出，计算指令数目，是必由之路。如果你这么做了，别忘记在你的记录中包含等待状态。同时也留意一些优化和指令集调度推迟到链接阶段，将不会在汇编器作为独立的模块输出。
我有一个小的，非常轻便的代码speed.c，可以打印出非优化的基础C操作符和库的速度。它不是一个基准程序(测量未经加权和平均)，但它能给新手一个关于C许多方面耗时计算的数字化的感知。
大多数编译器拥有多个优化级别，确保你使用了最高级别的优化。gcc拥有极好的优化级别和选项。一些编译器拥有特殊的关键字如#pragmas，inline，也会影响优化。
高级优化会使得书写不良的代码失灵。很少有优化器损坏完全正确的代码。副作用和估计顺序可能将事情搞砸，所以你可能需要在使用最高级别优化前，修正些许代码。信号处理在不合时宜的时候激活可能会妨碍一个优化过的程序，而对不经优化的程序没有影响。
使用gcc的 -finline-functions 选项， 其他一些编译器拥有在高级别优化时将小函数自动进行内联的功能。K&R C 编译器不会进行内联，或者只对汇编级别的库函数进行内联，比如数学库。C++编译器通常普遍都支持内联。
如果需要，C函数可以重构为宏，以便在没有内联的编译器上获得小幅度的速度提升。这可以在代码完全debug后进行。我看到的大多数debugger没有能力对宏扩展进行显示和跟踪。
通过宏内联的示例:
老代码:
新代码:
额外的括号是需要的，以保障如果foo用于优先级高于*的表达式，或者a和/或b包含优先级低于+或 - 的子表达式情况下的逻辑正确性。逗号表达式和do{…}while(0) 可以用作更复杂一点的函数操作，但存在一些限制：do-while 宏可以让你在宏中使用局部变量，但你无法返回一个值，而使用逗号表达式时的情况刚好相反。
一些警告:
大多数编译器(e.g. gcc -funroll-loops)将会这么做。但是如果你知道你的编译器不行，那么你可以小改一下代码以达到相同的效果。
原代码:
新代码:
测试i<100，以及返回分支顶端循环了11次，而不是100次。循环展开在循环执行固定的非质数次数并且迭代变量只在一个地方改变(在它初始化位置的旁边)时工作的更好。如果do_stuff() 没有使用i, 所有小的i++的可以被i+10替换。重排该for循环，为do-while 循环，可以使循环次数降为10。如果循环只有５次而不是１００次，那么你完全可以展开，以完全消除分支和测试开销。
为了某些结果的收敛计算，编译器经常拒绝展开，理由是展开将会改变结果。如果应用对额外的精度不敏感，你可以进行排列，以通过加倍循环迭代器，更少地测试收敛。
一个展开的循环，比一个未展开的版本要大，所以可能不再适合适配到拥有指令cache的机器, 这会使得展开版本稍慢。 在这个示例中，调用do_stuff()使得循环开销相形见绌，所以这种情况下任何从循环展开获得的好处，在和内联相比较都是没有意义的。
如果你碰巧和使用一个矢量化编译器，循环展开可能会和矢量优化冲突。
主要思想是，合并相同变量在相同范围内的相邻的循环。假设第二循环前向索引为空(array[i+3])，你可以这样做：
原代码:
新代码:
现在，递增和测试i的工作只有平常的一半。在某些情况下，局部化引用是很好的做法，提高了cache的效率。
一些机器拥有递减和与０比较的特殊指令，假设循环对方向不敏感：
原代码:
新代码:
然而我们需要警惕下文提到的前向预测cache。如果你打算用指针运算这么做。ANSI C有一个特殊规则，允许您将索引设置为超出数组末尾的一个元素，但对首元素却没有类似的规则 。
复杂运算简化就是使用可以产生相同效果的更简洁的运算代替复杂运算。很多编译器可以自动完成该转换，典型示例如下：
原代码:
新代码:
同时注意，C的数组索引主要是乘法，加法。乘法部分可以在某些情况下归属到复杂运算简化，尤其是在循环遍历一个数组的时候。
任何不依赖循环变量的运算部分，不受边沿效应影响的，都可以从循环中完全移出。大部分编译器对此支持的很好。保持循环内部的运算简洁，将恒定运算移除循环内部，有很多情况你将知道有些值不会变，但编译器在边沿效应的影响下，可能不会将它进行优化。这里的运算不仅仅指的是算法，数组索引，指针解引用，调用纯函数，等都是可能移出循环的可选对象。
在调用其他函数的循环中，你或许可以通过剥离部分子路径，指出哪部分是循环不变的，并在循环开始之前调用它。这或许不是很容易，并且可能没有很大提升，除非你调用的子路径重复open和close文件，或malloc和free大块内存，或者其他可能比较猛的操作。
一种通用的但并不总是最优的示例是在一段连续的语句中重复使用一个表达式。这可能和循环没有一点关系，如果有用的话你可以尝试这种替代：
原代码:
新代码:
老的Ｃ编译器允许在一定程度上重组算法表达式。ANSI 成文了算法表达式按照它们的组成方式进行计算，以避免不想要的情况发生。比如：
将不会被视为拥有相同的子表达式b/c, 如果你重写第二个表达式：
ANSI C编译器将自如地将b/c只计算一次。注意新代码使用浮点运算时可能会在溢出或得到稍微不同的结果方面表现出和未重写语句不同的行为。
在一段处理多种可选择情况的代码中，将测试和最多出现的情况的代码放在开始位置。通常这会表现为一个很长列的if-else互斥操作，但只有其中一个会被执行。通过将最有可能的一个置于首位，我们的执行流在经过该段代码时只需执行较少的if判断。
但是如果if的条件仅仅是一些简单判断比如x == 3, 考虑使用switch语句。一些编译器在翻译switch语句时颇为复杂。
首先让我们定义尾递归消除。当一个可递归函数调用它自己时，在某些条件下，编译器会使用汇编级等价的goto返回函数首部。这省去了栈增长，存储，寄存器恢复，以及其他函数调用开销。对于非常短小的递归调用非常多次的递归函数，递归消除可获得实质的速度提升。使用恰当的设计，递归消除可以获取一个递归调用，并把它转化为不论何种机器上的最快形式的循环。
尾递归消除已经存在了很长时间。他起源于功能化的语言诸如LISP等存在大量的递归操作，在该类语言中尾递归消除是很有必要的。C/C++以及类pascal语言属于命令式语言类别，并且极其高效，是否递归，可以不管尾递归消除带来的好处而直接进行编写编译，依然可以产生与类似的LISP语言同等水平甚至更高水平的性能。尾递归消除并不是在现代的每一个优化器上都支持的，尽管有很多已经支持了。
回到之前我提到的条件，为了使尾递归消除作为一种安全的优化手段，函数必须返回递归调用的值，而没有进一步的运算。举例来说:
上述代码可以对最终返回语句使用尾递归消除，因为从该isemptystr 调用返回的值正好是n+1次调用的值，而不存在进一步的运算。
再例:
上述代码不能使用尾递归消除，因为返回值没有被直接使用：调用完成后的返回值被乘以num，因此调用状态必须维护直到返回。即使支持尾递归消除的编译器也不能在此使用它；
一个允许尾递归消除的示例：
根据我的经验，命令式语言的优化器不会费心去完成这种方式的重写。我曾在Scheme 编译器中见到过这种重写优化。以此种写法编码的程序员应当用钝的头屑去除物暴打头和肩膀；
即使你的编译器实现了尾递归消除优化，你也不能假设他已经自动给你做了。你应当在应用尾递归消除之前重写即使非常简单的递归函数。如果这么做降低了代码可读性，那么该努力将是值得质疑的。
一大部分递归算法拥有简单的迭代副本。C语言编译器非常擅长于优化循环，可以在没有有时尾递归消除需要的繁重的条件的情况下做到优化。因此如果你必须在源码级别做到优化，在重写支持尾递归消除之前考虑使用普通的迭代。
最后，如果递归函数包含循环，或者大量的代码逻辑，尾递归消除能起到的优化作用就相对很微小了。因为尾递归消除只是优化递归，而不是算法本身的任何逻辑。函数调用是非常迅速的，优化已经非常快的东西是不值得的。
考虑使用查找表，尤其是在一个运算是迭代或递归的时候。e.g.收敛级数或者阶乘。（耗费常数级别时间的计算，能够经常比从内存中检索进行再计算更快，所以不要总是想着从查找表获得好处）
原代码：
新代码:
如果表太大，你可以在程序启动时使用一些初始化代码计算好所有的查找值，I或者由第二个程序来生成表，并打印成适合在源码中#include 的形式。在某些时候，表的大小会对分页调度空间产生显著影响。你应当让表包含前N个可能的情况，然后将他作为参数传递给一个函数来计算其他的项。只要需要的值是一个位于表中的有意义的数，我们都将获益；这是典型的空间换时间。
对于几乎所有的情况，库函数qsort都是足够快的，也就没必要自定义排序算法。将你的优化努力聚焦于比较函数。一般后面讨论的strcmp优化是比较有用的。
考虑提前格式处理输入数据，来加速比较历程：
如果你在排序结构体数组或者其他大的对象，将他们按指针分类，省去大对象的拷贝时间。
评估插入与查找的比率：
如果你自己写排序函数，为特定的序列写特定的排序过程和特定的比较方法。合并所有步骤到排序函数中，本质上内联比较方法和交换代码。
对于qsort完成后定制化的排序范式，你可以进行特殊的拷贝，前提是假设数据被用非常方便的机器大小交换，比如short，long，double。当对象宽度和机器基本类型大小匹配时，你可以进行直接交换而不用调用memcpy。
确保去掉断言和其他调试信息。
在快速循环中避免引用全局或者静态变量。不要使用volatile修饰符，除非你真正知晓他。大多数编译器把他理解为简单的寄存器对立面，将有意的不优化调用包含volatile的表达式。
避免传递你的变量的地址到其他函数。优化器必须假设被调函数有能力存放指向该变量的指针，并且该变量可能因为边沿效应而在一个完全不相关的函数中被改变。在并不强烈的优化级别中，优化器可能甚至会假设信号处理函数可能会在任何时候改变该变量。这些情况都与放置一个变量到寄存器相互抵触，对优化而言是最重要的。举例：
因为d将他的地址传递到另外一个函数，编译器将不再允许他在跨函数调用时留在寄存器中。然而依然可以让该变量留在寄存器中，关键字register可以用来追踪类似的问题。如果d被声明为寄存器变量，编译器将不得不警告他的地址被使用了。
尽管函数和模块化都是非常不错的东西，在一个频繁执行的循环中使用函数调用有可能会造成瓶颈。这个问题有几个方面，一些是上面已经略微提及的，除了执行另一个函数的指令调度开销：
线性化的代码，即使有一两个额外的语句，也要比充满if，&&，switch，goto的代码快。流水线式处理器更喜欢一波稳定的顺序式指令，而不是一波分支指令，哪怕分支可能跳过一些不需要的代码段落。
大多数str*, mem*系列的C库函数，操作字符串的时间和其长度成正比。所以很容易在循环调用中引起可观的瓶颈问题。有以下几个办法可以缓解这种情况：
strlen
避免在涉及字符串本身的循环中调用strlen()，即使你在修改字符串，你也应该重写他，其结果是，将x = strlen() 放在循环之前，在你增删一个字符时进行x++或者x–运算；
strcat
当在内存中使用strcat构建一个大字符串时，他将在每次调用时都会扫描该字符串的长度。如果你已经跟踪了该字符串的长度（比如用上面的strlen方法），你可以直接索引到字符串末尾，再strcpy或memcpy即可；
strcmp
你可以通过在调用之前，检查字符串的第一个字符来节省些许时间。显然，如果第一个字符不一样，就不必调用strcmp继续了，由于自然语言字母的非均匀分布，大写字母数据获得的时间收益不是26:1而更趋近与15:1；
但必须注意：
一种彻底不同的加速strcmp的方式是将你的所有字符串按顺序放到一个单一的数组中，如此你只需比较指针而不是字符串。如果所有的strcmp都是为了从一个大的已知的搜索一个值，并且你期望做更多的这种搜索，那么你应该搞一个哈希表玩玩。
strlen(s) == 0
检查空串是很常见的操作，即使是有经验的程序设计师也可能使用strlen来达到这个目的。但是如果你操作的字符串是非常可观的，strlen将会忠实地检查每个字符，直到遇见NUL结束符。使用*s=’\0’代替，可以节约函数调用开销，并且只需检查第一个字符；
strcpy(s, “”)
*s = ‘\0’ 就可以了，并且节省一次函数调用开销；
strncpy(s, t, n)
留意strncpy填充不足的字符为0，除了第一个用作结束字符串，其余的永远不会使用，所以有时候尽管不是很多，仍然是一种浪费。
memcpy/memmove
一般来说 memcpy 比 memmove 更快，因为他假定两个参数存在重叠。如果你试图用自己实现的版本代替他们，确保你自己的比其更快。
在一些真实奇怪场景中（带FPU的早期RISC芯片，包括很多基于SPARC的机器），你可以通过将整型数据乘除模块化到浮点操作。这总共需要共两件事：FPU帮助主CPU降低负荷，这样CPU可腾出手干一些其他的事情，但是大多是RISC机器以软件形式模拟整型乘除，不管怎样FPU的确能够加快整型乘除运算。但这不是绝对的，你应该在你即将运行的机器上对这两者都进行尝试。在整型和浮点型之间来回转换将会占据一个可观的时间，我听说这个问题在Apollos上尤为突出。
在很多机器上，float比double运行要快。如果瓶颈涉及到浮点运算，并且你不需要额外的精度，改变相关的变量到float类型，并查看运行结果，但与前面相似，如果任意使用float与double之间的转换，很可能会得不偿失。值得注意的是，在K&R 编译器以及，ANSI 编译器上使用 w/o原型， 在函数调用和很多表达式中，存在float到double的自动转化。
gcc比其他操作系统的编译器能产生更快些的代码。试着在你可以支配的所有编译器上编译你的代码，使用最快的一个编译包含瓶颈的一两个函数。其余的使用可以给出很多有用错误信息的，产生最可信输出的编译器，这在C++上尤为困难，因为不同的编译器使用不兼容的名字编码方案。
编译器一直在进步，最好是紧跟最新版。
一个典型的引起栈相关的问题是，使用大数组作为局部变量。在这种情况下，解决方案正式重写代码，使其使用static变量或global变量，或者从heap上申请。这对于拥有大的struct或其他参数的情况同样适用。在小栈机器上，栈临界程序不仅仅是运行速度缓慢，也可能在栈溢出时完全停止。
递归函数，即便是由很少的局部变量和参数，任然会影响性能。在一些古老的机器上，函数调用具有可观的开销，将递归函数重构为迭代可以节省一些时间。
一个有关的问题是最后调用优化（ last-call optimization）. 很多LISP 和 Scheme 编译器自动做这些事情。但是，很少有C编译器支持该功能。举例:
因为func1()最后的语句是调用func2()，在这一点以后，func1()就不需要他的变量了，可以移除他的栈帧。当func2()完成后，直接返回func1()的调用者。这不仅降低了最大栈深度，而且节约了一些从子路径返回代码执行开支，因为他只需执行一次，而不是两次，或多次(取决于函数结果传递的深度)。
如果func1() 和func2() 是同一函数的递归调用，编译器还可以做一些其他事情：栈可以被留下，函数调用由回到函数顶部的goto语句代替，这就是前面的尾递归消除。
估算值广泛变化，但是一个有能力的人类写的汇编级别的代码，能够比全优化编译器从良好的高级语言源码产生的汇编代码快10%。当然这不是一个可移植方案。RISC汇编尤其很难手写。
专家们采取的方案各有不同。一些建议从头开始编写自己函数的汇编版本，希望你能找到一种新奇的计算结果的方式，另一些则建议使用编译器产生的汇编代码作为初版然后在其基础上进行调优。
动态链接共享库的确是很棒的东西，尽管很多情况下，调用动态链接库函数，要比调用静态链接库函数慢一些. 主要的额外时间开支是一个以前的古老的问题，第一次调用动态链接库函数时，会伴随一些搜索，但其后的调用开支也将是微乎其微的。
对于包含数以千计函数的应用，启动时将会有一个可观的延迟，静态链接可以降低这种延迟，但也在一定程度上失去共享库带来的代码共用的益处。一般的做法是，你也可以有选择的将一些库链接为静态，一些为动态。比如X11, C和数学库你应该动态链接(因为其他进程也会使用该库，这样他就可以使用该库在内存中的拷贝)，但对于只与你自己应用相关的库应该静态链接之。
至于其他的机器相关的代码，你可以使用 #ifdef 来分开相应的特定机器相关的代码优化片段. 编译器不会预定义 RISC or SLOW_DISK_IO or HAS_VM or VECTORIZING，因此你应当亲自来将其编码在makefile文件或者头文件中。
当优化内存访问无论是虚拟内存或是cache，首要考虑的是局部化引用。这是程序在时间和空间上使用最近引用内存附近的就近地址的一种特性。优化虚拟内存和cache的主要区别在规模，虚拟内存页可以是大小从0.5kb到超过8kb的任何位置，并且将会花费数十毫秒的磁盘读取时间。cache块典型地从16bytes到256bytes范围内变动。并且读取时间保持在数十微秒量级。程序强制很多虚拟内存页或者cache行接二连三地加载被称为“颠簸”(“thrashing.”)。
你可以通过改变访问或者分配顺序，以及拆分数据结构为频繁使用和不频繁使用片段，一起分配频繁使用的数据等，来影响局部化引用。 (但不要傻傻地认为malloc在连续调用时总是返回相邻的内存块，你应当分配一块大大的缓冲区，自己确保相邻。但这也可能引起其他问题）。
搜索和排序算法在他们访问内存的模型上相差甚远。归并排序被认为是拥有最好的局部引用表现。搜索算法可能会考虑最近几步的搜索可能在同一页内存中发生，并且在这一点上选择不同的算法。
当步进通过多维数组时，确保先增加最右边的索引值。这对C程序员来说是很自然的，但对FORTRAN人员来说刚好相反。如果你发现你正在这样写C代码，你确实应该需要被再教育一会儿！
考虑拷贝指向字符串，数组，大的结构体的指针，而不是他们本身。只要你在修改字符串，数组或结构体之前做完，就都不会出问题。
ANSI C 现在需要结构体和其他一样进行传值调用，因此如果你有非常大的结构体，或者在中型结构体上进行了成千上万次函数调用，你应该考虑传递结构体指针，在改变被调用的函数之后，确保它没有扰乱结构体本身的内容。
如果你的一部分代码由于访问并行数组中的元素造成很大的内存使用量，你可以将他们整合到一个结构体数组中，以便于一个既定索引的数据在内存中保持连续。
如果你已经拥有了一个机构体数组，但发现程序的关键部分只是访问每个结构体中的很少的几个域，你可以将这些域切割成单独的数组，以避免不用的域不必要地读入到cache中。
在严格对齐的机器上，有时你可以通过安排结构体中小类型和域在一起，并以最严格对齐的类型开头。结尾可能任然存在填充，但是消除他们会破坏对齐带来的性能提升。
原代码:
新代码:
ANSI C 对内部结构体填充没做多少保证，但像这样的排列即使在最挑剔的RISC机器上，也会将性能损失降到最低。
典型的使用char或short类型的方式是用其来存储一个标志或模式。你可以通过牺牲可移植性，位域将这些标志组合到一个字节中。你可以使用移植性更好但比较麻烦的位掩码或者&操作符来提取其值。
一反常态，增加数据结构的对齐大小，来匹配cache行大小(或其整数倍)可以提高性能。其基本原理是，如果数据结构相对于高速缓存行大小是一个奇怪的大小，它可能会重叠两个高速缓存行，从而增加了从主内存中读取它所需的时间。
数据结构大小的增加可以通过在尾部添加哑域来解决，通常是一个字符数组。对齐经常难以控制，但通常可以使用如下手段:
理论上，你使用前向还是后向迭代一个数组是没什么区别的，但是一些cache是有预测性的，他将会在你需要前，尝试读取连续的cache行。因为这些cache必须工作地非常快，所以他们逻辑比较单一，无法进行逆向遍历内存页的预测。
一种通用的映射内存地址到cache行的方法是，剥去该地址的前导位。
假设直接映射1MB cache为128byte的cache行，并且程序使用16M的内存，所有的都在一个32bit地址宽度的机器上。最简单的将内存映射到cache的方法是屏蔽地址的首12bits和尾7bits。然后右移7bits，最终我们得到的是，映射任何两个在主内存中相距恰好是8192(2^13)字节的地址将被映射到同一cache行。如果程序碰巧使用8192字节大小的结构体构成的数组，在处理数组的过程中，引用每一个结构体中的元素，每次访问将会映射到相同的cache行，并强制重新装载，这将是一个可观的延迟。
这虽然看着是一个人为的情况，但任何是8192倍数大小的结构体都可以引起该问题。如果结构体大小减半， 问题严重性也降低一半，以此类推，但还是值得注意的。因为我们使用了仅一个cache行，任何在将来的对该数组的访问，都需要重新装载cache行，而不管我们假定的1MB容量。
对这种问题的解决方案是，将一个字段隔离到一个单独的数组中。假设该字段的宽度是4个字节，那么cache仅需每迭代遍历32次数组，重新装载一次(4*32 = 128bytes = 1cache 行的字节数)。这可能是，非常难得的情况：cache行能够按需提前预读，整个处理都全速运行。
malloc 和 free 有时有一些有趣的表现，并且在不同的机器上有完全不同实现。有些mallocs提供可以调整性能的方法 (比如mallopt)。
在一些应用中，malloc花费很少的时间，但free花费较多，一次如果你的程序使用了一堆内存，并且在其消亡之前不进行重用，程序可能运行的更快, 你在开头某处这样做:
#define free(x)
我强调这里存在通用性问题。长时间运行的使用一部分实质物理内存程序或守护进程应再他不需要时立即小心释放所有的相关资源。
首要原则是分配尽可能少资源的，这是一种老一套的手段，因为程序员避免使用malloc的麻烦，除非他们有更好的理由，但在栈上，受限于空间，毕竟能做事是比较有限的。如果你的数据是充满空洞的比如哈希表或者稀疏数组，这可能是你的优势，使用小表或者链表或者其他。
伙伴系统分配器 受制于大量的内部碎片，当你分配大小相近或略微大于2的平方的空间时，可能会比较糟糕，但这是比较罕见的。该分配器偏爱于将大小差不多的空间放到一起， 而不是按他们的事情顺序。这会影响局部化引用，有时是好的影响，有时则相反。
你可能拥有mallopt函数在你的Unix系列系统上。这可以使得你使用malloc相当快捷轻便地申请小内存块。
SunOS (以及一些其他的系统)拥有madvise() 和 vadvise() 系统调用。这可以为系统提供你将会使用哪种方法来访问内存的线索：随机，顺序，标记某些页不在使用等等。
在当前的计算机时代，内存，cache，硬盘，成本都在稳步下降。有些bug都不是事儿，不要动不动就重构代码，能用钱搞定的问题，就用钱搞定来赚更多钱。
但基本的常识还是要有的，对于大众市场软件来说，这不总是实用的。一方面是你不能告诉大家为了跑你的10美元的软件程序，需要花500美元来更新硬件。另一方面，增加交换缓冲区16M, 以1997年的物价来说，将会平均整体上花费4美元。
最好的方法是，你应当运行cache分析工具，来定位程序的哪一部分或者什么数据结构引起了cache问题。一些开发环境包含了类似的工具。一种好的方法是，根据对执行情况的分析，来推导问题可能位于哪个函数，尤其是涉及大数组和数据结构的地方。
I/O (in Unix) 经常将你的进程放入休眠状态。I/O请求可能是非常快的，但是可能另外的一些进程正在使用CPU，你的进程需要等待。因为等待时长存在任意性，取决于其他的进程在做什么，所以I/O密集型程序的优化是比较棘手的。
缓冲I/O一般(但不总是)比非缓冲的快。可以通过使用比正常大小更大的缓冲区来获得一些提升，尝试setvbuf()。如果你不用考虑可移植性，你可以尝试用大缓冲区，使用更低一层的控制方法read()，write()，来和fread()，fwrite()进行性能比较。在Unix机器上以一次一个单一字符模式使用read()和write()是非常慢的，这是因为存在频繁的系统调用开销。
如果可以的话，考虑使用比较省力的mmap。数据不用经过标准I/O，免去了一次缓冲区拷贝开销。依赖于复杂的分页硬件，数据甚至不用拷贝到用户空间，程序只需访问已经存在的拷贝。mmap()也提供预读，理论上，整个文件在你实际需要它之前，可以被先读入内存。最后，文件可以直接从磁盘分页映射到内存，而不用消耗虚拟内存。
如果可以的话，依然考虑使用mmap() 。如果程序中存在I/O密集和内存密集的权衡，考虑使用延迟free：当内存吃紧的时候，free未修改的记录，写出修改过的记录(可以写入临时文件)，随后再读入。如果你将记录写入用的磁盘空间用页空间代替，这将会省去很多不必要的麻烦。注：这句比较难理解，附上原文: Though if you take the disk space you’d use to write the records out and just add it to the paging space instead you’ll save yourself a lot of hassle.
你可以设定一个文件描述符为非阻塞 (see ioctl(2) or fcntl(2) man pages) 并且安排他在操作完I/O后向你的进程发出一个信号，期间你的进程可以做其他事情，包括发送I/O请求给其他设备。大规模并行将导致程序的复杂性。
多线程包可以提供帮助构建异步I/O程序。
如果你的程序向终端屏幕吐出很多数据，他在1200波特行的界面上将工作的很慢。等待界面赶上拖慢了你的程序运行。这并没有增加CPU或者磁盘时间，但对用户来说的确是变慢了。位图显示受制于相似的问题: xterms 关掉跳跃滚动有时会相当慢。
通常的解决办法是，用户清除掉不相干的数据。屏幕操作组件像curses可以通过降低无用的屏幕更新来提高速度。
套接字有一些奇怪的特性。比如发送短的，低频的消息非常慢。这是由于短的消息可能会被放到缓冲区一会儿，来等待其他缓冲区部分被填满。有些TCP套接字的选项可以避开这种特性，或者使用非流式套接字比如UDP。但一般来说限制还是在网络本身以及他的负载程度。
大多数情况下，发送越多数据消耗越多时间，然而，拥有交换机的局域网带宽可以达到理论值的上限。如果没有达到理论上限，你应当归咎于OS的IP层实现。考虑切换到另一个IP协议栈看看是否能有所提升。
在Unix 机器上，典型地存在两种套接字库BSD sockets, and TLI. 一个通常是根据另一个来实现的，可能会存在额外的内存拷贝，或其他开销。试试两者看看谁更快。
这个由Phong Vo and Dave Korn 写的用来替换标准IO，可以在这里找到（没找到）。通过稍微改变调用顺序达到了一些非常漂亮的优化和实质的提升。
以下是新手可能犯的错误：
程序设计人员趋向于高估他们写的程序的有用性，近似的最优值是：
运行个数 × 用户数量 × 节省的时间 × 用户薪资 - 优化时间 × 程序设计人员薪资
尽管 程序可能被数以n计的用户运行n次，多花一天时间节省40ms可能没什么卵用。
机器本身不是完全相同的。在一台机器上快，可能在另一台机器上相反。我不仅仅是指抽象的机器 like SPARC or MC68000, 也包括贴着序列号的实质的机器。额外的接口卡，不同的硬盘，用户日志，额外的内存，守护进程，以及任何其他可能的因素都会影响程序不同方面的运行速度，影响哪一部分程序可能是瓶颈，以及程序整体的运行速度。
一个特别的问题是，很多程序设计师都是超级用户，他们拥有配备内存，数学协处理器，大量磁盘空间的机器，然而用户可能只有最基本的配置的机器，用于浏览网页。程序设计人员对程序的性能存在偏见，可能不会优化占用用户 时间的代码，比如存在浮点运算或内存密集的子程序。
就像我一直提到的，很多优化可能已经被你的编译器搞定了。
不要养成依赖上述优化规则来写代码的习惯。只有当你发现某函数真正存在问题的时候，才用相关的手段来优化。一些规则如果广泛应用可能会使得代码更慢。几乎所有的对人类不清晰简洁的代码都会给将来的维护带来麻烦。确保对优化进行注释，否则后面的程序员可能简单假设这是不良代码而重写它。
花费一周优化程序，可能轻松花费数千美金。所以有时可以通过购买更快大的cpu更多的内存，更快的磁盘来解决问题。
新手经常假设在一行写很多语句，以及移除空行可以加速代码。这可能在某些解释性语言中有用，但对C而言有点用处都没有。
占主要时间比重的的一段代码，90% 的时间花费在了10%的代码上。
C库中一种设计合理的算法，以实现malloc/free。 Buddy system allocators在某种程度是依赖于块的大小，不只是分配顺序，来分配内存中的块。
在运行期间使用了与众不同的机器资源。严重依赖于CPU可以性的程序被称为compute bound. 这种程序通过安装更多内存，和更快的磁盘是无法加速的。
函数调用涉及改变栈指针寄存器，以及程序计数寄存器，传递参数，为结果分配空间等。这意味着，几乎所有的CPU状态都有被保存，并在函数调用完后进行恢复。CPU被设计成可以很快做这些事情，但额外的加速可以通过inlining来获得，或者将被调函数内嵌到主调函数中。被调函数使用主调函数的栈空间存储局部变量，并且在语法允许的情况下，直接引用参数而无需经过拷贝。
调用底层的操作系统函数，使用系统资源而不是CPU来读写数据。当等待资源就绪或请求完成时，CPU处于空闲状态，可能切换到其他进程。程序将大多数时间花在了等待I/O上，被称为I/O bound.
程序严重依赖于内存，无论是虚拟内存还是物理内存。这种程序将会有CPU等候时间，以等待数据cache更新，或者虚拟内存获得页。
程序复杂度的粗略度量。典型的写法是 O(f(N)) ，这里的 f(N) 是数学函数，定义了一个给定输入N，期望的程序运行时间上限。比如获得简单排序运行时间和被排序数据数量的平方成正比。这可以描述为 O(N^2). O-notation也可以用来描述空间复杂度。
提升程序执行速度的过程。取决于程序涉及的上下文环境，人类对于源码级别的优化，已经编译器在汇编级别的重排的努力。或者一些更低级别的因素。
一种CPU架构，执行的不同阶段在顺序上是交叉的，以便于一条指令正在执行，下一条指令正在获取，以前执行的结果正在写出。一些CPU有他们独特的pipeline阶段。
分析程序性能的一种程序。典型地，这种分析通过对程序计数器或栈进行内部采样。当被分析程序运行完毕后，profiler收集统计数据并且给出一个报告。合理使用profiler可能需要用特殊的操作重新编译被分析程序，并链接特殊的库。gprof and prof 是两个Unix程序广泛使用的profiler。
函数结果仅仅依赖于他的参数，没有边沿效应。
程序花费大部分时间在从栈上添加移除活动记录被称为stack bound. 很少有profilers可以直接测量这种问题。但可以从profiler给出的多数时间花在一个语句非常简单很方便统计时间的递归子程序上推导出来。
C中不常使用的一个关键字，其拥有实现定义的语义，但通常意思是指，一个变量不应该被放置到寄存器中，其可能受硬件或信号处理的边沿效应的影响。
如果一条指令对CPU而言过于复杂，结果可能不会立即得出，该延迟就被称为一个 wait state, 它由在结果得出之前经过的指令周期数来描述。流水线式CPU的编译器或者汇编器期望使用其他有用的指令填充wait state。
Copyright © 2012-2018 开丰娱乐-开丰注册登录绿色站 版权所有 琼ICP备xxxxxxxx号
电话：0898-08980898 手机：13876453617 地址：海南省海口市
在线咨询