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

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

このコミットは、Go言語のツールチェインにおけるI/O操作のパフォーマンス改善を目的としています。具体的には、libbioライブラリで提供されるバイト単位の読み書き関数BgetcおよびBputcの利用方法を最適化し、より効率的なマクロBGETCおよびBPUTCに置き換えることで、全体的なビルド時間の短縮を図っています。さらに、2バイトおよび4バイトのリトルエンディアン形式での読み書きを高速化するための新しいマクロBGETLE2/4およびBPUTLE2/4が導入されています。

コミット

commit 79dca0327ed8a7f65f3680e72cb1dcf4caaed457
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Fri Aug 30 15:46:12 2013 +0400

    libbio, all cmd: consistently use BGETC/BPUTC instead of Bgetc/Bputc
    Also introduce BGET2/4, BPUT2/4 as they are widely used.
    Slightly improve BGETC/BPUTC implementation.
    This gives ~5% CPU time improvement on go install -a -p1 std.
    Before:
    real            user            sys
    0m23.561s       0m16.625s       0m5.848s
    0m23.766s       0m16.624s       0m5.846s
    0m23.742s       0m16.621s       0m5.868s
    after:
    0m22.999s       0m15.841s       0m5.889s
    0m22.845s       0m15.808s       0m5.850s
    0m22.889s       0m15.832s       0m5.848s
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/12745047

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

https://github.com/golang/go/commit/79dca0327ed8a7f65f3680e72cb1dcf4caaed457

元コミット内容

libbio, all cmd: consistently use BGETC/BPUTC instead of Bgetc/Bputc Also introduce BGET2/4, BPUT2/4 as they are widely used. Slightly improve BGETC/BPUTC implementation. This gives ~5% CPU time improvement on go install -a -p1 std.

（libbio、全てのコマンド：Bgetc/Bputcの代わりに一貫してBGETC/BPUTCを使用する） （また、広く使用されているBGET2/4、BPUT2/4を導入する） （BGETC/BPUTCの実装をわずかに改善する） （これにより、go install -a -p1 stdで約5%のCPU時間改善が得られる）

変更の背景

Go言語のコンパイラやリンカなどのツールチェインは、多くのファイルI/O操作を行います。これらのI/O操作は、ビルド時間全体に大きな影響を与える可能性があります。特に、バイト単位の読み書きは非常に頻繁に行われるため、その効率が全体のパフォーマンスに直結します。

このコミットの背景には、Goツールチェインのビルドパフォーマンスを向上させたいという明確な目的があります。従来のBgetcやBputcといった関数呼び出しは、その都度関数呼び出しのオーバーヘッドが発生し、これが積もり積もって無視できないコストとなっていました。特に、Goの標準ライブラリをビルドするような大規模なI/O操作においては、このオーバーヘッドが顕著になります。

コミットメッセージに示されているベンチマーク結果（go install -a -p1 stdでの約5%のCPU時間改善）は、この最適化が実用的な効果をもたらすことを裏付けています。これは、Go開発者がビルド時間の短縮を重視し、低レベルなI/O操作の効率化にも注力していたことを示しています。

前提知識の解説

