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

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

このコミットでは、Go言語の標準ライブラリである hash/adler32 パッケージの最適化が行われました。具体的には、以下の2つのファイルが変更されています。

  • src/pkg/hash/adler32/adler32.go: Adler-32チェックサム計算の主要なロジックが含まれるファイル。
  • src/pkg/hash/adler32/adler32_test.go: Adler-32チェックサムのテストコードが含まれるファイル。

コミット

commit 60ffae25bc1e8ddacaa52952683bfaf6caebc9fd
Author: Nigel Tao <nigeltao@golang.org>
Date:   Fri May 25 09:58:38 2012 +1000

    hash/adler32: optimize.
    
    The bulk of the gains come from hoisting the modulo ops outside of
    the inner loop.
    
    Reducing the digest type from 8 bytes to 4 bytes gains another 1% on
    the hash/adler32 micro-benchmark.
    
    Benchmarks for $GOOS,$GOARCH = linux,amd64 below.
    
    hash/adler32 benchmark:
    benchmark             old ns/op    new ns/op    delta
    BenchmarkAdler32KB         1660         1364  -17.83%
    
    image/png benchmark:
    benchmark                       old ns/op    new ns/op    delta
    BenchmarkDecodeGray               2466909      2425539   -1.68%
    BenchmarkDecodeNRGBAGradient      9884500      9751705   -1.34%
    BenchmarkDecodeNRGBAOpaque        8511615      8379800   -1.55%
    BenchmarkDecodePaletted           1366683      1330677   -2.63%
    BenchmarkDecodeRGB                6987496      6884974   -1.47%
    BenchmarkEncodePaletted           6292408      6040052   -4.01%
    BenchmarkEncodeRGBOpaque         19780680     19178440   -3.04%
    BenchmarkEncodeRGBA              80738600     79076800   -2.06%
    
    Wall time for Denis Cheremisov's PNG-decoding program given in
    https://groups.google.com/group/golang-nuts/browse_thread/thread/22aa8a05040fdd49
    Before: 2.44s
    After:  2.26s
    Delta:  -7%
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/6251044

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

https://github.com/golang/go/commit/60ffae25bc1e8ddacaa52952683bfaf6caebc9fd

元コミット内容

このコミットは、Go言語の hash/adler32 パッケージの最適化を目的としています。主な改善点は、計算コストの高いモジュロ演算を内側のループの外に移動させたことと、ダイジェスト型（チェックサムの状態を保持する型）のサイズを8バイトから4バイトに削減したことです。これらの変更により、hash/adler32 のマイクロベンチマークで約17.83%の性能向上が見られ、image/png パッケージのベンチマークでも1.34%から4.01%の改善、さらに実際のPNGデコードプログラムでは約7%の実行時間短縮が達成されました。

変更の背景

Adler-32チェックサムは、データの整合性を確認するために広く使用されるアルゴリズムです。特に、Zlib圧縮ライブラリなどで内部的に利用されており、PNG画像フォーマットのデータストリーム（IDATチャンク）の圧縮にも使われるDeflateアルゴリズムの一部としてAdler-32が使われています。

Go言語の image/png パッケージは、PNG画像のエンコードとデコードを処理しますが、その過程でAdler-32チェックサムの計算が頻繁に行われます。もしAdler-32の計算が非効率であれば、それはPNG画像の処理速度に直接影響し、結果としてアプリケーション全体のパフォーマンスを低下させる可能性があります。

このコミットの背景には、Adler-32チェックサム計算のボトルネックを解消し、Go言語でPNG画像を扱う際のパフォーマンスを向上させるという明確な目的がありました。特に、モジュロ演算はCPUにとって比較的重い処理であり、これがデータ処理のホットパス（頻繁に実行されるコードパス）にある場合、大きなオーバーヘッドとなります。また、データ構造のサイズを削減することは、キャッシュ効率の向上やメモリ帯域幅の節約につながり、これもまたパフォーマンス改善に寄与します。

前提知識の解説

Adler-32 チェックサム

Adler-32は、RFC 1950で定義されているチェックサムアルゴリズムです。CRC32（Cyclic Redundancy Check）と比較して計算が高速ですが、衝突耐性（異なる入力データが同じチェックサムを生成する確率）は低いとされています。Adler-32は、2つの16ビットの和 s1 と s2 を累積することで計算されます。

  • s1: 入力データの各バイトの和を累積します。初期値は1です。
  • s2: s1 の累積和をさらに累積します。初期値は0です。

これらの和は、それぞれ mod (65521) でモジュロ演算されます。mod は65536未満の最大の素数です。この素数を使用することで、チェックサムの分布が均一になり、衝突の可能性を低減します。最終的なAdler-32チェックサムは、s2 を16ビット左シフトし、s1 とビットOR演算した32ビット値 (s2 << 16 | s1) となります。

