はじめに

PLATEAUなどの3D都市モデルデータには様々な形式がありますが、PLATEAUでは巨大なCityGMLファイル（XML）が大量にあるため、これらを高速に処理できることは重要です。XMLを読む処理が、そのまま計算資源の使用量や処理時間を決めるといっても過言ではありません。速くなればコストが下がり、ユーザーへのフィードバックも速くなって体験も向上します。

この記事では、Go で 高速・省メモリな XML ストリーミング処理を目指して作った gosax というライブラリについて書いていきます。

• Go 標準の encoding/xml が遅い場面とその理由
• gosax が何を犠牲にし、何を優先したのか
• どの工夫が効果的で、どこに注意が必要か

gosax とは

今回作ったライブラリがこれです。

https://github.com/orisano/gosax

gosax は、Go で書いた高速・省メモリな、SAX 風ストリーミング XML パーサです。

CGO なし（= libxml2 などに依存しない）で、入力全体をメモリに展開せずに処理できるようにしています。高速動作を目標にしており、その代わりに仕様の全部を面倒見ない部分もあります。

また、encoding/xml からの移行や気軽に試す用途向けに、gosax/xmlb という少しリッチなパッケージも用意しました。

背景

まず、高速にXMLを処理する方法として、Rust の XML パーサー quick-xml を使うのはどうか?という話がありました。

quick-xml は Rust で書かれた高性能な XML リーダー/ライターで、ゼロコピーに近い設計、メモリアロケーションの効率性、各種エンコーディングや名前空間解決のサポートなどの特徴を持ち、ベンチマークでは xml-rs の約50倍の速度を実現しています。

プログラミング言語は適材適所ではあると思うのですが、単一のシステムで複数のプログラミング言語を使うことは、メンテナンスコストを高くします。既存のアプリケーションでは Go が使われており、まず Go を用いた実装を検討することにしました。

ただ、Go 標準の encoding/xml には性能面で不安が残ります。公式の issue では、2017年にユーザーが大規模XMLファイルのSAX解析でC#と比較して極端に低いパフォーマンスを報告し、ボトルネックがディスクI/OではなくCPUであることを指摘しています。この issue は現在も「NeedsInvestigation」と「Performance」のラベルが付いたままで、根本的な改善は行われていません。

公式の issue 以外にも、encoding/xml が特定のユースケースで遅いため自作した、という話が多く存在しています。Redditでは、標準ライブラリの4倍高速なXMLトークナイザー（github.com/muktihari/xmltokenizer）の開発が報告されています。

また、github.com/tamerh/xml-stream-parser では、大規模XMLデータをストリーミング方式で効率的に解析するためのライブラリが公開されており、要素のスキップ機能、属性のみの解析、XPath クエリのサポートなどの機能を備えています。

golangleipzig.space の記事では、encoding/xml の性能問題を並列化で解決する方法が紹介されています。カスタムの TagSplitter を実装し、XMLストリームを約16MBのチャンクに分割してバッチ処理することで、327GBの PubMed XML データ(約3600万文書)の処理時間を逐次処理の177分から並列処理の20分へと約9倍改善しています。

また、2019 年に書かれた Eli Bendersky の記事では詳細なベンチマークがあり encoding/xml が遅いことが示されていました。230MBのXMLファイルの処理で、Go標準ライブラリは6.24秒かかるのに対し、Python の xml.etree.ElementTree(C実装の libexpat を使用)は3.7秒、そして純粋な C実装(libxml の SAX API)は0.56秒という結果でした。記事では、Cgo を使って libxml をラップした gosax モジュールも開発しており、最適化後は3.68秒まで高速化し、Python 実装と同等の速度を実現しています。この記事には実装コードとベンチマーク用リポジトリも公開されています。

このベンチマークは2024年にも Hacker News のコメント欄で第三者により実施されており、M1 Mac での再現テストでは Go 標準ライブラリが3.35秒、gosax が1.45秒、C が0.38秒という結果が報告され、大きな改善は見られないことが確認されました。筆者も手元でベンチマークを実行して同様の結果が得られることを確認しました。

既存実装でベンチマークを取る

quick-xml においても同様の実装をし、結果の確認を行いました。223MB の out.xml に対する結果は以下です。

今回のベンチは「巨大な XML の要素を数える」みたいな、かなりシンプルなケースです。文字列処理の細かい差よりも、まずはパーサのコアを見たいのと、CityGML みたいなデータでも前処理としてこういう走査はよくやるので、この形にしています。

