最近评论
正在载入评论列表...
仅仅为了弄清字符串有多大，就必须一次扫描完所有的字符串，然后在串接时还要再次对它们进行扫描。如果使用Pascal字符串，至少strlen操作是很快的。也许，我们可以编写一个能够为我们重新分配内存的strcat函数版本。
它将另外一整罐蠕虫（内存分配器）打开。你知道malloc函数是如何工作的吗？malloc函数的实质体现在，它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。调用malloc函数时，它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后，将该内存块一分为二（一块的大小与用户请求的大小相等，另一块的大小就是剩下的字节）。接下来，将分配给用户的那块内存传给用户，并将剩下的那块（如果有的话）返回到连接表上。调用free函数时，它将用户释放的内存块连接到空闲链上。到最后，空闲链会被切成很多的小内存片段，如果这时用户申请一个大的内存片段，那么空闲链上可能没有可以满足用户要求的片段了。于是，malloc函数请求延时，并开始在空闲链上翻箱倒柜地检查各内存片段，对它们进行整理，将相邻的小空闲块合并成较大的内存块。
这要用去三天的时间。经过一通“鸡飞狗跳”的混乱状况之后所得到的最终结果变成：malloc的性能表现为永远也快不起来（总是要遍历空闲链），有时候甚至显得不可预测，在清理内存时慢得使人害怕。（顺便说一下，这与垃圾收集系统的性能特征类似，不令人吃惊才怪呢。可见，人们做出的关于垃圾收集行为如何导致性能损失的所有断言都不完全成立。因为典型的malloc实现形式具有同样的性能损失，尽管略显温和。）
聪明的程序员通过总是分配大小为2的幂的内存块，而最大限度地降低潜在的malloc性能丧失。也就是说，所分配的内存块大小为4字节、8字节、16字节、18446744073709551616字节，等等。至于说原因，任何与Lego打过交道的人应该是一目了然的，这样做最大限度地减少了进入空闲链的怪异片段（各种尺寸的小片段都有）的数量。尽管看起来这好像浪费了空间，但也容易看出浪费的空间永远不会超过50%。因此，程序不会使用大小超过所需尺寸两倍的内存，这并不是大得不得了。
现在，不妨假设自己要编写可以自动重新分配目的缓冲区的“智能”strcat函数。总是应该分配所需要的实际尺寸吗？我的老师兼顾问Stan Eisenstat [1]建议，在调用realloc函数时，应分配出两倍于以前所分配的内存。这意味着，用户决不会调用realloc函数达lg（n）次以上。该性能特征即使对于大型字符串也可以忍受，并且决不会浪费多于50%的内存。
总而言之，在字节领地里，越往下走，生活就显得越来越凌乱。你难道不对自己再也用不着使用C语言编写内存分配函数而感到高兴吗？我们拥有Perl、Java、VB与XSLT这些伟大的编程语言，它们再也不会让你去考虑此类事情。不用问为什么，它们只管去做好了。
不过，竖直的基础结构偶尔也会从起居室的中部凸现出来，于是我们就得考虑是否使用String类，或者StringBuilder类，或者相关方面的一些差别，因为编译器仍然没有聪明到能够理解我们正在尽力完成的一切，从而试图帮助我们不在无意之中写出一些Shlemiel喷涂算法。
这篇随笔文章在我写了一篇说明以XML形式存储的数据不能用SELECT author FROM books实现性能很快的SQL语句的即兴网评[2]之后，受到了不友善攻击。正是因为大家没有理解我在说些什么，以及既然我们整天都在CPU周围打滚，这个主张可能才更显得有意义。
关系数据库是如何实现SELECT author FROM books的？在关系数据库里，关系表（例如books表）的每一行具有相同的字节长度，而每个字段距离各行开头的偏移量是大小固定的。因此，如果books表的每条记录是100个字节长，并且author字段处在偏移量为23的位置，那么作者们的名字就存放在第23，123，223，323等位置的字节处。移到该查询结果的下一条记录的代码是什么？大体上讲，这条代码为：
pointer += 100;
只用了一条CPU指令！快，快，实在是快！
现在我们来看XML中的books表。
<?xml blah blah>
<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解析成内存中的树结构吧，以便能够相当快速地处理它。在这里，针对SELECT author FROM books语句，CPU必须完成的工作量绝对会将人折磨至疯。正如每个编译器设计人员都知道的那样，语法分析与解释是在编译处理过程中最慢的部分。只要谈我们在解释、分析与建立抽象的内存语法树时，发现它涉及许多处理起来很慢的字符串素材，以及许多执行起来很慢的内存分配内容就够了。
况且，这还假定了有足够的内存用于一次性加载整个内容。对于关系数据库来说，在记录之间执行移动操作的性能是固定不变的，实际上它不过是一条指令的事。这是费了好大的力气有意为之的。同时，因为得益于内存映像文件，用户只需加载将要实际使用的那些磁盘页面。
对于XML来说，如果要做预分析的话，那么在记录之间执行移动操作的性能是固定不变的，只是启动时间极大；如果不做预分析，那么在记录之间执行移动操作的性能根据它前面的记录长度而变化，并且CPU指令长达好几百条。
这在我看来意味着，如果用户讲究性能，并且数据量很大，那么就不能使用XML。如果只有一点儿数据，或者事情做得不必很快，那么XML不失为一个好的形式。并且，如果用户确实希望鱼与熊掌兼得，就必须找出一种途径用于紧靠XML存放元数据。元数据跟Pascal字符串中用于计数的字节的作用差不多，它向用户给出提示信息，以便不用去分析与扫描字符串就能确定它们在文件的什么地方。当然，这样一来用户就不能使用文本编辑器去编辑文件了，因为那会搞乱元数据，从而它不再是真正的XML了。
对于听众中三个仍然在这一点上支持我的和颜悦色者，我希望你们已经学到了些东西或者重新考虑过一些事情。我希望针对诸如strcat与malloc函数到底如何工作之类的那些令人厌烦的一年级计算机课程素材所做出的思考，已经向你们提供了新的工具手段，从而在处理XML之类的技术问题时，制定出最新的关于顶层策略和体系方面的决定。
作为家庭作业，思考一下为什么Transmeta芯片总是会觉得行动迟缓？为什么关于TABLES的原始HTML说明设计得如此之差，以致Web页面的大型表不能够快速地显示给使用调制解调器的人们？为什么COM是如此棒，但在跨越进程边界时却不是这样的？还有，为什么NT人将显示器驱动程序放在内核空间，而不是用户空间？
所有这些事情都要求用户去思考字节，字节影响着用户在各种体系与策略方面做出决定。这就是我为什么坚持一种教学观点——大学一年级学生需要从基础学起，即用C语言以及从CPU开始向上逐步构建自己程序设计技能——的原因。我真的从心底里厌烦在多得出奇的计算机课程计划中，将Java看做是一门好的入门语言的做法。这些计划的理由是：Java语言虽然很“简易”且不会陷入所有那些令人厌烦的字符串与malloc素材之中，但是可以学习特别棒的OOP知识，从而使大型程序具有如此之多的模块化特性。
这是一场即将发生的教学灾难。一届又一届的毕业生正在侵袭我们，他们正在忽左忽右地创建着Shlemiel油漆匠算法，而他们甚至还没有意识到这一点。原因在于，他们根本就没有那种字符串在深层次上处理起来很困难的理念，即使在Perl脚本上也不能很好地看到那一点。如果想在某个方面把别人教好，自己首先得从最底层开始研究。这就像空手道功夫小子要做的事情一样。打蜡，剥蜡。打蜡，剥蜡。这样的过程要进行三个星期。然后，他就可以轻松击败其他小孩了。
