【计算机系统导论】3.5 编程珠玑


  • 翻译并执行程序(编译器、汇编器、链接器、加载器、动态链接库)
  • 程序执行过程(链接和加载)

随想

在动手做任何事情之前,我都会深思熟虑。但一旦开始做事,我就不怕把它扔到一边儿。有一点非常重要,程序员看待一段代码应当像对待一本书的烂章节那样,弃之如敝屣。千万不要过份迷恋一个想法,绝不要固守某样东西以致不能在必要时把它丢掉,这才是程序员应有的态度。

什么是编程?人们对此一直各持己见。有人说它是科学,有人说它是艺术,还有人称之为技能或手艺。我认为这三方面兼而有之。我们喜欢说它蕴含大量艺术成分,但是我们都知道它里面更多的是科学。

编程包含有大量科学,同时,它也有点像手艺。实际上,在许多人看来,编程是一项复杂的技能,这跟工具制造很像,需要精雕细琢。我认为,只要将科学、艺术和技能这三者拿捏得恰到好处,你就能取得一些引人瞩目的成绩。

经年累月,你的经验愈加丰富,积累的算法数以百计;你牢记自己学到的技巧、处理过的缺陷以及误入的死胡同。你记得自己犯过的所有错误、取得的所有成功。可以说,执行特定任务就像是从大杂烩中选定菜目,排出一席美味佳肴。你可以左手一份美味右手一盘佳肴,但搁在一起可能味同狗粮。懂得巧妙搭配食材才称得上好厨师。同样,把程序各个部分妥善组合在一起,才是成就优秀计算机程序员之道。

很多编程技巧都是可以传授的。一个优秀的程序员必须喜欢编程,对它感兴趣,这样他才会努力多学一点。优秀的程序员还要对美学有感觉,并且有相应的负罪感,能够敏锐地意识到什么时候违反了程序的美感。负罪感迫使他更加努力地去改进程序,使程序更加符合美感。

我相信使用自己写出来的东西非常重要。并不是说我是自己的程序的最好用户,而是因为经常使用的话我就可以意识到程序中的缺点,可以在发现什么地方做得很笨拙的时候就把它改掉。

一般认为世界上最早的编程语言是 1954 年开发的 FORTRAN 语言

从编程语言的进化过程来看,一个显著的关键词就是『抽象化』。抽象化就是提供一个抽象的概念,使用者即使不具备关于其内部详细情况的知识,也能够对其进行运用。由于不必了解其内部情况,因此也被称为『黑箱化』

汇编

机器语言上面是人类可读的汇编语言。汇编器将翻译为机器可以理解的二进制数,它甚至通过创造硬件中没有的符号指令来『扩展』指令集。

虽然大多数程序可以也应该使用高级语言编写,但是在某些情况下汇编语言也是必不可少的。在缺乏资源的移动计算设备中使用的程序一般都需要使用汇编语言编写,智能卡、科学仪器中的嵌入式处理器、无线的便携式数字助理都属于这类移动计算设备。汇编语言程序是底层的机器语言程序的符号表示。汇编器负责把汇编语言程序翻译成机器语言程序。

程序的执行速度对于某些应用来说是至关重要的,对于这些应用来说,单纯使用汇编语言编写程序并不是最好的方案,更好的方法是首先使用高级语言编写整个程序,然后测量程序的执行时间,最后使用汇编语言重新编写其中最耗时的部分。这样做的依据是在实际使用中,通常程序的大部分执行时间都花费在一小部分代码上。

许多汇编器都提供了宏,程序员可以使用宏为常用的代码序列起个符号名,这样可以方便后面的引用。一般来说,这些宏还可以使用参数,参数的用法很简单。宏是使用一系列字符串处理算法实现的。

大多数汇编器都使用两趟扫描技术。第一趟扫描建立一张符号表,符号表中主要存放标号、直接量和显式声明的标识符。这些符号可以采用无序的方式保存然后执行顺序查找,或者首先排序然后进行二分搜索,或者使用散列技术。如果在第一趟扫描过程中不需要删除符号,散列是最好的方法。第二趟扫描执行代码生成。某些伪指令在第一趟扫描中处理,而另一些在第二趟扫描中处理。

独立汇编的程序可以被链接到一起,形成一个可以运行的可执行二进制程序。这部分工作是链接器完成的。链接器的主要任务是重定位和绑定符号名。动态链接是指直到实际调用某个过程时才链接该过程的一种技术。Windows DLL 和 UNIX 的共享库都使用动态链接技术。

用汇编语言进行程序设计需要程序员放弃高级语言中的一些有益的特点——如数据结构、类型检查以及控制结构——以获得对机器执行指令的完全控制。一些应用的外部约束,如响应时间、程序大小等,需要程序员密切关注每条指令。然而,和高级语言程序相比,这种级别的关注带来的是更长、编写更费时、更难维护的汇编语言程序。

此外,三个趋势导致不必再用汇编语言来编写程序。第一个趋势是编译器的改进。现在,编译器生成的代码可以与最好的收工书写的代码相媲美——有时候甚至会更好。第二个趋势是新处理器的速度不仅更快,而且对于哪些可以同时执行多条指令的处理器,手工编程也变得更加困难。此外,现代计算机的快速发展也支持高级语言程序不再依赖单一的体系结构。最后,我们见证了日渐复杂的应用趋势,不仅有复杂的图形界面,而且还有许多先前不曾遇见的特征。由程序员组成的团队合作开发的大规模应用程序需要有由高级语言提供的模块化设计思想和语义检查的特点。

编程珠玑

结合处理器及存储系统(缓存的)一些特性来介绍基本的编码知识

编程珠玑番外篇-D. 高级语言怎么来的-1 http://blog.youxu.info/2009/05/13/hpl/
编程珠玑番外篇-E. 高级语言怎么来的-2 http://blog.youxu.info/2009/06/13/vm/
编程珠玑番外篇-F. 高级语言怎么来的-3 http://blog.youxu.info/2009/07/02/fortran/
编程珠玑番外篇-H. 高级语言怎么来的-4 http://blog.youxu.info/2009/08/31/lisp-and-ai-1/
编程珠玑番外篇-I. 高级语言是怎么来的-5 http://blog.youxu.info/2010/02/10/lisp-and-ai-2/
编程珠玑番外篇 -J. 高级语言是怎么来的-6 http://blog.youxu.info/2010/07/12/scheme-1/
编程珠玑番外篇 -K. 高级语言是怎么来的-7 http://blog.youxu.info/2011/09/27/lisp-prehistory/

程序优化

<代码大全> (Code Complete) 是一本很好的书. 我建议像我这样写的程序总行数不超过50万的程序员应该买一本放在案头 (当然<代码大全> 不如 这本书好, 这个我以后有机会写文章细谈) 如果你天天编程序, 我建议你买一本. 如果你已经有了<代码大全>, 我诚心建议你赶快翻开此书, 撕去第26章. 因为代码大全的其他章节可以让你成为优秀的程序员, 唯独第26章, 读了之后立即从优秀程序员变成最差的程序员. 为啥? 因为第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 就曾经说过, 其实两者差别不大 (http://hugunin.net/story\_of\_jython.html). 也有一些其他的测评说, 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), 就是一个绝好的例子. 对这个进化史感兴趣的读者不可错过这一章妙文.

捧个钱场?