Command	Note	Mean [s]	Min [s]	Max [s]	URL
./go-stdlib-count ./out.xml	go 1.22.2	3.094 ± 0.025	3.045	3.132	github
python3 etree-count.py ./out.xml	Python 3.12.3	2.262 ± 0.023	2.245	2.319	github
python3 lxml-count.py ./out.xml	Python 3.12.3	2.218 ± 0.015	2.191	2.232	github
./xml-stream-parser-count ./out.xml	go 1.22.2	1.553 ± 0.008	1.548	1.573	gist
./eliben-gosax-count ./out.xml	go 1.22.2	1.146 ± 0.010	1.134	1.171	github
./quick-xml-count ./out.xml	rustc 1.81.0-nightly, release build	0.426 ± 0.031	0.409	0.513	gist
./c-libxmlsax-count ./out.xml	Apple clang version 14.0.3, -O2	0.365 ± 0.004	0.362	0.374	github

この結果を見ると、Go の既存実装だと quick-xml と同等のパフォーマンスが出ないことがわかりました。「じゃあ Go で quick-xml ぐらいを狙うとしたら、何をやる必要があるのか？」が今回のスタート地点です。

実装方針

高速なライブラリを目指す以上、API デザイン、そして細部のパフォーマンスに気をつけて作る必要があります。愚直な実装を作りホットスポットを潰していくやり方が、早すぎる最適化を避ける方法として良いとされていますが、それでは駄目な場合もあります。

筆者は「Hotspot performance engineering fails」の考え方を支持しており、どこか一つのホットスポットがあってそれを潰していけばよい訳では無いと思っています。

そこで今回は以下の順番で進めました。

• まず制約を決める
• その制約の中で「勝ち筋がある設計」に寄せる
• その上でプロファイルしながら詰める

前提となる制約

• ビルドが大変になるので CGO に依存しない → libxml2 に依存しない
• 入力全体をメモリに展開しなくても処理できる → ストリーミングパーサー
• quick-xml と同等の速度を実現する → 不要なコピーを避ける

quick-xml の速度を目標として設定し、Go向けにポーティングすることをまず始めました。 quick-xml のパーサー部分はGCなどを考慮しないため、コンパイラの最適化性能が大きく劣後しているわけではないと考えたためです。

ただ Rust の作りと同じことが Go でできるわけではないので、ポートする際にどう実装するか考える必要がありました。筆者はもともと github.com/goccy/go-json にコントリビュートしていた経験から、Go で高速なパーサーを作る事例などを知っていました。

• https://dave.cheney.net/paste/gophercon-sg-2023.html
• https://dconf.org/2017/talks/schveighoffer.html

Go で必要のないデータコピーを避けられるバッファー、そのバッファーの上でパーサーを書く方法は pkg/json, goccy/go-json が大いに参考になりました。

gosax の設計

大規模なXMLを処理する際には、わずかなメモリ割り当て、データコピー、条件分岐といった要素がすべてパフォーマンスに影響を及ぼします。さらに問題となるのは、単一のボトルネックを解消すれば良いというわけではなく、複数の要因が同時にパフォーマンスを低下させる傾向にあることです。

そのため、gosaxでは当初から「性能向上が見込める設計上の制約」を明確に定め、その制約の下で実装を最適化する方針を採用しました。実装における主な特徴は以下の通りです。

• バッファーの一部分をそのままユーザーに露出するためコピーが発生しない
  • そのタイミングでアクセスする分には問題ないが、外に持ち出す際はコピーする必要がある
  • つまり、誤った使い方ができるようになっている（速さ優先）
• インターフェースを使っていない
  • Go だとインターフェースを使うと基本的にヒープに配置されるため
• 状態管理を関数を使って行う
  • switch のコストは減るが inline 化を行うことができない
• バッファーの拡張をパーサーが行う
  • パースしている関数の中が基本的に for ループになる

好みの問題もありますが、今回の目的（巨大なXMLを高速に走査する）においては、このような割り切りが有効でした。

速度の肝：バイト列検索

工夫した中でかなり速度において重要だったのが、バイト列検索部分です。

XMLのストリーミングパーサーは結局、 < や>、/>、クォート、空白といった区切り文字を探す処理が中心になります。ここが遅いと、その上にどれだけ賢い設計を乗せても速くなりません。

quick-xml は BurntSushi/memchr を使用しており、これは高速化に多大な労力を費やして作られたライブラリです。これがパーサーのパフォーマンスの根幹部分を担っているため、Go で同等のライブラリを作成してメンテナンスすることは難しいのが現実です。

