[インデックス 14745] ファイルの概要

コミット

commit cfcc3ebfa4358c7c5d94c2a9b32481ab0fb3aeaf
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Mon Dec 24 16:53:25 2012 +0100

    exp/norm: changed API of Iter.
    Motivations:
     - Simpler UI. Previous API proved a bit awkward for practical purposes.
     - Iter is often used in cases where one want to be able to bail out early.
       The old implementaton had too much look-ahead to be efficient.
    Disadvantages:
     - ASCII performance is bad. This is unavoidable for tiny iterations.
       Example is included to show how to work around this.
    
    Description:
    Iter now iterates per boundary/segment. It returns a slice of bytes that
    either points to the input bytes, the internal decomposition strings,
    or the small internal buffer that each iterator has. In many cases, copying
    bytes is avoided.
    The method Seek was added to support jumping around the input without
    having to reinitialize.
    
    Details:
     - Table adjustments: some decompositions exist of multiple segments.
       Decompositions that are of this type are now marked so that Iter can
       handle them separately.
     - The old iterator had a different next function for different normal forms
       that was assigned to a function pointer called by Next.
       The new iterator uses this mechanism to switch between different modes
       for handling different type of input as well.  This greatly improves
       performance for Hangul and ASCII. It is also used for multi-segment
       decompositions.
     - input is now a struct of sting and []byte, instead of an interface.
       This simplifies optimizing the ASCII case.
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/6873072

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/cfcc3ebfa4358c7c5d94c2a9b32481ab0fb3aeaf

元コミット内容

このコミットは、Go言語の実験的なUnicode正規化パッケージ exp/norm における Iter (イテレータ) のAPI変更を主目的としています。主な変更点は、Iter のユーザーインターフェースの簡素化、早期終了の効率化、そして内部実装の最適化です。特に、ASCII文字のパフォーマンス低下という既知の欠点に対処しつつ、ハングル文字や多セグメント分解の処理性能を向上させています。

変更の背景

exp/norm パッケージは、Unicode文字列の正規化（NFC, NFD, NFKC, NFKDなどの正規化形式への変換）を扱うためのものです。文字列の比較や検索において、異なる表現を持つ同じ意味の文字列を正しく扱うために正規化は不可欠です。

このコミットが行われた背景には、既存の Iter APIが実用的な目的には扱いにくいという問題意識がありました。特に、イテレーションの途中で処理を中断したい場合に、従来の Iter の実装が持つ過度な先読み（look-ahead）が効率を妨げていました。これは、正規化処理が複雑なUnicode文字の分解・合成を伴うため、不必要な計算やメモリコピーが発生しやすかったためと考えられます。

また、パフォーマンスの観点から、特にASCII文字のような単純なケースでの効率改善が求められていました。Unicode正規化は複雑なテーブルルックアップや文字の再配置を伴うため、単純なASCII文字列に対してもオーバーヘッドが生じがちです。このコミットは、これらの課題を解決し、より使いやすく、より効率的な正規化イテレータを提供することを目指しています。

前提知識の解説

• Unicode正規化 (Unicode Normalization): Unicodeには、同じ文字や文字シーケンスを複数の異なるバイト列で表現できる場合があります（例: 「é」は単一のコードポイントU+00E9で表現することも、基本文字「e」と結合文字「´」U+0301の組み合わせで表現することも可能）。正規化は、これらの異なる表現を統一された形式に変換するプロセスです。主な正規化形式には以下があります。
  • NFC (Normalization Form Canonical Composition): 互換性分解を行い、可能な限り結合します。
  • NFD (Normalization Form Canonical Decomposition): 正準分解を行い、結合は行いません。
  • NFKC (Normalization Form Compatibility Composition): 互換性分解を行い、可能な限り結合します。NFCよりも広範な互換性分解を行います。
  • NFKD (Normalization Form Compatibility Decomposition): 互換性分解を行い、結合は行いません。NFKCと同様に広範な互換性分解を行います。
