Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Goランタイムにおけるハッシュマップのルックアップ、特に文字列キーの比較処理を最適化するものです。文字列の比較ロジックを改善し、ハッシュ計算を回避できるケースを増やすことで、パフォーマンスの向上を図っています。

コミット

commit a696ae56db451f2f02ffdf63092e0c06dba1d0c5
Author: Keith Randall <khr@golang.org>
Date:   Tue Jul 30 21:39:57 2013 -0700

    runtime: optimize some hash lookups.
    
    When comparing strings, check these (in order):
    - length mismatch => not equal
    - string pointer equal => equal
    - if length is short:
      - memeq on body
    - if length is long:
      - compare first&last few bytes, if different => not equal
      - save entry as a possible match
      - after checking every entry, if there is only one possible
        match, use memeq on that entry.  Otherwise, fallback to hash.
    
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkSameLengthMap           43            4  -89.77%
    
    Fixes #5194.
    Update #3885.
    
    R=golang-dev, bradfitz, khr, rsc
    CC=golang-dev
    https://golang.org/cl/12128044

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

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

元コミット内容

runtime: optimize some hash lookups.

When comparing strings, check these (in order):
- length mismatch => not equal
- string pointer equal => equal
- if length is short:
  - memeq on body
- if length is long:
  - compare first&last few bytes, if different => not equal
  - save entry as a possible match
  - after checking every entry, if there is only one possible
    match, use memeq on that entry.  Otherwise, fallback to hash.

benchmark                 old ns/op    new ns/op    delta
BenchmarkSameLengthMap           43            4  -89.77%

Fixes #5194.
Update #3885.

R=golang-dev, bradfitz, khr, rsc
CC=golang-dev
https://golang.org/cl/12128044

変更の背景

Goのハッシュマップ（map型）は、キーと値のペアを効率的に格納・検索するための重要なデータ構造です。特に文字列をキーとして使用する場合、キーの比較処理がパフォーマンスに大きく影響します。従来のハッシュマップのルックアップでは、キーの比較に際して常にハッシュ値を計算し、その後バイトごとの比較（memeq）を行っていました。

しかし、文字列の比較には、ハッシュ計算よりも高速に等価性を判断できるケースがいくつか存在します。例えば、文字列の長さが異なる場合、それらは決して等しくありません。また、同じ文字列リテラルや、同じメモリ位置を指す文字列であれば、ポインタの比較だけで等価性を判断できます。

このコミットの背景には、このような高速パスを導入することで、特に文字列キーを持つハッシュマップのルックアップ性能を向上させるという目的があります。コミットメッセージにあるBenchmarkSameLengthMapの劇的な改善（-89.77%）は、この最適化が特定のシナリオで非常に効果的であることを示しています。これは、ハッシュ衝突が多く発生し、かつキーの比較が頻繁に行われるような状況で特に顕著な効果を発揮します。

Fixes #5194とUpdate #3885という記述から、この変更が既存のパフォーマンス問題や最適化の要望に対応していることが伺えます。

前提知識の解説

1. ハッシュマップ (Hash Map)

ハッシュマップ（Goではmap型）は、キーと値のペアを格納するデータ構造です。キーをハッシュ関数に通してハッシュ値を計算し、そのハッシュ値に基づいてデータを格納するバケット（bucket）を決定します。これにより、平均的にはO(1)の高速な検索、挿入、削除が可能になります。

  • ハッシュ関数: キーを入力として受け取り、固定長の数値（ハッシュ値）を返す関数です。異なるキーに対しては異なるハッシュ値を返すことが望ましいですが、ハッシュ衝突（異なるキーが同じハッシュ値を返すこと）は避けられません。
  • バケット: ハッシュマップ内でデータを格納する基本的な単位です。通常、配列として実装され、ハッシュ値に基づいてキーと値のペアが配置されます。
  • ハッシュ衝突の解決: 複数のキーが同じハッシュ値を持つ場合、それらは同じバケットに格納されます。衝突解決には、チェイニング（バケット内の要素をリンクリストで繋ぐ）やオープンアドレス法（空いている別のバケットを探す）などの手法があります。Goのハッシュマップはチェイニングに似た構造（バケット内に固定数のスロットを持ち、オーバーフローした場合は別のバケットにリンクする）を採用しています。
  • キーの比較: ハッシュマップでキーを検索する際、まずハッシュ値を計算してバケットを特定します。その後、そのバケット内の各エントリについて、格納されているキーと検索対象のキーが本当に等しいかどうかの比較（等価性チェック）を行います。この等価性チェックが、特に複雑なキー型（文字列など）の場合、パフォーマンスのボトルネックになることがあります。

