Saxon: 剖析 XSLT 处理器

XSLT 优化中有哪些高超技术?

本文描述了 XSLT 处理器(在本例中是作者的开放源码 Saxon)的实际工作原理。虽然已经存在了一些开放源码 XSLT 实现(请参阅 参考资料),但椐我们所知,目前还没有一个公开了其工作原理。本文打算填补这方面的空白。它描述了 Saxon 的内部工作,并演示了该处理器如何实现 XSLT 优化。它还说明了还有多少工作有待完成。本文假设您已经知道 XSLT 是什么以及它的工作原理。(如果您需要重温 XSLT 的基础知识,请参阅 Michael Kay 撰写的本文的姐妹篇,它给出了 XSLT 的概述。)

Michael H. Kay (mhkay@iclway.co.uk), 作家

作为 Saxon XSLT 处理器和 Wrox 书籍 XSLT Programmer's Reference 的作者,Michael Kay 在 XML 世界可谓大名鼎鼎。他的背景(以及很久以前的博士学位)是在数据库技术方面。从那时起,他设计了 Codasyl,这个关系型、面向对象和纯文本的数据库软件。



2001 年 2 月 01 日

我希望这篇文章能达到几个目的。首先,我希望它可以让样式表作者了解 XSLT 可以实现哪种类型的优化,以及哪些结构当前还没有优化。当然,这种优化的细节在各个处理器以及各个发行版之间都各不相同,但我希望通过阅读本文可以让您更好地了解幕后工作。其次,它描述了我认为当前的 XSLT 技术(我认为在这方面,Saxon 与其它 XSLT 处理器没有高级与否的区别),而且它还描述了我认为该技术将来进一步发展的领域。我希望本文可以激励那些有编译器和数据库优化经验的研究人员在这个领域中做进一步的工作。

最后(也是最重要的一点),本文打算成为初学者学习 Saxon 源代码的起点。它并不是简单地浏览代码,也没有假设您要深入到那一层。但是如果您不满足于钻研 JavaDoc 规范或源代码本身,这篇文章会对您有所帮助。

一些说明:所描述的版本是 Saxon 6.1,而且还讲述了代码的功能性故障,这些代码不能始终映射成软件包和模块结构。例如,本文将编译器和解释器描述成单独的功能组件。但在实际代码中,例如处理 <xsl:choose> 指令的模块既包含编译时代码,也包含运行时代码,以支持该指令。如果想要将本文用作代码的指南,我已经包括了对软件包和模块的特殊引用,这样您可以知道到哪里查看。

首先,我将描述 Saxon 产品的设计。Saxon 是一个 XSLT 处理器。即,它是使用 XML 文档和样式表作为输入,然后生成结果文档作为输出的程序。(我假设有 XSLT 的知识,如果您是初学者,可以阅读本文的 姐妹篇作为介绍。)

Saxon 包括了最初由 David Megginson 编写的开放源码 AElfred XML 语法分析器的副本,尽管它可以与其它实现 Java SAX 接口的语法分析器一起使用。Saxon 还包括了一个串行化器,用于将结果树转换成 XML、HTML 或纯文本。从技术上看,串行化器并不是 XSLT 处理器的一部分,但它在实际使用中是必不可少的。

Saxon 实现了 TrAX(XML 的 转换 API)接口,该接口被定义成 JAXP 1.1 Java 扩展的一部分。理解本文无须了解这个接口,但了解 TrAX 的体系结构有助于您理解构造 Saxon 的方法。

Saxon 体系结构

图 1 显示了 Saxon 软件的主要组件。

图 1. Saxon 体系结构
Saxon 体系结构

树构造器创建源 XML 文档的树表示法。它用于处理源文档和样式表。其中有两个部件:

  • XML 语法分析器 (包 com.icl.saxon.aelfred )读取源文档,并通知事件,如元素的开始和结束。
  • 树构建器 (模块 com.icl.saxon.Builder )被通知这些事件,并使用它们来构造 XML 文档的内存表示法。

