Valgrindでコード解析してみる

はじめに

テオ。弾薬が尽きた。このまま突入する、さらばだ。ヴァルハラで会おう。Wir sehen uns in Walhalla!
これは第二次世界大戦時のドイツ空軍のエースパイロット、ハインリヒ・エールラーの最後の言葉です。
北欧神話で戦死した人がラグナロク(終末の日)に備える場所とされるヴァルハラ。今日はそれにちなんで命名された解析ツールValgrindについて見ていきましょう。

申し遅れました。わたくしCADDiでコスト計算システムのバックエンドを担当している @kimu_di といいます。

こちらキャディAdvent Calendar 2020 17日目の記事となります。昨日は @yskeee000 の「KleinというProductについて」でした。

改めて、今回はValgrindという強力なコード解析・メモリデバッグツールについてお話します。
ここまで強力な解析ツールを使う必要はないことも多いですが、RustやC++を書く上で最後の最後のパフォーマンスの追い込みに力を発揮してくれること請け合いです。

改めてValgrindとは

普通、C++やRustで書いたプログラムはプロセッサに依存した実行可能ファイルへコンパイルされますね。Valgrindはそれを中間表現に変換し、それを再び機械語に翻訳し直して実行させるという手間を踏みます。パフォーマンスは低下しますが、中間表現を経由することで計測・解析・デバッグが容易になります。
ここにコードを追加することで様々なツールを機能させることが出来るようになっています。

よく使うツールをさらっとご紹介しましょう。

  • Memcheck
    初期化されていない・あるいは解放されたはずのメモリの使用、境界外への読み書き、メモリリークを検出するツール
  • Cachegrind
    キャッシュのプロファイラ。キャッシュのヒット率などを計測できる
  • Callgrind
    コールグラフの作成、ブランチ予測などのツール
  • Helgrind
    マルチスレッドのエラー検出ツール
  • Massif
    ヒーププロファイラ

導入

Ubuntuでは

$ sudo apt install valgrind

のように導入します。
ビジュアライザも入れましょう。

$ sudo apt install kcachegrind massif-visualizer

このあたりがあると幸せになれそうです。

kcachegrindでコールグラフを読み解く

まずはコールグラフを見てみましょう。

プログラムをvalgrindに食べさせながら実行します。

$ valgrind --tool=callgrind プログラム名 引数

Rustで開発している途中ならこうなるでしょう。

$ cargo build --relase
$ valgrind --tool=callgrind target/release/binary_name

まさか本番環境でdebug版を動かしていることはないでしょうから、リリースビルドを選ぶのを忘れないようにします。
そのあとvalgrindにプログラムを渡して実行ですね。

実行するたびにcallgrind.out.12345 のような名前でファイルが出力されます。lsコマンドで確認できると思います。
このファイルの中身をビジュアライザで見てみましょう。

$ kcachegrind callgrind.out.12345

これでツールが起動します。

このような画面が表示されましたね。

メニューバーには真新しいものはありませんが、View -> Cycle DetectionだけはOFFにしておくことをおすすめします。
この機能は再帰的な相互呼び出しをヒューリスティックに解析してコストを表示してくれるのですが、ONになっていると実際の関数が<Cycle1>のような計測結果に覆い隠されてしまいます。関数別の呼び出しコストを見たいので、OFFで良いでしょう。

左側がflat profileと呼ばれる領域で、ここにコールスタックのようなものを表示してくれます。実際にこのようなコールスタックがあるわけではないですが、現在の関数から見て呼び出す関数/呼び出される関数を上下に並べてコストが高い順に表示されます。

右側には視覚化された「ツリーマップ」やコールグラフ、呼び出し/呼び出される関数のリストが並びます。
Callerというのは、今扱っている関数を呼び出している親玉のこと、Calleeは今扱っている関数が呼び出す子分のことを指します。
また、CallGraphを選ぶと呼び出し階層をグラフ構造で表示してくれます。

この例ではripgrepというRust製の検索ツールをvalgrindで実行した結果を表示しています。
コールマップを見るとmain関数の中でばっくりと2つ大きな関数が占めていて、残りが小さめの関数で占められている事がわかります。
マップをクリックすると、それぞれの色分けされている領域がどの関数に対応しているかがわかります。

試しに押してみましょう。左側の大きな領域をクリックするとハイライトされますね。それは ignore::walk::WalkParallel::visit という関数で、すべての呼び出しのうち38%のコストを占めている事がわかります。

