回归原点

作者：周思博(Joel Spolsky)

译：Paul May 梅普华

Tuesday， December 11， 2001

属于Joel on Software， http://www.joelonsoftware.com

我们在这个站花了很多时间讨论让人兴奋的大局概念，像是.NET对Java、XML策略、锁住客户、竞争策略、软体设计、架构等等。这所有的概念就某方面来看就像是个夹心蛋糕。最上层有软体策略。再下来可以想想.NET之类的架构，然后再下面是个别的产品：像Java之类的软体开发产品或Windows之类的平台。

请再向蛋糕下层挖下去。是DLL吗？还是物件或是函数呢？都不是！再下去！下到某个地方就会想到用程式语言撰写，一行又一行的程式。

不过还不够深。今天我想谈的CPU。一片把位元组们搬来搬去的小矽晶片。先假装你是个新手程式师，把你所有的程式设计和软体还有管理知识都丢掉，然后回到最底层的冯纽曼的基本结构。暂时先把J2EE由你脑中拿掉，来想想位元组。

为什么要这样做呢？我认为人们所犯的某些大错虽然错在最高的架构层，但其实是因为不够了解或想错某些在最底层很简单的事情。你可能建了一座雄伟的宫殿，可是地基却是一塌糊涂。本来应该用好的水泥砖，结果却用了碎石头。所以宫殿看起来虽然华丽，可是浴缸却时常移位，而你根本不知道怎么回事。

所以今天就来个深呼吸。请跟着我来做个用C语言进行的小小练习吧。