语法分析器和构建器之间的接口是 Java SAX2 API。尽管 SAX API 仅经过非正式的标准化,但它由六个可免费获取的 XML 语法分析器实现,允许 Saxon 可交替地与这些语法分析器中的任何一个一起使用。在语法分析器和树构建器之间有一个组件,我将它称作 Stripper (我无法抗拒这个名称): Stripper 根据样式表(模块 com.icl.saxon.Stripper )中的 <xsl:preserve-space><xsl:strip-space> 伪指令,在空白文本节点被添加到树之前,除去这些节点。 Stripper 是 SAX 过滤器的一个良好示例,这是以 SAX 事件流作为输入,并生成另一个 SAX 事件流作为输出的一段代码。从更宏观的角度看,整个 Saxon 转换还可以当作 SAX 过滤器来进行操作。这个方法使将一个复杂的转换分解成以流水线排列的一系列简单转换变得非常容易。

树浏览器正如其名,允许应用程序通过浏览层次结构来从树中选择节点。由构建器组件构造的树表示法是 Saxon 的专利。这就是 Saxon 与其它 XSLT 处理器的不同之处:其它一些 XSLT 处理器使用通用 DOM 模型作为其内部树。使用 DOM 的优点是可以用第三方软件生成树。为其它目的构造的树可以直接作为转换的输入而提供,并且等同地,基于 DOM 的应用程序可以直接使用转换的输出。

在 Saxon 中,我注意到通过使用 DOM 而提供的互操作性带来了极高的成本。首先,DOM 树模型与 XSLT 处理器所需的 XPath 模型有本质上的差别,这种差异会增加将一个模型映射成其它模型所带来的运行时成本。例如,DOM 树可以包含 XPath 模型不需要的信息,如实体节点。其次,DOM 树可以就地更新,而 XSLT 处理模型意味着只能按顺序编写树。设计只能按顺序写的树可以实现效率。例如,每个节点可以包含一个序号,这就易于按连续的文档顺序排序节点,这是一个常见的 XSLT 需求。最后,DOM 实现通常包括许多同步代码以使多线程化访问安全。由于 XSLT 处理模型是“写一次读多次”的,同步逻辑可以变得更简单,使浏览树变得更快。

实际上,您将见到,Saxon 提供了两种不同的树实现,每一个都有其自己的构建器和浏览类(包 com.icl.saxon.treecom.icl.saxon.tinytree )。这两种实现提供不同的性能取舍。

样式表编译器在执行之前对样式表进行分析。它并不生成可执行代码;而是生成样式表的装饰树 表示法 ,在其中确认和分析这个样式表中的所有 XPath 表达式,并解析所有交叉引用,以及预先分配堆栈框架存储槽,诸如此类。因此,样式表编译器执行构造决策树的重要功能,以便在执行时查找正确的模板规则以处理每个输入节点;试图将每个节点与每个可能的模式进行匹配是非常费时的。然后在转换时,装饰树开始进入角色以驱动样式表处理。(编译器分布在 com.icl.saxon.style 软件包的类之间,特别是方法 prepareAttributes()preprocess()validate() 。)

在某个阶段,Saxon 确实包括了生成可执行 Java 代码的样式表编译器。但是,它只处理 XSLT 语言的一个子集,并且随着开发的发展,通过减少完整编译来达到性能增长。最后,我放弃了这个方法,因为开发复杂性不断增加而性能优势却在下降。当前市场上还没有完整的 XSLT 编译器。Sun 已经制作了一个编译器的 alpha 发行版,叫做 XSLTC,虽然仍处于开发的早期阶段,但看起来很有前途(请参阅 参考资料)。

