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

このコミットは、Go言語の実験的なexp/locale/collateパッケージにおける文字列比較（Compare、CompareString）および照合キー生成（Key、KeyString）のパフォーマンス改善とAPIの簡素化を目的としています。主な変更は、比較処理を「インクリメンタル」に行うように変更し、APIから明示的なバッファの受け渡しを不要にした点です。これにより、特に文字列比較の速度が大幅に向上し、照合キー生成においても正規化バッファの再初期化が不要になったことで性能が改善されています。

変更されたファイルは以下の通りです。

• src/pkg/exp/locale/collate/collate.go: 照合ロジックのコア部分。Compare、CompareString、Key、KeyStringの実装が変更され、Collatorおよびiter構造体が更新されています。
• src/pkg/exp/locale/collate/collate_test.go: collate.goの変更に対応するテストコード。CompareおよびKey関数の呼び出し方法が変更されています。
• src/pkg/exp/locale/collate/export.go: パッケージのエクスポートされた関数と型の定義。newCollatorの呼び出しに変更されています。
• src/pkg/exp/locale/collate/export_test.go: エクスポートされた関数のテスト。GetColElemsの引数からバッファが削除されています。
• src/pkg/exp/locale/collate/maketables.go: 照合テーブル生成ツール。テストコード内でバッファのリセット方法が変更されています。
• src/pkg/exp/locale/collate/regtest.go: 回帰テスト。Compare関数の呼び出し方法が変更されています。
• src/pkg/exp/locale/collate/table_test.go: 照合テーブル関連のテスト。テストデータが一部更新されています。
• src/pkg/exp/locale/collate/tools/colcmp/col.go: 照合比較ツール。Compare関数の呼び出し方法が変更されています。

コミット

コミットハッシュ: 8b7ea6489c40f2e54d01836b2fae611c39fb09d4 Author: Marcel van Lohuizen mpvl@golang.org Date: Thu Nov 15 22:23:56 2012 +0100

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

https://github.com/golang/go/commit/8b7ea6489c40f2e54d01836b2fae611c39fb09d4

元コミット内容

exp/locale/collate: changed implementation of Compare and CompareString to
compare incrementally. Also modified collation API to be more high-level
by removing the need for an explicit buffer to be passed as an argument.
This considerably speeds up Compare and CompareString.  This change also eliminates
the need to reinitialize the normalization buffer for each use of an iter. This
also significantly improves performance for Key and KeyString.

R=r, rsc
CC=golang-dev
https://golang.org/cl/6842050

変更の背景

このコミットの主な背景は、Go言語のexp/locale/collateパッケージにおける文字列の照合（比較およびソート）処理のパフォーマンス改善と、APIの使いやすさの向上です。

従来のCompareおよびCompareString関数は、比較対象の2つの文字列それぞれに対して完全な「照合キー」を生成し、その後にこれらのキーをバイト単位で比較するというアプローチを取っていました。この方法は、文字列が非常に長い場合や、文字列の初期部分で違いが判明する場合でも、常に完全なキーを生成する必要があるため、非効率的でした。特に、多くの文字列を比較するようなシナリオでは、このオーバーヘッドが顕著になります。

また、以前のAPIでは、CompareやKey関数に明示的に*Buffer型の引数を渡す必要がありました。これは、内部的なバッファの再利用を可能にするための設計でしたが、ユーザーにとってはAPIが複雑になり、バッファの管理を意識する必要がありました。さらに、このバッファが使用されるたびに正規化バッファを再初期化する必要があり、これがKeyおよびKeyString関数のパフォーマンスボトルネックとなっていました。

これらの課題を解決するため、以下の目標が設定されました。

1. インクリメンタル比較の導入: 文字列の照合キー全体を生成するのではなく、照合要素を逐次的に生成し、違いが判明した時点で比較を終了することで、不要な計算を削減する。
2. APIの簡素化: *Buffer引数を削除し、Collatorが内部でバッファを管理するようにすることで、ユーザーがバッファのライフサイクルを意識する必要をなくす。
3. 正規化バッファの効率的な利用: iter（イテレータ）が使用する正規化バッファの再初期化をなくし、KeyおよびKeyStringのパフォーマンスを向上させる。

これらの変更により、exp/locale/collateパッケージがより高速かつ使いやすくなることが期待されました。

前提知識の解説

このコミットを理解するためには、以下の概念について基本的な知識が必要です。

