CS巴别塔(1)

面试宝典3:计算机体系结构

Posted in Uncategorized by Kenny Yuan on 2010/10/31

(这段声明还是加上比较好:此《宝典》系列虽然名为“宝典”,但写的都是一些“不知道就别出来混”的基础知识。这一篇也仍然还是基础中的基础,而并非是什么高级货色——任何一个合格的在校本科生,学过计算机体系结构这门课的,都要懂得多得多——在我看来唯一可被理解的例外是那些在当年上学时,被劣质教材和老师害了的人。本文末尾有一本推荐的书籍,建议此类人士进补)

Human-Architecture

Human-Architecture

让我们来假设,有那么一天,作为软件工程师的你,面对这样一道Computer Architecture面试题:

程序在运行时,计算机内部到底会发生什么样的事情?

在继续阅读之前,请你先回想一下相关知识,并估算一下所涉及知识点的数量:

A. <10个;

B. 10-50个;

C. 50-100个;

D. >100个

请选择: ______。

……

以下,是我的回答(非标准答案,供参考):

首先是要搞清楚这台机器具有什么类型的ISA。ISA有四种:Stack,Accumulator,Register-Memory,Load-Store。现代的处理器都是Reg-Mem或者Load-Store的,或者说:有一些ISA,表面上是Reg-Mem这样的一只被汇编程序员所喜爱的喜羊羊,实际上它也是一头Load-Store的灰太狼(例如x86就是在CPU内部进行翻译的)。Stack类型的ISA似乎已经没有流行的硬件了,但是在许多Virtual ISA——也就是在各种高级语言虚拟机(HLL VM)中,却非常地流行。究其根本原因,应该是为了在各种不同的机器上移植的方便(因为这种结构对寄存器没有特别的要求)。

如果是Load-Store的ISA,那么可以肯定它是一个RISC处理器,那么它必有pipeline。例如经典的MIPS的5段流水线(ARM是3)。前面刚刚说过,不仅仅是RISC处理器,连x86也是把翻译出来的RISC操作码发射到超标量流水线中。这些辛辛苦苦翻译出来的操作码会用一个cache来缓存,名为trace cache。如果是RISC指令,因为其格式固定,还可以对其进行固定位置解码(fixed-field decoding)。在pipeline中,也有一些对软件透明,所以不太出名的部件,比如pipeline register,用来在各个stage之间传递数据。

pipeline不是随时都在满负荷工作的,时不时地会有一些停顿(stall),比如:因为结构冒险(structural hazard)引起的停顿。结构冒险是流水线冒险的一种,举例说明:如果register file的并行读写操作太多,port已经用光了,那么就会有一个停顿插入流水线;如果指令和数据都是存在同一个存储器中(冯·诺依曼结构),在同一时刻内又有WB(写回数据)和IF(取指令)的冲突,那么就需要插入一个停顿(也叫pipeline bubble)。哈佛结构不存在这种限制,而现代的冯·诺依曼处理器将Data Cache和Instruction Cache分开,也没有这种限制了(是的,不光是CISC和RISC,哈佛和诺依曼的界限也不是那么清晰了)。

(上面说到了存储器,我们先记下,一会接着再说它,否则就失去连续性了)

引起pipeline stall的原因,除了structural hazard,还有可能是control hazard控制冒险,比如各种转移(branch)。有了转移,就需要对转移进行预测,以便提高效率,否则流水线的损失太大太大。一般常用的转移预测(branch prediction)有这样几种:2-bit历史预测,多级相关预测(比如2级2bit 4KiB)。要进行这些预测,就需要额外的存储,一般CPU内建有BTB也就是branch target buffer。有些CPU中有多个这样的BTB,用于不同的预测,比如有的专门用来预测局部的转移(local branch prediction)。

有些转移是无条件的,比如call和jmp(goto),在现代处理器中对这种无条件的转移基本可做到不需耗费额外时钟周期。还有一种特殊类型的转移预测:return address prediction。我记得有个数据在C++或者JAVA这种高级语言中RET会占15%左右的转移总量,有了这个数据,这种类型的预测立即就有了意义:) 同理,对loop进行专门的loop prediction也是很有意义的。

除了前面说的两种,还有一种流水线冒险:数据冒险(data hazard)。数据冒险有三种,RAW(Read After Write),WAW(Write After Write)和WAR(Write After Read)。如果对R和W进行排列组合的话,其实还有RAR。但是我喜欢7z,不喜欢RAR,所以我说RAR不存在数据冒险(于是它就没有数据冒险)。

对于WAW和WAR,可以通过寄存器重命名(register renaming)来解决,也就是说,汇编大佬们注意了:CPU并不诚实,它欺骗了你,还一笑而过……嘿嘿……另一个可能会让汇编大佬伤心的事实是:处理器会乱序执行(out of order execution)多数指令(需要ROB — Re-Order Buffer的帮助),而且指令还是多发射(issue)的,这时候都没有先后关系了……前面讲的这些工作和一位几十年前在IBM工作,名叫Tomasulo的老爷爷有关(都已经过世两年了)。他用自己的姓来命名算法,所以大家虽然记不住他叫Robert,但还能知道他姓Tomasulo。

关于数据冒险,还有一种类型是RAW(Read After Write)。简单的解决方法是插入pipeline stall,等着数据写完再读,同时引来了pipeline的低效。更快的方法是在流水线内部的pipeline register直接传递数据,叫作直通或者短路。但即使加上了这种技术,有时候还是需要停顿,因为有时候从逻辑上来说,是必须要等的。

上面说的都是在ILP(Instruction Level Parallelism)级别的东西,其中也提到了内存,所以下面开始说一说内存相关的。

说到内存,就离不开Cache。Cache是一个伟大的发明,但一开始它却是为TLB(Translation Look-aside Buffer)服务的,因为“内存分页”的概念虽然好,但是多次间接地访问内存,搞得效率实再是太低下,于是有CPU设计者,在忍了再忍、忍无可忍的情况下,揭竿而起,给页表加上了cache——性能问题立即就得到了解决。

TLB和普通的cache一样,也会有hit和miss,现代CPU中的TLB在locality原则的保证下,甚至能够达到99%以上的TLB hit,但是那1%的TLB miss的penalty却非常地expensive(两个数量级以上),以至于无法忽略。据说TLB可以放在所有cache之前,或者在多级cache之间,或者在所有cache之后,分别对应:所有cache物理编址,L1 Cache虚拟编址+L2 Cache物理编址,以及所有Cache均为虚拟编码的三种情况,但实际上cache似乎都是物理编址的。理论上来讲,越大的Cache越需要用物理编址,否则一旦碰上进程切换……哼哼……

说到TLB就不得不说页表(本来它就是页表的cache)。页表有两种方式:多级页表和反向页表。32位地址模式下x86是三级每页4KiB,如果启用了PAE则是2MiB(这里多说一句,PAE不是Bank Switching,因为PAE扩展的那几位是参与VA->PA计算的)。AMD64位模式下为4级页表结构48Bit地址线。页表中对每个项(PTE)都至少有Present和Modified两个标志。P标志指示此页是否真在物理内存中,M标志指示此页是否在上次载入后被更改过。这两个标志是用来做虚拟内存的磁盘交换的,如果一个页被交换到磁盘上,它的P位就是False,访问它就会引发page fault中断,于是OS中断服务程序开始介入,假如不是非法访问的话,就要去从磁盘装载页面数据到物理内存,一般这时会硬盘狂响,界面冻结,用户开始捶打键盘……如果一个页由磁盘装入了内存,但一直还没有被更改过,那么M位就是False,也就是说如果在将来这个页要被换出的话,可以不必将它的内容写到磁盘。Linux内核中的pte_present()和pte_dirty()就是用来查询这两个标志的。除了这两个标志,还会有一些其它的,比如是否可更改等,用来做内存保护。