Go言語の hash パッケージ

Go言語の標準ライブラリには、ハッシュ関数やチェックサムアルゴリズムを提供する hash パッケージがあります。このパッケージは、hash.Hash インターフェースを定義しており、Write メソッドでデータを入力し、Sum や Sum32/Sum64 メソッドでハッシュ値やチェックサムを取得できます。hash.Hash32 は32ビットのハッシュ値を返すインターフェースです。

ベンチマーク

ソフトウェア開発において、コードの性能を測定するためにベンチマークが使用されます。Go言語には、testing パッケージに組み込みのベンチマーク機能があり、go test -bench=. コマンドで実行できます。

  • ns/op: 1操作あたりのナノ秒。この値が小さいほど高速であることを示します。
  • delta: 性能変化率。負の値は性能向上を示します。

モジュロ演算

モジュロ演算（剰余演算）は、ある数値を別の数値で割った余りを求める演算です。CPUによっては、除算やモジュロ演算は加算や乗算に比べて多くのクロックサイクルを必要とするため、計算コストが高いとされています。特に、タイトなループ内で頻繁に実行される場合、全体のパフォーマンスに大きな影響を与えます。

データ型とメモリレイアウト

プログラムのデータ構造がメモリ上でどのように配置されるかは、パフォーマンスに影響を与えます。

  • メモリフットプリント: データ構造が占めるメモリの量。小さいほど良い。
  • キャッシュ効率: CPUはメインメモリよりも高速なキャッシュメモリを持っています。データがキャッシュに収まる場合、アクセス速度が大幅に向上します。データ構造のサイズが小さいほど、キャッシュに収まりやすくなります。
  • アライメント: データがメモリ上で特定の境界に配置されること。適切にアライメントされていないと、アクセスが遅くなることがあります。

このコミットでは、digest 型を8バイトの構造体から4バイトの uint32 に変更することで、メモリフットプリントを削減し、キャッシュ効率を向上させています。

技術的詳細

このコミットにおける主要な最適化は以下の2点です。

  1. モジュロ演算のループ外への巻き上げ (Hoisting modulo operations out of the inner loop): Adler-32の計算では、s1 と s2 の累積和が mod (65521) を超えるたびにモジュロ演算を行う必要があります。元の実装では、このモジュロ演算がバイトごとの処理ループの内部で行われる可能性がありました。これは、各バイトを処理するたびに高コストなモジュロ演算が実行されることを意味し、パフォーマンスのボトルネックとなっていました。

    新しい実装では、RFC 1950で言及されている nmax (5552) という定数が導入されました。nmax は、255 * n * (n+1) / 2 + (n+1) * (mod-1) が 2^32-1 (uint32の最大値) を超えない最大の n の値です。この nmax を利用することで、nmax バイトのデータを処理する間は s1 と s2 が uint32 の範囲内に収まることが保証されます。

    これにより、update 関数は入力データを nmax バイトのチャンクに分割して処理するようになりました。各チャンクの処理中は、内側のループで s1 += uint32(x) と s2 += s1 という単純な加算のみが行われ、モジュロ演算は各チャンクの処理が完了した後に一度だけ (s1 %= mod, s2 %= mod) 実行されます。この変更により、内側のループが非常に高速になり、CPUのパイプライン効率が大幅に向上しました。

  2. ダイジェスト型サイズの削減 (Reducing digest type from 8 bytes to 4 bytes): 元の digest 型は、struct { a, b uint32 } として定義されており、a と b の2つの uint32 フィールドを持っていました。これは合計で8バイトのメモリを消費します。

    // Original
type digest struct {
    a, b uint32
}

    新しい実装では、digest 型が単一の uint32 型に変更されました。Adler-32の s1 と s2 はそれぞれ16ビットの値であるため、これらを1つの32ビット uint32 にパックすることが可能です。具体的には、s1 を下位16ビットに、s2 を上位16ビットに格納します (s2<<16 | s1)。

    // New
type digest uint32

    この変更により、digest 型のメモリフットプリントが8バイトから4バイトに半減しました。メモリ使用量の削減は、特に大量のAdler-32計算が行われる場合に、キャッシュヒット率の向上やメモリ帯域幅の節約に繋がり、わずかながらも全体のパフォーマンス向上に寄与します。コミットメッセージによると、この変更だけでマイクロベンチマークで1%の性能向上が見られました。

ベンチマーク結果の分析