このコミットを理解するためには、以下の概念について知っておく必要があります。

  1. Biobuf構造体とlibbioライブラリ: libbioは、Go言語のツールチェインが内部的に使用するバッファリングI/Oライブラリです。C言語で実装されており、ファイルからの読み書きを効率的に行うための機能を提供します。Biobuf構造体は、このライブラリにおけるI/Oバッファの状態を管理します。これには、バッファのポインタ、読み書き可能なバイト数、現在のオフセットなどが含まれます。

  2. 関数呼び出しのオーバーヘッド: C言語において、関数を呼び出す際には、引数のスタックへのプッシュ、リターンアドレスの保存、レジスタの保存・復元など、一定の処理コストが発生します。これは「関数呼び出しのオーバーヘッド」と呼ばれ、関数が頻繁に呼び出される場合、その合計コストは無視できないものとなります。

  3. マクロとインライン化: C言語のマクロは、プリプロセッサによってコードが展開されるため、関数呼び出しのオーバーヘッドが発生しません。これにより、小さな処理を頻繁に行う場合にパフォーマンス上の利点があります。コンパイラによっては、関数をインライン展開することで同様の最適化を行うことができますが、マクロはより直接的にオーバーヘッドを排除します。

  4. リトルエンディアン (Little-Endian): バイトオーダーの一種で、複数バイトで構成されるデータをメモリに格納する際に、最下位バイト（Least Significant Byte, LSB）から順にアドレスの小さい方へ格納する方式です。Goツールチェインの内部表現や、特定のアーキテクチャ（x86など）ではリトルエンディアンが採用されています。2バイトや4バイトの整数を効率的に読み書きするためには、このバイトオーダーを考慮した処理が必要です。

  5. Goツールチェインの構造: Go言語のビルドプロセスは、複数のツール（コンパイラ、リンカ、アセンブラなど）が連携して動作します。

    • cmd/5a, 6a, 8a: それぞれARM (5), x86-64 (6), x86 (8) アーキテクチャ用のアセンブラです。
    • cmd/5c, 6c, 8c: それぞれARM, x86-64, x86 アーキテクチャ用のCコンパイラです（Goのコンパイラは一部Cで書かれています）。
    • cmd/5g, 6g, 8g: それぞれARM, x86-64, x86 アーキテクチャ用のGoコンパイラです。
    • cmd/5l, 6l, 8l: それぞれARM, x86-64, x86 アーキテクチャ用のリンカです。
    • cmd/gc: Goコンパイラのフロントエンド部分です。
    • cmd/ld: リンカの共通部分です。
    • cmd/pack: Goのアーカイブファイルを操作するユーティリティです。 これらのツールは、中間ファイルやオブジェクトファイルの読み書きにlibbioを使用しています。

技術的詳細

このコミットの核心は、libbioにおけるI/O操作の最適化です。

1. Bgetc/BputcからBGETC/BPUTCへの移行

  • 既存の問題: 従来のBgetcおよびBputcはC関数として実装されており、1バイトの読み書きごとにC言語の関数呼び出しオーバーヘッドが発生していました。これは、特に大量のバイトを処理する際にパフォーマンスのボトルネックとなっていました。
  • 解決策: include/bio.hにおいて、BGETCとBPUTCがマクロとして再定義されました。
    • これらのマクロは、Biobuf構造体の内部バッファ（bbufまたはebuf）に直接アクセスし、バッファ内にデータがある場合は関数呼び出しなしでバイトを読み書きします。
    • バッファが空になった場合（読み込み時）や満杯になった場合（書き込み時）にのみ、実際のI/O操作を行う低レベルなC関数（BgetcやBputc）が呼び出されます。
    • この「バッファリングI/Oのインライン化」により、ほとんどの1バイトI/O操作で関数呼び出しのオーバーヘッドが排除され、CPU時間を大幅に削減できます。

2. BGETLE2/4およびBPUTLE2/4の導入

  • 既存の問題: 2バイトや4バイトの整数値を読み書きする際、従来のBgetcやBputcを複数回呼び出し、ビットシフトやビットOR演算を組み合わせていました。例えば、4バイト整数を読み込むBget4関数は、Bgetcを4回呼び出してバイトを結合していました。これもまた、複数の関数呼び出しオーバーヘッドと、バイト結合のための追加演算を伴いました。
  • 解決策:
    • include/bio.hに、2バイト (BGETLE2, BPUTLE2) および4バイト (BGETLE4, BPUTLE4) のリトルエンディアン整数を効率的に読み書きするための新しいマクロが導入されました。
    • これらのマクロもBGETC/BPUTCと同様に、可能であればBiobufの内部バッファに直接アクセスし、複数のバイトを一度に処理します。これにより、複数回の1バイトI/O関数呼び出しを回避し、パフォーマンスを向上させます。
    • 対応するC関数Bgetle2, Bgetle4, Bputle2, Bputle4がsrc/libbio/bgetc.cおよびsrc/libbio/bputc.cに新しく実装され、マクロがバッファを使い果たした際のフォールバックとして機能します。
    • 特に、src/cmd/ld/lib.cからBget4関数が削除され、その機能が新しいマクロに置き換えられたことは、この最適化の意図を明確に示しています。

3. ツールチェイン全体への適用

  • この変更は、Goツールチェインを構成する多数のファイル（アセンブラ、コンパイラ、リンカの各アーキテクチャ固有の実装や共通部分）にわたって適用されています。
  • 具体的には、src/cmd/5a/lex.c、src/cmd/5c/swt.c、src/cmd/5g/gobj.c、src/cmd/5l/obj.cなど、広範囲にわたるソースコードで、従来のBgetcやBputcの直接呼び出しが新しいBGETCやBPUTCマクロ、あるいはBGETLE*/BPUTLE*マクロに置き換えられています。
  • これにより、ツールチェイン全体でI/O操作の効率が向上し、結果としてgo installのようなビルドコマンドの実行時間が短縮されます。