另外,Linux的程序装载,也是依靠page fault的,所谓的装载器其实并没有将程序内容从磁盘向内存复制(名不符实的东西遍地都有,是吧?),而是靠mmap机制映射之,随后在用到时,自然会有page fault出现,于是程序自然就被一点一点装载好了(这种感觉有点像刚刚写好了一个原语操作,然后就立即用它去发威了)。

TLB和Cache是紧密结合工作的,一个VA的VPO(Virtual Page Offset)会直接送到Cache中做匹配,VPN(Virtual Page Number)则送到TLB作查找,二者并行进行,如果都是hit,PN又对得上,那么这就是我们最想要的情形了。反之就要准备好至少两个数量级以上的penalty。在有些CPU中,TLB也有data TLB/instruction TLB,以及L1 TLB/L2 TLB之分。更多类型和更大的TLB cache力求减少miss,用以保证更好的VA->PA性能。

说完了TLB回过头来再说Cache。一般的Cache都是Set Associative的,因为Full Associative会慢,而且代价高,Direct Map又太不灵活(有一个经验定律是:2-way Set Associative,与双倍size的direct map cache相比,其cache miss rate持平)。因为Set Associativity的特性决定了有时候cache line必须被换出(此时称为victim,可以用LRU或FIFO来决定谁是victim),所以这里面就有一个优化:放置一个victim cache,专门用来保存上次被换出,但是马上又要被换入的那个line(我还看过有paper说用空闲的cache来做virtual victim cache)。OS中也有许多利用Cache的Set Associativity的特性,比如Page Coloring, Slab Coloring, Hot-n-Cold Allocator(另:设想Buddy System和非Full Associative的Cache一起使用,会有什么问题?)

从类型上来说,Cache分instruction cache和data cache两种,分别用来cache指令和数据。前面在说pipeline的时候曾经说过,如果在流水线中同时有“将运算结果写回”和“取指令”两个操作,存储器是无法接受这样的任务的。但区分了Instruction和Data两种类型后,就不存在此问题了,因为两个cache当然可以同时读+写。这种划分的另一个好处是,指令和数据的各自有自己的locality(包括时间和空间局部性),而且很少有交集(那个会写LISP的不要笑!严肃点!我们这儿侃大山呢!),所以区别对待它们,能带来性能上的提升。

一般CPU中cache至少有两级:L1和L2,现在开始流行三级cache了。越小的cache越快(基本和寄存器相当),越大的cache越慢,但无论如何也比内存快(最慢的也比内存快一个数量级左右)。分级的cache就带来一个问题:L2缓存中是不是有全部的L1缓存的内容?L3缓存中是不是有全部的L1&L2缓存的内容?这个决策不是一成不变的,有三种情况:如果大的cache一定含有小cache的内容,那么就算是strictly inclusive的;如果一定没有,就是exclusive的;如果基本上有(但有时候可能没有),就是inclusive的(注意和strictly inclusive的区别)。如果是inclusive cache,那么显而易见这里面就有一个更新的问题:更新L1 cache的时候,什么时候再去更新L2 cache中的对应内容?

层次当然是越多越好

层次当然是越多越好

另一个cache问题是在多核心/多CPU系统中出现的(SMP和NUMA均有),一般称为cache coherence问题。每个核心/CPU的L1 Cache一定是独享的,那么,如果相同Physical Address的内容被装到了不同的Core/CPU的L1 Data Cache中,然后这些Core/CPU又要去更新它们,就会出现问题。为了解决这个问题,在硬件中提供 了directory方式或者监听的方式,其中监听方式很简单:监听别的cache中的写入,如果是相同的PA,那么可以将其标为invalidated状态然后重装入,或者将监听到的写入动作同样执行一遍。

关于Cache,还有一个初看无关,但是细细考虑后,发现很相关的问题:DMA。经典的DMA讲解中,把“数据装入了内存、从而能够被直接使用”当成一个很终极的目标,但是现在我们还有更快的Cache,倘若每次用到DMA数据就需要从主存中取——这倒是没什么别的问题,就是太慢了——用惯了这么快的cache,早就把我们都惯坏了。所以又有一种办法被提了出来:对DMA的数据进行cache pre-fetching。当然这种pre-fetching不能太过份,否则cache会被这些东西给灌满,而真正需要用的热数据都被换出了——这就是所谓的cache polluting。cache polluting其实就是过量的cache warming-up以至于伤害了性能。

(曾经在某讨论组见过一个狂人,说整个组的人都不懂什么叫set associative cache,只有他自己一个人懂得……会不会我这篇blog侵犯到这位狂人独有的知识产权了呢?嘻嘻……)

说完了Cache这回终于能够说到内存了。内存的访问速度很慢,比CPU要慢两个数量级以上——这也正是Cache的意义所在。Cache也是内存,只不过是SRAM,特点是速度快;而内存是DRAM,特点是集成度高(其实计算机体系结构的许多问题都是由速度和容量的tradeoff产生的)。和双稳态的SRAM不同,DRAM每隔一段时间(典型数据:几十毫秒)就需要刷新数据以保证不丢失。过去的DRAM都是异步时钟的,直到SDRAM的时候才变成同步的(S就是synchronous)。DRAM颗粒是通过RAS和CAS信号来选取地址的(先用RAS锁出一行到行缓冲,然后靠CAS挑出需要的),每个内存颗粒可以一次选出8bit,然后这样8个8bit,并列起来构成了64位宽的数据(话说SDRAM和DDR都是64位宽的,更老的EDO和FPRAM什么的就让它们往事随风都随风吧——还不如关注一下双通道和三通道呢!)。有些内存模组上面有9片内存颗粒,这就是ECC内存了,一般是给服务器用的(Google的人曾发paper说,统计一下他们用ECC发现的内存错误,发现比想像中的可要频繁多了——对几万台服务器进行了长达两年半的跟踪记录,发现每年会发生22,696个可纠正的错误)。这里我不打算详细讲解校验原理,只做一个这样的计算:不带额外的颗粒时是8×8=64位,用它编码可以表达2^64种状态。现在是8×9=72位,也就是说可以用2^72种状态来表达2^64种编码,也就是说每256种编码中,就只有1种是对的,其它的255种排列方式都是错的……(嗯,Richard Hamming老先生要是看了我这样来解说,不知道会不会气得跳出来,然后再演讲一个Me and My Regret)

内存的访问有alignment一说,也就是说取32位数的时候,最好低5位地址为0,64位的则要求低6位地址为0。如果不是对齐的话,就需要两次存储器访问才能把完整的数给拼出来(注意这时候不考虑Cache的问题,完全是在说内存本身)。

在内存和Cache之间,同样有数据同步的问题, 为解决此问题,在Cache中也设计有dirty标志位:如果Cache要被淘汰掉了,并且dirty位为True,那么就需要把cache中的数据写回到memory中。当然,也有可能是用Write Through方式更新memory(不过,即使是Write Through,也是可以利用buffer来后台批量更新memory的,而不像传统教科书上讲的那样地naive)

关于内存访问,我想说的最后一件事是:程序中的内存访问操作,其顺序并不是按照程序规定的那样,而是经过了Memory Re-Ordering的。这种机制是乱序执行的一种,CPU中的MOB(Memory Ordering Buffer)就是来做这件事情的。

