Saxon: XSLTプロセッサーの解体新書

XSLT最適化における現在の最先端は?

この記事では、XSLTプロセッサー (この場合は、著者が作成したオープン・ソースのSaxon) が実際に機能する方法を説明します。オープン・ソースのXSLTインプリメンテーションはいくつか存在していますが (参考文献を参照)、これまでに分かっているかぎり、それが機能する方法について説明した人はいません。この記事は、そのギャップを埋めることを意図しています。Saxonの内部動作について説明し、このプロセッサーがXSLTの最適化を扱う方法を示します。また、これから行わなければならない作業がどれほど多く残されているかも示します。この記事では、XSLTが何であるか、またどのように機能するかを読者がすでに知っていることを想定しています。(XSLTの基礎について改めて確認されたい方は、Michael Kayの姉妹記事、 XSLTはどのような言語かをお読みください。)

Michael Kay (mike@saxonica.com), Writer and programmer, Saxonica Limited

Author photo: Michael Kay

Michael Kayは、XMLの世界ではSaxon XSLTプロセッサーの作成者およびXSLT Programmer's Reference (Wrox社) の著者としてよく知られています。彼の背景 (かなり昔は博士だった) は、データベース・テクノロジーにあります。そのとき以来、彼は関係型でオブジェクト指向のフリー・テキスト・データベース・ソフトウェアであるCodasylを設計してきました。

この記事の執筆時において、Michaelは仕事の合間にあります (ただし、休んでいるわけではありません)。ICL (英国に拠点を持つITサービス企業) での24年間の勤務を終えたばかりで、すぐにSoftware AG に移り、将来のXML製品の方向を左右するアーキテクチャー・チームに加わる予定です。

著者は、自分がいつもWrox社の本のカバー写真のようにまじめな顔をしているわけではないことを証明するために、この写真を選びました。



2001年 2月 01日

この記事は、いくつかの目的を果たすと思います。まず、スタイル・シート作成者に対し、XSLTプロセッサーで処理可能な最適化の種類を示すとともに、現時点で最適化されていない構成の一部を (暗黙的に) 伝えます。もちろん、このような最適化の詳細はプロセッサーやリリースによって異なりますが、この説明を読めば、舞台裏で行われている作業がどのようなものかがずっと分かりやすくなるでしょう。2番目に、XSLTテクノロジーにおいて現在の最先端であると思えるもの (この点において、Saxonは基本的に他のXSLTプロセッサーより進んでも遅れてもいません) と、技法をさらに開発する余地があると思える分野について説明します。この分野において、この説明が、コンパイラーやデータベースの最適化に熟練した研究者による作業を刺激することを希望しています。

最後に (そして、重要度が最も低い点として)、この記事はSaxonのソース・コードを研究したいと思う方にとって出発点となることを意図しています。コードのツアーとして書かれたわけでも、読者が深く学ぶことを想定しているわけでもありません。しかし、JavaDocの仕様やソース・コードそのものを調べることによって得られる以上の高水準な概説に興味がある場合は、この記事が役立つかもしれません。

ただし書き: ここで説明するバージョンはSaxon 6.1であり、機能によるコードの分解説明は、パッケージやモジュールの構造にぴったりマップしない場合があります。たとえばこの記事では、コンパイラーとインタープリターを別々の機能コンポーネントとして説明しています。しかし、実際のコードでは、たとえば<xsl:choose> 命令を処理するモジュールに、この命令をサポートするコンパイル時コードと実行時コードの両方が含まれています。この記事をコードのガイドとして使用したい方は、随時含められているパッケージやモジュールの名前を参照してください。

まず、Saxon製品の設計について説明します。SaxonはXSLTプロセッサーです。つまり、XML文書とスタイル・シートを入力として取り、結果文書を出力として生成するプログラムです。(この記事では読者がXSLTの知識を持っていることを想定していますが、XSLTが始めての方は、姉妹記事を入門として使用できます。)

Saxonには、もともとはDavid Megginsonによって作成されたオープン・ソースのAElfred XMLパーサーのコピーが組み込まれていますが、Java SAXインターフェースがインプリメントされた任意のXMLパーサーを使用できます。また、結果ツリーをXML、HTML、またはプレーン・テキストに変換するシリアライザーも組み込まれています。このシリアライザーは、技術的にはXSLTプロセッサーの一部ではありませんが、実用上には不可欠です。

Saxonには、JAXP 1.1 Java拡張機能の一部として定義されたTrAX (Transformation API for XML) インターフェースがインプリメントされています。このインターフェースについて知らなくてもこの記事を理解できますが、TrAXのアーキテクチャーを理解していれば、Saxonの構造を理解するのに役立ちます。