この最適化は、GoツールチェインがC言語で書かれた部分のパフォーマンスを、低レベルなバッファリングとマクロによるインライン化という古典的な手法で改善した好例と言えます。

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

このコミットのコアとなる変更は、include/bio.hにおけるマクロの定義と、src/libbio/bgetc.cおよびsrc/libbio/bputc.cにおける新しい関数の実装、そしてGoツールチェインの各コンポーネントでのこれらのマクロへの置き換えです。

include/bio.h

--- a/include/bio.h
+++ b/include/bio.h
@@ -70,10 +70,28 @@ struct	Biobuf
 	unsigned char	b[Bungetsize+Bsize];
 };
 
+/*
+ * These macros get 1-, 2-, and 4-byte integer values by reading the
+ * next few bytes in little-endian order.
+ */
 #define	BGETC(bp)\
-	((bp)->icount?(bp)->bbuf[(bp)->bsize+(bp)->icount++]:Bgetc((bp)))
+#	((bp)->icount?(bp)->ebuf[(bp)->icount++]:Bgetc((bp)))
+#define	BGETLE2(bp)\
+	((bp)->icount<=-2?((bp)->icount+=2,((bp)->ebuf[(bp)->icount-2])|((bp)->ebuf[(bp)->icount-1]<<8)):Bgetle2((bp)))
+#define	BGETLE4(bp)\
+	((bp)->icount<=-4?((bp)->icount+=4,((bp)->ebuf[(bp)->icount-4])|((bp)->ebuf[(bp)->icount-3]<<8)|((bp)->ebuf[(bp)->icount-2]<<16)|((bp)->ebuf[(bp)->icount-1]<<24)):Bgetle4((bp)))\
+
+/*
+ * These macros put 1-, 2-, and 4-byte integer values by writing the
+ * next few bytes in little-endian order.
+ */
 #define	BPUTC(bp,c)\
-	((bp)->ocount?(bp)->bbuf[(bp)->bsize+(bp)->ocount++]=(c),0:Bputc((bp),(c)))
+#	((bp)->ocount?(bp)->ebuf[(bp)->ocount++]=(unsigned char)(c),0:Bputc((bp),(c)))
+#define	BPUTLE2(bp,c)\
+	((bp)->ocount<=-2?(bp)->ocount+=2,(bp)->ebuf[(bp)->ocount-2]=(unsigned char)(c),(bp)->ebuf[(bp)->ocount-1]=(unsigned char)(c>>8),0:Bputle2((bp),(c)))
+#define	BPUTLE4(bp,c)\
+	((bp)->ocount<=-4?(bp)->ocount+=4,(bp)->ebuf[(bp)->ocount-4]=(unsigned char)(c),(bp)->ebuf[(bp)->ocount-3]=(unsigned char)(c>>8),(bp)->ebuf[(bp)->ocount-2]=(unsigned char)(c>>16),(bp)->ebuf[(bp)->ocount-1]=(unsigned char)(c>>24),0:Bputle4((bp),(c)))
+
 #define	BOFFSET(bp)\
 	(((bp)->state==Bractive)?\
 		(bp)->offset + (bp)->icount:\
@@ -90,6 +108,8 @@ Biobuf*	Bfdopen(int, int);\
 int	Bfildes(Biobuf*);\
 int	Bflush(Biobuf*);\
 int	Bgetc(Biobuf*);\
+int	Bgetle2(Biobuf*);\
+int	Bgetle4(Biobuf*);\
 int	Bgetd(Biobuf*, double*);\
 long	Bgetrune(Biobuf*);\
 int	Binit(Biobuf*, int, int);\
@@ -99,6 +119,8 @@ vlong	Boffset(Biobuf*);\
 Biobuf*	Bopen(char*, int);\
 int	Bprint(Biobuf*, char*, ...);\
 int	Bputc(Biobuf*, int);\
+int	Bputle2(Biobuf*, int);\
+int	Bputle4(Biobuf*, int);\
 int	Bputrune(Biobuf*, long);\
 void*	Brdline(Biobuf*, int);\
 char*	Brdstr(Biobuf*, int, int);\

src/libbio/bgetc.c

--- a/src/libbio/bgetc.c
+++ b/src/libbio/bgetc.c
@@ -66,6 +66,26 @@ loop:
 	goto loop;
 }
 