说完内存,就可以开始说外存了。如果不把穿孔纸带/卡算在内的话,外存是从磁芯磁鼓磁带一类的东西开始的,中间还有过8英寸、5英寸和3英寸软盘(后来又出现过LS-120/Zip/MO等软盘替代品,但它们都被U盘给干掉了)。现在的主流外存是硬盘,不久的未来可能会是SSD的天下。倒是磁带这东西还没有全死,因为容量实再是巨大(最新的大约是一卷500TiB);或者严格说来,软盘也没有全死:那些闻名世界的中国制造小工厂,常常使用老旧设备,那些设备上的计算机只能吃软盘:) 硬盘是从PIO方式发展过来的,后来才出现了DMA方式,后来又制定了DMA66/DMA100/DMA133等标准。有个经验规律是说,带宽的增长是延时的增长的两倍速度,但对于硬盘来说,这增长的带宽只是通讯线上的理论速度,硬盘本身的连续传输速率还是受机械机构的限制,不可能太快;延时方面则是基本没变。最新的硬盘外圈的连续速率可以有100+MB/Sec,但内圈速度至少减半。之所以有这样的速率差别,是因为硬盘是恒角速度旋转的(光盘倒是可以恒线速度),在相同时间内,外圈转过的距离当然比内圈要长,于是就可以多安排扇区。传统教科书上认为每个磁道上的扇区数都是固定的,但硬盘厂商早就打破了这一限制:他们在硬盘内部的固件里把逻辑扇区映射到物理扇区。这样的映射还带来另一个好处——试想,现在的硬盘是10年前的1000倍容量,如果工艺的改变没有1000倍(这种好事不用去想的!),那么坏扇区出现的故障率就大大增高了(比如100倍以上)。所以每个硬盘在正常的存储区之外,还有一些额外的保留区域备用,一旦出现了坏扇区,硬盘会把出错的逻辑扇区映射到保留区域内,这样就可以保证硬盘继续正常使用,只不过受到一点性能的损失(原来还有可能是连续的,现在是一定不连续了)。希捷硬盘的三黄问题,其中有一黄就是这个“重映射扇区”的计数。

1GB Hard Disk vs. 1GB Flash Card

1GB Hard Disk vs. 1GB Flash Card

如果硬盘中的碎片不特别严重,那么空间局部性原理也是起作用的(时间局部性原理多数会起作用,但考虑到OS有disk cache,可以稍微放松一下要求)。所以硬盘也安装有Cache,用来缓存读和写,在测试硬盘时候出现的最高的峰值速率都是Cache的功劳(硬盘用的Cache就是普通的DRAM颗粒)。

最早的硬盘是并行通讯。很多年前,并行通讯是比串行通讯快的,因为线多,可以同时传送一个字节或者更多。但后来发现,如果提高时钟频率,线多了会导致串扰变大(比如DMA33只要求40根的排线,而DMA66的线需要80根,其中就是添加了40根地线,每根地线和信号线并排),这就限制了时钟频率的提升,最终影响到通讯速率(还限制了通讯线的长度)。设想一下:如果串行通讯的时钟速率能有并行通讯的8倍以上(大约吧,因为还有其它开销),那么8位并行口就可以被打败了。实际上,用了低电压差分信号的串行线可以相当地快:比如PCI Express(过去叫3GIO),其时钟速率是2.5GHz,而PCI总线是33MHz或者66MHz(服务器上用的PCI-X最高有133MHz的)。当然,多组LVDS信号也是可以并列的(注意这仍不是并行通讯),这样就有了另一个优势:可以根据带宽需要来灵活安排。硬盘也在这几年完成了从并行到串行的进化,SATA中的S就是Serial的缩写。串行的最后一个优势是成本,如果提升速率带来的结果是价格翻倍,制造商们就不可能答应,因为一般来说消费者不会为这个买单。

Parallel->Serial->PS2->USB, And It Works

Parallel->Serial->PS2->USB, And It Works

硬盘的另一个进化,或者说革命,是SSD。SSD有两个巨大优势:一是访问延时(或相应的IOPS)。硬盘的典型寻道是10ms左右(硬盘直径小一些,就可以转得再快一些,寻道时间就可以再小一些,但至少也有几个ms;NCQ也可以优化寻道时间,原理是减少多余的空转),在这期间CPU能完成大约三千万条指令的运算。而优质的SSD(非中国山寨品)可以在1微秒内完成“寻道”(这是软件测试数据,实际有可能更小,因为本来SSD就没有“道”,就是做地址转换而已),至少提高了4个数量级。反过来用它折算IOPS,如果均为随机访问,大小为1Byte,那么这样的SSD至少应该有10k的IOPS;而10ms寻道的硬盘,一秒内至多能够有100个IO。SSD不仅仅是极限值估算中占优,在测试软件的IOPS实测中,也是以数量级领先于硬盘。SSD的第二个优势是速度,读取速率领先硬盘2-6倍。SSD的写入速率比SSD的读要慢百分之十几(SLC),但仍然大幅领先硬盘,而且SSD的速率在未来可能还会大幅提高,反过来看硬盘,在这10年间,盘片介质的传输速率也就是提高了两到三倍。

(往上翻了翻,发现打了一大堆字了,幸亏我有Cherry的机械键盘,打起字来一点也不累,嘿嘿……另外,如果是用嘴说的话,估计嗓子早就冒烟了……嗯,顺便在此BS一下弃blog而去录音频的tinyfool,然后咱们继续……)

说了这么半天,还有一件重要的东西一直还没提到:中断。同步/异步中断,可屏蔽/不可屏蔽中断,硬件/软件中断(软件中断由指令引发,常被用来实现系统调用),这里允许我虎头蛇尾一下吧,此处就先不展开了。

嗯,另外还有一个有趣的技术,SMT。这个技术的思路是,反正现代的CPU都是superscalar的了,程序经常无法用上这么多的运算部件,但如果把它们拆成两个传统的处理器核心的话,在可以充分ILP的时候却又吃亏了,而且需要的部件也变多了,再考虑到某些情况下流水线的长长等待停顿,设计者就盯上了近些年来开始流行的多线程技术,在CPU内实现了多线程并行——这也是SMT名字的由来:Simultaneous Multi-Threading。SMT属于线程级别的并行(TLP),它和ILP不同,它同时解决流水线垂直和水平浪费的问题,从充分利用运算部件的角度来说,SMT肯定是赚到了,但是从Cache和TLB等的角度来说,多个线程有可能互相warm up也有可能互相pollute,胜负难料。另外,从CPU设计的角度来说,支持SMT肯定会更复杂(register file需要再大一些,program counter需要两份等),坊间有传闻说Intel的Core2系列CPU就是因为没时间去做而放弃了SMT……嗯,传说而已,作为不明真相的雪亮群众,我们一定要保持情绪蛋定。

最后写点和知识无关的话:我上面写的这些体系结构方面的东西,全部都是因为组装电脑才学到的。有一本名叫CSAPP的教材(国内翻译版名为《深入理解计算机系统》),被某些人奉为神器,但在我这个装机十几年的人眼里,其中没有任何新鲜的知识,都是炒冷饭。

然后,请允许我吐一个槽:有些写程序的人,格外瞧不起会装电脑的,声称那些装机高手都是XXXX……在我看来,这有可能是他们自身知识层次的限制,外加一些很常见的biases(具体的我就不列举了,有兴趣的同学可以回家翻心理学教材),才导致他们会说出这样的话来(而且还有个逻辑错误)。