Saxonのアーキテクチャー

Saxonソフトウェアの主なコンポーネントを図1に示します。

図1. Saxonのアーキテクチャー
図1

ツリー・コンストラクターは、ソースXML文書のツリー表現を作成します。これは、ソース文書とスタイル・シートの両方を処理するために使用され、次の2つの部分に分かれています。

  • 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プロセッサーと異なっている部分です。他のプロセッサーは、汎用のDOMモデルを内部ツリーとして使用しています。DOMを使用することの利点は、ツリーをサード・パーティー製のソフトウェアで生成できることです。異なる目的で構成されたツリーを変換への入力として直接提供したり、同様に、変換の出力をDOMベースのアプリケーションで直接使用したりできます。

わたしはSaxonにおいて、DOMの仕様によって得られるインターオペラビリティーにはコストがかかりすぎるという見方を採りました。まず、DOMツリー・モデルはXSLTプロセッサーで必要なXPathモデルより若干異なっており、この違いは一方のモデルを他方のモデルにマッピングする実行時コストを生じさせます。たとえば、DOMツリーには、XPathモデルでは不要な情報 (たとえば、エンティティー・ノード) を含めることができます。2番目に、DOMツリーはインプレースで(訳注:破壊的に)更新できますが、XSLT処理モデルでは、ツリーは順次作成されるだけです。順次作成だけが可能なツリー・モデルを設計すると、効率を達成できます。たとえば、各ノードにシーケンス番号を含めるなら、文書のシーケンス順序でノードを容易にソートできます。これは、XSLTでしばしば課される要件です。最後に、DOMインプリメンテーションには、マルチスレッド・アクセスを安全にするための同期コードが多数含まれています。XSLT処理モデルは「1度作成すれば何度でも読み取れる」というものなので、同期論理はずっと単純になり、ツリーのナビゲーションも高速になります。

実際、これから分かるように、Saxonには2種類のツリー・インプリメンテーションが備わっており、それぞれに独自のビルダーとナビゲーション・クラス (パッケージcom.icl.saxon.tree およびcom.icl.saxon.tinytree) があります。これら2つのインプリメンテーションでは、パフォーマンスのトレードオフが異なっています。

スタイル・シート・コンパイラーは、スタイル・シートを実行前に分析します。これは、実行可能コードでなく、スタイル・シートのデコレーション表現を生成します。デコレーション表現では、すべてのXPath表現が妥当性検査および構文解析され、すべての相互参照が解決され、スタック・フレーム・スロットが事前割り当てされています。これにより、スタイル・シート・コンパイラーは、各入力ノードを処理する適切なテンプレート規則を検索するために実行時に使用する決定ツリーを構成するという重要な機能を実行します。考えられるすべてのパターンに対して各ノードを突き合わせるのは極めて非効率的だからです。デコレーション・ツリーは変換時に機能して、スタイル・シート処理を駆動します。(このコンパイラーは、com.icl.saxon.style パッケージ内のクラス間、特に メソッドprepareAttributes()preprocess()、およびvalidate() 間に分散されています。)

一時期、Saxonには確かに、実行可能なJavaコードを生成するスタイル・シート・コンパイラーが組み込まれていました。しかしながら、これはXSLT言語のサブセットしか処理せず、テクノロジーの発展とともに、完全コンパイルによって実現するパフォーマンス向上も減少しました。結局、開発が複雑化すると同時にパフォーマンス上の利点が減少したため、わたしはこのアプローチを中止しました。現在、完全なXSLTコンパイラーは市場に存在しません。Sunがアルファ版を制作した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 インターフェースがインプリメントされています) です。このインタープリターは、デコレーション・スタイル・シートを使用して処理を駆動します。この言語の処理モデルに従い、まず、入力ツリーのルート・ノードを処理するテンプレート規則を見付けます。次に、そのテンプレート規則を評価します (規格の用語で言うと、「インスタンス化」されます)。

スタイル・シート・ツリーでは、それぞれのXSL命令タイプを表すのにさまざまなJavaクラスが使用されます。たとえば、次の命令を考えてみます。

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

このコード・フラグメントの効果は、ソース・ツリー上の現在のノードにタイプ <section> の親エレメントがある場合に、 <h3> エレメントを結果ツリーに出力することです。生成される <h3> ノードのテキスト内容は、親の sectiontitle 属性の値です。

このコード・フラグメントは、デコレーション・スタイル・シート上で図2に示す構造によって表されます。

図2. デコレーション・スタイル・シート・ツリー
図2