1. Unicode Collation Algorithm (UCA):

   • UCAは、Unicode文字列を言語的に正しい順序でソートおよび比較するための国際標準アルゴリズムです。単なるコードポイント順の比較ではなく、言語ごとの文字の重み付け、アクセント、大文字・小文字、句読点などのルールを考慮します。
   • UCAは、文字列を「照合要素（Collation Elements）」のシーケンスに変換し、これらの要素を比較することで順序を決定します。
   • 照合レベル: UCAは通常、複数のレベルで比較を行います。
     • Primary Level (第一レベル): 文字の基本的な形（例: 'a'と'A'は同じ）。最も重要なレベルで、言語によって異なる文字の順序を定義します。
     • Secondary Level (第二レベル): アクセントやダイアクリティカルマーク（例: 'a'と'á'）。第一レベルが同じ場合に適用されます。
     • Tertiary Level (第三レベル): 大文字・小文字、幅の違い（例: 'a'と'A'、全角と半角）。第二レベルが同じ場合に適用されます。
     • Quaternary Level (第四レベル): 句読点や記号、または可変要素（Variable Elements）の扱い。第三レベルが同じ場合に適用されます。
     • Identity Level (同一レベル): 最終的なバイト比較。全ての照合レベルが同じ場合に、元の文字列のバイト列を比較して最終的な順序を決定します。

2. 照合キー (Collation Key):

   • UCAに基づいて生成されるバイト列です。このバイト列は、通常のバイト比較（bytes.Compare）を行うだけで、元のUnicode文字列の言語的に正しい順序を反映するように設計されています。
   • 照合キーは、異なる照合レベルの重み（Primary, Secondary, Tertiaryなど）を連結して構成されます。これにより、キーをバイト比較するだけで、UCAの多段階比較ロジックを効率的に実行できます。

3. Unicode正規化 (Unicode Normalization):

   • Unicodeには、同じ文字を異なるバイト列で表現できる場合があります（例: éは単一のコードポイントU+00E9で表現することも、e (U+0065) と結合用アキュートアクセント (U+0301) の組み合わせで表現することもできます）。
   • 照合を正確に行うためには、比較対象の文字列を事前に一貫した形式に変換する必要があります。これを「正規化」と呼びます。
   • NFD (Normalization Form D): 分解正規化形式。結合文字を分解して表現します。UCAでは通常、NFD形式に正規化された文字列を処理します。

4. exp/locale/collateパッケージ:

   • Go言語の標準ライブラリの一部として提供されている、ロケール（地域や言語）に依存する文字列照合機能を提供する実験的なパッケージです。
   • このパッケージは、UCAを実装し、多言語環境での文字列のソートや比較を可能にします。

5. インクリメンタル比較:

   • 従来の「完全な照合キー生成→キー比較」とは異なり、文字列の照合要素を先頭から順に生成し、同時に比較を進める手法です。
   • 両方の文字列の照合要素を比較し、違いが検出された時点でそれ以上の要素生成や比較を停止します。これにより、文字列の後半部分が同じである場合や、早い段階で違いが判明する場合には、大幅なパフォーマンス向上が期待できます。

これらの概念を理解することで、コミットがもたらす技術的な改善点とその影響を深く把握することができます。

技術的詳細

このコミットにおける技術的な変更は、主に以下の3つの側面に集約されます。

1. インクリメンタル比較の実装:

   • 以前のCompareおよびCompareString関数は、まず両方の文字列の完全な照合キーを生成し、その後bytes.Compareでキーを比較していました。
   • 今回の変更では、Collator構造体に_iter [2]iterという2つのiter（イテレータ）を埋め込むことで、インクリメンタル比較を可能にしています。
   • 新しいcompare()メソッドが導入され、このメソッドが2つのイテレータ（ia, ib）を使用して、各照合レベル（Primary, Secondary, Tertiary, Quaternary）で逐次的に比較を行います。
   • compareLevelヘルパー関数は、指定された照合レベルの次の要素を取得する関数（例: (*iter).nextPrimary）を受け取り、両方のイテレータから要素を一つずつ取得して比較します。違いが見つかればその場で結果を返し、両方の要素が0（終端）になればそのレベルの比較を終了します。
   • これにより、文字列の早い段階で違いが判明した場合、それ以降の照合要素の生成や比較がスキップされ、大幅なパフォーマンス向上が実現されます。