P.S. 说起基础的教材来,倒是《Computer Architecture – A Quantitative Approach》这一本,相当地不错。本着国内技术圈儿喜欢8褂教材的习惯,我在这里多介绍一些背景:作者共有两人,其中John Hennessy是RISC的大牛,斯坦福大学的校长,MIPS的发明人和公司创立者;另一位David Patterson是伯克利的教授,RISC的大牛,SPARC处理器原型的发明人……(嗯,看来我的8褂工夫不到家,说完这几句就没词儿了——这俩人获得冯诺依曼奖什么的不知道是不是应该8一下)……我个人建议:每个有志把程序写得更好的人,至少要把此书精读一遍(在上学时没有学到好教材的,该进补一下了)。其中的理由,我就不论证了——应该会有一小撮儿的software die-hard同意我的观点吧?最后,套用一句公司老大的话:

Software + Hardware = Complete!

An Architect

An Architect

感谢 @welfear 指出几处问题。

然后,自己留言给自己“辩解”一下:这个文章是在某一个周六的下午闲得无聊憋得难受就打一口气打出来的(前一个月左右曾复习了一下体系结构方面的东西,外加某些情况,不写写文章就有点憋得难受了:),最近我还没有仔细review,如果有错误肯定是在所难免,等回头对这些文字开始生疏的时候,我会再来修改订正。所以,大家千万看的时候要注意挑错,别轻信我说的,呵呵……

Advertisements
Tagged with:

资深架构设计师的30条忠告

Posted in Uncategorized by Kenny Yuan on 2010/10/18

UI really matters!
界面真TMD不能忽视!

The design should base on the problem domain, not on what you have done before.
设计是应该按照问题域来进行的,而不该根据你过去做的事情为蓝本。

It’s hard to say “I was wrong”, but if you don’t say it, you’ll have to pay for it.
说出“我是错的”是很困难的,但是如果你(在该说的时候却)不说,你会为此付出代价。

It’s not your full time job demonstrating how to write code. You can do it, but not all the time.
你的工作不是做编程示范。你可以做,但是不要全身心投入进去。

Bug fixing is also your responsibility, don’t leave it to the maintenance team.
处理BUG也是你的责任,别把它扔给维护团队就不管了,要不然你的设计会被维护团队搞得面目全非的。如果写烂代码更方便的话,维护团队一定会写出大堆的烂代码的。作为架构师,你要去控制修改代码的成本,让成本最低的那一个成为你所期望的那一个(借鉴一下经济学)。

You are not Winston Wolf. Try to eliminate problems before they surface. (good design has less problems; you’re not a firefighter)
你不是一个专门来解决麻烦的(见《低俗小说》)。试着在麻烦出现前将它们干掉。(好的设计能消除问题和麻烦;你不是消防队员)

Design is technical, try to avoid politics. Or negotiate with politics to make things still work.
设计是技术问题。不要让政治参与其中。或者适当妥协以便让事情还能运转。

If your decision is based on some limitations, always remember those limitations along with your decision.
如果你的决策是基于某些限制的,那么在记住你的决策的同时,要记住这些限制(不要直接记住结论)

If you can summarize principles from your work, write it down. Then sometimes you’re able to know you were wrong.
如果你能在工作中总结出原则,就写下来。这样以后你就能知道你曾经如此这般地犯过错(我打赌你写过的多数都是错的,除了OCP,但那不是你发明的,嘿嘿)

If there are many programmers awaiting for your design, you’re definitely dead meat. (Human Resource driven is the sin)
如果有太多的程序员在等你的设计(来开工),你就死定了。(人力资源驱动是一种原罪)

Prevent lame metaphors; software is neither art nor brick building.
别用蹩脚的比喻;软件不是艺术,也不是砖墙。

Tell the user what you can provide; don’t ask them what they REALLY WANT.
告诉用户你能提供什么;别问他们“你到底要什么”。

Quality is your responsibility too, don’t hand it over to QA. (Design in the robust way)
质量也是你的责任;别把它们交给QA。

Don’t get smart. Write it down when you feel like a genius, and attack your idea as the most dangerous enemy.
别耍小聪明。当你感觉自己像天才似地做出一个设计的时候,要把它当成最危险的敌人来对待。

Reuse is not your purpose, it’s neither necessary nor sufficient to success.
“重用”不是你的目的。它不是“成功”的充分条件,也不是必要条件。别单纯为了重用去设计,别忘了重用是为了达到什么样的目的。

A language addict will always be a slave. Try to become a sensai.
语言上瘾者永远是一个奴隶;尝试变成斯普林特老师吧!

Solutions/Tools with high price guarantee nothing on productivity.
售价很高的解决方案/工具从不保证任何生产力。

Don’t say “Microsoft did the same thing”. It proves nothing. (Google/Facebook/Twitter/etc.)
别用“微软也这么干过”来支持你自己。它什么也证明不了(google/facebook/twitter同理)

Don’t try to collect information/requirements first and decide later; welcome to the moving planet.
别尝试先收集所有的信息和需求,然后再决定;欢迎来到地球——这颗移动的行星!

There’s no universal solution; The programming language sometimes can be the one, unfortunately we have lots of languages.
没有万能的解决方案;有时候编程语言可以是一个(万能解决方案),不幸的是我们有很多种语言

Age and experience are not the right way to defend yourself in an argument.
在争论中,年龄和经历不是你证明自己的正确方式(以德服人,以理服人)

Yesterday’s workaround is tomorrow’s limitation.
昨天的Workaround就是明天的限制

Good design evolves; bad design patches.
好的设计在进化,坏的设计不停地打补丁

Design what you’re able to write code for it. If it’s too hard to you, don’t count on the others.
用你能实现的方式来设计;如果困难到你也写不出来了,那么就别指望其它人

Don’t be the captain in the engine room.
不要成为引擎室里的船长(把船开好是你的职责,而添煤则不是)。

Inspect your design in each level.
在不同的级别下仔细检视你的设计。

Understand the hardware; your system doesn’t run in air. (Hardware goes wrong too)
要懂得硬件。你的系统不是在空气中运行的(但是可以Adobe Air)(硬件不是完美的,可能会出各种错误;)

Make your design natural and comfortable. Don’t fight against programmers, and don’t let them fight against your design.
让你的设计是自然而舒服的;别跟程序员斗争,也别让他们和你的设计斗争。(参考QT的舒适与灵活,外加良好的命名和强大的功能;另参见最小惊奇原则)

It’s too late when you realize it’s slow; design for performance;
当你意识到速率太慢的时候,已经太晚了。为性能而设计。

……嗯……如果你仔细数过了这些原则的数目,会发现其实只有29条。第30条我没有写,其实原打算是这样的:

(30)这篇文章是由Kenny Yuan在1.5小时内直接敲出来的,其中英文敲了一小时左右,中文翻译了半小时左右;他写这篇文章是为了说明:滔滔不绝地谈论具有迷惑性的原则是多么的容易!而且居然还能骗到一部分人哩……

