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

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

このコミットは、Goコンパイラ（cmd/gc）におけるメモリ使用量の最適化に関するものです。具体的には、不要な場合に「デッド値マップ（dead value maps）」の計算を行わないようにすることで、コンパイラのメモリフットプリントを削減します。

コミット

commit 145edc283fab61d732457ddd431e45a10da0f4d8
Author: Russ Cox <rsc@golang.org>
Date:   Fri Dec 20 19:14:42 2013 -0500

    cmd/gc: do not compute dead value maps if they will not be used
    
    Reduces 6g big.go memory usage from 251 MB to 242 MB.
    Reduces 6g slow.go memory usage from 529 MB to 453 MB.
    
    Mostly a memory savings; 6g slow.go is only about 5% faster.
    
    The test programs are at
    https://rsc.googlecode.com/hg/testdata/big.go (36k lines, 276kB)
    https://rsc.googlecode.com/hg/testdata/slow.go (7k lines, 352kB)
    
    R=golang-codereviews, bradfitz, iant
    CC=golang-codereviews
    https://golang.org/cl/42280045

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

https://github.com/golang/go/commit/145edc283fab61d732457ddd431e45a10da0f4d8

元コミット内容

Goコンパイラ（cmd/gc）において、デッド値マップが使用されない場合にはその計算を行わないようにする変更です。これにより、big.goのコンパイル時のメモリ使用量が251MBから242MBに、slow.goのコンパイル時のメモリ使用量が529MBから453MBに削減されました。この変更は主にメモリ削減を目的としており、slow.goのコンパイル速度は約5%向上するに留まります。

変更の背景

コンパイラは、プログラムの最適化やガベージコレクションの効率化のために、様々なデータ構造を内部的に構築します。その一つに「ライブネス情報」や「デッド値情報」があります。これらは、特定の時点でどの変数が「生きている」（将来的に使用される可能性がある）か、あるいは「死んでいる」（もはや使用されない）かを追跡するために用いられます。

しかし、これらの情報は常にすべてのコンパイルパスで必要とされるわけではありません。特に、デッド値マップのような特定の最適化やデバッグ情報生成にのみ使用されるデータは、それが不要な場合にまで計算・保持されると、コンパイラのメモリ使用量を不必要に増加させてしまいます。

このコミットの背景には、Goコンパイラが大規模なコードベースをコンパイルする際のメモリフットプリントを削減し、より効率的に動作させるという目的があります。特に、big.goやslow.goのような大規模なテストケースで顕著なメモリ使用量の削減が見られたことから、この最適化の重要性が伺えます。

前提知識の解説

1. Goコンパイラ (cmd/gc)

Go言語の公式コンパイラは、gc（Go Compiler）と呼ばれ、Goのソースコードを機械語に変換する役割を担っています。cmd/gcは、そのコンパイラの実装が含まれるディレクトリです。コンパイラは、構文解析、型チェック、中間コード生成、最適化、コード生成といった複数のフェーズを経て動作します。

2. ライブネス解析 (Liveness Analysis)

ライブネス解析は、コンパイラのデータフロー解析の一種です。プログラムの特定のポイントにおいて、ある変数の値が「ライブ（live）」であるか「デッド（dead）」であるかを決定します。

  • ライブ変数: その変数の現在の値が、プログラムの将来のどこかの時点で読み取られる可能性がある場合。
  • デッド変数: その変数の現在の値が、プログラムの将来のどの時点でも読み取られることがない場合（つまり、その値はもはや必要ない）。

ライブネス解析の結果は、レジスタ割り当ての最適化（デッドな変数が占めていたレジスタを解放する）、デッドコード削除（デッドな変数を計算するだけのコードを削除する）、ガベージコレクション（デッドなオブジェクトが占めていたメモリを解放する）など、様々なコンパイラ最適化に利用されます。

3. デッド値マップ (Dead Value Maps)

