xml - Quadratic runtime for Delphi XML (MSXML) routines

Question

At work, we're using a XML log file. Each log message is a <message> block with <date> and <time> subnodes, there are <submessage> blocks, <table> constructs and so on and the log file can be transformed to a localized HTML using some Delphi processing and XSLT later.

For medium sized log files (around 2 MB), we got performance problems (up to a minute for loading the XML and doing some basic manipulations) and I could reduce them to a test project like this (EDIT: Updated the code and added measurements):

procedure TForm1.PrepareTest(MessageCount : integer);
var
  XML : IXMLDocument;
  i : integer;
begin
  XML := NewXMLDocument;
  XML.DocumentElement := XML.CreateNode('root');
  for i := 1 to MessageCount do
  begin
    XML.DocumentElement.AddChild('message').Text := 'Test Text';
  end;
  XML.SaveToFile(XML_NAME);
end;

procedure TForm1.XMLTest;
var
  StartTime : Cardinal;
  XML : IXMLDocument;
begin
  StartTime := GetTickCount();
  XML := NewXMLDocument;
  XML.LoadFromFile(XML_NAME);
  Memo1.Lines.Add('Node count: ' + IntToStr(XML.DocumentElement.ChildNodes.Count));
  Memo1.Lines.Add('Time: ' + FloatToStr((GetTickCount() - StartTime) / 1000) + ' seconds');
end;

This results in the following time measurements (node count is increased by 25% per column, all times in milliseconds):

Node count      8000    10000   12500   15625   19531   24413   30516   38145   47681
Base test time  484     781     1140    1875    2890    4421    6734    10672   16812
Variation 1                             32      47      62      78      78      141
Variation 2     2656    3157    3906    5015    6532    8922    12140   17391   24985
  (delta Base)   2172    2376    2766    3140    3642    4501    5406    6719    8173

Note the two variations, the first is LoadFromFile only and the second one is additionally adding 10000 more nodes to the beginning (!) of the XML like PrepareTest does, which is worst case but looking at the delta to the base test, even this doesn't show quadratic effects. Also note that counting the nodes can be replaced with any other operation, so it looks like there is some delayed initialization/validation of the XML file involved that causes the problem and any manipulation afterwards shows expected behaviour.

Memory usage is not high, the last test case (47681 nodes) has a peak memory usage of 39 MB, its XML filesize is 1.3 MB.

The first thing that is done after loading the XML (e.g. reading or writing some nodes or accessing node count) is slow and it shows quadratic runtime behaviour, so any log file above 10 MB is unusable.

We already solved the performance problems along with some other things by parsing small chunks of 100 messages, and I'm aware that the Delphi XML routines are not suited/overkill for this use case - using a different XML library would most likely stop the performance problems. So I'm not asking for a solution for the problem (although it would be interesting to know if the problem can be solved without using a different XML library).

My question is: What is the reason for the quadratic runtime behaviour of the Delphi XML routines, respectively MSXML? I can't imagine things that would lead to this in XML loading/parsing/validating, besides really "stupid" things like managing the nodes in a linked list instead of a tree, but I might be overlooking something, perhaps DOM related.

score 7 · Accepted Answer

XML がロギングに適していないという mj2008 に同意します。とはいえ、この問題と一般的な大きな XML ファイルは、SAXを使用することでより高速に処理できます。XML データの着信ストリームを解析しながらイベントをスローします。これにより、項目をディスクから読み取るときに処理できるようになり、指数関数性が緩和されます。 XSLT に渡す前にすべてをメモリにロードします。

Delphi で SAX を (まだ) 行っていないことを後悔していますが、最も難しいのは、必要な SAX インターフェイス ( ISAXContentHandler など) を実装することだと思いますが、Delphi には TInterfacedObject と TAutoObject などがあります。

score 4 · Accepted Answer

一言で言えば、バイナリライブラリの MSXML が非常に遅いのはなぜですか? 知るか。誰も気にしない。分解しますか？マイクロソフトに侵入して、そのソースコードを入手しますか? これは Delphi ではなく、マイクロソフトのコードです。