(P.S. 之所以选择从“架构”这个角度来忽悠,是受到以下这个的启发:http://97-things.near-time.net/wiki/97-things-every-software-architect-should-know-the-book)

最后祝大家动脑快乐!

(P.P.S. 此为旧文,一直在草稿里忘了发。现在编辑一下发出来,其目的,当然是想要给大家的Google Reader再添一个未读数,嘻嘻——嗯,要keep it on the down low…)

渔讯——这拨儿都是咸带鱼

Posted in Uncategorized by Kenny Yuan on 2010/10/13
Big Fish

Big Fish

一段时间以来,我在慢慢总结自己的知识结构。原来是用DOT来做图(优势是可以画graph而不是仅仅限定于tree,而且还能上版本管理),但后来因为种种原因,转到了xmind的Mind Map方式——既然用了xmind,那就可以开始分享了。虽然我估计当前的完成度只有两、三成左右(很多地方没有深入展开,有些类别也还没有添加),但本着“Getting Real”的思想,还是尽早拿出来分享吧!题目仍然是标题党的形式:Interview Bible (面试圣经),嘿嘿

地址如下(可下载):

http://www.xmind.net/share/kenny_yuan/interview-bible/

Interview Bible (collapsed)

Interview Bible (collapsed)

Tagged with:

面试宝典2:算法和数据结构

Posted in Uncategorized by Kenny Yuan on 2010/05/07

本文已经404

原因——自己不满意,准备重写

Tagged with: ,

面试宝典1:程序性能优化

Posted in Uncategorized by Kenny Yuan on 2010/04/29

开场白:最近公司招人,接触了一批形形色色的工程师,但感觉绝大多数人基础都很差,在某次TL的讨论之后,就想到了写一个《面试宝典》系列。

卷首语:这个《面试宝典》名字是我一贯的标题党风格,其实在内容上都是很简单、很基础的——都是那种“不知道这些就别出来混”的知识点。所以,高手/牛人可以到此打住了——端咖啡——送客~~~

作/译序:此文可能会持续更新直到补充得比较完整为止,有什么要补充的欢迎留言

基础原则之万能利器:Profiling

如何测量距离?——直尺/游标卡尺/卷尺/etc
如何测量电压?——电压表/万用表
如何测量时间?——钟表/秒表
如何测量温度?——温度计
如何测量质量?——天平/台秤/etc
如何测量程序性能?——Profiler !

是的,Profiler就是这么一件又基础又重要的工具(小标题里的“万能”当然是标题党了,千万别真的相信)。要回答“程序为什么慢/什么地方慢/到底有多慢”等问题,离不开Profiler,就像测量长度离不开尺子一样。 (嗯,那位要测地月距离的,别抬杠了,请移步回你的实验室吧,我知道你是rocket scientist,高科技呢:)

可以使用软件Profiler,也可以使用硬件来做Profiling(DSO/Logic Analyzer/Hybrid DSO/Timer),在什么都没有的情况下,至少也可以输出Log或者用其它方式来达到Profiling的目的。
一般来说,测量工具对被测目标应该没有影响(或者极小),但是软件的Profiler却对被测目标有一定程度的影响——以此为代价,换来的是方便和廉价(免费)。

在系统外部对性能进行测试,也是一种测量性能的方式,只不过它所测量的粒度很大,不能用于分析源码,只能用于比较不同源码的优劣。

如何进行性能优化?

基本原则

原则:使用Profiler来找出最影响性能的那些程序,重点优化它们
分类:基本知识
提示:时刻记心间

原则:无论尝试了何种优化,都要使用profiler来测量这种优化
分类:基本知识
提示:时刻记心间

原则:一九原则
分类:基本知识
提示:运行中的软件有一种典型情况:10%的程序占了90%的运行时间,优化的重点是这10%的程序(10%和90%为约数)。应当使用Profiler来找出它们,改进它们并继续用Profiler测量改进的效果——在没有明显的性能热点的时候,就要考虑换一种思路进行优化了:比如使用“硬件优化”(参见下文)。在切换了设计和体系结构后,之前做的profiling也有可能会失效,要重新进行测量,每一种判断和决策必须得到证据的支持。

原则:Amdahl定律
分类:基本知识
提示:活学活用Amdahl思想(原本此定律是讲并行计算的)——在知道了“要优化的部分”占“整体”的比例之后,对于此次优化来说,最高可能的加速比也就可以计算出来了。所以不能过多期望,要多多开辟新战场。

原则:benchmark是个宝
分类:基本知识
提示:从来就没有可以代表所有程序的“典型程序”,所以要想在各种情况下均取得较好的性能,就需要使用benchmark方式对性能进行测量。

硬件优化

原则:使用更快的设备/通讯协议
分类:硬件优化
提示:有时候需要尝试跳出软件优化的框框来想问题
范例:使用SSD代替机械硬盘,在IO速率上你能提高2-5倍(在无RAID的情况下),在寻道时间上你能提高4个数量级(WOW!)

原则:对硬件友好
分类:硬件优化
范例:利用SIMD指令(如视频编码器);对Cache友好(数据Cache和指令Cache);对流水线友好(比如threaded code,削减分枝预测失误。注意这里的thread不是“线程”,是“线索化”);使用硬盘的外圈以达到更大的速度;

原则:利用硬件加速
分类:硬件优化
范例:使用D3D/OpenGL(哪怕是2D图形),使用GPU计算(如FFT),使用DMA不使用PIO,使用ASIC代替CPU进行专用计算(如常见的视频编解码专用芯片,还有加解密芯片),使用DSP对高负载数据进行处理(或预处理)

设计优化

原则:使用分布式计算
分类:设计优化
范例:使用HardoopHadoop;使用Memcached

原则:改进业务逻辑
分类:设计优化
范例:Google Chrome会扫描鼠标指针所在的位置,取得鼠标指针下的URL,然后去解析这些URL中的domain name(于是OS的DNS cache得到了warmup);对于某个name A,一组相关的names也会被送去解析(比如上次打开name A中的页面时,用到了其它的name B, C, D,那么这次也把name B, C, D送去解析)

原则:批量操作
分类:设计优化
备注:可以是业务逻辑优化,也可以去尝试利用底层提供的批操作机制(如writev)。批操作之后是否真的在性能上有提高,需要实测数据的支持。

原则:减少用户空间/内核空间的切换和数据交换
分类:设计优化
范例:例如在设计时就考虑去使用futex和zero-copy之类的技术,在特定场合下“有奇效”(嗯,前面这句话好有卖大力丸的感觉……)

原则:对输入进行缓存
分类:设计优化,缓存
范例:依靠CPU Cache/阵列Cache/磁盘Cache/磁盘/操作系统Cache/程序管理的Cache/专用Cache服务器等,对输入进行缓存,以加快速度

原则:对中间结果进行缓存
分类:设计优化,缓存
范例:预装载/索引/suffix tree

原则:对输出进行缓存
分类:设计优化,缓存
范例:使用buffer批量输出(匹配软件计算速度和设备的速度)

原则:空间换时间
分类:设计优化

原则:使用内存池
分类:设计优化,内存
提示:可以用类似slab的方式来优化可预期的内存使用

原则:使用更好/更合适的GC算法
分类:设计优化,内存

原则:控制内存交换
分类:设计优化,内存

原则:吸收掉不必要的界面更新
分类:设计优化,GUI

原则:只重绘更新的区域
分类:设计优化,GUI

原则:对可视化的结果进行缓存
分类:设计优化,GUI
备注:中间结果缓存的一个特例

原则:parallelism–利用多CPU/多核心
分类:设计优化,并行

原则:利用并发(concurrency)
分类:设计优化,并行
提示:在单CPU上跑并发也能提高性能
范例:线程池

原则:选取合适的锁类型
分类:设计优化,并行,锁
范例:使用Futex/读写锁/seq锁/RCU

原则:使用消息
分类:设计优化,并行,锁
备注:可以减少共享数据和锁

原则:使用异步模型
分类:设计优化,并行,锁
范例:使用epoll/kqueue等;nginx

原则:消除锁
分类:设计优化,并行,锁
提示:试用无锁的算法/数据结构(如Ring Buffer)/算法

原则:使用FP Paradigm
分类:设计优化,并行
提示:彪悍的FP不需要提示

算法优化

(其实算法往往是包含在设计中的)

原则:使用更优的算法,减小算法的阶
分类:算法优化
范例:使用BM/Sunday算法代替BF算法

原则:减小算法的常量(BigOO)
分类:算法优化
范例:使用sentry来编写double link list

原则:处理好Big Omega和BigO,使算法在“最坏的时候也不要太坏”
分类:算法优化
范例:quick sort,避免O(N*N)的情况

原则:使用更优的数据结构
分类:算法优化
范例:AVL Tree–>Hash Table–>Ternary Search Tree
备注:其实有些重复,主要是为了区分狭义的“算法”和“数据结构”

原则:寻找并行化算法
分类:算法优化
备注:和前面的parallelism有些重复,这个更多的是指可并行的算法而不是其它意义上的并行

小技巧

原则:编译器优化
分类:小技巧
范例:使用Intel的编译器,使用Intel的性能库IPP
备注:注意Proebsting定律

原则:树递归–>尾递归
分类:小技巧
备注:在许多语言中,尾递归是不需要栈的,自动转换成迭代了(例如在erlang中用尾递归实现无限循环)

原则:少用小技巧,以免妨碍大粒度上的性能优化
分类:小技巧
提示:主要是指那些影响并行计算的小技巧,或者那些没有使用profiler进行测量就草率进行的盲目优化

原则:远离“神话”
分类:小技巧
提示:有些流传的关于优化的神化不足信,“是骡子是马拉出来骝骝”,一切在profiler下见真章
范例:比如“大块内存分配非常慢”的神话(甚至有过一个人估计数量级的时候说:分配10M内存至少要1秒钟),比如“虚函数导致效率低”的神话,比如“解释运行比编译慢”的神话,等等

原则:使用Lazy Evaluation
分类:小技巧

原则:避免大对象复制
分类:小技巧
范例:RVO/RVal Ref

原则:预译码/编译成本地代码
分类:小技巧,解释器和VM
范例:PYC/HipHop

原则:混合使用各有优势的语言
分类:小技巧
范例:C里使用汇编;Python里使用C模块;

原则:使用二进制优化器
分类:小技巧
范例:JIT就是最出名的一种二进制优化;Win32SDK的BitBlt()函数也是;

……

重温:无论尝试了何种优化,都要使用profiler来测量这种优化
分类:红宝书
提示:时刻记心间

(2010年10月29日更新)

鸣谢:感谢Guancheng指出问题

参见:性能优化的方法和技巧(这是一个文章系列)

linuxperftools

图片来自http://www.brendangregg.com/linuxperf.html

Tagged with: ,

1990-1995年间学习编程语言的回忆录

Posted in Uncategorized by Kenny Yuan on 2009/08/17

绝对必要、又臭又长的作者声明:
1、虽然是回忆录,但本人是码农不是艺妓,想来看艳情的可以洗洗睡了。(推荐你看《往事回忆录》,那个很艳情,而且不黄不暴力)
2、我不是成功人士,想看成功人士的奋斗经历来励志的,可以关窗口了。(推荐你看《小兵传奇》,那个很成功、很励志)
3、我没开发过大项目,想看内核技术和巨型软件构建经验的,可以打酱油了。(推荐你看最近出的写WinNT故事的那本翻译书,不过我还没看过,只是听说不错)
4、我没有高学历,想围观高学历的地球原住民的,可以飞过、飘过、走过、路过、虫洞过了,这里没沙发。(推荐你看《新语丝》,有闲心的还可以去找找,看到底在加州理工的CS博士列表里面有没有唐峻)
5、写回忆录不是为了要显摆什么,记忆中是什么样就怎么写(当然,记忆重构是无法避免的)。本人绝不像某些国内伪专家一样装B,别人说什么东西好的时候,非得过来插一句说“我XX年前就见识过了”。那种人我最讨厌了,所以本文绝无半点那种倾向。所以,如果想跟我学装B也不要往下滚动了,我这人的特点是有一说一,认为自己好的也说,认为自己差的也说。(装B最好的方法是把一些人人尽知的东西,另一群不知道的人中传播,最好自己写BLOG来传播,参考经典著作而不要直接抄袭,这样最能装B!)
6、本人今年30岁,在1990年的时候我11岁,科特学习机也已经上市,已经具备了学习计算机的生理上的可能性,和客观条件上的可能性。各位福尔摩斯和柯南们可以回家了。

Basic

Basic是我编过的最多程序的语言,没有之一。虽然后来工作后也写过一些30-50MB CPP源码的项目,但我一直坚信BASIC是我写过最多程序的语言(大约是因为易得性直觉吧,估计真实数据不是这样的)。当时的BASIC是我自己唯一拥有的计算环境——科特学习机的F-BASIC。Basic是我见过的第一种编程语言,在我还没学会打字的时候就开始用它编程了。当时最大的愿望是写一个游戏程序。现在回想起来,这算是家长禁买游戏卡带给逼出来的发奋图强了。

当时的F-BASIC里有背景图可以组成画面,有超级马利中多数的卡通角色可以用程序控制。编写一个游戏程序从技术上看起来是可行的,而且我还有大量的时间,没有资金预算的问题——虽然这个项目的可行性评估完美通过,但最终还是理所当然地失败了,这是我人生中的第一个失败的软件项目,住在100公里外的表弟最终也没有能够玩到我写的游戏。原因倒是很简单:F-BASIC没有BASIC中的陷阱编程(一种类似于中断的东西,可用来捕获键盘输入),无法及时控制卡通人物行动,运行速度也太慢。这件事情的“蝴蝶效应”直到现在还余波未消——在讨论可行性的时候,我总是习惯于搞清楚“是不是真的可以”,不满足于从文字中求证,而是要测试过才放心。(当然,从另一个角度来看,所有的技术问题最终都是管理问题,这就是另外的话题了)

虽然游戏项目可耻地失败鸟,但收获还是有的。最大的收益就是学会了将问题转换为计算机表达,比如讨厌的约瑟夫问题,我一直不会用公式计算,都是在纸上画圈圈和叉叉,挪到计算机上还是挺节约白纸的;小学奥赛的经典名题“鸡兔同笼”在穷举法面前也不堪一击(虽然有无数求解公式,但我一直记不住);在《世界数学名题趣谈》上看到的那个可以计算PI值的无穷展开的算式,我也是没有用笔算的耐心的(如果让我也算出几百位PI之后发现出错了,同样也会吐血的),所以,写个分数运算程序,用计算机来运算还是很爽的——虽然当时的字串最长仅允许32字节,即使拼起来用,最终算不出几位有效数字。

在这种简陋的F-BASIC中,我还体验了一把“多媒体编程”。使用F-BASIC中的PLAY语句,播放三个声部的伴奏乐谱,然后录下来给音乐老师作教学用,作为交换,我可以弹她的电子琴。因为直接写那些不断重复的“CDEFGAB”唱名字串很繁,我开始用程序来生成字串,这是我第一次接触到程序和数据之间的相互转化问题。但很遗憾地是,F-BASIC不能由数据生成程序(如果有向磁盘LOAD和SAVE的标准BASIC倒还可能,F-BASIC是向录音机存储数据的)。后来当我见识到了eval之后不由得大喜过望——数据向程序转化的东西终于有了。

除了这些之外,BASIC对我的负面影响也很大,比如良好命名,模块划分等方面,它带给了我许多不好的习惯。这些在后来学习LISP的过程中阻碍了我很长一段时间,后来才慢慢改掉。记得有句名言说第一个学BASIC的程序员不会是好程序员,但我感觉这话太过绝对了。或许它表明了一种趋势和倾向,但并不是一定如此。人,长着脑袋,就是用来学习和改进的。

dBaseIII

中国最早的信息化就是用的这玩意,无数个单位买来“先进”的286微机就是为了“会计电算化”或者“电子信息化”,所用的工具九成九都是dBaseIII。当时的教育台里也总会有一个戴着龟壳大眼镜的谢顶老大爷,操着难懂地普通方言话,来讲解dBaseIII。我一直没有把dBase系列看成一个真正的计算机语言,最初以为它是数据库,现在觉得它是个带一定编程手段的查询语言。当时听说它比COBOL要先进不少,所以为了迈向“高大全”的目标,就把它顺便也学了。后来的《跟我学电脑》丛书,第四册整本讲的都是dBaseIII,我翻了无数遍,在纸上默写语法和程序,并且将样本数据进行了演算,最终搞明白了这种“语言”。借着为某些单位修理dBaseIII系统的机会,我“偷”到了不少上机时间。另外,在纸上推演dBaseIII数据的时候,也被迫学习了索引/二分之类的基础知识,认识到了算法和数据预处理的重要性,为后来学习《数据结构》等打下了基础。

Lisp

Lisp一直是我最喜欢的语言,没有之一;但LISP也是我一直没有能够掌握的语言之一(这回有“之一”了)。

我是在《跟我学电脑》那套从书中的《计算机语言发展历史》章节中知道LISP的,而且听起来它有一个很牛B的名字——人工智能语言。当时的中央电视台的译制片栏目放了一部195x年的美国电影《地球停转之日》(不是后来Keanu Reeves主演的那个翻拍版本),那里面的机器人功能很牛B,而且能听懂外星主人的语言,甚至人类小妞学着说的时候,它还知道把人类小妞给保护起来——我当时就认定这机器人一定是人工智能的了。于是就买了LISP的书来学习。这本书里讲的是Sun工作站上的Common LISP,还附带讲了LISP机的辉煌历史——这让我后来很自然地就接受了“用IDE工作”的理念,而且在相当长的一段时间排斥命令行编译(直到后来学了GNU MAKE才改正过来)。当然,对于LISP机关掉GC等待内存耗尽的故事,那本书里是不会讲的。这也是中国“学者”的通病,如果他说什么东西是好的,就只说优点不说缺点。这一点读书时一定要注意。

LISP对我来说的一大特点就是自然,计算机不像BASIC那样地讨厌,而是变成了一个很自然的描述工具。现在想来,这和LISP的历史渊源是有很大关系的——LISP最早就是John McCarthy发明的一种数学符号,而不是一种编程语言。只不过他的一个学生偶然在IBM 704机器上实现了可以解释执行的计算机语言LISP——关于IBM 704 blah blah这一大段是我死记硬背的,我这辈子还没见过这种机器,估计也没机会见识了。

正因为LISP的原始发明意图就是在纸上推演的数学符号,所以使用它的时候完全感觉不到太多的障碍,这种障碍在别的语言中有很多表现,这里就不一一举例了,相信大家都有体会。LISP的这个渊源,对当时的我来说,还有一点有着非同寻常的意义:它可以在纸上演算并求得结果,求解过程是可以直接用人类的大脑来做的,而不像C语言那样几乎不得不用机器语言来做。举个例子,虽然CAR这个函数名称的由来和寄存器有关,但是它却有着非常直观的含义——砍掉LIST中的第一个元素:(car ‘(1 2 3)) -> (2 3)。至于为什么我得在纸上演算,原因很简单:在那段时间里,如果一个中国的初中生能够接触SUN的小型机,那他一定是牛B到不能再牛B的人物——很明显我不是,所以我只能在纸上演算。

虽然LISP很直接和自然,但当时的我只有初二数学水平+一门粗浅握的《逻辑代数》,又没有太多的编程实践经验,所以对于某些东西的掌握还是很困难的,比如“闭包”这个怪物的意义,就让我困惑了很多年,直到后来看到了它和对象的等价式后才恍然大悟)

