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

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

本コミットは、Go言語の標準ライブラリstrconvパッケージにおける整数から文字列への変換処理のパフォーマンスを大幅に改善するものです。具体的には、FormatInt、AppendInt、FormatUint、AppendUintといった関数群の実行速度が34%から63%向上しています。この改善は、数値変換の内部ロジックをformatBitsという共通のヘルパー関数に集約し、特定の基数（10進数や2のべき乗の基数）に対して最適化されたパスを導入することで実現されました。

コミット

commit e0c006a9b0224ba6a346663724f9f8660321d5f3
Author: Robert Griesemer <gri@golang.org>
Date:   Tue Dec 6 08:15:45 2011 -0800

    strconv: 34% to 63% faster conversions
    
    (Note that the Int and Uint benchmarks use different test sets
    and thus cannot be compared against each other. Int and Uint
    conversions are approximately the same speed).
    
    Before (best of 3 runs):
    strconv_test.BenchmarkFormatInt    100000    15636 ns/op
    strconv_test.BenchmarkAppendInt    100000    18930 ns/op
    strconv_test.BenchmarkFormatUint   500000     4392 ns/op
    strconv_test.BenchmarkAppendUint   500000     5152 ns/op
    
    After (best of 3 runs):
    
    strconv_test.BenchmarkFormatInt    200000    10070 ns/op (-36%)
    strconv_test.BenchmarkAppendInt    200000     7097 ns/op (-63%)
    strconv_test.BenchmarkFormatUint  1000000     2893 ns/op (-34%)
    strconv_test.BenchmarkAppendUint   500000     2462 ns/op (-52%)
    
    R=r, rsc, r
    CC=golang-dev
    https://golang.org/cl/5449093

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

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

元コミット内容

strconv: 34% to 63% faster conversions

(Note that the Int and Uint benchmarks use different test sets
and thus cannot be compared against each other. Int and Uint
conversions are approximately the same speed).

Before (best of 3 runs):
strconv_test.BenchmarkFormatInt    100000    15636 ns/op
strconv_test.BenchmarkAppendInt    100000    18930 ns/op
strconv_test.BenchmarkFormatUint   500000     4392 ns/op
strconv_test.BenchmarkAppendUint   500000     5152 ns/op

After (best of 3 runs):

strconv_test.BenchmarkFormatInt    200000    10070 ns/op (-36%)
strconv_test.BenchmarkAppendInt    200000     7097 ns/op (-63%)
strconv_test.BenchmarkFormatUint  1000000     2893 ns/op (-34%)
strconv_test.BenchmarkAppendUint   500000     2462 ns/op (-52%)

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

変更の背景

このコミットの主な背景は、Go言語のstrconvパッケージにおける整数から文字列への変換処理のパフォーマンス改善です。コミットメッセージに示されているベンチマーク結果から明らかなように、変更前はFormatIntやAppendInt、FormatUint、AppendUintといった関数が比較的多くの時間を要していました。特にAppendIntは18930 ns/op、AppendUintは5152 ns/opと、頻繁に利用される操作であるにも関わらず、ボトルネックとなる可能性がありました。

Go言語はシステムプログラミングを意識した設計であり、高いパフォーマンスが求められます。文字列変換のような基本的な操作の効率は、アプリケーション全体の性能に大きく影響します。このコミットは、これらの基本的な操作を高速化することで、Goプログラムの全体的な実行効率を高めることを目的としています。特に、数値の文字列化はログ出力、データシリアライズ、ユーザーインターフェース表示など、多岐にわたる場面で利用されるため、その性能向上は広範な影響をもたらします。

前提知識の解説

Go言語のstrconvパッケージ

