最近评论
正在载入评论列表...
2001年12月11日，星期二
我在自己的Web站点上花了许多时间聊关于令人激动的“巨幅图画”素材方面的内容，比如说.NET与Java啦，XML策略啦，锁定啦，竞争策略啦，软件设计啦，体系结构啦，不一而足。所有这些素材在某种意义上讲，都是一块夹心蛋糕。位于顶层的是软件策略，接下来是诸如.NET之类的体系结构，然后是各种产品，即Java之类的软件开发产品，或者Windows之类的平台。
请继续往蛋糕的底层看。是动态连接库DLL？对象？函数？不！还要看得更低一些！在某个点上，要考虑用编程语言书写的代码行。
这样的层次还不够低，今天我要考察的是CPU——不停地向四周传输字节的小块硅片。假设您是一位编程新手，现在不妨抛弃业已建立的编程、软件与管理等方面的所有知识，重新回到底层的冯·诺依曼（Von Neumann）基本素材上来，并且暂时将J2EE踢出脑海，而只考虑“字节”。
这样做的意义何在？我觉得，人们所犯的一些最大错误（即使在体系结构的最高层）的根源在于，对处于最底层的几个简单事物理解不够或者一知半解。虽然金碧辉煌的宫殿已经建起来了，但地基却是一团糟。所用的建材不是上好的水泥板，而是零乱的碎石。于是乎，宫殿虽然很好看，但浴缸不时在浴室的地面滑来滑去，而让人不知所措。
好了，现在做一次深呼吸。看着我，这个小小的练习将用C语言来完成。
记住C语言中字符串的工作方式：字符串由系列字节组成，后跟一个取值为0[1]的空（null）字符。这里很明确地表明了两点：
1．如果不遍历字符串并查找末尾的空字符，就没有办法知道字符串在何处结束（即字符串长度）。
2．字符串中不能包含任何零。因此，C字符串中不能存放诸如JPEG图片之类的任何二进制数据块。
为什么C字符串要以这种方式工作？那是因为在上面开发了UNIX与C程序设计语言的PDP-7微处理器有一种ASCIZ字符串类型。ASCIZ的中文意思是“末尾有一个零的ASCII”。
这是存放字符串的惟一途径吗？不是。事实上，这是存放字符串最差的方式之一。对于重要程序、API、操作系统与类库，用户应该像躲避瘟疫一样地避开使用ASCIZ字符串。为什么呢？
下面从编写函数strcat的一个代码版本入手进行讨论。该函数的功能是将一个字符串附加在另一个字符串之后。
void strcat( char* dest, char* src )
{
while (*dest) dest++;
while (*dest++ = *src++);
}
对代码稍作研究，就可以明白这个函数正在做些什么。首先，它遍历第一个字符串以寻找空终止字符。一旦找到空字符，就逐字符将第二个字符串一次性拷贝到第一个字符串之后。
虽然这种操作与串接字符串的方法对于Kernighan与Ritchie[2]来说已经足够好了，但是也有它的问题。比如，假设有一串名字要在一个大字符串中串接起来，那就会暴露出来一些问题：
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码！”他的老板吼道。“这太令人难以接受了！第一天你干的工作量是今天的10倍！接下来是怎么回事？”
“我尽力了，”Shlemiel说道。“一天一天下去，我离油漆罐越来越远！”
（对于规模特大的应用来说，到底要“赊”多大存储空间[3]？）这则蹩脚的笑话很贴切地说明了，如果像前面给出的代码那样使用strcat函数将会出现什么结果。由于strcat的第一部分代码必须每次都扫描整个目的字符串，以反复寻找那个捉摸不定的空终止字符，因此该函数将比所希望的速度慢得多，并且它根本谈不上存在伸缩性。你每天使用的许多代码都有这个问题。很多文件系统是以一种在一个目录中放太多的文件的不恰当方式来实现的。说它不恰当的原因在于，一旦目录中达到成千上万个条目时，其运行性能就开始急剧下降。试着打开一个装填过度的Windows垃圾箱来看看运行情况如何——要花几个小时才能显示出文件，它与所包含的文件数目基本上不成线性关系。这里面的某个地方必定存在一个Shlemiel喷涂算法。不管什么时候，只要某个应用项目看起来应该具有线性性能，可它却表现出n2的性能，那么就得寻找隐藏于其中的那些Shlemiel们。它们通常是被库文件隐藏起来了。看到一个循环体中出现一列或者一个strcat函数未必要大声嚷嚷“找到n2了”，但那一定是问题之所在。