ただ bytes.IndexByte は内部でうまく SIMD が使われ、ロジックが Go チームによって高速化・メンテナンスが行われているため、なるべくこれを使うことにしました。一方で bytes.IndexAny を使う場合は SIMD が使われないので、こちらのケースは対応する必要があります。

また、Go で自分で SIMD を使ったアセンブリを書くという方法も考えられますが、筆者の実体験として高速にならないケース（inline 化ができない、ABI0 によるオーバーヘッドなど）によく遭遇していました。さらにメンテナンスコストや環境毎に実装を用意しないといけない点を考え、今回は採用しませんでした。

アセンブリを書く必要のない SWAR であればメンテナンスコストの問題はほとんどないため、今回はこちらを採用しました。このバイト列検索の高速化は gosax の性能に大きく影響しました。

このように、高速なパーサーを書くうえでは SIMD や SWAR の使用は避けられないため、どこかのレイヤーで実現できるようにしておく必要があります。

検証結果

以上の様々な工夫を凝らした gosax の性能ですが、以下の結果になりました。

ここで出しているのはかなりシンプルなケースなので、「この数値がそのまま実運用に出る」わけではありません。ただ少なくとも、Go でもこの方向で詰めれば速度は出せることがわかると思います。

Command	Note	Mean [s]	Min [s]	Max [s]	Relative	URL
./go-stdlib-count ./out.xml	go 1.22.2	3.094 ± 0.025	3.045	3.132	14.02 ± 0.34	github
python3 etree-count.py ./out.xml	Python 3.12.3	2.262 ± 0.023	2.245	2.319	10.25 ± 0.26	github
python3 lxml-count.py ./out.xml	Python 3.12.3	2.218 ± 0.015	2.191	2.232	10.05 ± 0.24	github
./xml-stream-parser-count ./out.xml	go 1.22.2	1.553 ± 0.008	1.548	1.573	7.04 ± 0.16	gist
./eliben-gosax-count ./out.xml	go 1.22.2	1.146 ± 0.010	1.134	1.171	5.19 ± 0.13	github
./quick-xml-count ./out.xml	rustc 1.81.0-nightly, release build	0.426 ± 0.031	0.409	0.513	1.93 ± 0.15	gist
./c-libxmlsax-count ./out.xml	Apple clang version 14.0.3, -O2	0.365 ± 0.004	0.362	0.374	1.66 ± 0.04	github
./orisano-gosax-count ./out.xml	go 1.22.2	0.221 ± 0.005	0.218	0.237	1.00	github

シンプルなケースにおいては目標の性能を達成していそうです。

ベンチマークを見るときの注意点

高速を謳うパーサーは様々なフォーマットで存在します。ベンチマークでは一番早い結果が出ており、他の実装に比べて優位であるとされています。

ただ、気をつけるべきは、そのパーサーはコストの高い仕様を無視しているだけではないのか、ということです。エスケープシーケンスを解釈していないため文字列の処理が早い、結果のソートをしない、などのケースが多くあります。

もちろんそれもライブラリ側の選択の一つであり、確かに特定のユースケースによっては不要なため、パフォーマンスを優先しユーザー側で回避したいという場合も存在します。

gosax も同様の考え方を採用しています。gosax は速度を優先するため、いくつかの責務をライブラリ側で担わない設計です。そのため、encoding/xml と同じ感覚で使うと問題が生じます。ユーザーはドキュメントを読み、正しい使い方を理解する必要があります。

そして、できれば、ベンチマークは必ず自分のユースケースで取り直すべきです。

同じライブラリの同じ使い方でも、名前空間の扱い方、欲しい情報の取り方（属性やテキスト等）、エスケープの有無でボトルネックが変わります。gosax が合っているかどうかは、実データ+プロファイル込みで判断するのが一番確実です。

終わりに

ひとまず目標の性能を達成したので gosax を用いて、PLATEAUのCityGML処理等、様々な処理を実装しました。これらの実装により非常に高速なXML処理ができるようになり、PLATEAU CityGML APiでは、その場で巨大なCityGMLを読み込み、数秒以内に結果を返すというAPIが実現しました。

このように、工夫次第で、Go でも高速な XML パーサーを作成できることがわかりました。ただし、不要なコピーを避けるには、Go では unsafe な実装しか選択肢がありません。安全かつ高速な API を提供できる Rust のような言語の方が、この領域に適していると感じました。

また、公表されているベンチマーク結果は鵜呑みにせず、自分が使うユースケースでベンチマークを取り直すのが一番良いです。その時にはプロファイリングも含めて行い、ライブラリのオプションを調整するところまで行うとよいでしょう。

良ければ Star してください。励みになります。

https://github.com/orisano/gosax