1/52

第8回
高速化チューニングとその関連技術１
渡辺宙志
慶應義塾大学理工学部
物理情報工学科

Outline1. チューニング、その前に
2. バグを入れないコーディング
3. デバッグの方法論

Jun. 6, 2019@計算科学技術特論A

本講義の内容
プログラム開発時間の短縮 (今週)・バグを入れないコーディング習慣・バグを入れにくい開発手順
・バージョン管理システム
・デバッグの効率化
とても今後の人生の役に立ちますプログラム実行時間の短縮 (来週)・プロファイラの使い方
・メモリ最適化・SIMD化等
ほとんど今後の人生の役に立ちません

2/52

3/52

チューニング、その前にチューニング、その前に (1/3)

最適化の第一法則：最適化するな最適化の第二法則(上級者限定)：まだするな

Michael A. Jackson, 1975

4/52

チューニング、その前に (2/3)

足が速いからといって良いサッカー選手になれるとは限らない

H. Watanabe, 2012

5/52

チューニング、その前に (3/3)

6/52

なぜ最適化するのか？
プログラムの実行時間を短くするためなぜ実行時間を短くしたいのか？

計算結果を早く手に入れるためなぜ計算結果を早く手にいれたいのか？
論文を早く書くため ← ここがとりあえずのゴール

最適化、並列化をする際には、必ず「いつまでに論文執筆まで持って行くか」を意識すること。だらだらと最適化にこだわらない。

7/52

典型的な研究スパン
年に二編論文を書く → 半年で一つの研究が完結

調査プログラム開発＋計算

執筆

調査：先行研究の調査や、計算手法についての調査 (1ヶ月)
開発＋計算：プログラム開発、計算の実行(4ヶ月)
執筆：結果の解析＋論文執筆＋投稿 (1ヶ月)

実態は・・・
調査

開発

デバッグ

計算

執筆

開発時間の大部分はデバッグに費やされている初心者であるほど、デバッグの占める割合が長くなる
コードの高速化は、研究時間の短縮にさほど寄与しない※ もちろん例外ありデバッグについて

8/52

Q. 最適化、並列化でもっとも大事なことは何か？
A. バグを入れないこと
開発において最も時間のかかるプロセスはデバッグ
並列プログラムのデバッグは絶望的に難しい
デバッグは時間がかかり、集中力が要求され、達成感もある
しかし、結局は自分が入れたバグを自分で取っているだけ「デバッグは仕事ではない」ということを肝に銘じること

バグの入り方

9/52

Q. バグはいつ入るか？
A. 機能を追加したとき

速効型：機能追加直後に判明するバグ→ バグを入れないコーディング
地雷型：機能追加後、後で判明するバグ→ デバッグの方法論10/52

バグを入れないコーディングバグを入れないコーディング
・バグが入りにくいプログラム習慣をつける・ コンパイラの警告を無視しない・ 普段からassertをいれる癖をつける
・ バグが入りにくい開発プロセスを踏む
・ 単体テスト・ sort+diffデバッグ
・ それでもバグが入ってしまったら・・・・ バージョン管理システムとの連携
・ デバッガの利用

11/52

コンパイラの警告を無視しない (1/4)
代入と比較の間違い
for(int i=0;i<10;i++){
if (i==3) puts("i=3!");if(i=3) puts("i=3! ");本当はこれが正しい}コンパイラはデフォルトで上記のコードに警告を出さないが、「-Wall」をつけると以下の警告を出してくれる$ g++ -Wall test.cpp
test.cpp: 関数 ‘int main()’ 内:
test.cpp:6:11: 警告: 真偽値として使われる代入のまわりでは、丸括弧の使用をお勧めします [-Wparentheses]
if(i=3)puts("i=3! ");注：この警告は、もしこれがミスでなく意図するコードならif ((i=3)) puts("i=3! ");と書けという意味。こうすると警告が消える。

12/52

コンパイラの警告を無視しない (2/4)

13/52

このプログラムの間違い、すぐにわかりますか？
#include <cstdio>
int add_three (int verylongname){
int veryverylongname= veryverylongname+ 3;
return veryverylongname;}int main(){printf("%d¥n", add_three(1));}
add_threeは、引数に3を加えた値を返す関数のつもりコンパイラの警告を無視しない (3/4)
・本来なら引数であるべき変数を、似た名前のローカル変数で書いてしまった
int add_three (int verylongname){
int veryverylongname= veryverylongname+ 3;
return veryverylongname;}int veryverylongname= verylongname+ 3;
ここは、本当はこれが正しい
コンパイラはデフォルトで以下のコードに警告を出さない