2. Goにおける文字列 (String)

Goの文字列は不変（immutable）なバイトスライスであり、内部的にはポインタと長さのペアとして表現されます。

type String struct {
    str unsafe.Pointer // 文字列データの先頭へのポインタ
    len int            // 文字列の長さ（バイト数）
}

文字列の比較（==演算子）は、まず長さが等しいかを確認し、次に内容がバイトごとに等しいかを確認します。

3. memeq関数

memeqは、指定されたメモリ領域の内容がバイトごとに等しいかを比較する関数です。C言語のmemcmpに似ています。文字列の比較において、長さが同じであると判断された後、実際に文字列の内容が一致するかどうかを判断するために使用されます。これはバイトごとの比較であるため、文字列が長いほど比較に時間がかかります。

4. パフォーマンス最適化の原則

ソフトウェアのパフォーマンス最適化では、一般的に以下の原則が適用されます。

  • 頻繁に実行されるコードパスの最適化: ボトルネックとなっている部分を特定し、そこを改善することで全体的な性能が向上します。
  • 早期終了 (Early Exit): 不一致が早期に判明する条件（例: 文字列の長さが異なる）を先にチェックすることで、不要な計算（例: バイトごとの比較）をスキップします。
  • キャッシュの活用: 参照の局所性を高めたり、計算結果を再利用したりすることで、メモリアクセスや計算コストを削減します。
  • ヒューリスティック (Heuristics): 常に最適ではないが、多くの場合に有効な経験則に基づいた最適化手法。例えば、文字列の先頭と末尾の数バイトを比較して、異なる場合はすぐに不一致と判断する、といった方法です。

技術的詳細

このコミットは、Goランタイムのハッシュマップ実装（src/pkg/runtime/hashmap.cとsrc/pkg/runtime/hashmap_fast.c）における文字列キーの比較ロジックを根本的に変更しています。主な変更点は、文字列の等価性チェックを多段階の高速パスに分割し、ハッシュ計算や完全なバイト比較（memeq）を可能な限り遅延または回避することです。

新しい文字列比較のロジックは、以下の優先順位でチェックを行います。

  1. 長さの不一致 (Length Mismatch):

    • QUICK_NE(x,y) マクロがこれに対応します。
    • 比較対象の2つの文字列の長さが異なる場合、それらは決して等しくありません。このチェックは非常に高速であり、すぐに不一致と判断できます。

  2. 文字列ポインタの等価性 (String Pointer Equality):

    • QUICK_EQ(x,y) マクロがこれに対応します。
    • 2つの文字列が同じメモリ位置を指している場合（つまり、同じ文字列リテラルや、同じ文字列を指す変数である場合）、それらは内容も完全に一致します。このチェックも非常に高速です。

  3. 短い文字列の直接比較 (Short String memeq):

    • FASTKEY(x) マクロが文字列の長さが32バイト未満であるかをチェックします。
    • 文字列が短い場合（32バイト未満）、ハッシュ衝突解決のために複数の候補を保持する複雑なロジックを導入するよりも、直接memeq（SLOW_EQ(x,y)）でバイト比較を行う方が効率的です。これは、短い文字列ではハッシュ衝突の可能性が低く、memeqのコストも低いためです。

  4. 長い文字列の最適化された比較 (Long String Optimized Comparison):

    • 文字列が長い場合（32バイト以上）に適用される、より複雑なヒューリスティックです。
    • 先頭と末尾の数バイト比較: MAYBE_EQ(x,y) マクロがこれに対応します。文字列の先頭と末尾からsizeof(CHECKTYPE)（通常はuint64またはuint32）分のバイトを比較します。もしこれらの部分が異なる場合、文字列全体が異なる可能性が非常に高いため、すぐに不一致と判断できます。これは、ハッシュ衝突が発生しやすい長い文字列において、完全なmemeqを回避するための高速なフィルタリングとして機能します。
    • 「可能性のある一致」の追跡: バケット内のエントリを走査する際に、上記の高速チェックを通過した（つまり、長さが同じで、ポインタが異なり、先頭と末尾のバイトが一致する）エントリを「可能性のある一致（keymaybe）」として記録します。
    • 単一の「可能性のある一致」の場合: バケット内の全てのエントリをチェックした後、もし「可能性のある一致」が1つだけであった場合、そのエントリに対してのみmemeq（SLOW_EQ(x,y)）を実行して最終的な等価性を確認します。これにより、ハッシュ計算を回避し、かつ不要なmemeqの実行を最小限に抑えます。
    • 複数の「可能性のある一致」の場合、または上記で一致が見つからない場合: 複数の「可能性のある一致」があった場合や、上記の高速パスで一致が見つからなかった場合は、従来のハッシュ計算と完全なmemeqによる比較（goto dohash）にフォールバックします。これは、最も確実だが最もコストの高いパスです。