• 結合文字 (Combining Characters): アクセント記号やダイアクリティカルマークなど、先行する基本文字と組み合わせて表示される文字です。Unicode正規化では、これらの結合文字の順序や合成が重要な要素となります。
• 分解 (Decomposition): ある文字を、その構成要素となる基本文字と結合文字に分解するプロセスです。
• 合成 (Composition): 分解された文字シーケンスを、可能な限り単一の文字に結合するプロセスです。
• イテレータ (Iterator): コレクション（この場合は文字列やバイトスライス）の要素に順次アクセスするためのオブジェクトです。exp/norm パッケージの Iter は、正規化されたセグメント（部分文字列）を順次提供します。
• 先読み (Look-ahead): イテレータが次の要素を決定するために、現在の位置より先のデータを事前に読み込むこと。効率的な処理のために必要ですが、過度な先読みはメモリ使用量や処理時間を増加させる可能性があります。
• ハングル (Hangul): 朝鮮語の文字体系。Unicodeでは、ハングル音節は複数の子音と母音の組み合わせとして分解・合成されることがあります。

技術的詳細

このコミットは、exp/norm パッケージの Iter 型の内部構造とAPIを大幅に変更しています。

1. Iter APIの変更:

   • 従来の SetInput / SetInputString メソッドが Init / InitString に変更されました。
   • Next メソッドのシグネチャが変更されました。以前は Next(buf []byte) int で、呼び出し側がバッファを提供し、書き込まれたバイト数を返していました。新しいAPIでは Next() []byte となり、イテレータ自身がバイトスライスを返します。これにより、呼び出し側はバッファ管理の複雑さから解放され、よりシンプルなUIが実現されました。
   • Seek メソッドが追加されました。これにより、イテレータの現在位置を任意にジャンプさせることが可能になり、再初期化なしに特定の入力部分から処理を再開できるようになりました。これは、特に大きな文字列を扱う際に、部分的な処理やスキップが必要な場合に有用です。

2. セグメントごとのイテレーション:

   • Iter は「境界/セグメントごと」にイテレーションを行うようになりました。これは、Unicode正規化の文脈で、意味のある最小単位（例えば、基本文字とその結合文字のまとまり）で文字列を区切って処理することを意味します。
   • Next() が返すバイトスライスは、入力バイト、内部の分解文字列、またはイテレータが持つ小さな内部バッファのいずれかを指します。これにより、多くの場合でバイトのコピーが回避され、メモリ効率が向上しています。

3. テーブル調整と多セグメント分解の扱い:

   • 一部の分解は複数のセグメントで構成されることがあり、これらは Iter が個別に処理できるようにマークされるようになりました。これにより、複雑なUnicode文字の正規化がより正確かつ効率的に行われます。
   • maketables.go で decompSet のサイズが [4] から [6] に変更され、firstMulti, endMulti などの新しい定数が追加されています。これは、多セグメント分解を識別し、適切に処理するための内部的な変更です。

4. next 関数のポインタとモード切り替え:

   • 従来のイテレータは、異なる正規化形式（NFC, NFDなど）に応じて異なる next 関数を関数ポインタとして割り当てていました。
   • 新しいイテレータでは、このメカニズムを拡張し、異なる種類の入力（ASCII、ハングル、多セグメント分解など）を処理するための異なるモードを切り替えるために使用しています。これにより、ハングル文字やASCII文字のパフォーマンスが大幅に向上しました。例えば、nextASCIIBytes や nextASCIIString といった専用の高速パスが導入されています。

5. input 型の変更:

   • input 型がインターフェースから string と []byte を持つ構造体に変更されました。
   • input 構造体は、str フィールド（文字列用）と bytes フィールド（バイトスライス用）を持ち、setBytes や setString メソッドでどちらのデータソースを使用するかを切り替えます。
   • この変更により、特にASCIIケースの最適化が簡素化されました。インターフェースを介した呼び出しは、Goのコンパイラにとって最適化が難しい場合がありますが、具体的な構造体に変更することで、より直接的なアクセスとインライン化が可能になり、パフォーマンスが向上します。