2. APIの簡素化とバッファ管理の変更:

   • Compare、CompareString、Key、KeyStringといった主要なAPIから、明示的な*Buffer引数が削除されました。
   • 以前は、ユーザーがcollate.Bufferをインスタンス化し、それを各関数に渡す必要がありました。これはバッファの再利用を意図したものですが、APIの複雑さを増していました。
   • 新しい実装では、Collator構造体自身が内部に_iter [2]iterを持つことで、必要なイテレータとそれに付随する正規化バッファ（iter.norm）や照合要素バッファ（iter.ce）を管理します。
   • Collator.iter(i)メソッドを通じて、内部のイテレータが取得され、そのイテレータが入力文字列を設定（setInput、setInputString）し、照合要素を生成します。
   • Buffer構造体は引き続き存在しますが、その役割は照合キーの格納に限定され、KeyやKeyStringの戻り値を保持するためのものとなりました。Buffer.ResetKeys()はBuffer.Reset()に名称変更され、キーバッファのみをリセットするようになりました。
   • この変更により、ユーザーはバッファの管理を意識することなく、より直感的にAPIを使用できるようになりました。

3. 正規化バッファの再初期化の排除とパフォーマンス向上:

   • 以前のiterの実装では、各比較またはキー生成のたびに正規化バッファが再初期化されていました。これは、特に短い文字列を多数処理する場合にオーバーヘッドとなっていました。
   • 新しいiter構造体は、norm [1024]byteという固定サイズの正規化バッファと、wa [512]colElemという固定サイズの照合要素バッファを内部に持ちます。
   • iter.init(c *Collator)メソッドで一度初期化されると、iter.reset()メソッドはこれらのバッファをクリアするだけで、再割り当てや再初期化は行いません。
   • iter.setInputおよびiter.setInputStringは、入力文字列を正規化し、その結果を内部のiter.normバッファに格納します。
   • iter.next()メソッドは、この正規化された入力から次の照合要素を抽出し、iter.ceバッファに追加します。
   • この変更により、KeyおよびKeyString関数が照合要素を生成する際の正規化バッファのオーバーヘッドが大幅に削減され、これらの関数のパフォーマンスも向上しました。

これらの技術的な変更は、exp/locale/collateパッケージの効率性と使いやすさを大きく改善し、Go言語における多言語対応の基盤を強化するものです。

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

このコミットにおけるコアとなるコードの変更は、主にsrc/pkg/exp/locale/collate/collate.goファイルに集中しています。

1. Collator構造体の変更:

   type Collator struct {
       Strength Strength
       f        norm.Form
       t        *table
       _iter [2]iter // 新しく追加された内部イテレータ
   }
   
   func (c *Collator) iter(i int) *iter {
       // TODO: evaluate performance for making the second iterator optional.
       return &c._iter[i]
   }
   

   Collatorが内部に2つのiterインスタンスを持つようになりました。これにより、Compare関数で2つの文字列を同時に処理できるようになります。

2. newCollator関数の導入と初期化:

   func newCollator(t *table) *Collator {
       c := &Collator{
           Strength: Quaternary,
           f:        norm.NFD,
           t:        t,
       }
       c._iter[0].init(c) // イテレータの初期化
       c._iter[1].init(c) // イテレータの初期化
       return c
   }
   

   New関数やInit関数（export.go）からnewCollatorが呼ばれるようになり、Collatorの生成時に内部のiterが初期化されるようになりました。

3. Buffer構造体の変更:

   type Buffer struct {
       buf [4096]byte // 内部バッファ
       key []byte     // 照合キーを保持
   }
   
   func (b *Buffer) Reset() { // ResetKeysからResetに名称変更
       b.key = b.key[:0]
   }
   

   Bufferは主にKeyやKeyStringの戻り値を保持するためのものとなり、ce（照合要素）バッファはiter内部に移動しました。ResetKeysメソッドはResetに名称変更されました。

4. CompareおよびCompareString関数のシグネチャ変更と実装:

   // 以前: func (c *Collator) Compare(buf *Buffer, a, b []byte) int
   // 変更後:
   func (c *Collator) Compare(a, b []byte) int {
       c.iter(0).setInput(c, a) // バッファ引数削除
       c.iter(1).setInput(c, b) // バッファ引数削除
       if res := c.compare(); res != 0 { // 新しい比較ロジック
           return res
       }
       if Identity == c.Strength {
           return bytes.Compare(a, b)
       }
       return 0
   }
   
   // CompareStringも同様に変更
   func (c *Collator) CompareString(a, b string) int {
       c.iter(0).setInputString(c, a)
       c.iter(1).setInputString(c, b)
       if res := c.compare(); res != 0 {
           return res
       }
       if Identity == c.Strength {
           if a < b {
               return -1
           } else if a > b {
               return 1
           }
       }
       return 0
   }
   

   *Buffer引数が削除され、Collator内部のイテレータを使用するようになりました。また、新しいcompare()メソッドを呼び出すことで、インクリメンタル比較が実行されます。

