分类：
2010-11-25 19:43:28
(把八卦和文章重新分了一下类, 准备围绕自己的心得写个编程珠玑番外篇, 这个算第三篇吧)
<代码大全> (Code Complete) 是一本很好的书. 我建议像我这样写的程序总行数不超过50万的程序员应该买一本放在案头 (当然<代码大全> 不如
为啥? 因为第26章讲的, 都是怎么调节代码使得代码跑得更加快的技巧, 而这些技巧, 几乎都是让一个好程序变成差程序的技巧, 是教你不管三七二十一先对程序局部优化的技巧. 而局部优化是让程序变得糟糕的最主要的一个原因. 用高爷爷的话说, 提前优化是万恶之源 (Premature optimization is the root of all evil). 这些技巧, 就是带你去万恶之源的捷径.
代码优化究竟是什么洪水猛兽, 又究竟有多少伟大的程序员因为代码优化声名扫地, 请看本期关于代码优化的八卦.
话说当年在贝尔实验室. 一群工程师围着一个巨慢无比的小型机发呆. 为啥呢, 因为他们觉得这个机器太慢了. 什么超频, 液氮等技术都用了, 这个小型机还是比不上实验室新买的一台桌上计算机. 这些家伙很不爽, 于是准备去优化这个机器上的操作系统. 他们也不管三七二十一, 就去看究竟那个进程占用CPU时间最长, 然后就集中优化这个进程. 他们希望这样把每个程序都优化到特别高效, 机器就相对快了. 于是, 他们终于捕捉到一个平时居然占50% CPU 的进程, 而且这个进程只有大约20K的代码. 他们高兴死了, 立即挽起袖子敲键盘, 愣是把一个20K的C语言变成了快5倍的汇编. 这时候他们把此进程放到机器上这么一实验, 发现居然整体效率没变化. 百思不得其解的情况下他们去请教其他牛人. 那个牛人就说了一句话: 你们优化的进程, 叫做 System Idle.
所以说. 优化这东西, 一定要有一个全局的思路, 否则就是纯粹的无用功, 有时候还是负功. 在<编程珠玑 II> 第一章, Jon Bentley 就着重提醒了代码 profiling 的重要性. 说到 profiling 这个词, 就不能不再次提到万众敬仰的高爷爷. 高爷爷在1970年的暑假, 通过捡Stanford 大学机房扔出来的垃圾(其实是含有程序的磁带), 写出了一篇震古烁今的论文 “An empirical study of FORTRAN programs” (FORTRAN 程序的实证分析). 除了抱怨写程序的人不看他的 TAoCP 之外(因为一个程序用了被高爷爷定性为史上最差的随机数发生器算法, 有兴趣的可阅读 TAoCP vol2), 这篇论文主要说了三个划时代的东西:
1. 对程序进行 profile 是每个编程系统的居家旅行必备.
2. 在没 IO 操作的情况下, 一个程序中 4% 的代码占用了超过50% 的运行时间.
3. 97% 的情况下对程序进行提前优化是万恶之源.
这三个道理, 用大白话说, 就是: 1 程序都存在热点, 有优化的空间. 2. 但是97%的情况下程序员优化的都是错的地方, 反而把程序优化糟了. 3. 想要做优化, 第一步就要先知道程序在什么地方耗时间而不是靠猜.
说到热点, 顺带拐八卦一下Java的速度. Java 1.5 的虚拟机的关键技术, 就是叫做 Hotspot (热点). 传统上, 大家都认为 Java 比C 要慢. 其实不然. Jython 的作者 Jim Hugunin 就曾经说过, 其实两者差别不大 (). 也有一些其他的测评说, Java 比 C 要快. 原因就在于, Java 虚拟机能够找到热点, 对热点专门做优化. 而C程序编译好了, 即使有热点, 也只能靠CPU去优化了. Java 的优化比 CPU 要深且更全局.
言归正传. 关于 FORTRAN 的 profile 的传统被继承了下来, 基本上现在任何的过程式主流编程语言都支持 profiling 工具. 关于 profile 怎么做的问题, 等我有空了好好写文章介绍. (因为我发现, 除了编程珠玑, 没有一本书提到过).
做程序优化的八卦就太多了, 说一个Beautiful Code 上的吧. 话说世界上做线性代数的库叫做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的访问. 关于怎样局部化访问还能获得正确的乘法, Beautiful Code 一书的第14章有非常好的讲解, 我就不废话了. 总之, 矩阵乘法局部化的好坏, 取决于一个机器的 cache 的大小.
多处理器和向量处理器就又不一样了. 要想利用好, 就要把计算任务平均的独立的分到不同的处理器上. 所以, 在这里, 优化就变成了分解成若干的小问题. 因此, 分治算法成了主流. 具体矩阵乘法怎么分块, 大学数学都讲了, 我就不废话了. 事实上, 之所以 nVidia 能和 Intel 干, 就是因为显卡上令人发指的有 64 个计算核心, 而 Intel 最牛X的才 4个. 那为啥 Intel 自己不多做几个核心呢? 因为 Intel 自己把自己带沟里去了 — Intel 处理器太复杂支持的功能太多了, 一块硅片上根本放不下很多核心. 而 nVidia 一直就是专用处理器, 每个核心功能简单, 可以做到很小.
Beautiful Code 第14章就是讲了随着计算机体系结构的变化, BLAS 是怎么进化的. Tanenbaum 曾经说过, 随着一个科技的出现, 某个 idea 可能就销声匿迹了. 但是说不定下一波科技再来的时候, 这个 idea 又复活了. BLAS 从串行, 到向量, 再到串行(带cache的RISC), 再到向量(Cell), 就是一个绝好的例子. 对这个进化史感兴趣的读者不可错过这一章妙文.