XML はログ記録には適していませんが、MSXML よりも OmniXML の方が適していると思われます。

ただし、はるかに優れた選択肢は、「追加のためにテキストファイルを開き、行を書き込み、テキストファイルを閉じる」という方法です。固有のスケーラビリティと、必要な解析の欠如に注意してください。

score 3 · Accepted Answer

他の方のコメントとは裏腹に、私は XML はロギングに優れたフォーマットだと思います。XML 用の Delphi VCL ラッパーはコアメモリを非常に貪欲に使用するため、大規模な純粋な TXMLDocument 処理のパフォーマンスが低いのはこのためかもしれません。

代わりに、単純な XSLT 変換を使用して XML ログに投稿することをお勧めします。このソリューションのパフォーマンスを大規模に測定したことはありませんが、現在報告されているものよりも大幅に改善されると思います.

スタイルシート。

たとえば、ログが次のようになっているとします...

<log>
  <message>This is the first message<message/> 
</log>

この単純な XSLT 1.0 スタイルシートには、パラメーターが含まれていますaddend-message...

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output indent="yes" omit-xml-declaration="yes" />
<xsl:strip-space elements="*" />  
<xsl:param name="addend-message" select="''" />

<xsl:template match="@*|node()">
  <xsl:copy>
    <xsl:apply-templates select="@*|node()" />
  </xsl:copy>
</xsl:template>  

<xsl:template match="log">
  <xsl:copy>
    <xsl:apply-templates select="@*|node()" />
    <message><xsl:value-of select="$addend-message" /></message>
  </xsl:copy>
</xsl:template>

... ログにメッセージを追加します。

言語バインディング

Delphi でこれを実現するには、次の宣言を使用します...

ITransform = interface
  procedure AddParameter( const sParamBaseName, sParamValue, sNamespaceURI: string);
  procedure Transform;
  property  InputDocumentFileName : string;
  property  OutputDocumentFileName: string;
end;

function MS_Transform( const sStylesheet: string): ITransform;

スタイルシートを文字列として渡して、ITransform を作成します。両方のファイル名プロパティをログのファイル名に設定します。ログにメッセージを追加する必要があるたびに、を呼び出しAddParameter()てからTransform().

ソリューションの実装の詳細

前述の言語バインディングの可能な実装の 1 つは ...

uses XMLIntf, msxml, msxmldom, sysutils;

type
  ITransform = interface
    ['{1004AE9A-D4AE-40E1-956D-AD98801AF7C1}']
      procedure SetInputDocumentFileName ( const sValue: string);
      procedure SetOutputDocumentFileName( const sValue: string);
      procedure AddParameter( const sParamBaseName, sParamValue, sNamespaceURI: string);
      procedure Transform;

      property InputDocumentFileName : string    write SetInputDocumentFileName;
      property OutputDocumentFileName: string    write SetInputDocumentFileName;
    end;

    TMS_XSLT = class( TInterfacedObject, ITransform)
    private
      FStylesheet: IXSLTemplate;
      FStylesheetAsDoc: IXMLDOMDocument2;
      FInputFN, FOutputFN: string;
      FProcessor: IXSLProcessor;;

      procedure SetInputDocumentFileName ( const sValue: string);
      procedure SetOutputDocumentFileName( const sValue: string);
      procedure MakeProcessor;

    publc
      constructor Create( const sStylesheet: string);
      procedure AddParameter( const sParamBaseName, sParamValue, sNamespaceURI: string);
      procedure Transform;

      property InputDocumentFileName : string    write SetInputDocumentFileName;
      property OutputDocumentFileName: string    write SetInputDocumentFileName;
    end;

  function MS_Transform( const sStylesheet: string): ITransform


function MS_Transform( const sStylesheet: string): ITransform
begin
result := TMS_XSLT.Create( sStylesheet)
end;

constructor TMS_XSLT.Create( const sStylesheet: string);
begin
  FStyleSheet := msxml.CoXSLTemplate60.Create;
  FStylesheetAsDoc := msxml.CoFreeThreadedDOMDocument60.Create;
  FStylesheetAsDoc.loadXML( sStyleSheetContent);
  FStylesheet.stylesheet := FStylesheetAsDoc  