学习LISP对我的影响很大,从小的方面来看,有“看得见的万能之手”——完美的MACRO系统;递归——人来负责简洁清晰的算法,机器来负责提高运算效率;GC——白胡子老管家式的周到服务;程序和数据的大一统——后来知道这叫S表达式;IF-ELSE——这个也是LISP的发明人John McCarthy在LISP里发明的(不是ALGOL 60),嗯,我承认这一条基本上是用来刁难人的;从大的方面来看,学习LISP让我开阔了视野,在后来的许多年里,都只把C风格的语言当成低级语言,而没有陷入语言成瘾的状态,对于2000年以后流行的各种语言也持有一种积极接受的态度——本来这些就都是从LISP里拿来的嘛!记得有一句名言,大致是说:1、世界上只有两种计算机语言,C风格的和LISP风格的;2、一个现代语言的发明,就是在C的风格基础上借用一些LISP的“先进”概念(比如精通LISP的James Gosling发明了带有GC的JAVA)

Prolog

最早知道Prolog还是在《跟我学电脑》那套书里知道的(若干年后才知道是自大的法国人强行发明的),当时书中称这种语言是“下一代的计算机语言”,是计算机业的未来。为了“不输在起跑线上”(当时很流行这句话),我立即就去把书买了回来,虽然不时地翻出来看,但一开始根本就没看懂;而且这本书上说:对于学生来说,同时学习Prolog和LISP是很难的事情,因为风格不统一。我当时在学LISP,所以Prolog就放弃了好长一段时间。