由 Saxon 的样式表编译器(在 com.icl.saxon.style.XSLStyleSheet 类中)生成的装饰树不能保存到磁盘,因为将树读到内存比重新编译原始代码还要费时(很可能是因为已经它增加的大小)。只要树还保留在内存中,您就可以重用它。树封装在一个叫作 PreparedStyleSheet 的对象中,该对象实现了 JAXP 1.1 中的 javax.xml.transform.Templates 接口。在服务器环境中使用同一个样式表来转换许多不同的源文档是很常见的。要允许这样做,已编译的样式表在执行时应该严格是只读的,以允许在多个执行线程中同时使用它。

Saxon 处理器的核心是 样式表解释器com.icl.saxon.Controller 类,它实现 JAXP 1.1 中的 javax.xml.transform.Transformer 接口)。该解释器使用装饰样式表树来驱动处理。按照语言的处理模型,它首先查找处理输入树根节点的模板规则。然后,它对该模板规则求值(或者按标准行话是“实例化”)。

样式表树使用不同的 Java 类来表示每种 XSL 指令类型。例如,考虑以下指令:

<xsl:if test="parent::section">
 <h3><xsl:value-of select="../@title"></h3>
</xsl:if>

这段代码的作用是如果源树中的当前节点有类型为 <section> 的父代元素,那么将 <h3> 元素输出到结果树中;生成的 <h3> 节点的文本内容是父代 sectiontitle 属性的值。

在装饰树上,由图 2 中显示的结构表示这段代码。

图 2. 装饰样式表树
装饰样式表树

样式表中的元素直接映射成树上的节点,如 表 1 所示。所有表示元素的 Java 对象都是 com.icl.saxon.style.StyleElement 的子类,而它又是 Saxon 树状结构中元素节点的缺省实现 com.icl.saxon.tree.ElementImpl 的子类。这两个 XPath 表达式由树节点引用的 com.icl.saxon.expr.Expression 对象表示。

表 1. 样式表元素及其对应的 Java 类
元素或表达式…………由此 Java 类中的对象表示
com.icl.saxon.style.StyleElement 的子类)
<xsl:if>com.icl.saxon.style.XSLIf
<h3> (输出,不是指令) com.icl.saxon.style.LiteralResultElement
<xsl:value-of>com.icl.saxon.style.XSLValueOf .
XPath 表达式com.icl.saxon.expr.Expression

执行 <xsl:if> 指令会执行相应 XSLIf 对象的 process() 方法。该方法访问测试 Expression 对象,该对象有一个方法 evaluateAsBoolean()evaluateAsBoolean() 用于对表达式求值以返回一个布尔结果。(这是一个优化:可以使用直接的 evaluate() 调用,然后将结果转换成一个布尔值,如规范中所描述的那样。布尔值通常会使求值过程变得更迅速。例如,当实际值或表达式是一个节点集时,一旦找到节点集的一个成员时,就可以立即知道最终的布尔值结果。)

如果 evaluateAsBoolean() 的结果是真,则 process() 方法会调用 样式表树上 XSLIf 节点的所有子节点的 process() 方法。如果结果不是真,它就直接退出。

同样, LiteralResultElementprocess() 方法将元素复制到结果树中,并处理 LiteralResultElement 的子元素,而 XSLValueOf 对象的 process() 方法将 select 表达式当作字符串进行求值,并将结果复制成结果树的文本节点。

因此,样式表解释器的主要组件是:

  • 用于每个包含那个指令逻辑的样式表类型的类
  • 一组支持类,用于处理变量的绑定、运行时上下文的管理以及与模板规则匹配的节点
  • 用于对 XPath 表达式求值并返回这些值的 XPath 表达式解释器

XPath 解释器(包 com.icl.saxon.expr )非常符合 解释器 设计模式,该模式是由 Gamma、Helm、Johnson 和 Vlissides 描述的面向对象软件的 23 种经典模式中的一个。XPath 语法的每个结构都有一个对应的 Java 类。例如, UnionExpr 结构(写作 A|B ,并表示两个节点集的联合)由 com.icl.saxon.expr.UnionExpression 类实现。通常在编译样式表时执行的 XPath 表达式语法分析器(模块 com.icl.saxon.expr.ExpressionParser ),生成直接反映表达式的语法分析树的数据结构。要对表达式求值,该结构中的每个类都有一个 evaluate() 方法,它负责返回表达式的值。如果是 UnionExpression 类, evaluate() 方法将对两个操作数求值,检查在这两种情况下节点集的结果,然后使用排序合并策略组成联合。