ダブルクリックするとコールマップが変わりました。

その関数の中に絞って表示してくれるというわけです。

このツールのソースコードを見れば、きっと重い実装であることが想像できますね。 crossbeamってなんでしょうと思って見てみると、並行プログラミングのライブラリです。つまり、これ自体にあまり意味はないですね。

なので、さらにその内側を見るとエイホ・コラシックという関数が見えます。これは文字列探索アルゴリズムの名前です。きっとこのあたりが処理の中核だと当たりをつけ、どれくらいのコストが掛かっているか、何を呼び出しているかがわかるでしょう。

massifでヒーププロファイリングを覗いてみる

ヒープとはご存知の通り、実行時に任意のタイミングで確保や解放ができるメモリ領域のことですね。
このプログラムがどれくらいのメモリを使うか探ってみましょう。

今度はmassifを使います。

$ valgrind --tool=massif --time-unit=B --stacks=yes プログラム名 引数

massif.out.23456 のようなファイルが出力されるので、これをビジュアライザに掛けます。

$ massif-visualizer massif.out.34567

例によってripgrepのメモリ消費を見てみました。

一目瞭然ですね。
右側でメモリ確保/解放の詳細を見ることができます。

今回はたいへん明確にメモリを使ったあと終了と同時に解放する右肩上がりのグラフになっていますね。

実務にて

業務にて、以上2つのツールを活用してコスト計算システムのコアのプロファイリングを行いました。
計算量の多く複雑なロジックを内包するコンポーネントだったのでボトルネックになっていることが予想されていましたが、意外にも、さほどメモリを消費せず、コールグラフを見るとメモリアロケーションが大半のコストを占めていたことが判明しました。 (残念ながらその結果は公開できないですが……。)

ボトルネックを探る手段としてたいへん強力な手段になった一方で、使い方がやや難しいといいますか、タバコに火を付けるのに火炎放射器を使うこともないですから、まずは簡単にミリ秒単位での出力から始めると良いでしょう(と、ボスからアドバイスを受けました) 通常のバックエンド開発としてはAPI単位で時間計測していくほうが遥かに簡単で効果的ですが、難解なアルゴリズムを用いたソフトウェア開発で力を発揮するかもしれません。

主にC++を書く方へ

valgrindの目玉ツールとしてmemcheckがあります。

$ valgrind --leak-check=full プログラム名

本来valgrindと言ったらコレがまっさきに出てくる機能です。主にメモリリークの検出に使われるものなのですが、Rustを普通に書いているとまず遭遇しないので……。まあ見ていきましょう。

メモリ解放忘れ

以下のようなコードで発生させてみます。

#include <iostream>

int main()
{
    int *p = new int;
    *p = 0;
    std::cout << *p << std::endl;
}

これをmemcheckに掛けると、 definitely lost: 確実に解放漏れがある、と怒られます。delete pを呼んでいないからですね。

未初期化

今度は *p=0 を消してみました。

#include <iostream>

int main()
{
    int *p = new int;
    std::cout << *p << std::endl;
    delete p;
}

Use of uninitialised value of ...と怒られますね。

二重解放

解放済みのポインタをもう一度解放してみます。

#include <iostream>

int main()
{
    int *p = new int;
    *p = 0;
    std::cout << *p << std::endl;
    delete p;
    delete p;
}

Invalid free() / delete / delete[] / realloc() と怒られました。そのとおり。

不正な読み込み

ポインタをずらして読んでみます。

#include <iostream>

int main()
{
    int *p = new int;
    *p = 0;
    std::cout << *(p + 1) << std::endl;
    delete p;
}

4つ分後ろ見てるよ、と怒られています。

不正な書き込み

最後です。初期化に続けて違う領域に書き込んでみます。

#include <iostream>

int main()
{
    int *p = new int;
    *p = 0;
    *(p + 1) = 0;
    std::cout << *p << std::endl;
    delete p;
}

Invalid write of ...と怒られますね。

memcheckまとめ

このように、厳格にメモリの使い方を指摘してくれますのでC++erの各位におかれましてはぜひお手元のプログラムを一度memcheckに掛けてみることをオススメします。 そして何よりも、メモリ安全なRustに切り替えることを考えると良いでしょう!

おわりに

Valgrindについて見てきました。 これであなたもプロファイリングマスターです。バイナリにビルドされているプログラムならたいてい解析できますので、お試しに身近なコマンドやプログラムを覗いてみてはいかがでしょうか。