コミットメッセージに示されているベンチマーク結果は、これらの最適化が実際に効果を発揮したことを明確に示しています。

  • hash/adler32 ベンチマーク:

    • BenchmarkAdler32KB: 1660 ns/op から 1364 ns/op へと、17.83% の大幅な改善。これは、Adler-32計算自体の効率が大きく向上したことを示しています。

  • image/png ベンチマーク: PNGのエンコード/デコード処理は内部でAdler-32を使用しているため、Adler-32の最適化が直接的にPNG処理の高速化に繋がります。

    • BenchmarkDecode* 系: デコード処理で1.34%から2.63%の改善。
    • BenchmarkEncode* 系: エンコード処理で2.06%から4.01%の改善。 これらの結果は、Adler-32の最適化がPNG処理のボトルネックの一部を解消したことを示唆しています。

  • 実世界のPNGデコードプログラムのウォールタイム: 特定のPNGデコードプログラムの実行時間が2.44秒から2.26秒へと、7% の改善が見られました。これは、マイクロベンチマークだけでなく、実際のアプリケーションレベルでも顕著な性能向上があったことを裏付けています。

これらの結果から、モジュロ演算の最適化とデータ型サイズの削減が、Adler-32チェックサム計算、ひいてはそれを利用するPNG処理のパフォーマンスに大きな影響を与えたことがわかります。

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

src/pkg/hash/adler32/adler32.go

  1. nmax 定数の追加:

    const (
    // mod is the largest prime that is less than 65536.
    mod = 65521
    // nmax is the largest n such that
    // 255 * n * (n+1) / 2 + (n+1) * (mod-1) <= 2^32-1.
    // It is mentioned in RFC 1950 (search for "5552").
    nmax = 5552
)

    nmax は、モジュロ演算をループ外に巻き上げるための重要な定数です。

  2. digest 型の変更:

    // Old:
// type digest struct {
//     a, b uint32
// }

// New:
// The low 16 bits are s1, the high 16 bits are s2.
type digest uint32

    digest 型が8バイトの構造体から4バイトの uint32 に変更されました。

  3. Reset() メソッドの変更: digest 型の変更に伴い、リセット処理も簡素化されました。

    // Old:
// func (d *digest) Reset() { d.a, d.b = 1, 0 }

// New:
func (d *digest) Reset() { *d = 1 }

    s1 の初期値が1であるため、uint32 型の digest に直接1を代入します。

  4. update 関数の大幅な変更: これが主要な最適化が行われた箇所です。

    // Old:
// func update(a, b uint32, p []byte) (aa, bb uint32) {
//     for _, pi := range p {
//         a += uint32(pi)
//         b += a
//         // invariant: a <= b
//         if b > (0xffffffff-255)/2 {
//             a %= mod
//             b %= mod
//             // invariant: a < mod && b < mod
//         } else {
//             // invariant: a + b + 255 <= 2 * b + 255 <= 0xffffffff
//         }
//     }
//     return a, b
// }

// New:
// Add p to the running checksum d.
func update(d digest, p []byte) digest {
    s1, s2 := uint32(d&0xffff), uint32(d>>16) // s1とs2をdigestから抽出
    for len(p) > 0 {
        var q []byte
        if len(p) > nmax { // nmaxバイトのチャンクに分割
            p, q = p[:nmax], p[nmax:]
        }
        for _, x := range p { // 内側のループでは加算のみ
            s1 += uint32(x)
            s2 += s1
        }
        s1 %= mod // チャンク処理後にモジュロ演算
        s2 %= mod
        p = q
    }
    return digest(s2<<16 | s1) // s1とs2をdigestにパックして返す
}

  5. Sum32() および Checksum() の簡素化: digest 型が直接32ビット値になったため、finish 関数が不要になり、これらの関数も簡素化されました。

    // Old:
// func (d *digest) Sum32() uint32 { return finish(d.a, d.b) }
// func Checksum(data []byte) uint32 { return finish(update(1, 0, data)) }

// New:
func (d *digest) Sum32() uint32 { return uint32(*d) }
func Checksum(data []byte) uint32 { return uint32(update(1, data)) }

src/pkg/hash/adler32/adler32_test.go

  1. テストケースの追加: 特に、strings.Repeat を使った長い文字列や、nmax の境界値付近のデータ (\xff を繰り返す文字列に1文字追加したもの) のテストケースが追加されました。これは、nmax を利用した新しい update ロジックの正確性を検証するためです。

  2. checksum ヘルパー関数の追加:

    // checksum is a slow but simple implementation of the Adler-32 checksum.
// It is a straight port of the sample code in RFC 1950 section 9.
func checksum(p []byte) uint32 {
    s1, s2 := uint32(1), uint32(0)
    for _, x := range p {
        s1 = (s1 + uint32(x)) % mod
        s2 = (s2 + s1) % mod
    }
    return s2<<16 | s1
}

    これは、RFC 1950に記載されているAdler-32のシンプルな（最適化されていない）実装です。この関数は、最適化された Checksum 関数が正しく動作するかどうかを検証するための「ゴールデンリファレンス」として使用されます。

  3. TestGolden 関数の変更: TestGolden 関数は、新しい checksum 関数と最適化された Checksum 関数の両方を使って、定義済みのゴールデンテストケースに対する結果を検証するように変更されました。これにより、最適化によって機能が損なわれていないことが保証されます。

    // Old:
// func TestGolden(t *testing.T) {
//     for i := 0; i < len(golden); i++ {
//         g := golden[i]
//         c := New()
//         io.WriteString(c, g.in)
//         s := c.Sum32()
//         if s != g.out {
//             t.Errorf("adler32(%s) = 0x%x want 0x%x", g.in, s, g.out)
//             t.FailNow()
//         }
//     }
// }

// New:
func TestGolden(t *testing.T) {
    for _, g := range golden {
        in := g.in
        if len(in) > 220 {
            in = in[:100] + "..." + in[len(in)-100:]
        }
        p := []byte(g.in)
        if got := checksum(p); got != g.out { // シンプルな実装で検証
            t.Errorf("simple implementation: checksum(%q) = 0x%x want 0x%x", in, got, g.out)
            continue
        }
        if got := Checksum(p); got != g.out { // 最適化された実装で検証
            t.Errorf("optimized implementation: Checksum(%q) = 0x%x want 0x%x", in, got, g.out)
            continue
        }
    }
}

コアとなるコードの解説

digest 型の変更と Reset()

元の digest 型は struct { a, b uint32 } で、a が s1、b が s2 に対応していました。これが type digest uint32 に変更されたことで、s1 と s2 の2つの16ビット値を1つの32ビット uint32 にパックして表現するようになりました。具体的には、s1 は uint32 の下位16ビット (d & 0xffff)、s2 は上位16ビット (d >> 16) に格納されます。

Reset() メソッドでは、s1 の初期値が1、s2 の初期値が0であるため、新しい digest 型では単に *d = 1 とすることで、s1 が1、s2 が0（上位16ビットが0）の状態を表現できます。

update 関数の最適化

update 関数は、Adler-32チェックサムの計算の中核を担う部分です。この関数の変更が、最も大きなパフォーマンス向上をもたらしました。

  1. s1, s2 := uint32(d&0xffff), uint32(d>>16): 入力された digest 値 d から、現在の s1 と s2 の値を抽出します。これにより、パックされた32ビット値から元の2つの16ビット値に戻します。

  2. for len(p) > 0 ループと nmax によるチャンク処理: 入力バイトスライス p を、nmax バイトのチャンクに分割して処理します。nmax は、RFC 1950で定義されている「5552」という値で、このバイト数であれば s1 と s2 が uint32 の範囲内でオーバーフローすることなく累積できることが保証されています。

    • if len(p) > nmax { p, q = p[:nmax], p[nmax:] }: p が nmax より長い場合、最初の nmax バイトを現在のチャンクとし、残りを q に格納して次のイテレーションで処理します。

  3. 内側のループ for _, x := range p: このループが、各バイトを処理する最も内側のホットパスです。

    • s1 += uint32(x): s1 に現在のバイト値 x を加算します。
    • s2 += s1: s2 に現在の s1 の値を加算します。

    重要な点: この内側のループでは、モジュロ演算が一切行われていません。これにより、CPUは予測可能な単純な加算命令を連続して実行でき、パイプラインのストールが減少し、非常に高い効率で処理を進めることができます。

  4. s1 %= mod と s2 %= mod: 内側のループが終了し、nmax バイト（または残りの全バイト）の処理が完了した後に、一度だけ s1 と s2 に対してモジュロ演算が適用されます。これにより、高コストなモジュロ演算の実行回数が大幅に削減され、全体のパフォーマンスが向上します。

  5. return digest(s2<<16 | s1): 更新された s1 と s2 の値を再び1つの uint32 にパックし、digest 型として返します。

この update 関数の変更は、Adler-32の計算ロジックを根本的に見直し、モジュロ演算の頻度を減らすことで、CPUの効率を最大限に引き出すことに成功しています。

Sum32() と Checksum() の簡素化

digest 型が直接32ビットのチェックサム値を保持するようになったため、Sum32() メソッドは単に uint32(*d) を返すだけでよくなりました。同様に、Checksum() 関数も update 関数が直接 digest 型を返すようになったため、その結果を uint32 にキャストするだけでよくなりました。これにより、コードがより簡潔になり、オーバーヘッドも削減されます。

関連リンク

参考にした情報源リンク

  • RFC 1950: ZLIB Compressed Data Format Specification version 3.3 (Adler-32アルゴリズムの公式定義と nmax の言及)
  • Go言語の testing パッケージドキュメント (ベンチマークに関する情報)
  • Adler-32チェックサムの最適化に関する一般的なプログラミング記事や議論 (モジュロ演算の巻き上げ技術について)
  • Go言語のソースコードとコミット履歴 (変更内容の具体的な確認)