この最適化は、hashmap.cで定義されるマクロ（FASTKEY, QUICK_NE, QUICK_EQ, SLOW_EQ, MAYBE_EQ）を通じてhashmap_fast.cの共通ロジックに適用されます。特にString型に対してこれらのマクロが再定義され、文字列特有の最適化が実現されています。

また、CHECKTYPEマクロが導入され、アーキテクチャ（amd64, 386, arm）に応じて比較するバイトの単位（uint64, uint32, uint8）が定義されています。これは、アライメントの問題や効率的なメモリ読み出しを考慮したものです。

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

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

  1. src/pkg/runtime/hashmap.c:

    • ハッシュマップの基本的な定義と、様々なキー型（uint32, uint64, Stringなど）に対するハッシュマップルックアップ関数のマクロ定義が含まれています。
    • このファイルで、String型に対する新しい比較マクロ（FASTKEY, QUICK_NE, QUICK_EQ, SLOW_EQ, MAYBE_EQ）が定義され、従来のEQFUNC, EQMAYBE, HASMAYBE, QUICKEQが削除されています。
    • CHECKTYPEマクロがアーキテクチャごとに定義されています。

  2. src/pkg/runtime/hashmap_fast.c:

    • ハッシュマップの高速ルックアップロジックの共通実装が含まれています。
    • HASH_LOOKUP1とHASH_LOOKUP2（それぞれmapaccess1_fastXXXとmapaccess2_fastXXXに対応）関数内で、上記の新しいマクロが使用されるようにロジックが変更されています。
    • 特に、FASTKEYによる短い文字列と長い文字列の分岐、QUICK_NE, QUICK_EQ, MAYBE_EQによる多段階の比較、そしてkeymaybe変数による「可能性のある一致」の追跡と、その後のSLOW_EQによる最終確認のロジックが追加・修正されています。

  3. src/pkg/runtime/mapspeed_test.go:

    • ハッシュマップのパフォーマンスを測定するためのベンチマークテストファイルです。
    • BenchmarkSameLengthMapという新しいベンチマークが追加されています。このベンチマークは、長い文字列で、かつ先頭と末尾の数バイトが異なるが長さは同じであるようなキーを使用し、ハッシュ衝突が発生しやすい状況でのマップルックアップ性能を測定します。このベンチマークの改善が、このコミットの主な成果の一つです。

コアとなるコードの解説

src/pkg/runtime/hashmap.c の変更点

// 変更前
// #define EQFUNC(x,y) ((x).len == (y).len && ((x).str == (y).str || runtime·memeq((x).str, (y).str, (x).len)))
// #define EQMAYBE(x,y) ((x).len == (y).len)
// #define HASMAYBE true
// #define QUICKEQ(x) ((x).len < 32)

// 変更後 (String型に対するマクロ定義)
#define FASTKEY(x) ((x).len < 32) // 短い文字列かどうかの判定
#define QUICK_NE(x,y) ((x).len != (y).len) // 長さが異なるかどうかの判定
#define QUICK_EQ(x,y) ((x).str == (y).str) // ポインタが同じかどうかの判定
#define SLOW_EQ(x,y) runtime·memeq((x).str, (y).str, (x).len) // 完全なバイト比較
#define MAYBE_EQ(x,y) (*(CHECKTYPE*)(x).str == *(CHECKTYPE*)(y).str && *(CHECKTYPE*)((x).str + (x).len - sizeof(CHECKTYPE)) == *(CHECKTYPE*)((y).str + (x).len - sizeof(CHECKTYPE))) // 先頭と末尾の数バイト比較

ここで、文字列比較の新しい戦略を定義するマクロ群が導入されています。FASTKEYは短い文字列（32バイト未満）を識別し、QUICK_NEは長さの不一致を、QUICK_EQはポインタの等価性を、SLOW_EQは完全なバイト比較を、そしてMAYBE_EQは長い文字列の先頭と末尾の数バイト比較を定義しています。

src/pkg/runtime/hashmap_fast.c の変更点

このファイルは、ハッシュマップのルックアップの共通ロジックを実装しています。変更の核心は、HASH_LOOKUP1とHASH_LOOKUP2関数内のキー比較ロジックです。