スタイル・シート内のエレメントは、表1 のように、ツリー上のノードに直接マップされます。エレメントを表すすべてのJavaオブジェクトは、 com.icl.saxon.style.StyleElement のサブクラスです。これ自体は、Saxonツリー構造におけるエレメント・ノードのデフォルト・インプリメンテーションである com.icl.saxon.tree.ElementImpl のサブクラスです。2つの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() メソッドが実行されます。このメソッドは、evaluateAsBoolean() メソッドを持つテスト・オブジェクトExpression にアクセスします。evaluateAsBoolean() を使用して式が評価され、ブール結果が戻されます(これは、1つの最適化です。仕様で説明されているように、直接的なevaluate() 呼び出しを使用してからその結果をブール値に変換することも可能です。しかしながら、ブール値が必要であることが分かっていれば、しばしば評価を高速に行えます。たとえば、実際の値や式がノード・セットである場合は、そのノード・セットの単一メンバーが見付かれば最終的なブール結果が分かります)。

evaluateAsBoolean() の結果が真であれば、process() メソッドはスタイル・シート・ツリー上にあるXSLIf ノードのすべての子ノードのprocess() メソッドを呼び出します。結果が真でなければ、単純に終了します。

同様に、LiteralResultElementprocess() メソッドは、このエレメントを結果ツリーにコピーして、LiteralResultElement の子エレメントを処理します。XSLValueOf オブジェクトのprocess() メソッドは、選択式をストリングとして評価し、結果をテキスト・ノードとして結果ツリーにコピーします。

したがって、スタイル・シート・インタープリターのキー・コンポーネントは次のようになります。

  • それぞれのスタイル・シート命令タイプ用の、その命令のロジックを含むクラス
  • 変数のバインディング、ランタイム・コンテキストの管理、およびテンプレート規則に対するノードの突き合わせを処理する、一連のサポート・クラス
  • XPath式を評価してその値を戻すXPath式インタープリター

XPathインタープリター (パッケージcom.icl.saxon.expr) は、Interpreter デザインパターン (Gamma、Helm、Johnson、およびVlissidesによって記述されたオブジェクト指向ソフトウェアの23の古典的なパターンの1つ ) に厳密に従っています。XPath文法の各構文要素には、対応するJavaクラスがあります。たとえばUnionExpr 構文 (A|B として記述され、2つのノード・セットの和集合を表す) は、クラスcom.icl.saxon.expr.UnionExpression によってインプリメントされています。XPath式パーサー (モジュールcom.icl.saxon.expr.ExpressionParser) は、通常はスタイル・シートのコンパイル時に実行され、式の構文解析ツリーを直接反映するデータ構造を生成します。式を評価するため、この構造の各クラスには値を戻す処理を担当するevaluate() メソッドがあります。UnionExpression クラスの場合、evaluate() メソッドは2つのオペランドを評価し、結果がどちらの場合にもノード・セットであることをチェックしてから、ソート・マージ戦略によって和集合を形成します。

Gammaその他によって記述されたデザインパターンにあるように、evaluate() メソッドはContext パラメーターを取ります。Context オブジェクトには、式を評価するために必要なすべてのコンテキスト情報がカプセル化されています。

これには、次のものが含まれます。

  • 現在のノードと現在のノード・リストに関する情報 (たとえば、XPath関数のposition()last() を評価するために必要)
  • 変数の値が保持されるcom.icl.saxon.Bindery オブジェクトへのアクセス情報
  • 式の有効範囲内にあるXML名前空間のリストへのアクセス情報 (名前の等価性をテストする際に必要)

XPathインタープリターには、Gammaその他による基本的なInterpreterパターンを拡張する最適化機能も組み込まれています。

たとえば、

  • それぞれの式クラスにはsimplify() メソッドがあり、式の書き換えが可能となっています。
    これにより、コンテキストに依存しない最適化が実行可能です。このとき、異なるXPath式への変換が行われる場合があります (たとえば、title[2=2]title に書き換えられ、count($x)=0not($x) に書き換えられる)。多くの場合、式の書き換えでは、特殊なケースを表す内部クラスが活用されます。たとえば、式section[@title] では、title属性を持つ、現在のエレメントのすべての子の<section> が戻されます。副次式@title は、それが現れるコンテキストのため、現在のノード上で特定の属性の存在をテストしてブール値を戻す特殊用途クラスを使用して書き換えることが可能です。
  • それぞれの式クラスにはevaluate() メソッドとenumerate() メソッドがあります。
    これにより、(ノード・セットを表す式の場合に) ノードを、一度にすべてでなく少しずつ検索することが可能です。また、関係データベース・システムで採用されている典型的な方法で、パイプライン実行が可能です。たとえば、和集合の式に対してenumerate() を呼び出すと、2つのオペランドを列挙したもの(訳注:2つのオペランドに対してenumerate()を適用した結果)がマージされます。このため、オペランドが文書順序にすでにソートされているかぎり、中間ノード・セット用にメモリーを割り振る必要がなくなります。

  • 式を段階的に簡約し、依存関係を除去することができます。
    式の簡約の概念は、関数型言語で広く使用されており、XPathなどの言語を最適化するのに特に適しています。それぞれの式クラスにはメソッドgetDependencies() があり、そのメソッドが依存するコンテキストの局面に関する情報を戻します。これにより、すでに特定の最適化が可能となっています。たとえば、式でlast() 関数が使用されていなければ、コンテキスト・リストに存在するエレメントの数を判別する先読み処理を行う必要はありません。さらに、それぞれの式にはメソッドreduceDependencies() があり、指定された依存関係が除去されて他の依存関係が残された等価の式を戻します。これが役立つのは、同じ式が繰り返し使用される場合です。たとえば、ソートが実行される前は、ソート・キー式が簡約されて、変数に対する依存関係 (リスト内のすべてのノードで同じ) が除去されますが、現在のノードに対する依存関係 (リスト内の各項目で異なる) は除去されません。

