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

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

このコミットは、Go言語の標準ライブラリ encoding/json パッケージにおけるJSONデコード処理のパフォーマンス改善を目的としています。特に、JSONキーのデコード時における文字列コピーの削減と、ケースフォールディング（大文字・小文字を区別しない比較）の効率化に焦点を当てています。これにより、デコード速度が大幅に向上しました。

コミット

commit 626da8d73741b0cdeaa1acc048fec9ec8286f2b5
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Wed Dec 18 07:30:21 2013 -0800

    encoding/json: speed up decoding
    
    Don't make copies of keys while decoding, and don't use the
    expensive strings.EqualFold when it's not necessary. Instead,
    note in the existing field cache what algorithm to use to
    check fold equality... most keys are just ASCII letters.
    
    benchmark               old ns/op    new ns/op    delta
    BenchmarkCodeDecoder    137074314    103974418  -24.15%
    
    benchmark                old MB/s     new MB/s  speedup
    BenchmarkCodeDecoder        14.16        18.66    1.32x
    
    Update #6496
    
    R=golang-dev, rsc, adg, r, mikioh.mikioh
    CC=golang-dev
    https://golang.org/cl/13894045

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

https://github.com/golang/go/commit/626da8d73741b0cdeaa1acc048fec9ec8286f2b5

元コミット内容

encoding/json: デコードの高速化

デコード中にキーのコピーを作成しないようにし、不要な strings.EqualFold の高コストな使用を避ける。代わりに、既存のフィールドキャッシュに、フォールド等価性をチェックするためのアルゴリズムを記録する。ほとんどのキーは単なるASCII文字であるため、これによって最適化が可能になる。

ベンチマーク結果: BenchmarkCodeDecoder:

  • 旧: 137,074,314 ns/op
  • 新: 103,974,418 ns/op
  • 改善率: -24.15%

BenchmarkCodeDecoder:

  • 旧: 14.16 MB/s
  • 新: 18.66 MB/s
  • 速度向上: 1.32倍

Issue #6496 を更新。

変更の背景

このコミットの主な背景は、Go言語の encoding/json パッケージにおけるJSONデコード処理のパフォーマンスボトルネックの解消です。特に、以下の2つの点が問題視されていました。

  1. JSONキーの文字列コピー: JSONオブジェクトのキーをデコードする際に、毎回新しい文字列を生成してコピーする処理が行われていました。これは、特に大きなJSONデータや多数のオブジェクトを含む場合に、メモリ割り当てとGC（ガベージコレクション）のオーバーヘッドを増大させ、パフォーマンスを低下させる要因となっていました。
  2. strings.EqualFold の非効率な使用: Goの encoding/json パッケージは、JSONキーとGoの構造体フィールド名をマッチングさせる際に、大文字・小文字を区別しない比較（ケースフォールディング）をサポートしています。この比較には strings.EqualFold 関数が使用されていましたが、この関数はUnicodeの複雑なケースフォールディングルールに対応するため、内部的に比較的重い処理を行っていました。しかし、多くのJSONキーは単純なASCII文字で構成されており、このような高コストな比較が常に必要とされるわけではありませんでした。

これらの問題を解決し、JSONデコードの速度と効率を向上させることが、このコミットの動機となっています。コミットメッセージに記載されているベンチマーク結果は、これらの最適化が実際に顕著なパフォーマンス改善をもたらしたことを示しています。

前提知識の解説

JSON (JavaScript Object Notation)

JSONは、人間が読み書きしやすく、機械が解析しやすいデータ交換フォーマットです。キーと値のペアの集まり（オブジェクト）と、値の順序付きリスト（配列）で構成されます。Web APIなどで広く利用されています。

Go言語の encoding/json パッケージ

Go言語の標準ライブラリである encoding/json パッケージは、Goの構造体とJSONデータの間のエンコード（Go -> JSON）およびデコード（JSON -> Go）機能を提供します。

  • json.Unmarshal(): JSONデータをGoの構造体にデコードする関数。
  • json.Marshal(): Goの構造体をJSONデータにエンコードする関数。

ケースフォールディング (Case Folding)