strconvパッケージは、Go言語の標準ライブラリの一部であり、基本的なデータ型（ブール値、整数、浮動小数点数）と文字列との間の変換機能を提供します。主な関数には以下のようなものがあります。

  • Itoa(i int) string: 整数iを10進数の文字列に変換するショートハンド。
  • FormatInt(i int64, base int) string: int64型の整数iを指定されたbase（基数、2から36）の文字列に変換します。
  • FormatUint(i uint64, base int) string: uint64型の符号なし整数iを指定されたbaseの文字列に変換します。
  • AppendInt(dst []byte, i int64, base int) []byte: int64型の整数iを文字列に変換し、既存のバイトスライスdstに追記して返します。これにより、メモリ再割り当てを減らし、効率的な文字列構築が可能です。
  • AppendUint(dst []byte, i uint64, base int) []byte: uint64型の符号なし整数iを文字列に変換し、既存のバイトスライスdstに追記して返します。

これらの関数は、fmt.Sprintfと比較して、より高速でメモリ効率の良い変換を提供することを目的としています。fmt.Sprintfは汎用的なフォーマット機能を提供しますが、その分オーバーヘッドが大きいため、単純な型変換にはstrconvが推奨されます。

整数から文字列への変換アルゴリズム

整数を文字列に変換する一般的なアルゴリズムは、基数変換に基づいています。例えば、10進数（基数10）の場合、数値を10で繰り返し割っていき、その余りを下位桁から順に取得します。余りが0から9であれば対応する文字（'0'から'9'）に変換し、それらを逆順に並べることで文字列を得ます。

より一般的な基数（例：2進数、16進数）の場合も同様に、指定された基数で繰り返し割っていき、余りを対応する文字（例：16進数なら'0'-'9', 'a'-'f'）に変換します。

このプロセスにおいて、特にパフォーマンスに影響を与える要因は以下の通りです。

  • 除算と剰余演算: これらの演算はCPUにとって比較的コストが高い操作です。特に大きな数値や、基数が2のべき乗でない場合に顕著です。
  • メモリ割り当て: 文字列を構築する際に、動的なメモリ割り当てが発生すると、ガベージコレクションのオーバーヘッドが増加し、パフォーマンスが低下します。Append系の関数は、既存のバッファを再利用することでこの問題を緩和します。
  • 基数ごとの最適化: 基数が10（10進数）の場合や、2のべき乗（2, 4, 8, 16, 32）の場合には、それぞれ特化した高速なアルゴリズムが存在します。例えば、2のべき乗の基数では、除算や剰余演算の代わりにビットシフトやビットマスク演算を用いることができます。

技術的詳細

このコミットの核心は、strconvパッケージにおける整数から文字列への変換ロジックを、formatBitsという単一の共通ヘルパー関数に集約し、その内部で複数の最適化パスを導入した点にあります。

formatBits関数の導入

以前はFormatUintとFormatIntがそれぞれ独立した変換ロジックを持っていましたが、この変更により、両者がformatBitsを呼び出すようになりました。formatBitsは以下の役割を担います。

  1. 基数の検証: 入力されたbaseが有効な範囲（2から36）にあるかを確認します。
  2. ゼロ値の特殊処理: uが0の場合、"0"を返すという共通の処理を行います。
  3. 符号処理: signedフラグがtrueで、かつ数値が負の場合、絶対値に変換し、最終的に結果文字列の先頭に'-'を追加します。
  4. 変換バッファ: [64 + 1]byteの固定長配列aをスタック上に確保し、ここに変換結果の文字を逆順に格納します。これにより、ヒープメモリの割り当てを避け、ガベージコレクションの負荷を軽減します。
  5. 最適化された変換パス:
    • 基数10 (10進数): 最も一般的なケースである10進数変換に対しては、コンパイラが最適化できるu % 10とu /= 10という定数による除算・剰余演算を使用します。これは、多くのCPUアーキテクチャで高速な命令に変換されるため、非常に効率的です。
    • 2のべき乗の基数: shiftsマップ（1<<1: 1, 1<<2: 2, ..., 1<<5: 5）を利用して、基数が2のべき乗（2, 4, 8, 16, 32）であるかを判定します。もしそうであれば、除算や剰余演算の代わりに、ビットシフト（u >>= s）とビットマスク（uintptr(u)&m）を使用します。これらのビット演算は、CPUにとって非常に高速な操作です。
    • 一般的な基数: 上記の最適化パスに該当しない基数（例：3, 5, 6など）に対しては、従来のu % bとu /= bという汎用的な除算・剰余演算を使用します。
  6. 結果の構築:
    • append_フラグがtrueの場合（AppendIntやAppendUintからの呼び出し）、変換結果のバイトスライスa[i:]を既存のdstバイトスライスに追記して返します。
    • append_フラグがfalseの場合（FormatIntやFormatUintからの呼び出し）、変換結果のバイトスライスa[i:]をstring()にキャストして新しい文字列として返します。