在 Gamma 描述的设计模式中, evaluate() 方法使用 Context 参数。 Context 对象封装了对表达式求值所需的所有上下文信息。

包括:

  • 关于当前节点和当前节点列表(例如对 XPath 函数 position()last() 求值所必需的)的信息
  • 访问保存变量值的 com.icl.saxon.Bindery 对象
  • 访问表达式作用域中 XML 名称空间列表,在测试名称的等价性时需要

XPath 解释器还包括扩展 Gamma 的基本解释器模式的优化特性

例如:

  • 每个表达式类都有一个 simplify() 方法,以允许表达式重写。 这就可以执行上下文独立的优化。有时,这会导致生成不同的 XPath 表达式(例如 title[2=2] 重写成 title ,而 count($x)=0 重写成 not($x) )。表达式重写通常使用表示特殊情况的内部类。例如,表达式 section[@title] 返回拥有标题属性的当前元素的所有子 <section> 。由于上下文中出现子表达式 @title ,就可能使用专用类来重写它,这个专用类用于测试当前节点上是否出现给定属性,并返回一个布尔值。
  • 每个表达式类都有一个 evaluate() 方法和一个 enumerate() 方法 。这(在表达式表示节点集的情况下)允许递增检索节点,而不是立即检索所有节点。这允许按关系数据库系统采用的典型方式进行流水线执行。例如,通过合并其两个操作数的枚举使在联合表达式上调用 enumerate() 可行。只要已经按文档顺序排序了这两个操作数,就不必为中间节点集分配内存。
  • 可以逐渐 减少表达式,以消除它们的相关性。 在函数型语言中已经广泛使用的表达式减少的概念,而且此概念特别适用于优化语言,如 XPath。每个表达式类都有一个 getDependencies() 方法,该方法返回关于方法依赖的上下文方面的信息。这就使某些优化成为可能。例如,如果表达式不使用 last() 函数,那么就不必执行先行处理来确定上下文列表中有多少元素。此外,每个表达式都有一个 reduceDependencies() 方法,它返回一个等价的表达式,在该表达式中消除了指定的相关性,而其余的都保留下来。这有助于重复使用同一个表达式。例如,在执行排序之前,减少了排序键表达式,以消除变量上的相关性(因为这些变量与列表中的每个节点相同),但不消除当前节点上的相关性(它将与列表中的每一项都不同)。

XSLT 语言给了处理器很大的自由,让它可以按其选择的顺序对表达式求值,因为它没有副作用。Saxon 中的常规策略是尽早对标量值求值(字符串、数字、布尔值),而尽可能晚对节点集求值。尽早对标量值求值可以通过只执行一次操作来实现优化。延迟对节点集求值可以避免在内存中不必要地保留大的列表,这样可以节省内存。它还可以节省时间,如果对于节点集的唯一操作就是测试它是否是空的(通常是这种情况),或者对它的第一个元素进行赋值。

最后, 输出器 组件( com.icl.saxon.output.Outputter 类)用于控制输出进程。Saxon 的结果树通常不在内存中具体化 -- 因为它的节点总是按文档顺序编写,一旦将它们输出到结果树中,就可以串行化这些节点。实际上,转换拥有的不是单个结果树,而是结果树的更改堆栈,因为 XSL 指令,如 <xsl:message><xsl:attribute> ,有效地将输出重定向到一个内部目的地,而 <xsl:variable> 构造了一个结果树片段,它实际上是以它自己为标题的独立树。这些元素的解释器代码调用输出器切换到新目的地,然后还原到原始目的地。

