程序优化中的测不准原理

September 2, 2008 – 3:50 pm

optimize在《The Art of Computer Programming》一书中有这样一句话:

Premature optimization is the root of all evil in programming.

相信大家肯定都已经耳熟能详了,也大都清楚我在“Ruby: 提升性能的几点尝试”中提到的优化程序应该走的基本步骤。虽然如此,这样的情况还是时常发生:花力气把代码大改一番之后发现性能并没有得到什么提升的时候,才开始悔恨自己没有先跑一遍 profiler 。可是如果只是机械地去重复“找出程序热点”、“优化热点”的步骤的话,实际上并没有掌握优化的真谛。

例如下面是我用 Valgrind 分析程序得到的一个结果报告:

valgrind.jpg

可以看到其中对 buf[i] 的调用消耗了相当多的时间,因为这被放在了一个大循环中。优化方法是把在循环外读取 buf[i] (这是一个重载的 operator [] 而不是普通的数组元素引用),将结果放在一个临时变量中,并在循环中直接使用这个临时变量的值。这样修改过后重新编译运行一下,发现性能果然提升不少!

可是,整个过程太顺利了,总让人有一种上当受骗的感觉,不是吗? :p 问题出在哪里呢?正是程序员的三大美德之首—— Laziness 被违背了。如果所有的优化问题都能通过这么机械的几个步骤来解决的话,何不写段代码来完成?事实上,这样的代码早已存在于编译器之中了。

对于上面的例子,只要打开编译器的优化选项就能自动优化掉,之所以在分析中出现这样的结果是因为 Valgrind 这样的分析程序需要精确地了解程序的结构,而它并不能保证在经过编译器的诡异地改写(亦即“优化”)之后程序会是什么样子。可是,实际运行的程序通常都是打开编译器优化选项、并去掉调试信息的,如果 profiler 不能分析真正的程序的话,那分析的结果便是毫无价值了。特别是在现在静态编译器优化越来越难,人们开始转向动态优化(JIT 技术)之后,最终运行着的程序简直就是乱七八糟。

这样的矛盾很像是测不准原理:一方面,为了了解程序的运行状况,人们希望程序尽量清晰(不是指从源代码的级别来说);另一方面,人们希望程序尽量优化,这又不可避免地让程序成为一个越来越接近“混沌”的东西。特别是当你需要做手工优化的时候,这两个需求就开始发生冲突了。类似的问题也出在程序调试上面。