XSLT言語では、副次作用がないため、Saxonは任意の順序で式を評価する大きな自由が得られます。Saxonにおける全体的なポリシーは、スカラー値 (ストリング、数値、ブール値) をできるだけ早く評価し、ノード・セット値をできるだけ遅く評価する、というものです。スカラー値を早めに評価すると、処理を1度だけ行えば済むことになるために最適化が実現します。ノード・セット値の評価を遅らせると、大規模なリストが不必要にメモリーに保持されることがなくなるため、メモリーを節約できます。また、ノード・セットに対する処理が、(しばしばそうであるように) 空かどうかのテストや最初のエレメントの値の取得だけであれば、時間も節約できます。

最後に、アウトプッター・コンポーネント (クラスcom.icl.saxon.output.Outputter) は、出力プロセスを制御するために使用されます。通常、Saxonの結果ツリーはメモリー内に実体化されません。ノードは、常に文書の順序で作成されるため、結果ツリーに出力されると同時に逐次化されます。実際には、変換時には単一の結果ツリーでなく、結果ツリーの可変スタックが存在します。これは、<xsl:message><xsl:attribute> などのXSL命令は結果的に出力を内部的な宛先にリダイレクトし、一方<xsl:variable> は結果ツリー・フラグメント (実際はそれ自体が別個のツリーである) を構築するためです。これらのエレメントのインタープリター・コードは、アウトプッターを呼び出して新しい宛先に切り替え、その後で元の宛先に復帰します。

外部出力は、シリアライザーを使用してファイルに書き込まれます。論理的には、シリアライザーは結果ツリーを入力として取り、フラット・ファイル文書に変換します。実際には、前述のように結果ツリーはメモリー内に実体化されないため、シリアライザーにはツリーのノードが文書順序で1つずつ渡されます。このノードのストリームは、SAX2に似たインターフェース (com.icl.saxon.Emitter) を使用して示されます。SAX2と異なるのは、名前と名前空間を表す詳細な方法です。XSLT勧告で定義されているように、XML、HTML、およびプレーン・テキストの出力用に別個のシリアライザーが存在します。Saxonでは、ツリーをユーザー作成のコードに提供してさらに処理したり、別のスタイル・シートへの入力としたりすることもできます。このため、複数のスタイル・シートを順番に適用することによって複数フェーズ変換を実現できます。


パフォーマンス

優れたパフォーマンスを実現することは、Saxonの設計を動かした要因の1つで、XSLT仕様への準拠の次に重要なものでした。これは、パフォーマンスがユーザーにとって非常に重要であるだけでなく、無料で使用可能なXSLTプロセッサーがいくつもある今、パフォーマンスが区別する特徴になるためです。

このセクションでは、XSLTプロセッサーのパフォーマンスに影響するいくつかの要因と、それぞれの分野でSaxonが速度を向上するために使用している戦略について説明します。


Java言語に関する問題

しばしば、Javaは低速であると言われます。この言葉は一部は正しいですが、注意深く限定する必要があります。

多くの人々は、Javaが低速な理由を、インタープリットされたバイトコードをネイティブ・コードの代わりに生成するためと考えています。これはかつては真実でしたが、ジャストインタイム・コンパイラーが存在する現在はそうではありません。ロー・コードの実行速度は、Cなどのコンパイル言語で作成された等価のコードとほとんど同じで、ときには上回ることもあります。

Javaの問題は、メモリーの割り振りに関するものです。CやC++ とは異なり、Javaでは自分でメモリーを操作し、ガーベッジ・コレクターを使用して不要なオブジェクトを解放します。これはプログラマーには非常に便利ですが、メモリーを浪費するプログラムが容易に作成されます。そのようなプログラムは、仮想メモリーを使いすぎて苦しんだり、オブジェクトの割り当てや解放が頻繁に行われることによってガーベッジ・コレクターに大きな負荷をかけたりします。