使用串行化器将外部输出写到文件中。逻辑上,这将使用结果树作为输入,并将它转成文本文件文档。实际上,如您所见,结果树没有在内存中具体化,所以串行化器将按文档顺序一次交出树的一个节点。使用类似与 SAX2 的接口 ( com.icl.saxon.Emitter ) 来显示这个节点流:它在如何表示名称和名称空间等细节方面与 SAX2 略有不同。如在 XSLT 推荐书中定义的,对于 XML、HTML 和纯文本输出,有独立的串行化器。Saxon 还允许将树提供给用户以便进一步处理,或者作为输入提供给另一个样式表。这允许按顺序应用几个样式表来完成多阶段转换。


性能

良好的性能当然是驱动 Saxon 设计的一个因素,仅次于符合 XSLT 规范。部分原因是这对于用户来说很关键,而且因为在可免费获取几个 XSLT 处理器的情况下,性能是区分优劣的主要因素。

这一节讨论了影响 XSLT 处理器性能的一些因素,以及在每种情况下 Saxon 用于提高速度的策略。


Java 语言问题

通常都认为 Java 很慢。这有其合理性,但需要仔细验证这种说法。

许多人认为造成 Java 速度慢的原因是它生成解释型字节码,而不是本机代码。以前是这样,但现在有了 JIT 编译器后情况就不同了。原始代码执行速度通常几乎与用编译型语言(如 C 语言)编写的等价代码相同(有时更快速)。

然而 Java 可能有内存分配的问题。与 C 和 C++ 不同,Java 自己管理内存,它使用无用信息收集器来释放不想使用的对象。这给程序员带来了很大的便利,但却易于创建浪费内存的程序:它们会因为过多使用虚拟内存而崩溃,或者因为过分频繁地分配和释放对象而使无用信息收集器过度操劳。

某些编码技巧使内存分配问题减至最少。例如,使用 StringBuffer 而不用 String ,使用可再用对象的池,等等。诊断工具可以帮助程序员确定何时使用那些技巧。使代码更快需要许多调整,但经论证这仍比使用诸如 C++ 之类的语言更简便,在这些语言中必须手工管理所有内存分配。

XSLT 处理给 Java 带来了实现树状结构的特殊挑战。Java 强行在每个对象的大小方面增加了相当大的开销(多达 32 个字节,取决于所使用的 Java VM)。这通常会在内存中生成一个比源 XML 文件大许多倍的树状结构。例如,空元素 <a> (在源文件中是 4 个字节)对于节点可以扩展成 Element 对象,对于其名称可以扩展成 Name 对象,还可以扩展成 Name 对象引用的 String 对象、空的 AttributeList 节点、空的 NamespaceList 节点,以及许多使这些对象互相链接,并且将它们与树中的父节点、兄弟节点和子节点链接的 64 位对象引用。简单实现可以根据这 4 个源码字节轻易地生成 200 个字节的树存储器。如果某些用户尝试处理那些原始大小超过 100 MB 的 XML 文档,可想而知,其结果是可预测的,并且通常是致命的。

这就是 Saxon 开始构建其树状结构的一个原因。通过消除实现完整 DOM 接口的需求,就可以除去树中的某些数据。消除支持更新的需求特别实用。例如,对于没有属性的元素,Saxon 使用另一个类,因为它知道如果元素一开始就没有属性,以后它也不会获得任何属性。Saxon 使用的另一个技巧是优化包含单一子文本节点(例如 <b>text</b> )的元素的公共状态存储器。

如 W3C 规范中所描述的,XPath 树模型包括属性和名称空间的节点。因为在转换过程中很少访问这些节点,所以 Saxon 按要求构造这些节点,而不是让它们永久占据树的空间。(这是 Gamma Flyweight设计模式。)