int a = a + 1;

14/52

コンパイラの警告を無視しない (4/4)

15/52(1) 「-Wall」オプションをつけてコンパイルすると・・・$ g++ -Wall test.cpp
test.cpp: 関数 ‘int add_three(int)’ 内:
test.cpp:5:45: 警告: ‘veryverylongname’ はこの関数内で初期化されずに使用されています [-Wuninitialized]
int veryverylongname = veryverylongname + 3;

ちゃんと「初期化されてない変数を使ってるよ」と教えてくれる(2) 「-Wall -Wextra」とオプションを追加すると・・・$ g++ -Wall test.cpp
test.cpp:4:5: 警告: 仮引数 ‘verylongname’ が未使用です [-Wunused-parameter]
int add_three(int verylongname){^
test.cpp: 関数 ‘int add_three(int)’ 内:
test.cpp:5:45: 警告: ‘veryverylongname’ はこの関数内で初期化されずに使用されています [-Wuninitialized]
int veryverylongname = veryverylongname + 3;^

「使われてない変数があるよ」とも教えてくれるIntelコンパイラでは、-w2で(1)を、-w3で(2)を教えてくれるコンパイラの警告を無視しないのまとめ16/52

普段から「-Wall –Wextra」相当のオプションを指定する癖をつける
コンパイラの警告を無視しない

コンパイラに指摘できる問題はできるだけ指摘させよう
普段から警告ゼロをキープすることが大事普段からassertをいれる癖をつける (1/4)
assertとは何か？
to state firmly that something is true
(From Longman Dictionary of Contemporary English)

C言語のassert
プログラムにおいて「成り立っていなければならない条件」を記述する#include <assert.h>...
assert(some condition);
中身が成り立っていれば何もしない
不成立なら、Assertion Failedと言ってプログラムがabortする※ JavaやPythonなど、多くの言語にassert機能がある

17/52

普段からassertをいれる癖をつける (2/4)

18/52

assertの例
void func(int a){assert(a<10);
printf("%d¥n",a);}入力となるaは10未満であるはず、と宣言する

int main(void){func(8); //OKfunc(11); //失敗する}

Assertionが破られたこと、ソースのどこでAssertionが破られたか教えてくれる

実行結果$ ./a.out
8
Assertion failed: (a<10), function func, file test.cpp, line 5.
zsh: abort./a.out普段からassertをいれる癖をつける (3/4)
assertの無効化
そんなチェックをたくさん入れたら遅くなるんじゃないの？

assertは「-DNDEBUG」オプションで無効にできます$ g++ -DNDEBUG test.cpp$ ./a.out
8
11

Assertion failedが起きない

開発中は有効に、プロダクトランの時には無効にする

19/52

普段からassertをいれる癖をつける (4/4)
assertに助けられた例
・ 粒子のペアが p1[N], p2[N]という2つの配列として表現されている
・ p1[i]とp2[i]がi番目のペアの粒子番号を表す
・ 高速化のため一度ソートし、必ず p1[i] < p2[i] となっているはずだった・ しかし念のためassert(p1[i] < p2[i]);を入れておいた・ 後日、自分がassertを入れたことも忘れた頃に・・・
Assertion failed: (p1[i] < p2[i] ), function calcforce, filecalcforce.cpp, line 125.

あとで追加した関数が、ソート関数を呼び忘れていたのが原因
コンパイル、計算は実行できるが、結果を地味に間違える

20/52

assertについてのまとめ

21/52

普段からassertを入れる癖をつける
どこに入れればいいかわからないんですが入れているうちにだんだん分かってきます※ この関数を呼ぶ時にはこうなってるはず、みたいなところに入れると良い

assertは「自分の実装意図」を示すコメント→ ただのコメントと違い、異常を検出してくれる
今日の自分が一ヶ月後の自分を助ける

転ばぬ先のassert

22/52

バグを入れない開発手順

バグを入れないために大事なこと頭を使わない
なるべく頭を使わず、機械的にチェックできる仕組みを作る

安全地帯を作る「ここまでは大丈夫」という「砦」を築きながら進む

23/52

バグを入れない開発手順
バグを入れない開発技法
長い歴史があり、現在も研究が進んでいる
XP、アジャイル開発、チケット駆動開発、テスト駆動開発、etc.

ここでは「sort+diffデバッグ」と「単体テスト」について説明する
sort+diffデバッグ
・ print文デバッグの一種・ 一致すべき情報が一致しているかどうか確認する手法
単体テスト
・ 開発したい部分だけを切り出してテストすること
・ いきなりコード全体でテスト(統合テスト)してはならない

24/52

sort+diff デバッグの例1：粒子対リスト作成 (1/2)
ペアリストとは？
相互作用距離(カットオフの距離)以内にある粒子対のリスト
全粒子対についてチェックすると O( N 2 )高速に粒子対を作成する方法 → グリッド探索
グリッド探索・空間をグリッドに切り、その範囲に存在する粒子を登録する→ 𝑂(𝑁)25/52

sort+diff デバッグの例1：粒子対リスト作成 (2/2)
ポイント
O(N)法とO(N^2)法は、同じconfigurationから同じペアリストを作るはずO(N^2)法は、計算時間はかかるが信頼できる (砦)手順

初期条件作成ルーチンとペアリスト作成ルーチンを切り出す(単体テスト)
O(N)とO(N^2)ルーチンに同じ初期条件を与え、ペアリストをダンプ
リストの順番は異なるので、sortしてからdiffを取る$ ./on2code | sort > o2.dat$ ./on1code | sort > o1.dat$ diff o1.dat o2.dat←結果が正しければdiffは何も出力しない

いきなり本番環境に組み込んで時間発展、などとは絶対にしない

26/52

sort+diff デバッグの例2：並列版リスト作成(1/2)
ペアリストの並列化
空間分割による並列化
各領域でそれぞれペアリストを作成

はじっこの粒子が正しく渡されているか？
周期境界条件は大丈夫か？
ポイント
並列化の有無に関わらず同じ配置からは同じペアリストを作成するはず

27/52

sort+diff デバッグの例2：並列版リスト作成(2/2)
ポイント
非並列版のペアリスト作成ルーチンはデバッグが終了しているはず (砦)

非並列版

同じ配置

並列版

sort
sort

sortdiff
この二つのペアリストは論理的に一致しているはず

28/52

バグを入れないコーディングのまとめ
新しい機能の追加や高速化をするたびに単体テストする
単体テストとは、必要なルーチンのみでコンパイル、実行すること全体のプログラムの一部に着目してテストすることではない
単体テストとは、ミクロな情報がすべて一致するのを確認することエネルギー保存など、マクロ量のチェックは単体テストではない「確実にここまでは大丈夫」という「砦」を築く
時間はかかるが信用できる方法と比較する
複数の機能を一度にテストしない

デバッグとは、入れたバグを取ることではなくそもそもバグを入れないこと

29/52

30/52

デバッグの方法論
地雷型バグのデバッグ方法

デバッグの方法論・・・その前に31/52

バージョン管理システム、使っていますか？
現代においてバージョン管理システムなしの開発は考えられないバージョン管理システムとはVersion Control System (VCS)
ファイルの編集履歴を管理するためのシステム
CVS, Subversion, Gitなどが有名
超優秀な秘書のようなもの

バージョン管理システムの役割

32/52

すべての編集履歴を保存する「あ、失敗した」を戻すことにできる「以前は動いてたのに」を再現できる

バックアップがわりになる※ リモートリポジトリを別サーバに用意した場合

修士論文提出直前にHDDが飛んだ
USBに保存してたデータが読めなくなった↑ こういう悲劇を防ぐ33/52Gitの仕組み
リモートリポジトリ
リポジトリ

pushclone

リポジトリ

fetch
プログラマ

commitプログラマ

ローカルに「リポジトリ」というデータベースがある
プログラマは「コミット」という作業で編集履歴を保存
編集履歴は「プッシュ」という作業でリモートリポジトリと同期する「クローン」により別の場所にリポジトリをダウンロードできる34/52

ありがちなパターン
ローカル1)開発したコードをスパコンへコード

スパコンコード
2)動かなかったので苦労して修正する