メモリーの割り振りに関する問題は、いくつかのコーディング技法によって最小化できます。たとえば、String の代わりにStringBuffer オブジェクトを使用したり、再使用可能オブジェクトのプールを使用したりする技法があります。診断ツールを使用すれば、プログラマーはこれらの技法を使用するタイミングを判断しやすくなります。コードの高速化には多くのチューニングが必要ですが、それでも、C++ などの言語を使用する (すべてのメモリー割り振りを手動で管理しなければならない) よりはおそらくずっと容易です。

XSLTの処理では、ツリー構造のインプリメンテーションが、Javaにとって特に挑戦となります。Javaでは、各オブジェクトのサイズにおいて、かなりのレッド・テープ(避けられない)・オーバーヘッド (最大で32バイト。使用するJava VMによる) が課されています。このため、しばしば、ソースXMLファイルの数倍の大きさのツリー構造がメモリー内に生成されます。たとえば、空エレメント<a/> (ソース・ファイルでは4バイト) を展開すると、ノードを表すElement オブジェクト、名前を表すName オブジェクト、Name オブジェクトによって参照されるString オブジェクト、空のAttributeList ノード、空のNamespaceList ノード、およびこれらのオブジェクトを相互および親、兄弟、および子ノードにリンクする多数の64ビットのオブジェクト参照が生成されます。単純なインプリメンテーションでも、これら4バイトのソースから生成されるツリーのストレージは200バイトに達する可能性があります。複数のユーザーが、ロー・サイズが100MB以上であるXML文書を処理しようとする場合、結果は予想可能で、一般に致命的なものとなります。

これは、Saxonが独自のツリー構造を持つに至った理由の1つです。DOMインターフェースをインプリメントする要件を除去したことにより、ツリーからいくらかのデータを除去できました。更新をサポートする要件を除去したことは、特に役立ちます。たとえば、Saxonは、属性を持たないエレメントについて、異なるクラスを使用します。はじめから属性がなければ、そのエレメントが後で属性を持つことはないことが分かっているためです。Saxonが使用する別の技法は、単一の子テキスト・ノードを含むエレメント (たとえば<b>text</b>) の共通状態のストレージを最適化することです。

W3C仕様で記述されているXPathツリー・モデルには、属性や名前空間のためのノードが含まれています。これらのノードは変換時にほとんどアクセスされないので、Saxonでは、これらのノードは永続的にツリー上のスペースを占めるのではなく、必要時に構成されます。(これは、Gammaその他によって作成されたFlyweight 設計パターンです。)

Saxonの最新リリースは、さらに一歩進んで、ノードがまったくJavaオブジェクトによって表されないツリー・インプリメンテーションを使用しています。代わりに、ツリー内のすべての情報は、整数の配列によって表されます。すべてのノードは一時 (またはflyweight) オブジェクトとして作成され、必要時にこれらの配列への参照として構成され、不要になると廃棄されます。このツリー・インプリメンテーション (パッケージcom.icl.saxon.tinytree) では、使用するメモリーがずっと少なくなり、構築も高速になりますが、ツリー・ナビゲーションは多少遅くなります。全体的に見ると、これは標準のツリーよりもパフォーマンスが高いと思われるため、デフォルトとして提供されています。

HashtableVector などの標準のユーティリティー・クラスも、Javaプログラムのパフォーマンスに影響します。開発者にとって、これらの便利なクラスをアプリケーション全体で自由に使用することは魅力的です。しかしながら、代償もあります。一部には、これらのクラスは実際に必要なこと以上のことを行うという理由で、1つの目的のためだけに設計されたクラスよりもオーバーヘッドが大きくなります。また、これらのクラスはマルチスレッド化に関して最悪の状態を処理するように設計されています。データ構造が複数のスレッドによって同時にアクセスされないことが分かっている場合は、これらの既製のクラスを使用する代わりに独自のオブジェクトを設計することにより、同期に関するコストを節約できます。Vector を配列に置き換えることには、しばしば割に合うことです。唯一の欠点は、Vector が自己管理クラスであるのに対し、配列の拡張を手動で処理しなければならないことです。


ロケーション・パスの評価