ケースフォールディングとは、文字列を比較する際に、大文字・小文字の区別をなくす処理のことです。例えば、"Hello" と "hello" を同じものとして扱う場合に使用されます。Unicodeには、特定の文字が複数の異なる文字にケースフォールドされるような複雑なルールが存在します（例: ドイツ語の ß は ss にフォールドされる）。strings.EqualFold はこれらの複雑なルールに対応しています。

strings.EqualFold 関数

Goの strings パッケージに含まれる EqualFold 関数は、2つの文字列がUnicodeのケースフォールディングルールに従って等しいかどうかを判定します。この関数は、内部的にUTF-8デコードやUnicodeテーブルの参照を行うため、単純なASCII文字の比較に比べて処理コストが高くなります。

bytes.Equal と bytes.EqualFold

  • bytes.Equal: 2つのバイトスライスが完全に一致するかどうかを判定します。非常に高速です。
  • bytes.EqualFold: strings.EqualFold と同様に、2つのバイトスライスがUnicodeのケースフォールディングルールに従って等しいかどうかを判定します。

パフォーマンス最適化の観点

  • メモリ割り当ての削減: 新しいオブジェクト（文字列など）を頻繁に作成すると、ヒープメモリの使用量が増加し、ガベージコレクションの頻度と時間が長くなります。これにより、アプリケーションの応答性が低下する可能性があります。既存のメモリを再利用したり、コピーを避けたりすることで、メモリ割り当てを削減し、パフォーマンスを向上させることができます。
  • CPUサイクルの削減: 不要な計算や複雑なアルゴリズムの実行を避けることで、CPUの使用率を下げ、処理速度を向上させることができます。特に、頻繁に呼び出される関数（例: JSONデコードループ内のキー比較）では、わずかな改善でも全体として大きな効果をもたらします。

技術的詳細

このコミットは、JSONデコードのパフォーマンスを向上させるために、主に以下の2つの技術的アプローチを採用しています。

  1. JSONキーの文字列コピーの回避:

    • 以前のバージョンでは、JSONオブジェクトのキーを読み取る際に、unquote 関数が string 型のキーを返していました。これは、元のバイトスライスから新しい文字列を生成し、コピーすることを意味します。
    • このコミットでは、unquote の代わりに unquoteBytes 関数が導入され、キーを []byte 型で直接返すように変更されました。これにより、不要な文字列コピーとそれに伴うメモリ割り当てが削減されます。decode.go の object メソッド内で、key, ok := unquote(item) が key, ok := unquoteBytes(item) に変更されています。

  2. ケースフォールディング比較の最適化:

    • JSONキーとGoの構造体フィールド名のマッチングにおいて、大文字・小文字を区別しない比較が必要な場合、以前は常に strings.EqualFold が使用されていました。
    • このコミットでは、encoding/json/fold.go という新しいファイルが追加され、キーの特性に基づいて最適なケースフォールディング比較関数を選択するメカニズムが導入されました。
    • field 構造体に nameBytes []byte と equalFold func(s, t []byte) bool という新しいフィールドが追加されました。
      • nameBytes: 構造体フィールド名をバイトスライスとして保持します。これにより、bytes.Equal やカスタムのバイトスライス比較関数を直接使用できるようになります。
      • equalFold: この関数ポインタは、そのフィールド名に特化したケースフォールディング比較ロジックを保持します。
    • foldFunc 関数が導入されました。この関数は、与えられたフィールド名（バイトスライス）を分析し、その特性に応じて以下の4種類の最適化された比較関数の中から最適なものを選択して返します。
      1. bytes.EqualFold: キーに非ASCIIのUTF-8文字が含まれる場合。最も汎用的で遅い。
      2. equalFoldRight: キーに特殊なフォールディングASCII文字（'k', 'K', 's', 'S'）が含まれる場合。これらの文字はUnicodeで3つのルーンにマップされる可能性があるため、特別な処理が必要です。
      3. asciiEqualFold: 特殊なフォールディングASCII文字は含まれないが、非文字（アンダースコアなど）が含まれる場合。
      4. simpleLetterEqualFold: 特殊なフォールディングASCII文字も非文字も含まれない、単純なASCII文字のみで構成される場合。最も高速。
    • この選択ロジックにより、ほとんどのJSONキーが単純なASCII文字であるという事実を利用し、不要な高コストな bytes.EqualFold の呼び出しを避けることができます。
    • encode.go の typeFields 関数内で、field 構造体を生成する際に fillField 関数が呼び出され、nameBytes と equalFold 関数ポインタが適切に設定されるようになりました。
    • decode.go の object メソッド内で、フィールド名との比較が strings.EqualFold(ff.name, key) から ff.equalFold(ff.nameBytes, key) に変更され、動的に選択された最適化された比較関数が使用されるようになりました。