ライブネス解析の概念を拡張したもので、特定のプログラムポイントで変数がデッドになった際に、その変数が保持していた値に関する情報（例えば、それがポインタであった場合に、そのポインタが指していたメモリ領域がもはや参照されないこと）を追跡するためのデータ構造です。これは、ガベージコレクタがメモリをより正確かつ効率的に回収するために利用されることがあります。例えば、あるポインタ変数がデッドになった場合、そのポインタが指していたオブジェクトもデッドであると判断できれば、そのオブジェクトをガベージコレクションの対象とすることができます。

4. Bvec (Bit Vector)

ビットベクトルは、ブール値の配列を効率的に表現するためのデータ構造です。各ビットが特定の要素の有無（真/偽）を示します。コンパイラでは、ライブネス情報や到達可能定義など、多数のブール値を扱うデータフロー解析において頻繁に利用されます。メモリ効率が良く、ビット単位の論理演算（AND, ORなど）によって高速に集合演算を行える利点があります。

5. Array

この文脈でのArrayは、Goコンパイラ内部で使われる動的な配列データ構造を指します。C言語で実装されているGoコンパイラでは、Arrayは通常、要素の追加や削除が可能な可変長配列として実装されています。

技術的詳細

このコミットの核心は、Goコンパイラのライブネス解析フェーズにおける「デッド値マップ」の計算を条件付きにすることです。

Goコンパイラは、関数ごとにライブネス情報を計算します。この情報には、各プログラムポイントでのライブ変数に関する情報だけでなく、ガベージコレクションのために「デッド値」に関する情報も含まれることがあります。デッド値マップは、特にポインタ型の変数がデッドになった際に、そのポインタが指していたメモリ領域がもはやアクセスされないことをガベージコレクタに伝えるために使用されます。

しかし、すべてのコンパイルシナリオでこのデッド値マップが必要とされるわけではありません。例えば、特定の最適化パスやデバッグ情報の生成が不要な場合、デッド値マップを計算することは単なるリソースの無駄になります。

このコミットでは、src/cmd/gc/plive.cファイル内の以下の関数が変更されています。

  1. newliveness関数の変更:

    • この関数は、ライブネス解析に必要なLiveness構造体を初期化します。
    • 変更前は、deadvaluesとargsdeadvaluesという2つのArray（デッド値マップを格納する）を常に初期化していました。
    • 変更後、computedeadという新しい引数が追加されました。この引数がtrueの場合にのみ、deadvaluesとargsdeadvaluesが初期化され、falseの場合はnil（NULL）に設定されます。これにより、不要なメモリ割り当てと初期化が回避されます。

  2. freeliveness関数の変更:

    • この関数は、Liveness構造体によって割り当てられたメモリを解放します。
    • 変更前は、deadvaluesとargsdeadvaluesが常に存在すると仮定して、それらの内容を解放していました。
    • 変更後、lv->deadvalues != nilという条件が追加され、deadvaluesとargsdeadvaluesが実際に初期化されている場合にのみ、その内容を解放するように変更されました。これにより、nilポインタの解放によるクラッシュを防ぎ、コードの堅牢性が向上します。

  3. livenessepilogue関数の変更:

    • この関数は、ライブネス解析の最終段階で、ライブネス情報とデッド値情報を構築します。
    • 変更前は、deadvaluesとargsdeadvaluesに常にBvec（ビットベクトル）を割り当て、追加していました。
    • 変更後、lv->deadvalues != nilという条件が追加され、デッド値マップが実際に使用される場合にのみ、これらのビットベクトルの割り当てと追加が行われるようになりました。

  4. liveness関数の変更:

    • この関数は、ライブネス解析の全体をオーケストレーションします。
    • newliveness関数を呼び出す際に、deadsym != nilという条件をcomputedead引数として渡すようになりました。deadsymは、デッド値に関するシンボル（おそらくデバッグ情報や特定の最適化フラグに関連するもの）であり、これが存在する場合にのみデッド値マップが必要と判断されます。

これらの変更により、コンパイラはデッド値マップが不要な場合に、そのためのメモリ割り当て、計算、および解放のオーバーヘッドを完全に回避できるようになります。結果として、コンパイル時のメモリ使用量が削減され、特に大規模なGoプログラムのコンパイル効率が向上します。

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

変更はsrc/cmd/gc/plive.cファイルに集中しています。