最も特徴的な種類のXPath式 (XPathの名前の由来となっている) は、ロケーション・パスです。ロケーション・パスは、ソース・ツリー内のノードを選択するために使用します。ロケーション・パスは、本質的に、起点といくつかのステップで構成されています。これは、UNIXファイル名やURLと類似しており、各ステップが単一のノードでなくノードのセットを選択することが異なっています。たとえば./chapter/section は、現在のノードの子であるすべての<chapter> の子であるすべての<section> を選択します。起点は、ツリーをナビゲートする開始点を識別します。これには、現在のノード、ソース・ツリーのルート・ノード、異なるツリーのルート・ノード、またはキーを使用する値によって位置指定されるノードのセットを使用できます。ロケーション・パス内の各ステップは、1つのノードから関連するノードのセットにナビゲートします。各ステップはナビゲーションの軸 (子の軸がデフォルト) によって定義されます。たとえば、祖先の軸ではすべての上位ノードが選択され、後方兄弟の軸では起点ノードのそれ以下の兄弟がすべて選択され、子の軸ではその子が選択されます。軸を指定するだけでなく、各ステップでは、必須ノードのタイプ、必須ノードの名前、およびそのノードが満たさなければならない述部 (たとえば、B で始まる値を持つ子テキスト・ノードなど) を指定できます。

ロケーション・パスの実行戦略を考案するという問題は、(データベースにおける)関係照会を最適化するという問題に匹敵します。もっとも理論的にはまだまだで、使用する技法は、仕様で記述されているとおりにナビゲーションを正確に行う単純な戦略とほとんど異なりません。たとえば、スタイル・シートでは、連想アクセスをサポートする場合に組み込まなければならないキーを指定することができます (SQLでのCREATE INDEX と同様) が、Saxonでは、これらの索引はそれを明示的に参照する (key() 関数を使用する) 照会をサポートする場合にのみ使用され、直接的な述部を使用する照会を最適化する場合には使用されません。

ロケーション・パスに関してSaxonで現在使用されている最適化技法には、次のものがあります。

  • できるだけソートを避ける。
    多くのXSLT命令では、ノードを文書順序で処理する必要があるため、ノードを文書順序で取得するためにいくらかの努力を払っています。また、ノードのソートを避けるために、そもそも式の評価が文書順序あるいは逆文書順序で行なえるかどうかを判定するのに、より多くの努力を払いました。1つの例として、式//item (/descendent-or-self::node()/item の省略形として定義されている) は、位置述語が使用されていなければ、/descendent::item で置き換えることができます。後者の式では、自然に文書順序でノードが評価されますが、前者はそうではありません(訳注:前者は/descendant-or-self:node()/の評価のために木を一回走査し、その後あらためてそれらの子供ノードをテストします)。
  • 述部の簡約。
    これにより、述部を定数値 (真または偽) に簡約し、ロケーション・パス全体を単純化できることがあります。多くの場合は、共通の副次式を除去するだけです。たとえばフィルター式$x[count(.|$y)=count($y)] (XSLT 1.0で集合の論理積操作を容易に行う唯一の方法) では、count($y) が1度しか評価されません。
  • 位置述語による早めの終了。
    たとえば、para[position() <= 3] における述語では、現在のノードの子である<para> のうち最初の3つが選択されます。3番目のノードの後で処理を停止できるので、この述部をすべての<para> エレメントに明示的に適用して真になるかどうかを調べる必要はありません。
  • 属性参照の最適化。
    XPathモデルでは、属性は子エレメントとまったく同じように扱われます。これにより、XPath言語は非常に単純化されています。しかし、エレメントは特定の名前の属性を1つしか持つことができないため、属性へのアクセスは最適化できます。この最適化では、属性ノードが必要ない場合はツリー上で実体化されないという事実も考慮に入れています。つまり、XPath式child::title では、すべての子エレメントがスキャンされ、title という名前のエレメントが検索されますが、同様の式attribute::title (しばしば@title に省略される) では、関連する属性が直接取得されます。
  • ロケーション・パスの遅延評価。
    特定のコンテキストでロケーション・パス式を評価すると、実際のノード・リストはメモリーに戻されず、コンテキストの依存関係がすべて除去された別の式 (「内包ノード・セット」と言う。クラスcom.icl.saxon.expr.NodeSetIntent) が戻されます。内包ノード・セットが実際に使用される場合を除き、そのメンバーは列挙されません。使用される方法によっては、まったく検索しなくてもよい場合もあります。たとえば、ノード・セットがブール値のコンテキストで使用される場合、必要な唯一の処理はそれが空であるかのテストです。3度目に使用された内包ノード・セットは、外延的に保存され、メモリーと引き換えに処理時間を短縮します。これは、SQLにおけるビューの実体化と似ています。

スタイル・シートのコンパイル

すでに説明したように、Saxonが最初に行う処理は、スタイル・シートを「コンパイル」して、後で効率的に実行できるようにデコレーション・ツリーに変えることです。これにより、関係する命令が実行されるたびに処理を行うかわりに1度で済ませることが可能になります。