3)スパコンで実行中、別の修正をする

コードA4)修正したコードをスパコンへコードB

コードB
あっ、コードAを上書きしちゃった！

35/52

バージョン管理している場合
ローカル

スパコン

リポジトリ
2) リポジトリからスパコンへクローン

1)開発したコードをリポジトリへ

コード

コード

コード
3)動かなかったので苦労して修正する

5)スパコンの修正を忘れて別の修正

6)修正をコミットしようとして、衝突に気づく

コードB

衝突

コードA

4)修正をコミット

7)スパコン向けの修正と新しい修正を統合 (マージ)

コードC

コードA

GitHubについて
GitHubとはGitのホスティングサービス
無料でリモートリポジトリを作成できるプライベートリポジトリ(非公開)も無料で作成可能

コミットなどのアクティビティが可視化される

36/52

バージョン管理システムのまとめバージョン管理システムはバックアップの代わりになる
リモートリポジトリは物理的に異なるサーバに作ること
GithubやGitlabのプライベートリポジトリの活用などバージョン管理システムは作業履歴が保存される作業した結果が失われない問題があった場合に遡って調べることができるバージョン管理システムを使うと作業効率が倍以上になる→ 使わないと人生を半分損する

37/52

38/52地雷型バグ
地雷型バグとは？
バグを入れた後、しばらくしてから発見されるバグ
・最初から入っていたが、これまで気づかなかったタイプ
・機能追加時に、思わぬところに影響が波及したタイプ
バグを見つけたら？
いきなりデバッグをはじめない
デバッグにおいて重要なのは原因究明「いつのまにかなおっていた」は一番まずい→ 最初にやることは現場保全

