Balisage 2009标识技术会议(四)

第二天(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. http://www.amazon.com/XSLT-2-0-Programmers-Reference-Programmer/dp/0764569090 
  2. http://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. (http://www.balisage.net/Proceedings/vol3/html/Kay01/BalisageVol3-Kay01.html
  4. http://en.wikipedia.org/wiki/Simple_API_for_XML
  5. http://en.wikipedia.org/wiki/Coroutine
  6. http://www.w3.org/Style/XSL/