5. compare()およびcompareLevel()関数の追加:

   func (c *Collator) compare() int {
       ia, ib := c.iter(0), c.iter(1)
       // 各照合レベルでの比較ロジック
       // ...
       if res := compareLevel((*iter).nextPrimary, ia, ib); res != 0 {
           return res
       }
       // ...
       return 0
   }
   
   func compareLevel(f func(i *iter) int, a, b *iter) int {
       a.pce = 0 // 照合要素のポインタをリセット
       b.pce = 0
       for {
           va := f(a) // 次の照合要素を取得
           vb := f(b)
           if va != vb { // 違いがあれば即座にリターン
               if va < vb {
                   return -1
               }
               return 1
           } else if va == 0 { // 両方とも終端に達したらループ終了
               break
           }
       }
       return 0
   }
   

   インクリメンタル比較の核心部分です。各照合レベルで要素を逐次的に比較します。

6. KeyおよびKeyFromString関数の変更:

   // 以前: func (c *Collator) Key(buf *Buffer, str []byte) []byte
   // 変更後:
   func (c *Collator) Key(buf *Buffer, str []byte) []byte {
       buf.init()
       return c.key(buf, c.getColElems(str)) // getColElemsの引数からバッファ削除
   }
   
   // KeyFromStringも同様に変更
   func (c *Collator) KeyFromString(buf *Buffer, str string) []byte {
       buf.init()
       return c.key(buf, c.getColElemsString(str)) // getColElemsStringの引数からバッファ削除
   }
   

   getColElemsおよびgetColElemsStringの引数から*Bufferが削除され、これらの関数がiter内部のバッファを使用するように変更されました。

7. getColElemsおよびgetColElemsString関数の変更:

   // 以前: func (c *Collator) getColElems(buf *Buffer, str []byte)
   // 変更後:
   func (c *Collator) getColElems(str []byte) []colElem {
       i := c.iter(0) // 内部イテレータを使用
       i.setInput(c, str)
       for !i.done() {
           i.next() // 照合要素を内部バッファに追加
       }
       return i.ce // 内部バッファの参照を返す
   }
   
   // getColElemsStringも同様に変更
   func (c *Collator) getColElemsString(str string) []colElem {
       i := c.iter(0)
       i.setInputString(c, str)
       for !i.done() {
           i.next()
       }
       return i.ce
   }
   

   これらの関数は、Collatorの内部イテレータを使用し、照合要素をイテレータの内部バッファに格納するようになりました。

8. iter構造体の変更とメソッドの追加:

   type iter struct {
       src        norm.Iter
       norm       [1024]byte // 正規化バッファ
       buf        []byte
       t          *table
       p          int
       minBufSize int
   
       wa  [512]colElem // 照合要素バッファ
       ce  []colElem
       pce int // 照合要素の現在位置
   
       _done, eof bool
   }
   
   func (i *iter) init(c *Collator) { // 初期化メソッド
       i.t = c.t
       i.minBufSize = c.t.maxContractLen
       i.ce = i.wa[:0] // 内部バッファを初期化
       i.buf = i.norm[:0] // 内部バッファを初期化
   }
   
   func (i *iter) reset() { // リセットメソッド
       i.ce = i.ce[:0]
       i.buf = i.buf[:0]
       i.p = 0
       i.eof = i.src.Done()
       i._done = i.eof
   }
   
   func (i *iter) setInput(c *Collator, s []byte) *iter { // 入力設定
       i.src.SetInput(c.f, s)
       i.reset()
       return i
   }
   
   func (i *iter) setInputString(c *Collator, s string) *iter { // 入力設定
       i.src.SetInputString(c.f, s)
       i.reset()
       return i
   }
   
   // 以前: func (i *iter) next(ce []colElem) []colElem
   // 変更後:
   func (i *iter) next() { // 引数からceが削除され、内部バッファに直接追加
       // ...
       i.ce, sz = i.t.appendNext(i.ce, i.buf[i.p:])
       // ...
   }
   
   // 各照合レベルの次の要素を取得するメソッド
   func (i *iter) nextPrimary() int { ... }
   func (i *iter) nextSecondary() int { ... }
   func (i *iter) prevSecondary() int { ... } // 後方比較用
   func (i *iter) nextTertiary() int { ... }
   func (i *iter) nextQuaternary() int { ... }
   

   iter構造体は、正規化された入力と生成された照合要素を保持するための内部バッファを持つようになりました。また、各照合レベルの次の要素を効率的に取得するための新しいメソッドが追加されました。