CBA(1) 再現性テスト (同じ条件で実行したら同じバグを発生するか？)(2) バグを再現する最低限のコードを切り出す (容疑者の限定)

問題の切り分け (1/2)
実行したらSegmentation Faultと言われて止まった
やってはならないこと→ いきなりソースを見ながら原因を探る(特にダメなのが頭の中でのトレース実行)
やるべきこと・どこで止まったかを調べる
・どうやって調べるか？
→ print文による二分探索 (gdbでも可)
printf “1”;・・・
printf “2”;・・・
printf “3”;

出力が「1」であればこの間で止まっている

出力が「12」であればこの間で止まっている

上記を繰り返して、プログラムが止まる場所を特定する

39/52

問題の切り分け (2/2)
バグの発生箇所は、配列の領域外参照だった
const int N = 10;
double data[N];・・・
double func(int index){
return data[index]; ← ここでindex=10だった}

indexの値は0から9でないといけないのに、どこかでおかしな値が入った(バグの発生箇所と、止まる箇所は一般に異なる)
おかしな値になった場所をどうやって探すか？
→ assertを入れまくる(if文でも可)#include <assert.h>double func(int index){
assert(index<N); assertには「満たすべき条件」を記載する
・・・}

assertにひっかかると、以下のようなエラーが出て止まる
Assertion failed: (i<10), function func, file test.cc, line 7.

40/52

実際に経験したバグ (1/2)

41/52

起きたこと
・ ローカルPCで問題がなかったのに、スパコンでバグる
・ スパコンでも条件によりバグったりバグらなかったりする→ 当初、通信関連を疑ったが、乱数が原因だった
原因となった関数
与えられた整数Nについて、0からN-1までの数字をランダムに返す関数を意図してこんなコードを書いた
double myrand_double (void){
return (double)(rand())/(double) (RAND_MAX);}RAND_MAX=2147483647

int myrand_int (const int N){
return (int)(myrand_double()*N);}

実際には・・・

randは最高でRAND_MAXの値を返すので、myrand_intは低確率(21億分の1の確率)でNを返す

実際に経験したバグ (2/2)

42/52

const int N = 10;
double data[N];int index = myrand_int(N);

21億分の1の確率でNを返す// (ずっと遠くで)return data[index];

21億分の1の確率で配列外参照

だいたい2000ノード、1日ジョブで確率50%くらいで失敗した→ ローカルPCでは10年くらい流しても踏まないバグ

この種のバグの原因に「最初から思い至る」のは難しい
・ print文+assert文デバッグを行う
・ 必ず原因を究明し、放置しない

問題の切り分けとバージョン管理 (1/2)

43/52

例：メインカーネルを修正し、別のインプットを与えたら計算が失敗
問題の切り分けその機能を追加したことによるバグ？
もともとバグっていたものが顕在化？

インプット
A

計算ルーチン
(修正前)

OK

インプット
B

計算ルーチン
(修正版)

NG

容疑者
ルーチン追加前のソースを取って来て、Input Bを食わせる

インプット
BOK

今回の修正でバグが入ったNG

もともとあったバグが顕在化した計算ルーチン(修正前)

バージョン管理をしていると、問題の切り分けが容易

問題の切り分けとバージョン管理 (2/2)

44/52

昔入れたバグほど、デバッグが困難に (修正内容を忘れているから)
明日の自分は他人バージョン管理していれば・・・(1)ここでバグ発覚(2)ここまでは動作することを確認(砦)Ver. 1

Ver. 2

Ver. 3

Ver. 4

Ver. 5(3)実はここでバグ混入
デバッグ時間軸

Ver. 2とVer. 3のdiffを取れば、どこが原因かがすぐわかる
デバッグ目的以外にも「あのジョブを実行した時のソースが欲しい」ということはよくあるバージョン管理システムはタイムマシン