记得[C的字串用法](http://www- ee.eng.hawaii.edu/Courses/EE150/Book/chap7/subsection2.1.1.2.html)吧：它们是由一串位元组后面接一个null字元(值为0)所组成。这里有两个明显的暗示：

必须整个字串走一遍找到结尾的null字元，才能知道字串在哪里结束(也就是说字串的长度)。
字串里不能有任何零。所以你不能用C字串来储存JPEG图片之类的二进位大物件。

为什么C字串要这样运作呢？因为发明UNIX和C语言时用的PDP-7微处理器有一种ASCIZ字串型别。ASCIZ意思是「用Z(零)结尾的ASCII。」

这是储存字串唯一的方法吗？并不是，事实上它是储存字串最烂的方法之一。只要是有作用的程式、API、作业系统、类别库，都应该像躲瘟疫一样避开ASCIZ字串。为什么呢？

让我们由撰写strcat 这个把一个字串接到另一个字串的程式开始。

void strcat( char dest， char src )
{
while (*dest) dest++;
while (dest++ = src++);
}

大约读一下这段程式，想想我们这里做些什么。我们先扫描第一个字串寻找结尾的NULL字元。找到之后再扫描第二个字串，扫描时每次把一个字元复制到第一个字串。

这种字串处理和字串连接对[Kernighan和Ritchie](http://cm.bell- labs.com/cm/cs/cbook/)来说够好了，不过还是有些问题。举例来说。如果你有一大堆名字，全部都要附加到一个大字串后面：

**char bigString[1000]; *_/ 我永远不知道要配多少记忆体… */
_ bigString[0] = ‘\0’;
strcat(bigString，“John， “);
strcat(bigString，“Paul， “);
strcat(bigString，“George， “);
strcat(bigString，“Joel “);

这程式能动，对吧？没错，而且看起来不错也很干净。

它的效能如何？是不是尽可能的快呢？它能处理更多资料吗？如果我有一百万个字串要连接，这样做适合吗？

答案是否。这段程式用了_油漆工Shlemiel的演算法_ 。Shlemiel是谁？他是下面这个笑话的主角：

Shlemiel得到一个在路上涂油漆的工作，他要漆在路中间的间断分隔线。第一天他拿了一罐油漆去漆好了300码的路。「做得真好！」他的老板说「你手脚真快啊！」然后就给他一个铜板。

第二天Shlemiel只漆了150码。「这样啊，没有昨天好，不过也还是很快。150码也很了不起。」也给他一个铜板。

第三天Shlemiel只漆了30码。「只有30码而已！」老板就哇哇大叫了。「这实在是无法接受！第一天你漆了十倍的长度耶！究竟怎么回事啊？」

「我也没办法啊，」Shlemiel说「我每隔一天就离油漆罐愈来愈远啊！」

(想挑战的可以回答真实的数字是什么？)

这个烂笑话正确地说明了使用像我刚刚写的strcat 版本会发生的状况。由于strcat 的第一段每次都必须扫描目的字串，重复地找寻可恶的结尾NULL字元，所以这个函数会比真正需要的时间慢上许多，而且完全不能正常处理更多的资料。你每天用的程式中很多都有这个问题。很多档案系统的实作方式都有问题，不适合把几千个档案放在同一个目录里。因为同一个目录里有几千个档案时效率就会急速下降。试着打开一个塞满垃圾的Windows资源回收桶看看有多慢

要花几小时才能显示出来，显然并非与内含档案数量成线性关系。里头某处一定有个油漆工Shlemiel演算法在作怪。当你发现某件事本来应该有线性的效能，实际上却是次方的效能，就可以去找隐藏的Shlemiel。他们常常躲在你的程式库里。看着一长串的 strcat 或是回圈中的strcat 并不会让你立即喊出「n次方」，不过凶手就是它了。

要怎么修正这个问题呢？有几个聪明的C程式师实作了他们自己的mystrcat ，内容如下：

char mystrcat( char dest， char* src )
{
** ** while (*dest) dest++;
while (dest++ = src++);
return –dest;
}

我们在这里做了什么？我们多花了一点点成本，传回指向较长的新字串_结尾_ 的指标。如此呼叫这个函数的程式就可以选择不必重新扫描，直接把新字串接上去：

**char bigString[1000]; *_/ 我永远不知道要配多少记忆体… */
_ *char p = bigString;
bigString[0] = ‘\0’;
p = mystrcat(p，“John， “);
p = mystrcat(p，“Paul， “);
p = mystrcat(p，“George， “);
p = mystrcat(p，“Joel “);

这段程式的效率当然是线性而非n次方的，所以要连接很多东西时也不会变慢太多。

Pascal的设计者注意到这个问题也加以「修正」了，修正的方法是在字串的第一个位元组存一个位元组数。这就叫做Pascal字串。Pascal字串里可以放零也不必用NULL字元结尾。因为一个位元组只能放0到255的数字，所以Pascal字串最长只能到255个位元组，不过由于他们不用在结尾加NULL字元，所以占的记忆体和ASCIZ字串一样。Pascal字串的好处是取字串长度时不必用回圈了。在Pascal里求字串长度不用回圈，只要一个组合组言指令就够了。当然是快太多了。

旧的麦金塔作业系统全都是用Pascal字串。很多其他平台的C程式师也为了速度而用Pascal字串。Excel内部就是用Pascal字串，所以Excel里很多地方的字串长度最多只能到255个位元组，这也是Excel飞快无比的原因之一。

有很长一段时期，如果想在C程式里写一个Pascal字串文字，必须写成：

char str = “\006Hello!”;*

没错，你得自己手工算出位元组的数目，然后写死在字串的第一个位元组。懒惰的程式师会做下面的事，结果就拖慢了程式：

char str = “Hello!”;
str[0] = strlen(str) - 1;

注意这个例子里用的字串既是用NULL字元结尾(编译器做的)又是Pascal字串。我习惯称之为fucked字串 ，因为这比 NULL字元结尾的Pascal字串 好叫多了。不过这里是普通级频道，所以_你_ 还是用较长的名字吧。

我之前省略了一个很重要的问题。记得这一行程式吗？

**char bigString[1000]; *_/ 我永远不知道要配多少记忆体… */_

由于我们今天的主题是位元，所以不应该就这样忽略它。我应该要用正确的写法：找出需要的位元组数然后配置正确的记忆体量。

我不需要这样做吗？

这是一定要的。如果不做的话，某个聪明的骇客读我的程式时会注意到，我只配置了1000个位元组并_期望_ 这数字足够，他们会找出某些聪明的方法，让我把一个长1100位元组的字串strcat 到原本1000位元组的记忆体中，然后就会覆盖堆叠框并改变返回位址，于是当这个函数返回时就会执行到骇客写的程式。当他们说某个程式有一个缓冲区溢出 漏洞时就是指这种东西。从前这可是骇客和蠕虫侵入的头号原因，不过微软 Outlook出来后，入侵就简单到连小朋友都会做了(译注：因为漏洞很多又可以用VBScript写)。

好吧，所以说这些程式师都只是些漏洞百出的傻瓜。他们应该要算出要配置的记忆体数量才对。

不过实际上在C里并_不是_ 这么容易。让我们回到我们的小小范例：

我们_应该_ 要配置多少记忆体呢？让我们试试正确的方式。

char bigString;
int i = 0;
i = strlen(“John， “)
+ strlen(“Paul， “)
+ strlen(“George， “)
+ strlen(“Joel “);
bigString = (char) malloc (i + 1);
*_/ 记得预留结尾NULL字元的空间！*/_
…

我已经晕了。你可能正打算放弃去别的地方。我不怪你，不过请再忍耐一下，因为快要变得很好玩了。

我们必须把每个字串扫描一次才能算出所有字串的总长度，然后在连接字串时又要再扫描一遍。既然用Pascal字串时strlen 动作会变快。或许我们可以写一个能替我们配置记忆体的strcat 。

这时就出现_另一种_ 蠕虫(译注：指下面所讨论的可用链结)：记忆体配置器。你知道malloc 的运作原理吗？malloc 的特性是有一长串由可用记忆体组成的链结串列，名为_可用链结(free chain)_ 。当你呼叫malloc 时会扫描链结串列，找寻大小满足要求的记忆体区块。然后把区块切成两块，一块是你所要求的大小，另一块则是剩下的记忆体，把你要的那块传给你，再把另一块(如果有的话)放回链结串列中。当你呼叫 free 时会把释放的区块加回可用链结。最后可用链结会被切割成很多小块，当你要求大块记忆体时就会找不到大小适合的记忆体。于是malloc 就会逾时并开始扫描可用链结，尝试把相邻的小可用区块合并成较大的区域。这个动作会花个三天半(译注：就是说很慢啦)。这一团混乱的最后结论就是说 malloc 的效能特性绝不会非常快(一定要扫描可用链结)，而且偶而(无法预测)要清理时还会慢到晕倒。(补充一下，令人惊讶的是这和garbage collected系统的效能特性是一样的。所以人们说garbage collection的效能损失有多么巨大，不完全是事实，因为一般的malloc 实作都有着相同类型的效能损失，只不过稍为好一点点。)

聪明的程式师在配置记忆体时会用2的次方为大小(比如4位元组，8位元组，16位元组，18446744073709551616位元组等等)，让 malloc 的潜在不隐定性降到最低。这样可以让可用链结里小碎块的数量降到最低，而有玩乐高积木的人应该都能直觉理解其原因。虽然似乎有点浪费空间，不过很容易就会看出浪费的空间不会超过总空间的一半。所以你的程式最多只会占用所需空间的两倍，这应该不是什么大问题才对。

假设你写了一个聪明的strcat 函数，可以自动重新配置目的缓冲区。这个函数是否应该每次都重新配置到刚好的大小呢？我的老师兼心灵导师Stan Eisenstat建议，当你呼叫 realloc 时每次都应该用原本配置大小的两倍。意思是永远不必呼用realloc 超过**< NOBR>lg n**次，即使是对很大的字串来说也会有很不错的效率特性，而且也绝不会浪费超过一半的记忆体。

总而言之，在这往下到最底层的位元组世界中，生命愈来愈混乱。现在是不是很庆幸不需要再用C写程式呢？我们现在有像Perl、Java、VB、XSLT之类的伟大程式语言，让你永远都不用考虑这种事情，因为程式语言都想办法替你处理好了。不过偶而铅管等基础设施还是会在客厅地板中央突出来，这时候我们就得考虑要用 String 类别还是StringBuilder 类别，或是想想某些类似的差异，因为编译器还不够聪明，无法理解我们尝试完成的每件事，也无法帮助我们_不会_ 疏忽写出油漆工Shlemiel演算法。

上星期我写过如果你的资料是以XML方式储存的话，就无法实作出快速的SQL叙述 SELECT author FROM books 。为了避免有人不懂我在说什么，我再强调一次今天整天都在讲CPU层次的事。这样子应该比较看得懂上面的意思吧。

一个关联式资料库会如何实作SELECT author FROM books 呢？在关联式资料库中，资料表的每一行(举例来说是books 资料表)的位元组数都完全相同，而且各个栏位由列开头起算的偏移量都是固定的。所以举个例子来说，如果books 资料表中每个记录的长度都是100个位元组，而author 栏是位于偏移量23的地方，那么各个作者就会存在第23， 123， 223， 323等位元组的位址。在这个SQL查询中要移到下一个记录时要怎么做呢？基本上只要这样就好：

pointer += 100;

只要一个CPU指令。够快了吧。

现在让我们来看看用XML格式储存的books资料表。

<?xml 废话… >

UI Design for Programmers
Joel Spolsky

The Chop Suey Club
Bruce Weber

来个小问题。要移到下一个记录的程式要怎么写？

呃…

这时候一个好的程式师可能会说，好吧，让我们分析XML转成树状结构存在记忆体里，这样处理起来会相当快。不过这时候CPU要处理SELECT author FROM books 所做的工作量绝对会无聊到让你哭出来。每个编译器作者都知道字汇和语法分析是编译过程中最慢的部份。简单的说，字汇分析和语法分析时牵涉到大量的字串处理(前面已经发现这是很慢的)和大量的记忆体(也是已知很慢的)，然后还要在记忆体中建立一个抽象文法树。而且还要假设你拥有足够的记忆体可以一次载入所有资料。在关联式资料库中，在记录间移动的速度是固定的，而且实际上只要_一个CPU指令_ 。这是刻意设计出来的。另外利用记忆体映对档案，就只要把真正要用的资料由载入对应的磁碟区块即可。在用XML的时候，如果有作前处理预先分析，在记录间移动的速度也是固定的，不过需要大量的启动时间，如果不预先分析，那么在记录间移动的速度就要看之前的记录有多长了，而且不管怎么都要几百个CPU指令。

对我来说，这表示当资料量很大又要求速度时不能用XML。如果资料不多或做的事并不需要速度，XML是个不错的格式。如果你想鱼与熊掌兼得，就得想个方法在XML以外加些诠释资料(metadata)，储存类似Pascal字串中位元组数目的资料。这样能提示资料在档案中的位址，就不需要再去扫描分析了。不过当然不能用文字编辑器去编辑档案了，因为会把诠释资料弄乱，所以其实这也不能算上真正的XML了。

对于那些一直跟着我撑到这里的读者，我希望你已经学到或是重新思考了某些事情。我希望探讨像strcat 和malloc 究竟如何运作这种枯燥的电脑科学一年级课程，能在你面对XML等技术时，协助你思考最新的高层次策略与架构上的决策。至于今天的作业，可以想想为什么全美达(Transmeta)的晶片好像总是卖不好。或者想想为什么最早HTML规格的TABLE设计会烂到让拨接上网的人不能快速的显示大型表格。也可以想想COM既然这么快，为什么跨越行程边界时又快不起了。或者NT设计者为什么会把显示驱动程式放入核心空间而不留在使用者空间呢。

这所有的问题都需要你考虑位元组的层次，而它们也影响到我们在各种架构和策略上所做整体而高层次的决策。我认为电脑科系一年级学生应该由基础开始学起，使用C并由CPU开始一路建立观念，这正是原因。很多电脑科学计划认为Java很「容易」，不用碰无聊的字串/记忆体配置就能学习最酷的物件导向技术，能让你的大程式更加模组化，所以很适合当作入门学习的电脑语言。我对这种想法其实非常的反感。这是一个蕴酿中的教学灾难。毕业生一代代下来会愈来愈堕落，到处写出油漆工Shlemiel演算法而完全不自知，因为他们完全不知道，虽然perl指令看不出来，但是字串的底层操作其实是很困难的。如果你想把某人教好，就得从最底层开始。就像电影「小子难缠」一样。不断的上蜡打蜡。三个星期后轻轻松松就把别的小鬼干掉了。