From The Joel on Software Translation Project

回归原点

作者：周思博 (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的字串用法吧：它们是由一串字节后面接一个null字符(值为0)所组成。这里有两个明显的暗示：

1. 必须整个字串走一遍找到结尾的null字符，才能知道字串在哪里结束(也就是说字串的长度)。

1. 字串里不能有任何零。所以你不能用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来说够好了，不过还是有些问题。举例来说。如果你有一大堆名字，全部都要附加到一个大字串后面：

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[1000];     /* 我永远不知道要配多少内存... */
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

我们应该要配置多少内存呢？让我们试试正确的方式。

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</NOBR>次，即使是对很大的字串来说也会有很不错的效率特性，而且也绝不会浪费超过一半的内存。

总而言之，在这往下到最底层的字节世界中，生命愈来愈混乱。现在是不是很庆幸不需要再用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 废话...>
<books>
     <book>
          <title>UI Design for Programmers</title>
          <author>Joel Spolsky</author>
     </book>
     <book>
          <title>The Chop Suey Club</title>
          <author>Bruce Weber</author>
     </book>
</books>

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

呃...

这时候一个好的程序员可能会说，好吧，让我们分析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指令看不出来，但是字串的底层操作其实是很困难的。如果你想把某人教好，就得从最底层开始。就像电影「小子难缠」一样。不断的上蜡打蜡。三个星期后轻轻松松就把别的小鬼干掉了。

这些网页的内容为表达个人意见
Copyright (c)1999-2005 Joel Spolsky. 所有权利皆予保留