+int
+Bgetle2(Biobuf *bp)
+{
+	int l, h;
+
+	l = Bgetc(bp);
+	h = Bgetc(bp);
+	return l|(h<<8);
+}
+
+int
+Bgetle4(Biobuf *bp)
+{
+	int l, h;
+
+	l = Bgetle2(bp);
+	h = Bgetle2(bp);
+	return l|(h<<16);
+}
+
 int
 Bungetc(Biobuf *bp)
 {

src/libbio/bputc.c

--- a/src/libbio/bputc.c
+++ b/src/libbio/bputc.c
@@ -44,3 +44,17 @@ Bputc(Biobuf *bp, int c)\
 	}\
 	return Beof;\
 }\
+\
+int
+Bputle2(Biobuf *bp, int c)
+{\
+	Bputc(bp, c);
+	return Bputc(bp, c>>8);
+}\
+\
+int
+Bputle4(Biobuf *bp, int c)
+{\
+	Bputle2(bp, c);
+	return Bputle2(bp, c>>16);
+}\

その他のファイルでの変更例 (src/cmd/5a/lex.c の一部)

--- a/src/cmd/5a/lex.c
+++ b/src/cmd/5a/lex.c
@@ -485,14 +485,14 @@ void
 zname(char *n, int t, int s)
 {
 
-	Bputc(&obuf, ANAME);\
-	Bputc(&obuf, t);\t/* type */
-	Bputc(&obuf, s);\t/* sym */
+	BPUTC(&obuf, ANAME);\
+	BPUTC(&obuf, t);\t/* type */
+	BPUTC(&obuf, s);\t/* sym */
 	while(*n) {
-		Bputc(&obuf, *n);\
+		BPUTC(&obuf, *n);\
 		n++;
 	}\
-	Bputc(&obuf, 0);\
+	BPUTC(&obuf, 0);\
 }
 
 void
@@ -503,11 +503,11 @@ zaddr(Gen *a, int s)
 	char *n;\
 	Ieee e;\
 
-	Bputc(&obuf, a->type);\
-	Bputc(&obuf, a->reg);\
-	Bputc(&obuf, s);\
-	Bputc(&obuf, a->name);\
-	Bputc(&obuf, 0);\
+	BPUTC(&obuf, a->type);\
+	BPUTC(&obuf, a->reg);\
+	BPUTC(&obuf, s);\
+	BPUTC(&obuf, a->name);\
+	BPUTC(&obuf, 0);\
 	switch(a->type) {
 	default:
 		print("unknown type %d\n", a->type);
@@ -522,45 +522,33 @@ zaddr(Gen *a, int s)
 
 	case D_REGREG:
 	case D_REGREG2:
-		Bputc(&obuf, a->offset);\
+		BPUTC(&obuf, a->offset);\
 		break;
 
 	case D_CONST2:
 		l = a->offset2;\
-		Bputc(&obuf, l);\
-		Bputc(&obuf, l>>8);\
-		Bputc(&obuf, l>>16);\
-		Bputc(&obuf, l>>24);\
+		BPUTLE4(&obuf, l);\
 		// fall through
 	case D_OREG:
 	case D_CONST:
 	case D_BRANCH:
 	case D_SHIFT:
 		l = a->offset;\
-		Bputc(&obuf, l);\
-		Bputc(&obuf, l>>8);\
-		Bputc(&obuf, l>>16);\
-		Bputc(&obuf, l>>24);\
+		BPUTLE4(&obuf, l);\
 		break;
 
 	case D_SCONST:
 		n = a->sval;\
 		for(i=0; i<NSNAME; i++) {
-			Bputc(&obuf, *n);\
+			BPUTC(&obuf, *n);\
 			n++;
 		}\
 		break;
 
 	case D_FCONST:
 		ieeedtod(&e, a->dval);\
-		Bputc(&obuf, e.l);\
-		Bputc(&obuf, e.l>>8);\
-		Bputc(&obuf, e.l>>16);\
-		Bputc(&obuf, e.l>>24);\
-		Bputc(&obuf, e.h);\
-		Bputc(&obuf, e.h>>8);\
-		Bputc(&obuf, e.h>>16);\
-		Bputc(&obuf, e.h>>24);\
+		BPUTLE4(&obuf, e.l);\
+		BPUTLE4(&obuf, e.h);\
 		break;
 	}\
 }

コアとなるコードの解説