end;

procedure TMS_XSLT.MakeProcessor;
begin
if not assigned( FProcessor) then
  FProcessor := FStylesheet.createProcessor
end;

procedure TMS_XSLT.SetInputDocumentFileName( const sValue: string);
begin
FInputDoc := sValue
end;

procedure TMS_XSLT.SetOutputDocumentFileName( const sValue: string);
begin
FOutputDoc := sValue
end;

procedure TMS_XSLT.AddParameter( const sParamBaseName, sParamValue, sNamespaceURI: string);
begin
MakeProcessor;
FProcessor.addParameter( sParamBaseName, sParamValue, sNamespaceURI)
end;

procedure TMS_XSLT.Transform;
var
  Doc: TXMLDocument;
  DocIntf: IXMLDocument;
  oXMLDOMNode: IXMLDOMNodeRef;
  sOutput: string;
begin
MakeProcessor;
try
  Doc  := TXMLDocument.Create( nil);
  Doc.Options := [doNodeAutoCreate, doNodeAutoIndent, doAttrNull, doAutoPrefix, doNamespaceDecl];
  Doc.DOMVendor := GetDOMVendor( 'MSXML');
  DocIntf := Doc;
  DocIntf.LoadFromFile( FInputFN);
  DocIntf.Active := True;
  if Supports( DocIntf.Node.DOMNode, IXMLDOMNodeRef, XMLDOMNode) then
    FProcessor.input := XMLDOMNode.GetXMLDOMNode;
  FProcessor.transform;
  while oProcessor.readyState <> 4 do sleep(1);
  sOutput := FProcessor.output;
  if sOutput = '' then exit;
  WriteToFile( sFOutputFN, sOutput);
  // Alternate way..
  //  Doc  := TXMLDocument.Create( nil);
  //  Doc.Options := [doNodeAutoCreate, doNodeAutoIndent, doAttrNull, doAutoPrefix, doNamespaceDecl];
  //  Doc.DOMVendor := GetDOMVendor( 'MSXML');
 //   DocIntf := Doc;
  //  DocIntf.LoadFromXML( sOutput);
  //  DocIntf.Active := True;
  //  DocIntf.SaveToFile( FOutputFN)
finally
  FProcessor := nil
  end
end;

これは、 Microsoft の MS XML ライブラリと XSLT エンジンにバインドします。残念ながら、 Saxon の XSLT プロセッサを Delphi コードにバインドする便利な方法を知りません。

代替実装

MS の XSLT エンジンを活用するための別の実装は、私の回答 here に示されています。この方法の欠点は、パラメーター化がネイティブではないことです。スタイルシートをパラメータ化するには、変換前にスタイルシートで文字列置換を行うことにより、独自のロールを作成する必要があります。

パフォーマンスに関する考慮事項

大量のロギングを迅速に行っている場合は、メッセージをキャッシュしてメモリに記録し、あまり頻繁ではない定期的な間隔で、単一の XSLT 変換でキャッシュをパージしてすべてのメッセージを書き込むことをお勧めします。

score 1 · Accepted Answer

「指数」という用語を数学的な意味で使用していますか、それとも一般的な意味で使用していますか? たとえば、それが本当に二次関数なのか、それとも何らかのしきい値 (メモリサイズ) に達するまでパフォーマンスがかなり線形であり、その時点で突然低下する関数なのかを知ることは興味深いでしょう。

2Mb を処理するのに 1 分もかかる場合は、何かがひどく間違っています。あなたの環境については推測できるほどよくわかっていませんが、これにはせいぜい 1 秒ほどかかるはずです。ドリルダウンして、時間がどこに向かっているのかを見つける必要があります。XML の解析に時間を費やしているのか、解析が完了した後に XML を処理しているのかを確認することから始めます。

xml - Quadratic runtime for Delphi XML (MSXML) routines

4 に答える 4

スタイルシート。

言語バインディング

ソリューションの実装の詳細

代替実装

パフォーマンスに関する考慮事項

Related

Reference