后来在某一天,偶然翻看Prolog的时候,我突然间就顿悟了(不过我没有像阿基米德那样光着屁股裸奔)。比如在Prolog里定义一个逻辑关系,根本不用像BASIC那样绞尽脑汁定义变量存储,也不用像LISP那样编写函数去递归求解,如果我说farther(A, B).的话,那就是有一个A是B的父亲,至于A和B是什么,Prolog不知道、也不必知道,甚至对于father这个谓词它也不知道,它只知道这其中的逻辑关系。当然,如果仅仅能够接受这样的输入,也没什么意思,但Prolog可以在这些云山雾罩的关系的基础上,继续定义逻辑关系,并且最终还能自动求解,比如:定义一个grandfather,就可以在father的基础上定义谁是谁的爷爷(多说一句:Prolog默认没有交换律——请按群论来理解这个“交换律”的意思)。

过去学的种种语言,无论是LISP、C++还是BASIC,编程的人都得替计算机想出如何求解的过程来(不论看起来复杂的迭代,或者看起来简洁的递归,其实都是在定义求解的过程),而且往往还得发明一些东西来帮助计算机:比如用BASIC这样的东西来求解约瑟夫问题,还得用自定义规则,用来模拟语言本身不支持的链表结构。但是Prolog就不一样了,它就像一个解题机器一样,你告诉他一堆事实和规则,然后就可以提问了——完全不需要告诉它解题的“过程”。Prolog其实也并不知道答案“到底是什么”,但是它可以按照你定义的规则求解出你所需要的答案(可能需要多打几次分号)。至此,我发现我的逻辑代数白学了,学一个简单的Prolog语法就全部解决了嘛!