Append関数の効率化

AppendIntとAppendUintは、以前はFormatIntやFormatUintを呼び出し、その結果の文字列をバイトスライスに変換してappendしていましたが、この変更により、formatBitsに直接append_フラグをtrueで渡すようになりました。これにより、中間的な文字列生成とそれに伴うメモリ割り当てが不要になり、直接バイトスライスに書き込むことで大幅な効率化が図られています。

ベンチマークの追加

strconv/itoa_test.goには、BenchmarkFormatInt、BenchmarkAppendInt、BenchmarkFormatUint、BenchmarkAppendUintという新しいベンチマーク関数が追加されました。これにより、変更によるパフォーマンス改善が定量的に測定され、将来の変更に対する回帰テストとしても機能します。

これらの技術的詳細は、Go言語がパフォーマンスを重視し、低レベルな最適化（ビット演算、スタック割り当て、中間オブジェクトの削減）を積極的に取り入れていることを示しています。

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

src/pkg/strconv/itoa.go

  • FormatUint関数とFormatInt関数の実装が大幅に簡素化され、新たに導入されたformatBits関数を呼び出す形に変更されました。
    • 旧来のループによる変換ロジック（var buf [64]byte, j := len(buf), buf[j] = ..., u /= bなど）が削除されました。
    • FormatIntにおける負の数の処理もformatBitsに委譲されました。
  • AppendInt関数とAppendUint関数も同様に、formatBits関数を呼び出す形に変更されました。append_引数をtrueに設定することで、結果を直接バイトスライスに追記するように変更されています。
  • 新たにdigits定数（"0123456789abcdefghijklmnopqrstuvwxyz"）とshiftsマップが定義されました。
  • formatBits関数が新規に追加されました。 この関数が、すべての整数から文字列への変換ロジックの大部分を担うようになりました。

src/pkg/strconv/itoa_test.go

  • TestItoa関数内のAppendUintのテストケースが修正されました。以前は"abc"というプレフィックスを付けてテストしていましたが、新しいAppendUintの動作に合わせて、nilスライスに追記する形に変更されました。
  • 新しいベンチマーク関数が追加されました。
    • BenchmarkFormatInt
    • BenchmarkAppendInt
    • BenchmarkFormatUint
    • BenchmarkAppendUint これらのベンチマークは、itob64testsやuitob64testsといった既存のテストデータセットを使用して、各変換関数のパフォーマンスを測定します。

コアとなるコードの解説

formatBits関数 (src/pkg/strconv/itoa.go)

const digits = "0123456789abcdefghijklmnopqrstuvwxyz"

var shifts = [len(digits) + 1]uint{
	1 << 1: 1, // base 2 (binary)
	1 << 2: 2, // base 4
	1 << 3: 3, // base 8 (octal)
	1 << 4: 4, // base 16 (hexadecimal)
	1 << 5: 5, // base 32
}

// formatBits computes the string representation of u in the given base.
// If signed is set, u is treated as int64 value. If append_ is set, the
// string is appended to dst and the resulting byte slice is returned as
// the first result value; otherwise the string is simply returned as the
// second result value.
func formatBits(dst []byte, u uint64, base int, signed, append_ bool) (d []byte, s string) {
	if base < 2 || base > len(digits) {
		panic("invalid base")
	}

	if u == 0 {
		if append_ {
			d = append(dst, '0')
			return
		}
		s = "0"
		return
	}

	var a [64 + 1]byte // +1 for sign of 64bit value in base 2
	i := len(a)

	x := int64(u)
	if x < 0 && signed {
		u = -u // Convert to absolute value for conversion
	}

	// convert bits
	if base == 10 {
		// common case: use constant 10 for / and % because
		// the compiler can optimize it into a multiply+shift
		for u != 0 {
			i--
			a[i] = digits[u%10]
			u /= 10
		}
	} else if s := shifts[base]; s > 0 {
		// base is power of 2: use shifts and masks instead of / and %
		m := uintptr(1)<<s - 1
		for u != 0 {
			i--
			a[i] = digits[uintptr(u)&m]
			u >>= s
		}
	} else {
		// general case
		b := uint64(base)
		for u != 0 {
			i--
			a[i] = digits[u%b]
			u /= b
		}
	}

	// add sign, if any
	if x < 0 && signed {
		i--
		a[i] = '-'
	}

	if append_ {
		d = append(dst, a[i:]...)
		return
	}
	s = string(a[i:])
	return
}