これらの変更により、collateパッケージの内部構造が大きく変わり、パフォーマンスとAPIの使いやすさが向上しています。

コアとなるコードの解説

このコミットの核心は、exp/locale/collateパッケージにおける文字列比較のパラダイムシフトにあります。

1. Collatorとiterの連携によるインクリメンタル比較:

   • 以前は、Compare関数が呼び出されるたびに、比較対象の2つの文字列それぞれに対してKey関数が呼ばれ、完全な照合キーが生成されていました。これは、文字列が長い場合や、早い段階で違いが判明する場合でも、常に全ての照合要素を計算する必要があるため、非効率でした。
   • 新しいアプローチでは、Collator構造体が内部に_iter [2]iterという2つのiter（イテレータ）インスタンスを保持します。これらのイテレータは、比較対象の2つの文字列（aとb）それぞれに対応します。
   • Collator.Compare(a, b)が呼び出されると、まずc.iter(0).setInput(c, a)とc.iter(1).setInput(c, b)が実行され、それぞれのイテレータに入力文字列が設定されます。この際、文字列は内部で正規化され、イテレータのnormバッファに格納されます。
   • 次に、c.compare()メソッドが呼び出されます。このメソッドは、UCAの照合レベル（Primary, Secondary, Tertiary, Quaternary）に従って、順に比較を進めます。
   • compareLevelヘルパー関数は、特定の照合レベルでの比較を担当します。この関数は、両方のイテレータからそのレベルの次の照合要素を一つずつ取得し（例: ia.nextPrimary(), ib.nextPrimary()）、それらを比較します。
   • もし要素に違いがあれば、その時点で比較を終了し、結果を返します。これにより、文字列の後半部分が同じである場合や、早い段階で違いが判明する場合には、それ以降の照合要素の生成や比較がスキップされ、大幅なパフォーマンス向上が実現されます。
   • 各iterは、nextPrimary(), nextSecondary(), nextTertiary(), nextQuaternary()といったメソッドを持ち、これらが内部のce（照合要素）バッファから適切なレベルの要素を抽出し、必要に応じてnext()を呼び出してさらに照合要素を生成します。

2. バッファ管理の抽象化と効率化:

   • 以前のAPIでは、CompareやKey関数に*Buffer引数を明示的に渡す必要がありました。これは、ユーザーがバッファの再利用を管理することを強制し、APIの使いやすさを損ねていました。
   • このコミットでは、Collatorが内部でiterインスタンスを管理することで、バッファの管理を抽象化しました。ユーザーはもはやBufferをCompare関数に渡す必要がありません。
   • iter構造体は、正規化された入力文字列を保持するnormバッファと、そこから抽出された照合要素を保持するceバッファを内部に持ちます。これらのバッファは、iter.init()で一度初期化されると、iter.reset()で内容がクリアされるだけで、再割り当ては行われません。
   • これにより、特にKeyおよびKeyString関数が照合要素を生成する際に、正規化バッファの再初期化が不要になり、これらの関数のパフォーマンスも大幅に向上しました。
   • Buffer構造体は残されていますが、その役割は主にKeyやKeyStringが生成した照合キーを保持するためのものとなり、APIの引数としての役割はなくなりました。

これらの変更により、exp/locale/collateパッケージは、より高速で効率的な文字列照合機能を提供し、同時に開発者にとってより使いやすいAPIを実現しています。インクリメンタル比較は、特に大規模なデータセットのソートや、頻繁な文字列比較が必要なアプリケーションにおいて、顕著な性能改善をもたらすでしょう。

関連リンク

• Unicode Collation Algorithm (UCA): https://unicode.org/reports/tr10/
• Unicode Normalization Forms: https://unicode.org/reports/tr15/
• Go言語のexp/localeパッケージ (GoDoc): このパッケージは実験的なものであり、Goのバージョンによっては標準ライブラリに統合されているか、あるいは異なるパスにある可能性があります。最新の情報はGoの公式ドキュメントを参照してください。

参考にした情報源リンク

• Go Collation CL (Change List): https://golang.org/cl/6842050 (コミットメッセージに記載されているCLへのリンク)
• Go言語のソースコード: src/pkg/exp/locale/collate/ ディレクトリ内の関連ファイル。
• Unicode Consortium: UCAや正規化に関する公式ドキュメント。
• Go言語の公式ドキュメント: exp/locale/collateパッケージに関する情報。