Saxon 的最新发行版更迈进了一步:它使用的树实现中,根本不使用 Java 对象来表示节点。事实上,树中的所有信息以整数数组表示。所有节点都创建成临时(或轻量级)对象,按要求构造成对这些数组的引用,并在不再需要时废弃。该树实现(包 com.icl.saxon.tinytree )占用极少的内存,并且构建过程更迅速,但其代价是浏览树的速度会稍微慢一点。总而言之,它的性能比标准树更好,因此我将它作为缺省值提供。

标准实用程序类,如 HashtableVector 也影响 Java 程序性能。开发者常常在整个应用程序中使用这些便利类库。然而,这是要付出代价的。其中一部分是因为类能做的超出了您真正需要的,与只为一种用途设计的类相比,它们会产生更多的开销。它们还是按多线程设计的,用于处理最坏的情况。如果您知道多个线程不会同时访问数据结构,那么可以设计您自己的对象,而不必使用这些现有的类,从而节省同步成本。用数组替换 Vector 通常会得到回报,唯一的缺点是需要手工处理数组的扩充,而 Vectors 是自我管理的。


位置路径求值

最有特点的 XPath 表达式(XPath 从中获取其名称)是位置路径。位置路径用于选择源树中的节点。位置路径基本上包括起始地址和许多步骤。它类似于 UNIX 文件名或 URL,除了每个步骤选择一组节点而不是单一节点。例如, ./chapter/section 选择当前节点的所有 <chapter> 子节点的所有 <section> 子节点。起始地址标识浏览树的起始点:它可能是当前节点、源树的根节点、另一棵树的根节点或由键定位的一组节点。位置路径中的每个步骤都从一个节点浏览到一组相关的节点。每个步骤都是根据浏览轴(子轴是缺省值)定义的:例如,祖辈轴选择所有祖辈节点,以下的兄弟轴选择原始节点下的所有兄弟节点,子轴选择其子节点。除了指定轴之外,每个步骤还可以指定所需节点的类型(如元素、属性或文本节点),所需节点的名称,以及该节点必须满足的谓词(例如,子文本节点的值以 B开头)。

为位置路径设计执行策略等同于优化关系型查询的问题,尽管当前理论还不够先进,而且所使用的大多数技巧与规范中描述的简单策略的浏览方式略有不同。例如,尽管在样式表中可以指定必须构建以支持联合访问的键(而不是 SQL 中的 CREATE INDEX ),Saxon 目前只是使用这些索引来支持明确引用它们的查询(通过使用 key() 函数),并且永远不优化使用直接谓词的查询。

当前在 Saxon 中对于位置路径使用的优化技术包括:

  • 尽可能避免排序。 许多 XSLT 指令要求按文档顺序处理节点,因此需要花精力按文档顺序检索节点,还要花更大精力来检测检索节点的自然顺序是文档顺序还是逆向文档顺序,因而无需排序。这样的一个示例就是表达式 //item (它被定义成 /descendent-or-self::node()/item 的缩写)可以由 /descendent::item 代替,只要它不使用位置谓词。后一个表达式将自然地按文档顺序检索节点,而前一个则不是这样。
  • 减少谓词。 有时这可能使谓词减少到常量值 true 或 false,允许简化整个位置路径。通常它只是除去公共子表达式。例如,在过滤器表达式 $x[count(.|$y)=count($y)] 中(它是 XSLT 1.0 中执行一组逻辑乘操作的唯一简便方法)中,Saxon 只对 count($y) 求值一次。
  • 使用位置谓词提前终止。 谓词 para[position() <= 3] 选择当前节点的前三个 <para> 子节点。没有必要对每个 <para> 元素应用该谓词来查看它是否是真,因为处理可能在第三个节点后停止。
  • 优化属性引用。 XPath 模型对待属性与对待子元素完全一样,这大大简化了 XPath 语言。但是,由于一个元素对于一个给定名称最多有一个属性,因此可以优化对属性的访问权。该优化还考虑到属性节点并没有在树上真正具体化,除非需要使用它们。这就意味着当 XPath 表达式 child::title 扫描所有子元素来查找名为 title 的子元素时,类似的表达式 attribute::title (通常缩写成 @title )会直接得到相关属性。
  • 位置路径的弱求值。 对特殊上下文中的位置路径表达式求值不会返回内存中实际节点的列表,事实上它返回另一个表达式(称作“内包节点集”,类 com.icl.saxon.expr.NodeSetIntent ),在这个表达式中除去了所有上下文相关性。仅当真正使用内包节点集时,才会枚举其成员:并且根据如何使用它,可能根本无需检索这些成员。例如,如果该节点集在布尔型上下文中使用,唯一需要的处理就是测试它是否是空的。当第三次使用内包节点集时,将在扩展存储它,以内存换取处理时间。这就象 SQL 中的具体化视图。