このformatBits関数は、整数から文字列への変換における中心的なロジックを担っています。

  • digits定数: 変換に使用される文字セットを定義しています。これにより、基数2から36までの任意の基数に対応できます。
  • shiftsマップ: 基数が2のべき乗である場合に、その基数に対応するビットシフト量（例: 基数2なら1ビット、基数4なら2ビット）を効率的に取得するためのマップです。これにより、除算・剰余演算の代わりに高速なビット演算を使用できます。
  • dst []byte: 結果を追記するバイトスライス。Append系の関数から呼び出される際に使用されます。
  • u uint64: 変換対象の符号なし整数。符号付き整数も内部で符号なしに変換されて処理されます。
  • base int: 変換する基数（2から36）。
  • signed bool: 変換対象が符号付き整数であるかを示すフラグ。trueの場合、負の数であれば最終的に'-'が追加されます。
  • append_ bool: 結果をdstに追記するか、新しい文字列として返すかを制御するフラグ。

内部処理のフロー:

  1. 基数チェック: baseが有効範囲外であればパニックします。
  2. ゼロ値処理: uが0であれば、"0"を返します。append_がtrueならdstに'0'を追記し、そうでなければ文字列"0"を返します。
  3. バッファ初期化: aという[64 + 1]byteの配列を宣言します。これは、64ビットの数値が基数2で表現された場合に最大64桁になることと、符号用の1バイトを考慮したサイズです。この配列はスタック上に確保されるため、ヒープ割り当てが不要です。
  4. 符号処理: signedがtrueでx（元のuをint64にキャストしたもの）が負の場合、uを絶対値に変換します。
  5. 変換ロジック（3つのパス）:
    • base == 10 (10進数): 最も頻繁に使われる10進数変換の最適化パスです。u % 10とu /= 10をループで実行し、余りをdigitsから対応する文字に変換してaに逆順に格納します。コンパイラがこれらの定数除算・剰余演算を効率的な命令に変換できるため、高速です。
    • s := shifts[base]; s > 0 (2のべき乗の基数): shiftsマップからbaseに対応するシフト量sが取得できれば、その基数は2のべき乗です。この場合、u % baseの代わりにuintptr(u)&m（mは1<<s - 1、つまりビットマスク）を、u /= baseの代わりにu >>= s（ビットシフト）を使用します。ビット演算はCPUにとって非常に高速なため、大幅なパフォーマンス向上が期待できます。
    • else (一般的な基数): 上記の最適化パスに該当しない基数（例: 3, 5, 7など）の場合、汎用的なu % bとu /= b（bはuint64(base)）を使用します。
  6. 符号の追加: 変換が完了した後、元の数値が負でsignedがtrueであれば、aの先頭に'-'を追加します。
  7. 結果の返却:
    • append_がtrueの場合、dstにa[i:]（変換結果のバイトスライス）を追記して返します。
    • append_がfalseの場合、a[i:]をstring()にキャストして新しい文字列として返します。

このformatBits関数は、Go言語のパフォーマンス志向の設計思想をよく表しており、一般的なケース（10進数）と特定の高速化が可能なケース（2のべき乗の基数）に対して、それぞれ最適なアルゴリズムを選択することで、全体的な変換速度を向上させています。また、スタック上の固定長バッファを使用することで、ガベージコレクションの負荷を軽減し、メモリ効率も高めています。

関連リンク

参考にした情報源リンク