不知道物理学家们是如何处理“测不准原理”似乎让人有些无奈的结论的呢?

  1. 21 Responses to “程序优化中的测不准原理”

  2. 我觉得,一个比较好的方法是在写程序的时候通过一些特殊的语句“告诉”编译器下面这段代码的特征,比如if语句有多大的可能会符合条件,或者一个while有多大的可能会继续循环。这样,编译器就可以“猜”下一步要干什么,更好地安排汇编代码或者进行寄存器数据依赖的优化。

    编译器再聪明也无法达到”最优化”,否则就是停机问题了。

    这样写出来的代码也许就会比较清晰而且也优化了吧。

    但这样程序员要考虑的东西就更多了。未来程序员写程序的方式或许会有些改变吧。。。

    By Chunhao on Sep 2, 2008

  3. @Chunhao,
    No, 我不同意你的观点,确实,现在在比较底层的代码例如 Linux Kernel 里面会有诸如 if (likely(blabla)) 这样的代码来指导编译器来安排生成的代码,但是这只是现在这种无奈状况的一种 work around ,而不是我们要努力达到的最终目标。

    抛开最优化不谈,JIT 的技术正是用于解决这类编译器无法“静态地”根据代码猜测出来的问题。例如一个 if 语句在执行了很多遍之后, JIT compiler 就可以根据执行情况来做统计,判断这个语句更可能是 taken 还是 not taken 并动态编译相应的优化代码。JIT 编译器能获得比静态编译器更加丰富的信息,我觉得,这才是杀手锏和编译器未来的方向。

    By pluskid on Sep 2, 2008

  4. 像你说的这样用JIT compiler根据执行情况来做统计,是不是一种太依赖技术太懒惰的表现 :) ,尽管程序员需要有这样的精神。

    然而程序员对代码的了解通常是会大于编译器对代码的了解的,我们这么做只是在极其复杂(汇编编程)和极其简单(不做优化)之间找到一种适度的平衡吧。

    为什么我们程序员总是以一种高高在上的姿态来命令编译器、硬件做这个做那个,而不愿给他们提供一些力所能及的帮助,哪怕只是多写一句话。有时这样做比设计出一个更复杂的编译器得到的好处大得多。

    By Chunhao on Sep 2, 2008

  5. “程序员对于程序更了解”只能说在一个更加全局的层面上才成立,比如,整个算法的重新设计之类的地方,而更加微观的层面的东西必然不如电脑了解,这也是为什么 premature optimization 是 evil 了:程序员总是以为自己很了解自己的代码,觉得这个地方很低效,但有时候其实只是无关紧要的一段代码而已。

    By pluskid on Sep 2, 2008

  6. 我觉得真正的优化都应该交给编译器~~
    程序中补来补去的总是不和谐~

    记得有一篇文章说JAVA String合并的,本来是使用s1+s2+s3这样的简单写法,但是效率不很高,后来又使用了.append函数,甚至是预先计算好字符串长度,分配好内存,然后直接填进去的写法,效率在低级版本中的JAVA编译器中有所提高。但是在新版本的编译器里面,反而s1+s2+s3这种简单的写法最好~

    所以我喜欢Beautiful Code :p 除非忍无可忍的情况…

    By quark on Sep 2, 2008

  7. 刚刚开始学习AI的时候,觉得很不爽。为什么造个机器人还要弄个Turing Test.他本来就是个机器人啊,为什么要做的和人一模一样呢。就像Wright Brothers,如果他们和后人也是一定要做一个和鸟一样的machine而不是后来去learn了aerodynamics,估计所谓的”artificial flight”又要晚很久出现了吧。
    但是其实,这就是一个learn的过程啊。
    在学习的时候,在造东西的时候永远不要compromise说,能飞就可以了,我能帮助这个编译器明确就好了。做的时候想如何达到完美。最后即使没有达到当初的目标,也许也能有别的突破。

    By boisde on Sep 2, 2008

  8. @quark,
    能让编译器优化的就尽量让他优化了。而且其实什么时候要 beautiful code ,什么时候要 optimized code ,是不能一概而论的。 :)

    By pluskid on Sep 2, 2008

  9. @boisde,
    恩,看着好累,旁征博引啊…… @_@

    不过,我觉得还是那句话:不能一概而论。其实很多时候学院派的理想化和“现实社会”里的东西还是有很多不一样。就我个人来说,我很喜欢那种“深度优先”的方式:在做什么东西的时候有新的问题或者主意,就一直 follow 下去,解决了之后再回溯回来。而在实际的软件工程中如果不分清优先级高低随意偏离项目主线的话,最后往往会死得很惨…… >_<

    By pluskid on Sep 2, 2008

  10. 项目主线。。。

    据说当年写程序最初人类的仿真方式就是所谓的introspection…和你这个”深度优先”好相似啊。。

    果然是学长啊。。求msn…

    By boisde on Sep 2, 2008

  11. 话说这些天总是听着听不懂的粤语和听不怎么懂的英文,搞得自己说话也很奇怪。。

    要保持不随大流果然是很困难的。

    By boisde on Sep 2, 2008

  12. @boisde,
    唉,我是真看不懂你说的什么……

    By pluskid on Sep 2, 2008

  13. 下回试试valgrind。。。gprof实在不会用。。。怎么测结果都不太对。。。

    By Mike on Sep 2, 2008

  14. 你用的这个valgrind前端是啥?好像很不错~

    By rhythm on Sep 8, 2008

  15. @rhythm,
    kcachegrind, 是用来查看 valgrind 生成的数据的。

    By pluskid on Sep 8, 2008

  16. 赞!很好用~~ 之前装过,但是没仔细看过怎么个用法 :-)

    By rhythm on Sep 8, 2008

  17. 很羡慕你这个博客+wiki的空间,你是到哪里申请这个空间的?谢谢啦。

    By netawater on Sep 10, 2008

  18. @netawater,
    呵呵,这个是在朋友的服务器上架的。

    By pluskid on Sep 10, 2008

  19. 那你是否了解有类似这个站点的公共空间服务提供商了,我想帮朋友建一个这么漂亮的主页,:)

    By netawater on Sep 10, 2008

  20. @netawater,
    不好意思,我不了解,你可以去问 Jack

    By pluskid on Sep 10, 2008

  21. 好的算法,才是王道。
    算法上没有余地了,再想这些方法。

    By hacker47 on Sep 25, 2008

  22. @hacker47,
    呵呵,那为何不是“这些方法没有余地了,再想算法”呢?

    By pluskid on Sep 25, 2008

Post a Comment