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

このコミットは、Go言語の標準ライブラリであるstrconvパッケージ内の整数から文字列への変換（itoa、AppendUint、FormatUintなど）のパフォーマンスを大幅に改善することを目的としています。具体的には、src/pkg/strconv/itoa.goファイル内のformatBits関数における基数10（10進数）変換ロジックが最適化されています。

コミット

commit 465aba66c1080b44bc669dd60aa1dc29e01c4a6f
Author: Robert Griesemer <gri@golang.org>
Date:   Wed Dec 14 10:45:59 2011 -0800

    strconv: even faster int conversion
    
    benchmark                           old ns/op    new ns/op    delta
    strconv_test.BenchmarkFormatInt         10038         8217  -18.14%
    strconv_test.BenchmarkAppendInt          6822         4969  -27.16%
    strconv_test.BenchmarkFormatUint         2811         1814  -35.47%
    strconv_test.BenchmarkAppendUint         2349         1360  -42.10%
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/5488083

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

https://github.com/golang/go/commit/465aba66c1080b44bc669dd60aa1dc29e01c4a6f

元コミット内容

strconv: even faster int conversion

このコミットは、strconvパッケージにおける整数変換をさらに高速化します。ベンチマーク結果は以下の通りです。

ベンチマーク名	old ns/op	new ns/op	delta
`strconv_test.BenchmarkFormatInt`	10038	8217	-18.14%
`strconv_test.BenchmarkAppendInt`	6822	4969	-27.16%
`strconv_test.BenchmarkFormatUint`	2811	1814	-35.47%
`strconv_test.BenchmarkAppendUint`	2349	1360	-42.10%

変更の背景

Go言語のstrconvパッケージは、数値と文字列間の変換を提供する基本的な機能です。これらの変換は、ログ出力、ユーザーインターフェースの表示、ネットワークプロトコルにおけるデータのシリアライズなど、多くのアプリケーションで頻繁に使用されます。そのため、これらの変換処理の効率は、Goアプリケーション全体のパフォーマンスに大きな影響を与えます。

このコミットの背景には、既存の整数から文字列への変換ロジック（特に10進数変換）が、さらなる最適化の余地があるという認識がありました。特に、大きな数値を変換する際に、ループ内で1桁ずつ処理する現在の方法がボトルネックになっている可能性がありました。コンパイラが除算や剰余演算を最適化できる余地を最大限に引き出し、ループの反復回数を減らすことで、全体的なスループットを向上させることが目標でした。

ベンチマーク結果が示すように、この変更はFormatInt、AppendInt、FormatUint、AppendUintといった主要な整数変換関数において、最大で42%以上の顕著なパフォーマンス改善をもたらしています。これは、Goアプリケーションが数値を文字列に変換する際のCPUサイクルを削減し、より高速な実行を可能にすることを意味します。

前提知識の解説

このコミットの変更を理解するためには、以下の前提知識が役立ちます。

整数から文字列への変換 (itoa):
- コンピュータ内部では数値はバイナリ形式で表現されますが、人間が読み書きする際には10進数などの文字列形式に変換する必要があります。この変換プロセスは "integer to ASCII" (itoa) と呼ばれます。
- 一般的なitoaの実装では、数値を基数で繰り返し除算し、その剰余を桁として取り出し、逆順に文字列を構築します。例えば、123を10進数に変換する場合：
  - 123 % 10 = 3 (最初の桁)
  - 123 / 10 = 12
  - 12 % 10 = 2 (次の桁)
  - 12 / 10 = 1
  - 1 % 10 = 1 (最後の桁)
  - 1 / 10 = 0 (終了)
  - 結果を逆順に並べて "123"
除算と剰余演算のコスト:
- CPUにおける除算（/）と剰余（%）演算は、加算、減算、乗算に比べて一般的に高コストな操作です。特に、コンパイル時に除数が定数でない場合、コンパイラによる最適化が難しくなります。
- しかし、除数が定数（例: 10や100）の場合、多くのコンパイラは除算を乗算とビットシフトの組み合わせに変換して最適化することができます。これは、除算が逆数の乗算として表現できるためです。
ループアンローリング (Loop Unrolling):
- ループアンローリングは、ループの反復回数を減らすことで、ループのオーバーヘッド（カウンタのインクリメント、条件チェック、ジャンプ命令など）を削減する最適化手法です。
- 例えば、100回繰り返すループを、2回分の処理を1回の反復で行うように変更し、ループ回数を50回に減らすといった形です。これにより、命令キャッシュの効率が向上したり、パイプラインのストールが減少したりする可能性があります。
Go言語のstrconvパッケージ:
- Goの標準ライブラリの一部で、文字列と基本データ型（整数、浮動小数点数、真偽値）の間で変換を行うための関数を提供します。
- FormatInt, FormatUint, AppendInt, AppendUintなどが含まれ、それぞれ指定された基数で整数を文字列にフォーマットしたり、既存のバイトスライスに追加したりする機能を提供します。

これらの知識を背景に、今回のコミットがどのようにしてパフォーマンスを向上させたのかを理解することができます。

技術的詳細

このコミットの技術的な核心は、10進数変換における「2桁同時処理」と「定数配列による高速な桁取得」にあります。

従来の10進数変換は、ループ内で数値を10で除算し、剰余を求めて1桁ずつ処理していました。これは直感的ですが、大きな数値の場合、ループの反復回数が多くなり、除算・剰余演算のコストが累積します。

新しいアプローチでは、以下の最適化が導入されています。