開発時間軸

デバッグのまとめ
バグったら、再現するコードを保存する (現場保全)
いつバグが混入したか確認する (砦)バグに関係のないルーチンを削除していく (問題の切り分け)
print文、assert文デバッグ (頭を使わない)※ 統合開発環境やデバッガなどのツールも活用
とにかく原則として頭を使わないこと

デバッグ (プログラミング)とは「ここまでは絶対大丈夫」という砦を築いていく作業

45/52

デバッガの利用 (1/5)
デバッガとは？
デバッグの支援ツール
デバッグに便利な機能がたくさん含まれている
ほとんどの統合環境(IDE)にはデバッグ支援機能が含まれる
コマンドラインツールだと gdb が有名

何ができるか？
・ブレークポイント・ステップ実行・スタックトレース
・変数監視
・その他非常に多機能

46/52

デバッガの利用 (2/5)

47/52

変数の書き換えタイミングを知りたい
変数の値がおかしくなった (assertにひっかかった)でもソースのどこでその変数を書き換えているかわからない(特にポインタやグローバル変数を多用したコードなどで発生)
グローバル変数a (常に10未満であるはず)
int a = 0;
int main() {func1();
func2();
func3();
func4();
このどこかでaを変な風にいじっているfunc5();
func6();
func7();
func8();
func9();
assert(a < 10);
ここでassertに失敗している}ウォッチポイント(watch)を使う

デバッガの利用 (3/5)

48/52

1. プログラムを「-g」オプションつきでコンパイル
2. 実行ファイルを指定してgdbを起動
3. ウォッチポイントの指定（条件 a>=10)
4. 実行$ g++ -g test.cpp (1)$ gdb ./a.out(2)(gdb) watch a >=10 (3)Hardware watchpoint 1: a >=10(gdb) run(4)
Thread 2 hit Hardware watchpoint 1: a >=10Old value = false
New value = true
0x0000000100000cf8 in func5 () at test.cpp:99 void func5(){a = 15;}

test.cpp の 9行目にあるfunc5の関数内で問題の代入がされていることがわ
かったデバッガの利用 (4/5)

49/52

不正な引数による関数呼び出しを検出したい
void func(int a){assert(a < 10);// Do something}
int main(void){
func1();
func2();
func3();
func4();
func5();
func6();
func7();
func8();
func9();}

引数の値として a<10が想定されているAssertion failed: (a < 10), function func, file test.cpp, line 7.

不正な引数で呼ばれたことはわかるが、どこで不正な値が入ったかまではわからない
このどこかでfuncを不正な引数で呼んでいる

ブレークポイント(break)とバックトレース(bt)を使う

デバッガの利用 (5/5)

50/52

1. プログラムを「-g」オプションつきでコンパイル
2. 実行ファイルを指定してgdbを起動
3. funcにブレークポイントを指定
4. 先のブレークポイントに、条件(a>=10)追加
5. 実行 (a=11になっので止まる)
6. バックトレース(呼び出し履歴)の表示
7. 呼び出し元を表示(up)$ g++ -g test.cpp (1)$ gdb ./a.out(2)(gdb) break func (3)Breakpoint 1 at 0x100000ce1: file test.cpp, line 7.
(gdb) condition 1 a >= 10 (4)(gdb) run (5)Thread 2 hit Breakpoint 1, func (a=11) at test.cpp:7
7 assert(a < 10);(gdb) bt (6)#0 func (a=11) at test.cpp:7#1 0x0000000100000cb1 in func7 () at test.hpp:8#2 0x0000000100000d39 in main () at test.cpp:19
func7の呼び出し方がまずいことがわかる(gdb) up (7)#1 0x0000000100000cb1 in func7 () at test.hpp:8
8 void func7(void){func(11);}
test.hppの8行目、func7内で、func(11)と呼んでいることがわかった

デバッガのまとめ
ウォッチポイントにより、変数がいつ誰によって書き換えられたか検出できる
バックトレースにより、ある関数がどういう履歴で呼び出されたのかをたどることができる

実行中の変数の値を逐一チェックできる
・ デバッガを使うとプログラムを「生きたまま」解析できる
・ print文デバッグ→静的な解析
使い方を覚えるまでの学習コストは高い
しかし、プログラムを日常的に組むなら「必ず」元が取れる

51/52

今日のまとめ頭を使うなツールを使えバージョン管理システムを使う
デバッグのコストを意識する→ バグを入れないプログラミング→ すばやくデバッグするコツ

次回は高速化、チューニング、並列化のコツを扱います

52/52