Joel Spolsky 撰文：回到基础，从CPU和字节重新理解编程

我们在本网站上花了很多时间讨论那些令人兴奋的宏大话题，比如 .NET 与 Java 之争、XML 策略、锁定效应、竞争策略、软件设计、架构等等。可以说，所有这些东西都像是一层层叠起来的蛋糕。最上面一层是软件策略。再往下，我们考虑像 .NET 这样的架构；再往下，是单个产品：像 Java 这样的软件开发产品，或者像 Windows 这样的平台。 请再往蛋糕的更下层走。DLL？对象？函数？不！还要往下！到了某个层次，你考虑的就是用编程语言写出来的代码行。 还不够低。今天我想聊聊 CPU。一小块硅片在那里搬运字节。假设你是一个初学者程序员。抛开你积累的关于编程、软件、管理的一切知识，回到最底层的冯·诺依曼基本概念。暂时把 J2EE 从脑子里清空。想想字节。 为什么要这么做？我认为，人们即使在最高的架构层面上犯下的一些最大错误，也源于对最底层几个简单事物的理解薄弱或错误。你建起了一座宏伟的宫殿，但地基一团糟。下面不是一块漂亮的水泥板，而是一堆碎石。所以宫殿看起来不错，但浴缸偶尔会滑过浴室地板，而你完全不知道发生了什么。 所以今天，深呼吸。请跟我一起做一个小练习，用 C 语言来进行。 记住 C 语言中字符串的工作方式：它们由一串字节组成，后面跟一个空字符，其值为 0。这有两个明显的含义： C 字符串为什么这样工作？因为 UNIX 和 C 语言赖以发明的 PDP-7 微处理器有一种 ASCIZ 字符串类型。ASCIZ 的意思是“ASCII，末尾带一个 Z（零）”。 这是存储字符串的唯一方式吗？不，事实上，这是存储字符串最糟糕的方式之一。对于非平凡的程序、API、操作系统、类库，你应该像躲避瘟疫一样避免 ASCIZ 字符串。为什么？ 让我们先写一个 strcat 的代码版本，这个函数把一个字符串追加到另一个字符串后面。 void strcat( char* dest, char* src ) while (dest) dest++; while (dest++ = src++); 稍微研究一下这段代码，看看我们在做什么。首先，我们遍历第一个字符串，寻找它的空终止符。找到之后，我们遍历第二个字符串，一次一个字符地复制到第一个字符串上。 这种字符串处理和字符串拼接方式对 Kernighan 和 Ritchie 来说已经够用了，但它有问题。问题在这里。假设你有一堆名字，想把它们追加成一个大字符串： char bigString[1000]; / 我永远不知道该分配多少 / bigString[0] = '\0'; strcat(bigString,"John, "); strcat(bigString,"Paul, "); strcat(bigString,"George, "); strcat(bigString,"Joel "); 这能行，对吧？是的。而且看起来干净漂亮。 它的性能特征是什么？它达到最快速度了吗？它的扩展性好吗？如果我们有一百万个字符串要追加，这会是好方法吗？ 不是。这段代码用的是“油漆工谢尔米尔算法”。谢尔米尔是谁？他就是这个笑话里的那个人： 谢尔米尔找到一份街道油漆工的工作，负责给马路中间的虚线刷漆。第一天，他拿着一罐油漆上路，刷完了 300 码。 “干得不错！”老板说，“你是个快手！”然后付给他一个戈比。 第二天，谢尔米尔只完成了 150 码。“嗯，这不如昨天，但你还是个快手。150 码也还过得去，”然后又付给他一个戈比。 第三天，谢尔米尔刷了 30 码。“只有 30 码！”老板吼道。“这不可接受！第一天你干了十倍的工作量！怎么回事？” “我没办法，”谢尔米尔说。“每天我都离油漆罐越来越远！” （附加题：实际数字是多少？）这个蹩脚的笑话恰好说明了当你像我刚才那样使用 strcat 时发生了什么。因为 strcat 的第一部分每次都必须扫描目标字符串，一遍又一遍地寻找那个该死的空终止符，所以这个函数比它需要的慢得多，而且完全不具备良好的扩展性。你每天使用的很多代码都有这个问题。许多文件系统的实现方式使得在一个目录里放太多文件是个坏主意，因为当一个目录里有成千上万个项目时，性能会开始急剧下降。试着打开一个塞得过满的 Windows 回收站，看看实际效果——它要花好几个小时才能显示出来，这显然不是文件数量的线性关系。那里一定藏着某个“油漆工谢尔米尔算法”。每当某件事看起来应该是线性性能，却似乎表现出 n 平方性能时，就去找找隐藏的谢尔米尔。它们常常被你的库隐藏起来。看到一列 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 平方，所以当你有大量内容要拼接时，它不会出现性能退化。

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）