2桁同時処理 (Loop Unrolling for 2 digits):
- for u >= 100 という条件でループを回し、一度に2桁（100の位と10の位）を処理するように変更されました。
- u / 100 で上位の桁を、u % 100 (または u - q*100) で下2桁（0〜99）を取得します。
- これにより、ループの反復回数が約半分になり、ループオーバーヘッドと高コストな除算・剰余演算の回数が削減されます。
定数配列 digits01 と digits10 の導入:
- digits01 は 01234567890123456789... のように、各10のブロックで0から9が繰り返される文字列です。
- digits10 は 00000000001111111111... のように、各10のブロックで同じ数字が10回繰り返される文字列です。
- 例えば、j が 0 から 99 までの2桁の数値である場合、digits01[j] は j の1の位の文字を、digits10[j] は j の10の位の文字を直接参照できます。
  - 例: j = 23 の場合、digits01[23] は '3' を、digits10[23] は '2' を返します。
- これにより、j % 10 や j / 10 といった除算・剰余演算を行うことなく、配列のインデックス参照だけで2桁の文字を効率的に取得できるようになります。配列アクセスは通常、除算よりもはるかに高速です。
コンパイラ最適化の活用:
- u / 100 や u - q*100 (これは実質的に u % 100 と同じ) のような定数による除算・剰余演算は、Goコンパイラが乗算とビットシフトに最適化しやすい形です。2桁同時処理により、この最適化の恩恵をより大きく受けることができます。
- ループの最後に残った1桁または2桁の数値（u < 100 の場合）は、別途 if u >= 10 の条件で処理されます。ここでも同様に、digits 配列と定数除算が使われます。

これらの変更の組み合わせにより、特に大きな整数を10進数文字列に変換する際のパフォーマンスが劇的に向上しました。

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

変更は src/pkg/strconv/itoa.go ファイルに集中しています。

--- a/src/pkg/strconv/itoa.go
+++ b/src/pkg/strconv/itoa.go
@@ -35,7 +35,11 @@ func AppendUint(dst []byte, i uint64, base int) []byte {
 	return dst
 }
 
-const digits = "0123456789abcdefghijklmnopqrstuvwxyz"
+const (
+	digits   = "0123456789abcdefghijklmnopqrstuvwxyz"
+	digits01 = "0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789"
+	digits10 = "0000000000111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999"
+)
 
 var shifts = [len(digits) + 1]uint{
 	1 << 1: 1,
@@ -66,12 +70,22 @@ func formatBits(dst []byte, u uint64, base int, neg, append_ bool) (d []byte, s\
 
 	// convert bits
 	if base == 10 {
-		// common case: use constant 10 for / and % because
-		// the compiler can optimize it into a multiply+shift
-		for u >= 10 {
+		// common case: use constants for / and % because
+		// the compiler can optimize it into a multiply+shift,
+		// and unroll loop
+		for u >= 100 {
+			i -= 2
+			q := u / 100
+			j := u - q*100
+			a[i+1] = digits01[j]
+			a[i+0] = digits10[j]
+			u = q
+		}
+		if u >= 10 {
 			i--
-			a[i] = digits[u%10]
-			u /= 10
+			q := u / 10
+			a[i] = digits[u-q*10]
+			u = q
 		}
 
 	} else if s := shifts[base]; s > 0 {

コアとなるコードの解説

変更の中心は formatBits 関数内の if base == 10 ブロックです。

新しい定数 digits01 と digits10 の追加:
- digits 定数に加えて、digits01 と digits10 という2つの新しい文字列定数が定義されました。これらは、0から99までの2桁の数値に対応する1の位と10の位の文字を高速に取得するためのルックアップテーブルとして機能します。
メインループの変更 (for u >= 100):
- 以前は for u >= 10 で1桁ずつ処理していましたが、新しいコードでは for u >= 100 となり、一度に2桁を処理するようになりました。
- i -= 2: バイトスライス a のインデックスを2つ減らします。これは、2桁分の文字を格納するためです。
- q := u / 100: 現在の数値 u を100で除算し、上位の桁（次のループで処理される部分）を q に格納します。
- j := u - q*100: u の下2桁（0〜99の範囲）を j に格納します。これは u % 100 と同じ意味ですが、コンパイラが q*100 を最適化できる可能性があるため、この形式が選ばれていると考えられます。
- a[i+1] = digits01[j]: j の1の位の文字を digits01 から取得し、バイトスライス a の現在の位置の次のインデックス（つまり、下位の桁）に格納します。
- a[i+0] = digits10[j]: j の10の位の文字を digits10 から取得し、バイトスライス a の現在の位置（つまり、上位の桁）に格納します。
- u = q: 次のループの処理のために、u を q (100で割った値) に更新します。
残りの桁の処理 (if u >= 10):
- メインループ for u >= 100 が終了した後、u は0から99の間の値になります。
- if u >= 10: もし u が10以上であれば（つまり、残りが2桁の場合）、以前の1桁処理ロジックと同様に処理します。
  - i--: インデックスを1つ減らします。
  - q := u / 10: 10の位を q に格納します。
  - a[i] = digits[u-q*10]: u の1の位の文字を digits から取得し、格納します。
  - u = q: u を10の位に更新します。
- もし u < 10 であれば（つまり、残りが1桁の場合）、ループや if ブロックに入らず、そのまま a[i] = digits[u] で処理されます（これは変更前のコードでも同様）。

この変更により、特に大きな数値の変換において、ループの反復回数が減り、かつ各反復内でより効率的に桁の文字を取得できるようになり、全体的なパフォーマンスが大幅に向上しました。

参考にした情報源リンク

Go言語の公式ドキュメント
Go言語のソースコード
一般的な整数から文字列への変換アルゴリズムに関する情報
コンパイラの最適化（特に定数除算とループアンローリング）に関する情報

comemo