スタイル・シートのコンパイル時に実行される一部のタスクは次のとおりです。

  • 妥当性検査。
    大多数のユーザー・エラーは、コンパイル・フェーズで検出できます。これには、一見すると実行時エラーに思えるエラーも含まれます。XPath式では、動的タイプ指定が使用されます (式や変数のタイプは、評価されるまで必ずしも知られていません)。ただし、実際のXPath式の大多数の場合、タイプはコンパイル時に知られています。したがって、たとえば<xsl:for-each select="$x+2"> は、XPath式$x+2 でノード・セットが戻されることが決してないため、即座にエラーとして認識できます。多くの場合は、<xsl:for-each select="$x"> がエラーであることを検出することさえ可能です。これは、割り当てステートメントの不在により、変数のタイプをしばしば宣言から推定できることが示されているためです。
  • 式の単純化。
    これに使用するいくつかの技法についてはすでに説明しました。式が使用される重要なコンテキストの1つは、属性値テンプレートです。たとえば、リテラル結果エレメント<td width="{$x * 2}"> の出力は、<td> エレメントで、そのwidth 属性は実行時に計算されます。重要なコンパイル・タスクは、属性値テンプレートを実行時の評価に適した効率的な構造に変換することです。
  • 変数と他の名前のバインディング。
    すべての変数宣言はコンパイル時に見ることができるため、コンパイラーは、呼び出された各テンプレート規則にスタック・フレーム上のスロットを事前に割り振ることが可能です。このとき、式にある変数への参照は、ローカル・スタック・フレームまたはグローバル変数リストにある特定のスロットに静的にバインドできます。同様に、テンプレートや外部関数などの他の名前付きオブジェクトへの参照も、しばしば静的に解決できます。XPath構文では名前 (たとえば、キー名や10進形式の名前) を動的に生成できますが、名前がリテラルとして提供される共通の場合を検出してその名前を静的にバインドすることも引き続き可能です。

他の場合、コンパイル時に処理を行える可能性は低いですが、実行時に繰り返し実行を避けることによって節約を行えます。1つの例は、format-number() です。これは、引数の1つとして、10進数に必要な出力形式を記述するパターンを取ります。形式パターンが直前の実行時と同じである共通の場合を検出することにより、かなりの節約が可能です。このような最適化で唯一厄介な局面は、前の実行時のメモリーを、現在のスレッドに関連した場所に保持しなければならないことです。スタイル・シート自体の上に保持することはできません (これを行うにはスレッド・セーフでなければならないためです)。


テンプレート規則のパターン・マッチング

パターン・マッチング操作にはコストがかかる可能性があるため、検索をインテリジェントに行うことが非常に重要です。そのため、スタイル・シート・コンパイラーは決定ツリーを構成し、実行時にはそのツリーを使用して、特定のノードに適用されるテンプレート規則を判別します。

ここで、決定ツリーという用語はゆるい意味で使用されています。このセクションでは、実際のデータ構造とアルゴリズムについて少し詳しく説明します。(ソース・コード内のモジュールcom.icl.saxon.RuleManager およびcom.icl.saxon.Mode を参照してください。)

<xsl:apply-templates/> 命令がノードに適用される場合は、そのノード用にテンプレート規則が選択される必要があります。マッチング規則が存在しない場合、Saxonは組み込み規則を使用します。複数の規則が存在する場合、SaxonはXSLT仕様に含まれるアルゴリズムを使用して、優先される規則を判別します。このアルゴリズムは、ユーザー割り振りの優先順位、システム割り振りの優先順位、あるスタイル・シートに別のスタイル・シートがインポートされたときに確立された優先順位関係、および (他のすべてが失敗した場合) ソース・スタイル・シートにおける規則の相対的な順序に基づいています。

典型的なスタイル・シートでは、ほとんどのテンプレート規則はツリー内のエレメント・ノードと突き合わされます。他のノード (テキスト・ノード、属性、およびコメントなど) と突き合わされる規則は、比較的まれです。また、ほとんどのテンプレート規則では、突き合わせ対象のエレメント名が完全に提供されます。名前のないノードに関する規則は許可されますが、あまり使用されません(たとえば、*[string-length(.) > 10] は、11文字以上のテキスト内容を持つエレメントと突き合わされます)。