include/bio.h の変更

  • BGETCマクロの改善:
    • 変更前: ((bp)->icount?(bp)->bbuf[(bp)->bsize+(bp)->icount++]:Bgetc((bp)))
    • 変更後: ((bp)->icount?(bp)->ebuf[(bp)->icount++]:Bgetc((bp)))
    • bbufからebufへの変更は、Biobuf構造体の内部的なバッファ管理の改善を示唆しています。icountは読み込み可能なバイト数、icount++はポインタを進める操作です。icountが0でない（バッファにデータがある）場合は直接バッファから読み込み、そうでなければBgetc関数を呼び出してバッファを補充します。
  • BPUTCマクロの改善:
    • 変更前: ((bp)->ocount?(bp)->bbuf[(bp)->bsize+(bp)->ocount++]=(c),0:Bputc((bp),(c)))
    • 変更後: ((bp)->ocount?(bp)->ebuf[(bp)->ocount++]=(unsigned char)(c),0:Bputc((bp),(c)))
    • ocountは書き込み可能なバッファサイズ、ocount++はポインタを進める操作です。ocountが0でない（バッファに空きがある）場合は直接バッファに書き込み、そうでなければBputc関数を呼び出してバッファをフラッシュします。unsigned charへのキャストは、バイト単位の書き込みを明示しています。
  • BGETLE2/4およびBPUTLE2/4マクロの新規導入:
    • これらのマクロは、それぞれ2バイトおよび4バイトのリトルエンディアン整数をバッファから直接読み書きするためのものです。
    • 例えばBGETLE4は、icountが少なくとも4バイト分あるかを確認し、あればバッファから4バイトを直接読み込み、リトルエンディアンの順序で結合して整数値を生成します。なければBgetle4関数を呼び出します。
    • これにより、複数バイトの読み書きにおいても、ほとんどの場合で関数呼び出しを回避し、インラインで高速な処理が可能になります。
  • 関数プロトタイプの追加: Bgetle2, Bgetle4, Bputle2, Bputle4の関数プロトタイプが追加され、これらのマクロがフォールバックするC関数が存在することを宣言しています。

src/libbio/bgetc.c および src/libbio/bputc.c の変更

  • Bgetle2, Bgetle4関数の実装:
    • Bgetle2はBgetcを2回呼び出し、リトルエンディアンの順序で結合します。
    • Bgetle4はBgetle2を2回呼び出し、リトルエンディアンの順序で結合します。
    • これらの関数は、マクロがバッファから直接読み書きできない場合にのみ呼び出されます。
  • Bputle2, Bputle4関数の実装:
    • Bputle2はBputcを2回呼び出し、リトルエンディアンの順序でバイトを書き込みます。
    • Bputle4はBputle2を2回呼び出し、リトルエンディアンの順序でバイトを書き込みます。
    • これらの関数も、マクロがバッファに直接書き込めない場合にのみ呼び出されます。

各ツールチェインファイルでの変更

  • src/cmd/5a/lex.cの例に見られるように、従来のBputc(&obuf, ...)のような1バイト書き込みはBPUTC(&obuf, ...)に、複数バイトの書き込み（例: 4バイト整数l）はBputc(&obuf, l); Bputc(&obuf, l>>8); ...のような形式からBPUTLE4(&obuf, l);のような新しいマクロに置き換えられています。
  • 同様に、読み込み側でもBgetcの直接呼び出しがBGETCに、Bget4のような複数バイト読み込みがBGETLE4に置き換えられています。
  • これにより、Goツールチェインの各コンポーネントが、より効率的なバッファリングI/Oマクロを利用するようになり、全体的なパフォーマンスが向上します。

この変更は、Goツールチェインのビルドパフォーマンスを向上させるための、低レベルかつ広範囲にわたる最適化であり、関数呼び出しのオーバーヘッドを削減し、バッファリングI/Oを最大限に活用することで、顕著なCPU時間削減を実現しています。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード (特にsrc/libbioディレクトリ): https://github.com/golang/go/tree/master/src/libbio
  • C言語におけるマクロと関数のパフォーマンスに関する一般的な情報 (例: インライン展開、関数呼び出しオーバーヘッド)
  • リトルエンディアンとビッグエンディアンに関する一般的な情報
  • Go言語のコンパイラ/リンカの内部構造に関する一般的な情報 (Goのドキュメントや関連する論文など)
    • （具体的なURLはコミット内容からは特定できないため、一般的な情報源として記載）