--- a/src/cmd/gc/plive.c
+++ b/src/cmd/gc/plive.c
@@ -690,7 +690,7 @@ progeffects(Prog *prog, Array *vars, Bvec *uevar, Bvec *varkill)\n // liveness computation.  The cfg argument is an array of BasicBlock*s and the\n // vars argument is an array of Node*s.\n static Liveness*\n-newliveness(Node *fn, Prog *ptxt, Array *cfg, Array *vars)\n+newliveness(Node *fn, Prog *ptxt, Array *cfg, Array *vars, int computedead)\n {\n \tLiveness *result;\n \tint32 i;\n@@ -719,8 +719,13 @@ newliveness(Node *fn, Prog *ptxt, Array *cfg, Array *vars)\n \n \tresult->livepointers = arraynew(0, sizeof(Bvec*));\n \tresult->argslivepointers = arraynew(0, sizeof(Bvec*));\n-\tresult->deadvalues = arraynew(0, sizeof(Bvec*));\n-\tresult->argsdeadvalues = arraynew(0, sizeof(Bvec*));\n+\tif(computedead) {\n+\t\tresult->deadvalues = arraynew(0, sizeof(Bvec*));\n+\t\tresult->argsdeadvalues = arraynew(0, sizeof(Bvec*));
+\t} else {\n+\t\tresult->deadvalues = nil;\n+\t\tresult->argsdeadvalues = nil;\n+\t}\n \treturn result;\n }\
 \n@@ -741,13 +746,15 @@ freeliveness(Liveness *lv)\n \t\tfree(*(Bvec**)arrayget(lv->argslivepointers, i));\n \tarrayfree(lv->argslivepointers);\n \n-\tfor(i = 0; i < arraylength(lv->deadvalues); i++)\n-\t\tfree(*(Bvec**)arrayget(lv->deadvalues, i));\n-\tarrayfree(lv->deadvalues);\n-\n-\tfor(i = 0; i < arraylength(lv->argsdeadvalues); i++)\n-\t\tfree(*(Bvec**)arrayget(lv->argsdeadvalues, i));\n-\tarrayfree(lv->argsdeadvalues);\n+\tif(lv->deadvalues != nil) {\n+\t\tfor(i = 0; i < arraylength(lv->deadvalues); i++)\n+\t\t\tfree(*(Bvec**)arrayget(lv->deadvalues, i));\n+\t\tarrayfree(lv->deadvalues);\n+\t\n+\t\tfor(i = 0; i < arraylength(lv->argsdeadvalues); i++)\n+\t\t\tfree(*(Bvec**)arrayget(lv->argsdeadvalues, i));\n+\t\tarrayfree(lv->argsdeadvalues);\n+\t}\n \n \tfor(i = 0; i < arraylength(lv->cfg); i++) {\n \t\tfree(lv->uevar[i]);\n@@ -1333,10 +1340,12 @@ livenessepilogue(Liveness *lv)\n \t\t\tarrayadd(lv->livepointers, &locals);\n \n \t\t\t// Dead stuff second.\n-\t\t\targs = bvalloc(argswords() * BitsPerPointer);\n-\t\t\tarrayadd(lv->argsdeadvalues, &args);\n-\t\t\tlocals = bvalloc(localswords() * BitsPerPointer);\n-\t\t\tarrayadd(lv->deadvalues, &locals);\n+\t\t\tif(lv->deadvalues != nil) {\n+\t\t\t\targs = bvalloc(argswords() * BitsPerPointer);\n+\t\t\t\tarrayadd(lv->argsdeadvalues, &args);\n+\t\t\t\tlocals = bvalloc(localswords() * BitsPerPointer);\n+\t\t\t\tarrayadd(lv->deadvalues, &locals);\n+\t\t\t}\n \t\t}\n \n \t\t// walk backward, emit pcdata and populate the maps\n@@ -1391,9 +1400,11 @@ livenessepilogue(Liveness *lv)\n \t\t\t\ttwobitlivepointermap(lv, liveout, lv->vars, args, locals);\n \n \t\t\t\t// Record dead values.\n-\t\t\t\targs = *(Bvec**)arrayget(lv->argsdeadvalues, pos);\n-\t\t\t\tlocals = *(Bvec**)arrayget(lv->deadvalues, pos);\n-\t\t\t\ttwobitdeadvaluemap(lv, liveout, lv->vars, args, locals);\n+\t\t\t\tif(lv->deadvalues != nil) {\n+\t\t\t\t\targs = *(Bvec**)arrayget(lv->argsdeadvalues, pos);\n+\t\t\t\t\tlocals = *(Bvec**)arrayget(lv->deadvalues, pos);\n+\t\t\t\t\ttwobitdeadvaluemap(lv, liveout, lv->vars, args, locals);\n+\t\t\t\t}\n \n \t\t\t\tpos--;\n \t\t\t}\n@@ -1487,7 +1498,7 @@ liveness(Node *fn, Prog *firstp, Sym *argssym, Sym *livesym, Sym *deadsym)\n \tcfg = newcfg(firstp);\n \tif(0) printcfg(cfg);\n \tvars = getvariables(fn);\n-\tlv = newliveness(fn, firstp, cfg, vars);\n+\tlv = newliveness(fn, firstp, cfg, vars, deadsym != nil);\n \n \t// Run the dataflow framework.\n \tlivenessprologue(lv);\

コアとなるコードの解説

newliveness関数の変更

 static Liveness*
-newliveness(Node *fn, Prog *ptxt, Array *cfg, Array *vars)
+newliveness(Node *fn, Prog *ptxt, Array *cfg, Array *vars, int computedead)
 {
  	Liveness *result;
  	int32 i;
@@ -719,8 +719,13 @@ newliveness(Node *fn, Prog *ptxt, Array *cfg, Array *vars)
  
  	result->livepointers = arraynew(0, sizeof(Bvec*));
  	result->argslivepointers = arraynew(0, sizeof(Bvec*));
-	result->deadvalues = arraynew(0, sizeof(Bvec*));
-	result->argsdeadvalues = arraynew(0, sizeof(Bvec*));
+	if(computedead) {
+		result->deadvalues = arraynew(0, sizeof(Bvec*));
+		result->argsdeadvalues = arraynew(0, sizeof(Bvec*));
+	} else {
+		result->deadvalues = nil;
+		result->argsdeadvalues = nil;
+	}
  	return result;
 }
  • newliveness関数にcomputedeadという新しいint型（C言語では真偽値として扱われる）の引数が追加されました。
  • このcomputedeadの値に基づいて、result->deadvaluesとresult->argsdeadvaluesの初期化が条件分岐されるようになりました。
  • computedeadが真の場合、これらは通常通りarraynewで初期化されます。
  • computedeadが偽の場合、これらはnil（NULLポインタ）に設定されます。これにより、デッド値マップが不要な場合に、関連するデータ構造のメモリ割り当てが完全にスキップされます。

freeliveness関数の変更

@@ -741,13 +746,15 @@ freeliveness(Liveness *lv)\
  	\tfree(*(Bvec**)arrayget(lv->argslivepointers, i));\
  	arrayfree(lv->argslivepointers);\
  
-\tfor(i = 0; i < arraylength(lv->deadvalues); i++)\
-\t\tfree(*(Bvec**)arrayget(lv->deadvalues, i));\
-\tarrayfree(lv->deadvalues);\
-\n-\tfor(i = 0; i < arraylength(lv->argsdeadvalues); i++)\
-\t\tfree(*(Bvec**)arrayget(lv->argsdeadvalues, i));\
-\tarrayfree(lv->argsdeadvalues);\
+\tif(lv->deadvalues != nil) {\
+\t\tfor(i = 0; i < arraylength(lv->deadvalues); i++)\
+\t\t\tfree(*(Bvec**)arrayget(lv->deadvalues, i));\
+\t\tarrayfree(lv->deadvalues);\
+\t\n+\t\tfor(i = 0; i < arraylength(lv->argsdeadvalues); i++)\
+\t\t\tfree(*(Bvec**)arrayget(lv->argsdeadvalues, i));\
+\t\tarrayfree(lv->argsdeadvalues);\
+\t}\
  
  	for(i = 0; i < arraylength(lv->cfg); i++) {
  	\tfree(lv->uevar[i]);
  • deadvaluesとargsdeadvaluesの解放処理が、if(lv->deadvalues != nil)という条件ブロックで囲まれました。
  • これは、newlivenessでこれらのポインタがnilに設定されている可能性があるため、nilポインタを逆参照して解放しようとすることを防ぐための安全策です。これにより、プログラムのクラッシュを防ぎます。

livenessepilogue関数の変更

@@ -1333,10 +1340,12 @@ livenessepilogue(Liveness *lv)\
  	\t\t\tarrayadd(lv->livepointers, &locals);\
  
  	\t\t\t// Dead stuff second.\
-\t\t\targs = bvalloc(argswords() * BitsPerPointer);\
-\t\t\tarrayadd(lv->argsdeadvalues, &args);\
-\t\t\tlocals = bvalloc(localswords() * BitsPerPointer);\
-\t\t\tarrayadd(lv->deadvalues, &locals);\
+\t\t\tif(lv->deadvalues != nil) {\
+\t\t\t\targs = bvalloc(argswords() * BitsPerPointer);\
+\t\t\t\tarrayadd(lv->argsdeadvalues, &args);\
+\t\t\t\tlocals = bvalloc(localswords() * BitsPerPointer);\
+\t\t\t\tarrayadd(lv->deadvalues, &locals);\
+\t\t\t}\
  	\t}\
  
  	\t// walk backward, emit pcdata and populate the maps
@@ -1391,9 +1400,11 @@ livenessepilogue(Liveness *lv)\
  	\t\t\t\ttwobitlivepointermap(lv, liveout, lv->vars, args, locals);\
  
  	\t\t\t\t// Record dead values.\
-\t\t\t\targs = *(Bvec**)arrayget(lv->argsdeadvalues, pos);\
-\t\t\t\tlocals = *(Bvec**)arrayget(lv->deadvalues, pos);\
-\t\t\t\ttwobitdeadvaluemap(lv, liveout, lv->vars, args, locals);\
+\t\t\t\tif(lv->deadvalues != nil) {\
+\t\t\t\t\targs = *(Bvec**)arrayget(lv->argsdeadvalues, pos);\
+\t\t\t\t\tlocals = *(Bvec**)arrayget(lv->deadvalues, pos);\
+\t\t\t\t\ttwobitdeadvaluemap(lv, liveout, lv->vars, args, locals);\
+\t\t\t\t}\
  
  	\t\t\t\tpos--;\
  	\t\t\t}
  • livenessepilogue関数内のデッド値マップ（argsdeadvaluesとdeadvalues）へのBvecの割り当てと追加、およびそれらの値の記録が、if(lv->deadvalues != nil)という条件ブロックで囲まれました。
  • これにより、newlivenessでデッド値マップが初期化されていない場合（つまりnilの場合）には、これらの処理がスキップされ、不要な計算とメモリ操作が回避されます。

liveness関数の変更

@@ -1487,7 +1498,7 @@ liveness(Node *fn, Prog *firstp, Sym *argssym, Sym *livesym, Sym *deadsym)\
  	cfg = newcfg(firstp);\
  	if(0) printcfg(cfg);\
  	vars = getvariables(fn);\
-\tlv = newliveness(fn, firstp, cfg, vars);\
+\tlv = newliveness(fn, firstp, cfg, vars, deadsym != nil);\
  
  	// Run the dataflow framework.\
  	livenessprologue(lv);
  • liveness関数がnewlivenessを呼び出す際に、新しい引数computedeadにdeadsym != nilという値を渡すようになりました。
  • deadsymは、デッド値に関するシンボル（例えば、デバッグ情報生成のためにデッド値情報が必要な場合などに設定されるシンボル）を指します。
  • この変更により、deadsymが存在する場合にのみcomputedeadがtrueとなり、デッド値マップが計算されるようになります。それ以外の場合はfalseとなり、デッド値マップの計算はスキップされます。

これらの変更は、Goコンパイラの内部動作をより効率的にし、必要な場合にのみリソースを消費するように最適化されています。

関連リンク

参考にした情報源リンク