// 変更前 (抜粋)
// if(h->B == 0) { // One-bucket table
//     if(HASMAYBE) { keymaybe = -1; }
//     quickkey = QUICKEQ(key);
//     for(...) {
//         if(b->tophash[i] != 0) {
//             if(quickkey && EQFUNC(key, *k)) { ... return; }
//             if(HASMAYBE && EQMAYBE(key, *k)) { ... }
//         }
//     }
//     if(HASMAYBE && keymaybe >= 0) { if(EQFUNC(key, *k)) { ... return; } }
// } else { // Multi-bucket table
//     dohash:
//     // ... hash calculation ...
//     for(...) {
//         if(b->tophash[i] == top && EQFUNC(key, *k)) { ... return; }
//     }
// }

// 変更後 (抜粋)
if(h->B == 0) { // One-bucket table
    if(FASTKEY(key)) { // 短い文字列の場合
        for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) {
            if(b->tophash[i] == 0) continue;
            if(QUICK_NE(key, *k)) continue; // 長さ不一致
            if(QUICK_EQ(key, *k) || SLOW_EQ(key, *k)) { // ポインタ一致 or 完全一致
                value = v; FLUSH(&value); return;
            }
        }
    } else { // 長い文字列の場合
        keymaybe = -1; // 可能性のある一致のインデックス
        for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) {
            if(b->tophash[i] == 0) continue;
            if(QUICK_NE(key, *k)) continue; // 長さ不一致
            if(QUICK_EQ(key, *k)) { // ポインタ一致
                value = v; FLUSH(&value); return;
            }
            if(MAYBE_EQ(key, *k)) { // 先頭と末尾の数バイト一致
                if(keymaybe >= 0) { // 複数の可能性のある一致がある場合、ハッシュにフォールバック
                    goto dohash;
                }
                keymaybe = i; // 可能性のある一致を記録
            }
        }
        if(keymaybe >= 0) { // 可能性のある一致が1つだけの場合
            k = (KEYTYPE*)b->data + keymaybe;
            if(SLOW_EQ(key, *k)) { // 完全一致をチェック
                value = (byte*)((KEYTYPE*)b->data + BUCKETSIZE) + keymaybe * h->valuesize;
                FLUSH(&value); return;
            }
        }
    }
} else { // Multi-bucket table
    dohash: // ハッシュ計算にフォールバックするラベル
    // ... (ハッシュ計算とバケット選択のロジック) ...
    do {
        for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) {
            if(b->tophash[i] != top) continue;
            if(QUICK_NE(key, *k)) continue; // 長さ不一致
            if(QUICK_EQ(key, *k) || SLOW_EQ(key, *k)) { // ポインタ一致 or 完全一致
                value = v; FLUSH(&value); return;
            }
        }
        // ... (オーバーフローバケットの処理) ...
    } while(b != nil);
}

このコードスニペットは、ハッシュマップのルックアップ処理におけるキー比較の新しいフローを示しています。

  • FASTKEY(key)によって、短い文字列と長い文字列で異なる最適化パスが選択されます。
  • 短い文字列の場合、長さとポインタのチェックの後、直接SLOW_EQ（memeq）が試みられます。
  • 長い文字列の場合、長さとポインタのチェックの後、MAYBE_EQによる先頭/末尾バイトの高速チェックが行われます。
  • keymaybe変数は、MAYBE_EQを通過した候補を追跡するために使用されます。もし複数の候補が見つかった場合、または最終的に一致が見つからなかった場合は、dohashラベルにジャンプして従来のハッシュベースの比較にフォールバックします。
  • dohashパスでは、ハッシュ値とtophash（バケット内のエントリのハッシュ値の上位バイト）が一致するエントリに対して、QUICK_NE, QUICK_EQ, SLOW_EQの順で比較が行われます。

この多段階の比較ロジックにより、多くのケースでハッシュ計算や高コストなmemeqを回避し、マップルックアップのパフォーマンスを大幅に向上させています。

関連リンク

  • Go言語のmap型に関する公式ドキュメントやブログ記事
  • Goランタイムのハッシュマップ実装に関する詳細な技術解説（Goのソースコードを深く掘り下げた記事など）
  • ハッシュテーブル、ハッシュ関数、衝突解決に関する一般的なデータ構造とアルゴリズムの資料

参考にした情報源リンク

  • Go言語のソースコード: src/pkg/runtime/hashmap.c, src/pkg/runtime/hashmap_fast.c, src/pkg/runtime/mapspeed_test.go
  • コミットメッセージと関連するGerrit CL (https://golang.org/cl/12128044)
  • Go issue tracker: #5194, #3885 (これらのissueの具体的な内容は、今回の検索では直接見つかりませんでしたが、コミットメッセージからパフォーマンス改善に関連するものであると推測されます。)
  • Go言語の文字列の内部表現に関する情報
  • ハッシュマップのデータ構造とアルゴリズムに関する一般的な知識