创建高效的MSXML应用
code{font-family:"courier new";color:#006}
pre{font-family:"courier new";background-color:#e1e1e1;color:#006}
a {text-decoration:underline}
创建高效的MSXML应用
原作：Ben Berck 2002.03.06
翻译： onestab 2002.08.03
我阅读过几十篇书籍和文章，都是为那些需要用XML做些事情的程序员提供指导的。这些资料对初学XML开发的程序员是有帮助的，并且带有一些短小的例子（都在10KB以下，通常小于1KB）。
在这些例子中用到的技术并不总适用于实际开发，尤其是处理特别巨大的文件时。比如，当你需要处理122MB大小的XML文件，每个文件都源于不同的应用程序时会发生什么？
这就是我的团队在尝试为公司开发基于服务器的XML执行引擎，以及试验一个允许任何人上传文件并将其转换为XML, SVG,HTML等格式的网站时所面临的两难境地。简言之，我们的目的是要能够处理任何东西，从Microsoft Word到Quark文件，哪个都不算小。
显然最先想到的就是增加内存和提高处理器的处理能力。不过这也太容易了些，因为我们想到了大O问题。还记得大学里学过的大O表示法吗？一个算法可以用所占用的处理器周期(时间)和消耗的内存(空间)与其所要处理的元素数量之比来衡量。大O表示法代表了算法固有的适用范围，比如一个时间复杂度为O(n2)或空间复杂度为O(n2)的算法的效率较低，因为它极大地限制了计算机所能处理的问题的规模。
当我们试图用一个支持XML DOM的解析器解析一个很大的XML文件时，就首先遇到了这个大O问题。这种方案是将整个XML文件以树型结构装入内存。装入或存储文件所用的时间为O(n)。初看起来似乎可以接受，然而，除了简单的装入文件，要做的事情还有许多。
我们还要写代码读这个DOM，分析它，让它干活。我们曾经假定这种分析（比如查找某个元序）所花的时间为O(n)。出乎我们的意料，实际所花的时间是我们无法接受的O(n2)。
我们通过分析找出了问题的关键：getItem。这是许多DOM程序员最常用的简单函数。就像检索一个数组一样，这种方法简单而且好用 -- 至少对小的XML文件来说是如此。然而，DOM树实际上更像一个链表，无法随机访问。DOM中这个方法的实现必须要遍历链表。在包含n个元素的链表中循环时，将会有0.5(n2-n)次引用，即O(n2)。从文档中我们很快发现DOM中的另一个函数nextNode也能提供所要的这种功能。我们于是就更改了这行代码，很快就得出了结果（如下表所示）。对于这种大型XML来说，改变一行代码就会显著地提高性能。
10,000 个节点
100,000 个节点
1 百万个节点
getItem( i )
15 秒
~23 秒
> 1 小时 (未完成)
nextNode( )
1 秒
12 秒
~200 秒
服务器产品的开发者都知道，当你想同时处理多个用户和进程时，内存是极其宝贵的资源。只是简单地把getItem改为netNode并不能阻止DOM很快地消耗掉你的服务器内存。
对于大多数的处理任务，没有必要将整个XML文件装入内存。XML开发人员都认为在处理大文件时，像SAX之类的基于事件的解析器是个更好的选择，因为它不须将多个元素同时装入内存。开始处理元素时调用一个函数，干完活后，就弃掉它。元素被SAX解析器丢弃后，所处理的XML文件的哪部分应当保存在内存中（或相反）要由开发者做出决定。
我们很快决定从DOM转到SAX。最终，我们的核心部件之一就能简单地抽取大型XML文件并存到另一个文件，不需要保存任何状态信息。但是，我们追求的是O(1)的空间性能，这也是任何精巧的服务器应用程序所渴求的。
我们采用MSXML3.0所带的SAX来处理文档。微软的MXXMLWriter设计了一个ContentHandler，它可以接受与SAX同样的事件入口参数。在微软给出的示例中，整个过程是互相关联的，这就意味着你可以高效地将XML文件复制到MXXMLWriter。我们简单地增加了些代码，将这种复制操作仅限定于SAX解析过程中所遇到的元素子集。不过，现在它还不在磁盘上，在将其送回到磁盘之前，UTF-8编码出了些小问题。
还有另一个问题。MXXMLWriter将它的所有输出都放在一个名为output的字符串属性中。这就是我们在开发服务器应用程序时所遇到的另一个大O问题。MXXMLWriter将收集到的子文件都放在内存中，当我们准备将它存回磁盘时，必须要申请一块几乎同样大小的内存进行Unicode到UTF-8的转换。因为子文件的大小随着原来的XML文件的大小呈线性增加，我们的O(1)空间算法降为O(n)，效果不好。
微软关于IMXWriter的文档中的output属性的说明部分给我们带来了希望：“你可以将这个属性设置为任何IStream接口的实现，结果文件将被写入所提供的IStream.”
听起来令人鼓舞，但是由于缺少示例代码和有关IStream接口的COM详细资料却令我们很为难。最终，我们发现，一旦你用一个恰当设计的IStream钩起了MXXMLWriter，程序的其余部分是不变的。每当MXXMLWriter积累起4,096个Unicode字符(占用8 KB内存)，就会调用IStream的Write方法，将缓冲区的内容转换为UTF-8(另外占用3.3 KB)并写入文件。不管文件或子文件有多大，这种设计一次消耗的内存不超过几十KB。这就是所谓的O(1)空间性能，意味着现在你可以到忙碌的服务器上的其它地方去寻找瓶颈了。
我准备了实现IStream的IFileStream类的代码样本，以及将缓冲区内容从Unicode转换为UTF-8的代码，xml_article.cpp
如果你想看看我们正在使用的XML执行服务器，请访问http://createxml.com。
