关于程序优化的八卦

本文出自：
(把八卦和文章重新分了一下类,准备围绕自己的心得写个编程珠玑番外篇,这个算第三篇吧)
代码大全(CodeComplete)是一本很好的书.我建议像我这样写的程序总行数不超过50万的程序员应该买一本放在案头(当然代码大全不如SoftwareTools这本书好,这个我以后有机会写文章细谈)如果你天天编程序,我建议你买一本.如果你已经有了代码大全,我诚心建议你赶快翻开此书,撕去第26章.因为代码大全的其他章节可以让你成为优秀的程序员,唯独第26章,读了之后立即从优秀程序员变成最差的程序员.
为啥?因为第26章讲的,都是怎么调节代码使得代码跑得更加快的技巧,而这些技巧,几乎都是让一个好程序变成差程序的技巧,是教你不管三七二十一先对程序局部优化的技巧.而局部优化是让程序变得糟糕的最主要的一个原因.用高爷爷的话说,提前优化是万恶之源(Prematureoptimizationistherootofallevil).这些技巧,就是带你去万恶之源的捷径.
代码优化究竟是什么洪水猛兽,又究竟有多少伟大的程序员因为代码优化声名扫地,请看本期关于代码优化的八卦.
话说当年在贝尔实验室.一群工程师围着一个巨慢无比的小型机发呆.为啥呢,因为他们觉得这个机器太慢了.什么超频,液氮等技术都用了,这个小型机还是比不上实验室新买的一台桌上计算机.这些家伙很不爽,于是准备去优化这个机器上的操作系统.他们也不管三七二十一,就去看究竟那个进程占用CPU时间最长,然后就集中优化这个进程.他们希望这样把每个程序都优化到特别高效,机器就相对快了.于是,他们终于捕捉到一个平时居然占50%CPU的进程,而且这个进程只有大约20K的代码.他们高兴死了,立即挽起袖子敲键盘,愣是把一个20K的C语言变成了快5倍的汇编.这时候他们把此进程放到机器上这么一实验,发现居然整体效率没变化.百思不得其解的情况下他们去请教其他牛人.那个牛人就说了一句话:你们优化的进程,叫做SystemIdle.
所以说.优化这东西,一定要有一个全局的思路,否则就是纯粹的无用功,有时候还是负功.在编程珠玑II第一章,JonBentley就着重提醒了代码profiling的重要性.说到profiling这个词,就不能不再次提到万众敬仰的高爷爷.高爷爷在1970年的暑假,通过捡Stanford大学机房扔出来的垃圾(其实是含有程序的磁带),写出了一篇震古烁今的论文AnempiricalstudyofFORTRANprograms(FORTRAN程序的实证分析).除了抱怨写程序的人不看他的TAoCP之外(因为一个程序用了被高爷爷定性为史上最差的随机数发生器算法,有兴趣的可阅读TAoCPvol2),这篇论文主要说了三个划时代的东西:
1.对程序进行profile是每个编程系统的居家旅行必备.
2.在没IO操作的情况下,一个程序中4%的代码占用了超过50%的运行时间.
3.97%的情况下对程序进行提前优化是万恶之源.
这三个道理,用大白话说,就是:1程序都存在热点,有优化的空间.2.但是97%的情况下程序员优化的都是错的地方,反而把程序优化糟了.3.想要做优化,第一步就要先知道程序在什么地方耗时间而不是靠猜.
说到热点,顺带拐八卦一下Java的速度.Java1.5的虚拟机的关键技术,就是叫做Hotspot(热点).传统上,大家都认为Java比C要慢.其实不然.Jython的作者JimHugunin就曾经说过,其实两者差别不大(http://hugunin.net/story_of_jython.html).也有一些其他的测评说,Java比C要快.原因就在于,Java虚拟机能够找到热点,对热点专门做优化.而C程序编译好了,即使有热点,也只能靠CPU去优化了.Java的优化比CPU要深且更全局.
言归正传.关于FORTRAN的profile的传统被继承了下来,基本上现在任何的过程式主流编程语言都支持profiling工具.关于profile怎么做的问题,等我有空了好好写文章介绍.(因为我发现,除了编程珠玑,没有一本书提到过).
做程序优化的八卦就太多了,说一个BeautifulCode上的吧.话说世界上做线性代数的库叫做BLAS,基本上是工业标准.因为线性代数运算太重要了,所以各大处理器厂商都有BLAS的实现.Intel的叫MKL,AMD的叫ACML.矩阵乘法实现的好坏,直接决定了处理器的性能测试的分数(因为现代测处理器的速度的程序,比如LAPACK指数,基本上都是用BLAS里的矩阵乘法做基准).去年nVIDIA高调宣传自己的CUDA系统比CPU厂商快10倍到100倍,借此打开了GPU计算的大门(令人发指的达到500GFlops,Intel最新的只有50GFlops).其中CUDA可以理解为是BLAS在nVIDIA平台上的实现.自从nVidia推出CUDA以后,俨然不把intel这些厂商放在眼里,心想,小样,你们还是做通用处理器吧,浮点乘法这些高级的东西,还是放在显卡上比较好.nVidia和IBM/SONY的阴谋很不小呢.要是浮点计算比Intel快这么一两个数量级,以后世界上前五百名超级计算机就全部变成什么用光纤网连起来的PS3机群,nVidia显卡机群之类的.人家外行见了计算机科学家肯定要问:你们搞高性能计算机究竟是搞计算还是打网络游戏啊??
还是言归正传(我怎么老走题?),简要的说一下BLAS优化.单处理器上对BLAS的优化主要体现在对cache的高效使用.矩阵乘法中,如果矩阵都是按照行存储,则在A*B中,对B的访问是按列的.假设B一行有N个元素,那么在存储器中,两个同列不同行的元素所在的存储单元相差N.因此,对B的访问并不是局部化的.因为访问不局部化,所以每次乘法,都需要从内存中调一个cache单元到CPU.这个极大的降低了处理器的执行速度.因此,矩阵乘法的优化的核心,在于局部化B的访问.反过来,如果矩阵按照列存储,则要局部化对A的访问.关于怎样局部化访问还能获得正确的乘法,BeautifulCode一书的第14章有非常好的讲解,我就不废话了.总之,矩阵乘法局部化的好坏,取决于一个机器的cache的大小.
多处理器和向量处理器就又不一样了.要想利用好,就要把计算任务平均的独立的分到不同的处理器上.所以,在这里,优化就变成了分解成若干的小问题.因此,分治算法成了主流.具体矩阵乘法怎么分块,大学数学都讲了,我就不废话了.事实上,之所以nVidia能和Intel干,就是因为显卡上令人发指的有64个计算核心,而Intel最牛X的才4个.那为啥Intel自己不多做几个核心呢?因为Intel自己把自己带沟里去了Intel处理器太复杂支持的功能太多了,一块硅片上根本放不下很多核心.而nVidia一直就是专用处理器,每个核心功能简单,可以做到很小.