样式表编译

我已经描述了 Saxon 所做的第一件事就是将样式表“编译”成装饰树以便以后能够有效地执行。这提供了一个很好的机会,可以只执行一次操作,而不必每次都执行相关指令。

在样式表编译阶段完成的一些任务如下:

  • 确认。在编译阶段可以检测出大多数用户错误。这包括第一眼看上去象运行时错误的一些错误。XPath 表达式使用动态定类型(在对表达式或变量求值之前,不必知道表达式或变量的类型)。但是,对于大多数实际 XPath 表达式,在编译时类型 已知的。因此,例如, <xsl:for-each select="$x+2"> 可以立即识别成一个错误,因为 XPath 表达式 $x+2 永远不会返回节点集。在许多情况下,甚至可以检测出 <xsl:for-each select="$x"> 是一个错误,因为缺少赋值语句就意味着通常可以根据声明来推断变量的类型。
  • 简化表达式。 已经讨论过所使用的一些技巧。一个使用表达式的重要环境是在属性值模板中。例如,文字结果元素 <td width="{$x * 2}"> 输出 <td> 元素,在运行时计算出它的 width 属性。一个重要的编译任务是将属性值模板转换成有效的结构以便在运行时求值。
  • 绑定变量和其它名称。由于所有变量在编译时都是可见的,因此编译器可以提前为每个被调用的模板分配堆栈框架上的槽。然后表达式中对变量的引用可以静态绑定到本地堆栈框架或一列全局变量的特定槽上。同样,其它对已命名对象(如模板和外部函数)的引用通常可以静态解析。在某些情况下,XPath 语法允许动态生成名称(例如,键名称或十进制格式的名称),但它仍可以检测一般情况,即以文字形式提供名称,然后静态绑定它。

在其它情况下,在编译时执行操作不太可行,但执行保存可以避免在运行时执行重复操作。一个例子就是 format-number() 函数,它使用一个模式(描述十进制数所需的输出格式)作为它的一个变量。如果检测到格式模式与前一次执行相同的一般情况,则可以节省大量操作。这种优化唯一棘手的一面是将前一次执行的内存保留在与当前线程相关的位置:它不能保留在样式表自身中,因为需要保证线程安全。


模板规则的模式匹配

模式匹配操作可能是非常昂贵的,因此智能地集中搜索是非常重要的。因此样式表编译器构造了决策树,在运行时用它来决定将哪个模板规则应用于给定节点。

在此,我较为随意地使用术语 决策树 。本节较为详细地描述了实际的数据结构和算法。(请参阅源代码中的模块 com.icl.saxon.RuleManagercom.icl.saxon.Mode )。

当对某个节点应用 <xsl:apply-templates> 指令时,必须为该节点选择模板规则。如果没有匹配的规则,Saxon 会使用内置规则。如果有超过一个规则,则处理器会向 XSLT 规范中的算法报告决定哪个规则取得优先权。这个算法基于用户分配的优先级、系统分配的优先级、当一个样式表导入另一个样式表时建立的优先权关系,以及 -- 如果其它所有都失败 -- 源样式表中规则的相对顺序。