このため、Saxonの戦略では、規則が2種類に分離されています。ノードのタイプと名前がパターンで明示的に指定される特定規則と、そうでない一般規則です。決定ツリーのデータ構造には、ノード・タイプとノード名をキーとする、特定規則用のハッシュ・テーブルが含まれます。このテーブルの各エントリーは、優先順位の高い順にソートされた規則のリストです。また、すべての一般規則用の単一リストが含まれます。このリストも優先順位の高い順になっています。特定のノード用のパターンを見付ける際に、Saxonは2種類の検索を行います。1つは、関連するノード・タイプおよび名前に関する、そのノードに一致する特定規則のうち優先順位が最も高いものの検索で、もう1つは、そのノードに一致する一般規則のうち優先順位が最も高いものの検索です。その後、これらのうち優先順位が高いものが選択されます。

複数の部分で構成されるパターン (たとえば、chapter/title) の場合は、再帰的なアルゴリズムが使用されます。この突き合わせが真になるのは、テスト対象のノードがtitle と一致し、その親ノードがchapter (モジュールcom.icl.saxon.pattern.LocationPathPattern) と一致する場合です。この単純なアプローチは、位置述部を使用するパターンには使用できません。たとえばchapter/para[last()] は、chapter内にある最後のpara エレメントとのみ一致します。このような位置パターンの突き合わせは、非常にコストがかかる可能性があるので、para[1] などのパターンの共通ケースを特定的に処理するほうが価値があります。


番号付け

ツリー上のノードに番号を付ける (<xsl:number/> 命令を使用する) ことは、最適化の上で挑戦となります。なぜなら、<xsl:number/> の各実行は、独立にそれぞれの現在ノードに番号を割り当て、その番号は、<xsl:number/> 命令のさまざまな属性に基づく複雑なアルゴリズムによって定義されるからです。このアルゴリズムは、最後のノードの番号が19であれば次のノードの番号が20になることを保証するものではありません (ただし、ほとんどの場合はそうなります)。このような一般的な順番のケースを検出することは重要です。そうでないと、大規模なノード・セットへの番号付けのパフォーマンスはO(n2) となります。これは、XSLT勧告で指定されている番号付けアルゴリズムを各ノードに独立的に適用した場合に得られる値です。

Saxonでは、少数の一般的なケースにおいてこの最適化を実現し、番号付けアルゴリズムの属性のほとんどをデフォルト指定します。具体的には、<xsl:number/> 命令の最新の結果を記憶しておき、かなり複雑であるが頻繁に満たされる特定の条件が真になれば、この記憶している番号に1を加えた番号をノードに付けることができます。


最後に

わたしはこの記事において、Saxon XSLTプロセッサーの内部、特に変換速度を向上させるために使用されるいくつかの技法を概説しようとしました。Saxonの最初のバージョンをリリースしてから18か月あまりのうちに、パフォーマンスは20倍向上しました (メモリーの不足のために苦しんだ実行の場合はそれ以上)。

次の18か月で同様の向上が見られることはなさそうです。しかし依然として、特に<xsl:number/> などの構造について、改善可能な範囲があります。別の例を挙げれば、Saxonでは、並列実行によって開けた可能性を探ることすら始まっていません。これは、この言語によって非常に魅力的なオプションとなっているものです。

この研究における最大の挑戦は、おそらく、ソース・ツリーをメモリー内に構築せずに動作できるXSLTプロセッサーを作成することでしょう。多くの人々はこのような開発を歓迎するでしょうが、容易でないことは確かです。

参考文献

  • 同じ著者による、 XSLTはどのような言語か。これは、この記事の姉妹記事として公開されています。
  • 同じ著者による、Wrox社のXSLT Programmer's Reference。これは、XSLT言語の包括的なガイドです。
  • W3C発行のXSLT 1.0勧告。これは、XSLT言語の決定的な仕様です。
  • W3C発行のXPath 1.0勧告。これは、XSLTスタイル・シートで使用されるXPath表現構文の決定的な仕様です。
  • Document Object Model (DOM) は、HTMLおよびXML文書を表す標準的なオブジェクト・セットと、それをアクセスして操作するための標準的なインターフェースを提供します。
  • Simple API for XML。これは、XML文書の内容をパーサー・イベントのストリームとして処理するための標準的なインターフェースです。
  • この記事で説明したオープン・ソースのXSLTプロセッサーであるSaxon のホーム・ページ。
  • SUN XSLTC Compiler:現在はアルファ・リリースです。
  • Transformation API for XML (TrAX) はJAXP 1.1の一部として定義されています。JAXP 1.1は、Java Community ProcessによってJSR-63 で公開されています。
  • Design Patterns: Elements of Reusable Object-Oriented Software。Gamma、Helm、Johnson、Vlissides著。Addison-Wesley、1998年。ISBN 0-201-63361-2。このすばらしい本はオンラインでは使用できませんが、Amazon.comで購入することができます。

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=XML
ArticleID=243379
ArticleTitle=Saxon: XSLTプロセッサーの解体新書
publish-date=02012001