これらの変更により、JSONデコード時のメモリフットプリントが削減され、CPU効率が向上し、全体的なパフォーマンスが大幅に改善されました。

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

このコミットは主に以下の4つのファイルに影響を与えています。

  1. src/pkg/encoding/json/decode.go:

    • import から "strings" が削除され、"bytes" が追加されました。
    • decodeState.object メソッド内で、JSONキーの読み取り部分が変更されました。
      • key, ok := unquote(item) が key, ok := unquoteBytes(item) に変更されました。これにより、キーが []byte として扱われるようになります。
    • フィールドマッチングのロジックが変更されました。
      • if bytes.Equal(ff.nameBytes, key): 完全一致の比較に bytes.Equal が使用されるようになりました。
      • if f == nil && ff.equalFold(ff.nameBytes, key): ケースフォールディング比較に、field 構造体にキャッシュされた equalFold 関数が使用されるようになりました。

  2. src/pkg/encoding/json/encode.go:

    • field 構造体に以下のフィールドが追加されました。 
      type field struct {
    name      string
    nameBytes []byte                 // []byte(name)
    equalFold func(s, t []byte) bool // bytes.EqualFold or equivalent
    // ... 既存のフィールド ...
}
    • fillField 関数が追加されました。この関数は field 構造体を受け取り、nameBytes を []byte(f.name) で初期化し、equalFold を foldFunc(f.nameBytes) の結果で初期化します。
    • typeFields 関数内で、field 構造体を生成する際に fillField 関数が呼び出されるようになりました。

  3. src/pkg/encoding/json/fold.go (新規ファイル):

    • このファイルは、ケースフォールディング比較の最適化ロジックをカプセル化しています。
    • caseMask, kelvin, smallLongEss などの定数が定義されています。
    • foldFunc 関数が定義されています。これは、与えられたバイトスライス s に基づいて、最適なケースフォールディング比較関数（bytes.EqualFold, equalFoldRight, asciiEqualFold, simpleLetterEqualFold のいずれか）を返します。
    • equalFoldRight, asciiEqualFold, simpleLetterEqualFold の3つの最適化された比較関数が定義されています。これらは、特定の条件（ASCIIのみ、特殊文字の有無など）下で bytes.EqualFold よりも高速な比較を提供します。

  4. src/pkg/encoding/json/fold_test.go (新規ファイル):

    • fold.go で定義されたケースフォールディング比較関数群の単体テストが含まれています。
    • さまざまな文字列の組み合わせと、特殊なUnicode文字（ケルビン記号 K、ラテン小文字ロングS ſ）を含むテストケースが含まれており、各比較関数の正確性と効率性を検証しています。

コアとなるコードの解説

decode.go の変更点

// 旧: key, ok := unquote(item)
// 新: key, ok := unquoteBytes(item)

この変更は、JSONキーを文字列（string）としてではなく、バイトスライス（[]byte）として直接扱うようにします。unquote は string を返すため、内部でメモリ割り当てとコピーが発生します。一方、unquoteBytes は []byte を返すため、元のバイトスライスへの参照を返すか、必要最小限のコピーで済ませることができます。これにより、デコード時のメモリ割り当てが削減され、ガベージコレクションの負荷が軽減されます。

// 旧: if ff.name == key {
// 新: if bytes.Equal(ff.nameBytes, key) {

