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

本コミットは、Go言語のunicodeパッケージにおけるテーブル生成の改善に関するものです。具体的には、maketables.goの出力を一貫性のある形にするため、マップの要素をソートしてから処理するように修正されています。

コミット

コミットハッシュ: b4d6b71e169f48009948174cfc2478892ccb757d
作者: Russ Cox rsc@golang.org
日付: 2011年10月19日 16:02:22 (EDT)
コミットメッセージ: unicode: sort tables.go
詳細: Makes tables.go output consistent across maketable runs.

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

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

元コミット内容

unicode: sort tables.go

Makes tables.go output consistent across maketable runs.
(It was already inconsistent across architectures; the new
map iteration order just make it inconsistent across runs.)

R=r
CC=golang-dev
https://golang.org/cl/5303046
---
 src/pkg/unicode/maketables.go |   32 +-
 src/pkg/unicode/tables.go     | 6976 ++++++++++++++++++++---------------------
 2 files changed, 3508 insertions(+), 3500 deletions(-)

変更の背景

このコミットは、Go言語の開発における重要な時期に行われました。2011年当時、Go言語はまだ1.0リリース前の状態で、言語の仕様や実装が固まりつつある段階でした。この変更の背景には、以下のような要因があります：

マップの反復順序の変更: Go 1.0のリリースに向けて、マップの反復順序を意図的にランダム化する変更が行われました。これは、開発者がマップの順序に依存することを防ぐための設計決定でした。
決定論的な出力の必要性: maketables.goは、Unicodeの文字プロパティテーブルを生成するためのツールです。このツールの出力は、コンパイル時に決定論的である必要があり、実行のたびに異なる結果が生成されると、ビルドの再現性や一貫性に問題が生じる可能性がありました。
クロスプラットフォームでの一貫性: コメントにもあるように、既にアーキテクチャ間で不整合があり、新しいマップ反復順序により実行間での不整合も生じるようになったため、この問題を根本的に解決する必要がありました。

前提知識の解説

Go言語のマップと反復順序

Go言語のマップ（map）は、キーと値のペアを格納するデータ構造です。Go 1.0より前のバージョンでは、マップの反復順序は実装に依存していましたが、ある程度予測可能でした。しかし、Go 1.0からは意図的にランダム化されました。

// Go 1.0以前は、ある程度予測可能だった
m := make(map[string]int)
m["a"] = 1
m["b"] = 2
m["c"] = 3

// Go 1.0以降は、毎回異なる順序で反復される
for k, v := range m {
    fmt.Println(k, v)
}

Unicode文字プロパティテーブル

Unicodeは、世界中の文字を統一的に扱うための標準規格です。Go言語のunicodeパッケージは、文字の分類（文字、数字、記号など）や属性（大文字、小文字など）を判定するためのテーブルを提供します。

// 文字の分類を判定する例
unicode.IsLetter('A') // true
unicode.IsDigit('5')  // true
unicode.IsSpace(' ')  // true

RangeTableとは

RangeTableは、Unicode文字の範囲を効率的に表現するためのデータ構造です。個々の文字を列挙するのではなく、連続する文字の範囲を記録することで、メモリ効率とルックアップ性能を向上させます。

type RangeTable struct {
    R16         []Range16
    R32         []Range32
    LatinOffset int
}

type Range16 struct {
    Lo, Hi, Stride uint16
}

従来の実装:
- マップの要素をそのまま順番に配列にコピー
- マップの反復順序に依存した出力
新しい実装:
- マップの要素をスライスにコピー
- sort.Strings()を使用してソート
- 決定論的な順序で出力

ソート処理の追加

変更前のコードでは、マップの反復順序がそのまま出力順序に影響していました：

// 変更前
func allCategories() []string {
    a := make([]string, len(category))
    i := 0
    for k := range category {
        a[i] = k
        i++
    }
    return a
}

変更後は、明示的にソートを行うことで、決定論的な出力を保証しています：

// 変更後
func allCategories() []string {
    a := make([]string, 0, len(category))
    for k := range category {
        a = append(a, k)
    }
    sort.Strings(a)
    return a
}

パフォーマンスの改善

変更により、以下の改善も行われています：

メモリ効率の向上: make([]string, 0, len(category))により、必要な容量を事前に確保
動的な要素追加: append()を使用することで、より柔軟な配列操作が可能

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

`allCategories()`関数の変更

// src/pkg/unicode/maketables.go:269-283
func allCategories() []string {
-   a := make([]string, len(category))
-   i := 0
+   a := make([]string, 0, len(category))
    for k := range category {
-       a[i] = k
-       i++
+       a = append(a, k)
    }
+   sort.Strings(a)
    return a
}

`all()`関数の変更

// src/pkg/unicode/maketables.go:285-297
func all(scripts map[string][]Script) []string {
-   a := make([]string, len(scripts))
-   i := 0
+   a := make([]string, 0, len(scripts))
    for k := range scripts {
-       a[i] = k
-       i++
+       a = append(a, k)
    }
+   sort.Strings(a)
    return a
}

コアとなるコードの解説

スライスの初期化パターンの変更

変更前のアプローチ:

a := make([]string, len(category))
i := 0
for k := range category {
    a[i] = k
    i++
}

このアプローチでは、スライスの長さを事前に確定し、インデックスを使って直接代入していました。しかし、これには以下の問題がありました：

インデックス管理: 手動でインデックスを管理する必要があり、エラーが発生しやすい
順序の非決定性: マップの反復順序がそのまま出力順序に影響

変更後のアプローチ:

a := make([]string, 0, len(category))
for k := range category {
    a = append(a, k)
}
sort.Strings(a)

新しいアプローチでは：

容量の事前確保: make([]string, 0, len(category))により、メモリ再割り当てを防ぐ
安全な要素追加: append()を使用することで、インデックス管理を自動化
明示的なソート: sort.Strings()により、決定論的な順序を保証

ソートアルゴリズムの選択

Go言語のsort.Strings()は、内部的にIntroSort（イントロソート）を使用しており、以下の特徴があります：

平均時間計算量: O(n log n)
最悪時間計算量: O(n log n)（QuickSortの最悪ケースO(n²)を回避）
安定性: 安定ソートではないが、文字列の場合は問題なし

メモリ効率性の改善

// 変更前：初期長さを設定
a := make([]string, len(category))

// 変更後：容量のみ事前確保
a := make([]string, 0, len(category))

この変更により：

メモリ使用量: 同じ容量を確保するが、初期長さは0
append()の効率: 容量が十分なため、内部的な再割り当てが発生しない
型安全性: 空のスライスから開始するため、未初期化要素のアクセスを防ぐ

comemo