在典型的样式表中,大多数模板规则匹配树中的元素节点。匹配其它节点(如文本节点、属性和注释)的规则相对较少。此外,大多数模板规则完整提供了它们必须匹配的元素名称。允许使用未命名节点的规则,但这些规则并不常用(例如, *[string-length(.) > 10] ,它匹配任何文本内容多于 10 个字符的元素)。

因此,Saxon 的策略是将规则分成两种:特定规则(在模式中明确指定节点类型和名称)和一般规则(不指定节点类型和名称)。决策树的数据结构包含了特定规则的散列表,按节点类型和节点名称为键,其中每一项都是规则列表,按优先级降序排列;另外有一个列表包含所有一般规则,按优先级排序。要查找某特定节点的模式,处理器将进行两次搜索:一次是为适用于匹配该节点的相关节点和名称搜索优先级最高的特定规则,另一次是搜索与该节点匹配的优先级最高的一般规则。然后选择所找到的优先级最高的规则。

对于由多部分组成的模式,如 chapter/title ,所使用的算法是递归的:如果正在测试的节点匹配 title ,并且父节点匹配 chapter (模块 com.icl.saxon.pattern.LocationPathPattern ),则匹配成功。该简单方法不能用于使用位置谓词的模式;例如 chapter/para[last()] ,它只匹配 para 元素,如果该元素是某一章的最后一个元素。匹配这些位置模式可能非常耗时,所以值得特别处理类似模式(如 para[1] )的一般情况。


编号

对树上的节点进行编号(使用 <xsl:number> 指令)带来了特殊的优化问题。这是因为每次执行 <xsl:number> 时都会单独将一个号码分配给当前节点,该号码由使用 <xsl:number> 指令中各个属性的复杂算法定义。算法中并没有指定如果上一个节点的号码是 19,那么下一个的编号就是 20,但大多一般情况下都是如此。检测那些一般连续编号情况很重要。否则,对大的节点集进行编号将有 O(n 2) 性能,这就类似于将 XSLT 推荐书中指定的编号算法单独应用于每个节点。

在少数一般情况下,Saxon 会完成该优化,其中编号算法的大多数属性都是缺省值。特别是,它对 <xsl:number> 指令的最新结果进行编号,如果遇到某些复杂但有经常能满足的条件,它知道可以通过对这个已记住的号码加 1 来对此节点进行编号。


结束语

在本文中,我已经尝试给出了 Saxon XSLT 处理器内幕的概述,特别是它用于提高转换速度的一些技术。在我发布了 Saxon 最早版本后的大约 18 个月中,性能已经提高了 20 个百分点(或者更多,如果是在缺少内存的情况下运行)。

以后的 18 个月中不太可能有类似的改进。但是,仍有很大的空间可以提高,特别是类似于 <xsl:number> 的构造。另举一例,Saxon 还没有开始研究并行执行的可行性,这可以使这种语言更具吸引力。

也许最大的研究挑战是编写不用在内存中构建源树就可以操作的 XSLT 处理器。许多人都欢迎这样的开发,但它并不是一件容易完成的工作。

参考资料

条评论

developerWorks: 登录

标有星(*)号的字段是必填字段。


需要一个 IBM ID?
忘记 IBM ID?


忘记密码?
更改您的密码

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件

 


在您首次登录 developerWorks 时,会为您创建一份个人概要。您的个人概要中的信息(您的姓名、国家/地区,以及公司名称)是公开显示的,而且会随着您发布的任何内容一起显示,除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。

所有提交的信息确保安全。

选择您的昵称



当您初次登录到 developerWorks 时,将会为您创建一份概要信息,您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。 您的昵称在 developerWorks 社区中必须是唯一的,并且出于隐私保护的原因,不能是您的电子邮件地址。

标有星(*)号的字段是必填字段。

(昵称长度在 3 至 31 个字符之间)

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件.

 


所有提交的信息确保安全。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=XML
ArticleID=21865
ArticleTitle=Saxon: 剖析 XSLT 处理器
publish-date=02012001