Balisage 2009标识技术会议（四）

  • Article

第二天（8/12/2009），下午

关键词：管道，流处理，XSLT 2.1，推与挽模型（Push and Pull Model）

在我的书架上有两本非常醒目的红色封面参考书，XSLT 2.0[1]和XPath 2.0[2]，这两本书的作者Michael Kay的讲演内容就是今天下午我想着重向大家介绍的。

会议安排了Michael连续两个主题讲演。第一个是关于“基于管道的XML处理”（Pipeline based XML processing）[3]，第二个是“制定中的XSLT 2.1标准的流处理功能”。基于管道的XML处理所指的是在对XML的处理过程中需要经过一系列的步骤，而这些步骤实际上可以通过管道（pipeline）采用流的方式处理，当然前提是这个处理的每个步骤都需要支持“流”（streamability，这个英文单词是XSLT标准制定工作组自创的）。而所谓基于“流”的处理是指一个相对内存来说巨大的XML文件可以被分割成比较小的单元进行顺序处理。而这样的单元可以是每一个SAX [4]的消息，例如startElement和EndElement，或者是一个XML的部分，比如一个节点（Node）和原子化的量值（Atomic Value）。

而对于XML的处理来说，一般只有两种方式：组构和析构（compose and decompose）。每个步骤则采用“推”或“挽”的方式对XML组构或析构。在将这些步骤连接起来的时候由于它们各自的极化方式不一样（“推”或“挽”）或对XML的单元访问方式不一样（顺序，乱序，或在一个子树中乱序，子树与子树间顺序），要么需要一个控制器（controller）将“推”模型和“挽”模型连接起来，要么需要将XML的子树或全树缓存在内存中，结果往往造成整个处理流程的效率降低。Michael举了一个他自己的XQuery处理器例子，由于使用控制器和两个线程将“推”和“挽”两个步骤联系起来，结果比起一个单一“推”或单一“挽”的处理流程效率降低了差不多45%。会后有人提问有关在多核的系统中，是否这样的架构会体现出优势，Michael表示肯定。另外，他介绍了一个非常有用但被人淡忘的概念[5]，其实所谓的“推”或“挽”模型是可以相互转换的，在多线程的代价比较大的环境里，使用“协同程序”（co-routine）的方法可以在单一线程的条件下将“挽”模型转变为“推”模型，反之亦然。

XSLT 2.1的流处理功能是Michael应邀添加的新讲座，类似在音乐会里的加演节目。作为XSLT标准的编辑（editor），Michael对于这方面的内容当然非常熟悉。由于这篇博客的长度有限，我无法深入介绍XSLT 2.1的流处理功能，况且许多标准的细节还在起草阶段，这里就一些有趣或有争议的功能稍作解读：

  1. xsl:stream语句的引入
    新标准引入xsl:stream语句，用户使用该语句表示希望在xsl:stream之内的转型采用“流”处理方式。有人在会后提出疑问，认为这个语句将使用或不使用“流”处理的决定权交给用户，而用户往往不清楚自己设计的XSLT程序是否真可以采用“流”处理。理想情况应该是用户使用现有的XSLT语句，而“聪明”的XSLT处理器能够通过静态分析找出可以进行“流”处理的局部转型或全面转型。这其实也是XSLT标准工作小组一直在争论的话题。
  2. xsl:iterate系列语句的引入
    新标准引入xsl:iterate语句，它同xsl:for-reach语句有一样的语法结构，但是用来在“流”处理中支持可以进行尾递归优化的迭代循环和变量传递。举个例子，比如我们希望计算一个财务报告中的累计总计（running total），用传统的XSLT 1.0的xsl:for-each 将会效率特别低，堆栈内存使用为O(n)，而即使是支持尾递归优化的XSLT 1.0处理器也需要大约O(N^2)的时间（O(1+2+…+N) = O(N(N+1)/2)）。而采用xsl:iterate语句的“流”处理可以将堆栈内存减少至O(1)，时间减少至O(N)。写出的XSLT语句类似这样：
    <xsl:stream href="accounts_10gb.xml">
    <xsl:iterate select="transaction">
    <xsl:param name="running-total" select="0"/>
    <running_total><xsl:value-of select="$running_total"/></running_total>
    <xsl:next-iteration>
        <xsl:with-param name="running-total"
           select="$running-total + total"/>
          </xsl:next-iteration>
    </xsl:iterate>
    </xsl:stream>

XSLT 2.1还引入了xsl:mode语句，它同xsl:template的“mode”属性一起用来标识某个XSL的模板是否适用于“流”处理；引入了xsl:merge语句支持多个XML文件的相互融合，这里就不一一细数了。希望了解更多XSLT最新情况的读者可以关注一下XSL标准的官方网站[6]。

  1. https://www.amazon.com/XSLT-2-0-Programmers-Reference-Programmer/dp/0764569090 
  2. https://www.amazon.com/XPath-2-0-Programmers-Reference-Programmer/dp/0764569104
  3. Kay, Michael. “You Pull, I’ll Push: on the Polarity of Pipelines.” Presented at Balisage: The Markup Conference 2009, Montréal, Canada, August 11 - 14, 2009. In Proceedings of Balisage: The Markup Conference 2009. Balisage Series on Markup Technologies, vol. 3 (2009). doi:10.4242/BalisageVol3.Kay01. (https://www.balisage.net/Proceedings/vol3/html/Kay01/BalisageVol3-Kay01.html) 
  4. https://en.wikipedia.org/wiki/Simple_API_for_XML
  5. https://en.wikipedia.org/wiki/Coroutine
  6. https://www.w3.org/Style/XSL/