これは、構造体フィールド名とJSONキーの厳密な比較を string から []byte に変更したものです。ff.nameBytes は構造体フィールド名のバイトスライス表現であり、key はJSONキーのバイトスライス表現です。bytes.Equal は2つのバイトスライスがバイト単位で完全に一致するかを高速にチェックします。

// 旧: if f == nil && strings.EqualFold(ff.name, key) {
// 新: if f == nil && ff.equalFold(ff.nameBytes, key) {

この変更は、ケースフォールディング比較の核心部分です。以前は常に strings.EqualFold を使用していましたが、これはUnicodeの複雑なルールに対応するため、常に高コストでした。新しいコードでは、ff.equalFold という関数ポインタを使用します。この関数ポインタは、foldFunc によって、そのフィールド名に最適な比較ロジック（simpleLetterEqualFold, asciiEqualFold, equalFoldRight, または bytes.EqualFold）が事前に設定されています。これにより、ほとんどのケースでより高速な比較関数が使用され、パフォーマンスが向上します。

encode.go の変更点

type field struct {
    name      string
    nameBytes []byte                 // []byte(name)
    equalFold func(s, t []byte) bool // bytes.EqualFold or equivalent
    // ...
}

func fillField(f field) field {
    f.nameBytes = []byte(f.name)
    f.equalFold = foldFunc(f.nameBytes)
    return f
}

field 構造体への nameBytes と equalFold の追加は、最適化された比較のための情報をキャッシュする目的です。nameBytes は、構造体フィールド名をバイトスライスとして保持することで、decode.go での bytes.Equal 比較を可能にします。equalFold は、そのフィールド名に特化したケースフォールディング比較関数を保持します。

fillField 関数は、field 構造体が作成される際に一度だけ呼び出され、これらのキャッシュされた値を設定します。特に foldFunc(f.nameBytes) の呼び出しは、フィールド名がどのような文字で構成されているかを分析し、その後のデコード処理で最も効率的な比較関数を選択・設定します。これにより、デコードループ内で毎回この分析を行う必要がなくなり、オーバーヘッドが削減されます。

fold.go の新規追加

fold.go は、ケースフォールディング比較の最適化ロジックを実装する新しいファイルです。

  • foldFunc(s []byte) func(s, t []byte) bool: この関数は、与えられたバイトスライス s（構造体フィールド名）を分析し、その特性に基づいて最適なケースフォールディング比較関数を返します。

    • s に非ASCIIのUTF-8文字が含まれる場合: bytes.EqualFold を返します。これは最も汎用的ですが、最も遅いです。
    • s に特殊なフォールディングASCII文字（'k', 'K', 's', 'S'）が含まれる場合: equalFoldRight を返します。これらの文字はUnicodeで特殊なケースフォールディングルールを持つため、専用の処理が必要です。
    • s に非文字（数字、記号など）が含まれるが、特殊なフォールディングASCII文字は含まれない場合: asciiEqualFold を返します。
    • s が単純なASCII文字（'k', 'K', 's', 'S' を含まない）のみで構成される場合: simpleLetterEqualFold を返します。これは最も高速な比較です。

  • equalFoldRight(s, t []byte) bool: s がASCII文字のみで構成され、かつ 's', 'S', 'k', 'K' のいずれかを含む場合の bytes.EqualFold の特殊化です。t にUnicode文字が含まれる可能性があるため、t のバイトをルーンとしてデコードし、s の対応するASCII文字と比較します。

  • asciiEqualFold(s, t []byte) bool: s がASCII文字のみで構成され、かつ特殊なフォールディング文字を含まない場合の bytes.EqualFold の特殊化です。文字以外のASCII文字（例: アンダースコア）も考慮します。

  • simpleLetterEqualFold(s, t []byte) bool: s が単純なASCII文字（'k', 'K', 's', 'S' を含まない）のみで構成される場合の bytes.EqualFold の特殊化です。最も高速な比較であり、ほとんどのJSONキーがこのカテゴリに分類されることを想定しています。

これらの最適化された比較関数は、JSONデコード時にフィールド名をマッチングさせる際のCPUコストを大幅に削減します。特に、一般的なASCIIキーの場合には、非常に高速なバイト比較が可能になります。

関連リンク

参考にした情報源リンク

  • (特になし)