从那以后,我一直疑惑为什么LISP被称为人工智能语言而Prolog不是。而且“谓词”这个概念被我深深地记在了心中。到后来听说ISO14882 C++98标准中竟然有谓词Pred,我着实兴奋了好久,但后来仔细一研究,原来跟Prolog的完全不是一回事。不过,C++模板编程在某些方面来看倒是很有Prolog的风格,这也是有一段时间我不自觉地陷入了“template误区”的原因之一。

C++

借一句当年流行的歌:“你这样,一个语言,让我欢喜让我忧……”。最早我学C++仍然是因为《跟我学电脑》这套丛书,那里面介绍了B语言转化为C语言,然后升级为C++语言(根本没提和UNIX的关系!)。既然要学,那我就学一个最好的吧!于是就略过了C,直接学的C++。所以在之后的10多年里,我一直很鄙视“学C++必定要先学C”这样的说法。当时买的是张国锋写的C++的书,大约是91年版或者92年版的,只是在讲语言,没有讲编译、链接和调试。因为我是BASIC出身,又喜欢LISP,所以在“如何将程序变为机器码”这一环节是一直是缺失的,直到后来整了一套Visual Studio 97(VC++ 5.0)的光盘才真正开始熟悉整个的编译-调试过程。我还记得第一次碰到“找不到链接符号”这个错误时,我用了好几天才搞明白是函数体忘了写。在这方面的知识一直仅仅是够用,直到后来在做过一个集成开发环境(IDE)后才得到了加强:许多问题都是在解析过OMF文件信息之后才真正理解的。因为自己有这一段经历,所以我在教别人的时候一直强调:第一天就必须要上机来熟悉开发环境。懂得如何生成代码和调试代码,是作为一个编译型程序员必不可少的技能。

C++的教材在讲class的时候喜欢用复数(complex)作为例子。对于当时只有初中二年级数学知识的我,这就不啻于天书了,许多年一直没能明白虚、实分量的相加代表了什么。还好里面有一个动物的比喻能够帮我理解OO的概念。但也仅限于封装、继承、多态等基础知识,很长一段时间我没有意识到C++是多范型的程序语言。后来我学习C++开始转向“实用”这个“目标”(其实是学Windows SDK):先是学习了MFC,然后开发过许多控件和程序,帮老师做过学校的课题,往杂志投稿过一些VC程序,大约在99年左右,我开始有些飘飘然了,觉得C++不过尔尔(其实是连C++和VC都没分清)——这种心理一直持续到大约一两年后,有一次偶然在CSDN上看到某装B人士,正在以极为不屑的态度批评一个发贴者不懂“面象对象”,他祭出的武器就是OCP。经过google得知OCP的内容后,我不由惊叹“此为神器也!”,继而开始拜读Bertrand Meyer的《OOSC》,从此再也不敢“翘尾巴”了。之后的许多年里,我一直在观察周边的人,发现许多人的OO教育从一开始都是错的。我认为这不仅仅是我本人的一个教训,也是教育的失败:当你让学生接触到某种东西的时候(例如OO),只给他看一些零碎的基础概念(封装、继承),教一些基本的实现手段(语法),从来不说这种东西的思想精髓在哪里(OCP/LSP/etc.),也没有提供任何延伸阅读材料,反倒是在一个封闭的小圈子里不停地说这东西好,这东西就是某个样子的——事实上这个“样子”却违悖了其中的精髓思想,而且一说就是十多年不间断(因为教材是抄来抄去的?)。若干年后,某些曾经被错误教育的有识之士终于意识到了问题,从国外重新引进了原本的精髓思想。但也已经无法成为主流了,错误积累的太过深重,OO本身已经完全毁掉了。

说到C++几乎不得不说《设计模式》。国内的中文译本大约是在2000年出版的。在当时设计模式很受人们推崇,给人一种万能药的感觉,仿佛有了它中国就不必再担心软件结构的设计问题了。在我看来这又是典型的“大炼钢铁”式的思维——一味地追寻成功者的足迹,不管是不是充分条件(甚至不管是否必要)。我一直觉得设计模式在国内吹嘘得过分了。从OCP等原则出发,可以推出许多模式;从LISP语言看过去,许多模式就是一陀额外的屎——但是这个想法一直不敢太公开(人微言轻啊),直到后来读到Peter Norvig的那个Presentation。

C++的98标准及相关的一些知识是在CSDN论坛上得知的,后来疯狂地购买和阅读C++的相关书籍,几年后名单上的差不多有20本书以上。至此,算是重学了一遍C++(书单中还真包括一本《C++ Primer》)。看过之些书这后,在之前的OO的基础上,明白了对象模型的细节,熟知了STL和模板的应用(甚至有超级古怪的应用),熟记了一些常见的陷阱和Workarounds,甚至还背诵过三字节操作符这样罕见的东西。现在回想起来,学习这些东西的机会成本,其实还是蛮高的。

古老的C++语言因为泛型编程而焕发了“第二春”,但我对C++语言的兴趣却开始慢慢消失。虽然一直还在关注着这一领域,但也只是在关注了。从网上随处可见的关于C++的争论之中,我能体会到一些人不是因为理智,而是因为某种情结和瘾癖而在捍卫着C++,他们的思维陷入了一个怪圈中。一开始我觉得这是因为见识的问题,后来意识到,归根结底还是因为open mind的问题。等到了“否定C++以外的东西”成为了你的第一反应的时候,或者当你总是下意识地寻找和传播C++的好处的时候,你的大脑很可能就开始封闭了。这是一件很危险的事情,而且更危险的是你自己很难意识到这种状态。有一段时间,我曾经几乎要陷到这种状态当中去,幸运地是,偶然有一次聊天时说到LISP,在我向别人介绍LISP的强大的同时,我突然感觉到天灵盖处的一阵颤栗,仿佛冥冥之中的设计好的某段程序重新启动了,十年前学习各种编程语言时的感受重新涌入了大脑,迫使几乎侵占了所有地盘的C++重新回归了它应该有的位置。后来LP推荐《心理学》给我看。在此之前,我曾经因为一本特别差劲的教材,而误解心理学为伪科学——这一错就是十多年!在LP的推荐之下,我看了David Myers的《心理学原理》,才终于接触到了真正的心理学(其它好书也有一堆,这里同样就不列举了)。学过了心理学之后,我对自己当时的心态也就有了一个更加清醒的认识。我决定把这些写下来的原始动机,也是为了总结+自醒,也供他人借鉴。

Pascal

将Pascal写进来有点时间线的问题,因为Pascal是在上高中为了参加奥赛而学的。但既然上面讲C++时,已经说了后来发生的事情,这里也一并说一说吧:Pascal语言,我也是对着书在纸上啃下来的,没有上机。有了前面学过的那些语言作为基础,学Pascal只用了不到一周的课余时间。这个事情对我的影响却是负面的,有很长一段时间,我错误地以为学习一门新语言是简单地事情——有了原来打的基础,学习语言本身的确是很简单,但是我却忽略了程序库的重要性。我一直不会JAVA语言就是因为它的语法太平淡了。虽然我在上大学时,也有过一本1000多页的《JAVA内裤大全》,但JAVA还是被我给错过了。

(更新:昨天浏览了一下,发现写出来一个大BUG,看来狂打字的时候脑子果然是不灵光的,但既然这么久过去了,BUG我也不改了,留着给人用来挑错吧,呵呵)

Tagged with: ,