コアとなるコードの変更箇所

このコミットで変更された主要なファイルは以下の通りです。

• src/pkg/exp/norm/iter.go: Iter 型の定義、Init, InitString, Next, Seek メソッドの実装が大幅に変更されました。特に、nextDecomposed と nextComposed のロジックが簡素化され、nextASCIIBytes, nextASCIIString, nextHangul, nextMulti, nextMultiNorm などの新しい内部イテレーション関数が追加されました。
• src/pkg/exp/norm/input.go: input 型がインターフェースから構造体に変更され、skipASCII, skipNonStarter, appendSlice, copySlice, charinfoNFC, charinfoNFKC, hangul などのメソッドが input 構造体のメソッドとして再実装されました。
• src/pkg/exp/norm/forminfo.go: formInfo 構造体に nextMain フィールドが追加され、各正規化形式のデフォルトの next 関数を指すようになりました。また、Properties に multiSegment メソッドが追加されました。
• src/pkg/exp/norm/maketables.go: 内部的な decompSet の定義が変更され、多セグメント分解を識別するための新しい定数が追加されました。
• src/pkg/exp/norm/tables.go: firstMulti, endMulti などの新しい定数が追加され、分解テーブルのデータ構造が更新されました。
• src/pkg/exp/norm/example_iter_test.go: 新しい Iter APIの使用例を示すテストファイルが追加されました。特に EqualOpt 関数は、ASCII文字のパフォーマンス最適化のワークアラウンドを示しています。
• src/pkg/exp/norm/iter_test.go, src/pkg/exp/norm/normalize_test.go, src/pkg/exp/norm/normregtest.go, src/pkg/exp/norm/composition.go, src/pkg/exp/norm/composition_test.go: 新しい Iter APIに合わせて既存のテストや関連コードが更新されました。

コアとなるコードの解説

iter.go の変更が最も重要です。

• Iter 構造体から outStart, inStart, maxp, maxseg, tccc, done といったフィールドが削除され、buf (内部バッファ), multiSeg (多セグメント分解の残り), asciiF (ASCII専用の高速パス関数) が追加されました。これにより、イテレータの状態管理がよりシンプルかつ効率的になりました。
• Next() メソッドは引数を取らなくなり、[]byte を直接返すようになりました。これは、イテレータが内部でバッファを管理し、必要に応じて入力のバイトスライスを直接参照するか、内部バッファにコピーして返すことで、呼び出し側の負担を軽減し、コピーを最小限に抑える設計思想を反映しています。
• nextDecomposed と nextComposed 関数は、それぞれNFD/NFKDとNFC/NFKCの正規化ロジックを実装していますが、内部的な状態管理が Iter 構造体に移譲され、よりクリーンなコードになっています。特に、ASCII文字やハングル文字の高速パスへの分岐ロジックが追加され、パフォーマンスが向上しています。
• input.go の input 構造体への変更は、Goの型システムを活用して、文字列 (string) とバイトスライス ([]byte) の両方を効率的に扱うための基盤を提供します。これにより、文字列操作における不必要な変換やコピーが削減されます。

全体として、このコミットは exp/norm パッケージの Iter の内部設計を根本的に見直し、パフォーマンスと使いやすさの両面で大幅な改善を実現しています。特に、Unicode正規化の複雑な特性（結合文字、多セグメント分解など）を効率的に処理するための巧妙な最適化が施されています。

関連リンク

• Go言語の exp/norm パッケージのドキュメント (コミット当時のもの、または最新版): https://pkg.go.dev/golang.org/x/text/unicode/norm (現在の x/text/unicode/norm パッケージに相当)
• Unicode正規化の概要: https://unicode.org/reports/tr15/

参考にした情報源リンク

• コミットメッセージ内の https://golang.org/cl/6873072 (Gerrit Code Reviewへのリンク)
• Go言語のソースコード (特に src/pkg/exp/norm ディレクトリ)
• Unicode Standard Annex #15: Unicode Normalization Forms