C や C++ でプログラムの書いたことのある多くの人は、「プログラムを高速化したいけれど、どこが一番のボトルネックか分からない」とか、「メモリリークがあるようだけれど、どこで発生しているか分からない」といった問題で苦しめられた経験が一度くらいはあると思います。もちろん、こうした問題の解決策として、アドホックにプログラムをチューニングしたり、目でプログラムを追ってメモリリークの発生箇所を突き詰めることも可能ですが、時間がかかってしまうことが多々ありますし、あまり楽しい作業でもないと思います。
そんなときに役に立つのが、Performance tools です。具体的には、このソフトウェアは以下の 4 つのツールで構成されています。
TCMalloc: マルチスレッドプログラムに適した、高速な malloc の実装 Heap Checker: メモリリークを検出するライブラリ Heap Profiler: 各関数におけるメモリの使用量を計測・表示するツール CPU Profiler: サンプリングによって各関数の実行時間を計測・表示するツール これらのツールを使って、プログラムの高速化やバグの検出などを行なうことができます。例えば、Heap Profiler を使えば、プログラム中のどこでどれだけメモリが使用されているかを、簡単に把握することができます。下の図のような、ノードが各関数の中で確保されているメモリの量を、エッジが関数の呼び出し関係を表す有向グラフとして、メモリの使用状況を可視化することができます。
同様に、CPU Profiler を使えば以下のような重みつきコールグラフを出力することができます。このグラフを見ながらプログラム中のボトルネックを特定するといったこともできるでしょう。
Performance toolsの使い方
使い方は簡単です。基本的には、どのツールもTCMalloc のライブラリをリンクするだけで使用する事ができ、 ソースコードの変更は必要はありません。例えば gcc を使ってプログラムをコンパイルしている場合でしたら、"-ltcmalloc" をコンパイルオプションに付け加えるだけで、 TCMalloc の提供する malloc/free がプログラム中で呼ばれるようになります。例えば、
gcc [...] -ltcmalloc
とするだけです。また、Heap Profiler であれば、
gcc [...] -o myprogram -ltcmalloc HEAPPROFILE=/tmp/profile ./myprogram
と実行することで、メモリの使用状況のログを取ることができます。この場合ですと、定期的に(例えば 1 GB メモリが割り当てられる度に)、/tmp 以下に profile.0001.heap、...、profile.0100.heapといったログファイルが生成されます。このログファイルを以下のように pprof に与えると、先に述べたようなグラフが表示されます。
pprof --gv myprogram profile.0100.heap
TCMalloc
以上に述べたツールの中で、ここでは特に、TCMalloc (Thread-Caching Malloc) について少し詳しく解説します。これは高速な malloc の実装で、例えば glibc 2.3 malloc (ptmalloc2) との比較で、
ptmalloc2 で(サイズの小さなオブジェクトの)malloc/free に約 300 ナノ秒かかったところ、TCMalloc では約 50 ナノ秒しかかからなかったという実験結果があります(2.8 GHz の P4 上での測定)。
TCMalloc は、大きく言って 2 つの特長を持ちます。1 つは、マルチスレッドプログラムにおけるロックの競合を削減しているという点です。サイズの小さなオブジェクト (<= 32K) の malloc/free においては、ロックの競合はほとんど発生せず、大きなオブジェクトにおいても、細粒度で効率的な spin lock を用いるようにしています。もう 1 つの特長は、サイズの小さなオブジェクトをメモリ効率の良い方法で表現するということです。単純な malloc/free の実装だと、各オブジェクトごとに(例えば 4 バイトの)ヘッダを用意し、そこにオブジェクトのサイズなどの情報を格納しておく必要があります。これは、オブジェクト解放時に、そのオブジェクトのアドレスから解放すべきメモリサイズを計算するためです。それに対してTCMalloc では、例えば 8 バイトのオブジェクトを N 個確保するのに約 8N * 1.01 バイトしか必要としません。
それでは、TCMalloc がどう実装されているかについて、簡単に説明します。TCMalloc によって管理されるメモリは、各スレッドごとに用意された「スレッドキャッシュ」と、全スレッドによって共有される「中央ヒープ」から成ります。基本的には、サイズが 32K 以下のオブジェクトはスレッドキャッシュ上に確保され、それより大きなオブジェクトは中央ヒープに確保されます。スレッドキャッシュ上ではロックを必要とせずにオブジェクトを確保することができるため、高速化が図れます。
スレッドキャッシュは、各オブジェクトをそのサイズに応じて「クラス」に分類することによって、効率的なメモリ管理を実現しています。例えば、サイズが 1 バイトから 8 バイトのオブジェクトはクラス 0 に、サイズが 9 バイトから 16 バイトのオブジェクトはクラス 1 に分類されます。そして、このクラスごとに、空きオブジェクトを管理するための連結リストが用意されています。
例えば、サイズが 14 バイトのオブジェクトを確保する際には、クラス 1 の空きリストから先頭の要素を取り出して、それを使うようにします。また、オブジェクトを解放する際には、そのオブジェクトのアドレス(ページ番号)から、クラスを計算できるようにしておきます。こうすることで、各オブジェクトごとにヘッダを用意して、サイズを記憶しておく必要がなくなります。
まとめ
Google が公開している Performance tools、特に TCMalloc について説明しました。もし少しでも興味を持った方は、是非使ってみてください。より詳しい情報を知りたい方は、
Wiki(英語) や
ソースコード などを参照して下さい。
2009年 5 月 11 日 Posted by Google Performance tools team Google が Google Code でオープンソースとして公開しているソフトウェアの解説シリーズ(前回のエントリ )の第 4 回です。今回は Performance tools について紹介します。この Performance tools は、実際に Google 社内で広く使われており、特に、C++ でテンプレートを使用するマルチスレッドアプリケーションを開発する際に役立ちます。Linux 環境を主に対象としています。Performance tools とは?
C や C++ でプログラムの書いたことのある多くの人は、「プログラムを高速化したいけれど、どこが一番のボトルネックか分からない」とか、「メモリリークがあるようだけれど、どこで発生しているか分からない」といった問題で苦しめられた経験が一度くらいはあると思います。もちろん、こうした問題の解決策として、アドホックにプログラムをチューニングしたり、目でプログラムを追ってメモリリークの発生箇所を突き詰めることも可能ですが、時間がかかってしまうことが多々ありますし、あまり楽しい作業でもないと思います。 そんなときに役に立つのが、Performance tools です。具体的には、このソフトウェアは以下の 4 つのツールで構成されています。TCMalloc: マルチスレッドプログラムに適した、高速な malloc の実装 Heap Checker: メモリリークを検出するライブラリ Heap Profiler: 各関数におけるメモリの使用量を計測・表示するツール CPU Profiler: サンプリングによって各関数の実行時間を計測・表示するツール これらのツールを使って、プログラムの高速化やバグの検出などを行なうことができます。例えば、Heap Profiler を使えば、プログラム中のどこでどれだけメモリが使用されているかを、簡単に把握することができます。下の図のような、ノードが各関数の中で確保されているメモリの量を、エッジが関数の呼び出し関係を表す有向グラフとして、メモリの使用状況を可視化することができます。 同様に、CPU Profiler を使えば以下のような重みつきコールグラフを出力することができます。このグラフを見ながらプログラム中のボトルネックを特定するといったこともできるでしょう。Performance toolsの使い方
使い方は簡単です。基本的には、どのツールもTCMalloc のライブラリをリンクするだけで使用する事ができ、 ソースコードの変更は必要はありません。例えば gcc を使ってプログラムをコンパイルしている場合でしたら、"-ltcmalloc" をコンパイルオプションに付け加えるだけで、 TCMalloc の提供する malloc/free がプログラム中で呼ばれるようになります。例えば、gcc [...] -ltcmalloc
とするだけです。また、Heap Profiler であれば、gcc [...] -o myprogram -ltcmalloc HEAPPROFILE=/tmp/profile ./myprogram
と実行することで、メモリの使用状況のログを取ることができます。この場合ですと、定期的に(例えば 1 GB メモリが割り当てられる度に)、/tmp 以下に profile.0001.heap、...、profile.0100.heapといったログファイルが生成されます。このログファイルを以下のように pprof に与えると、先に述べたようなグラフが表示されます。pprof --gv myprogram profile.0100.heap
TCMalloc
以上に述べたツールの中で、ここでは特に、TCMalloc (Thread-Caching Malloc) について少し詳しく解説します。これは高速な malloc の実装で、例えば glibc 2.3 malloc (ptmalloc2) との比較で、ptmalloc2 で(サイズの小さなオブジェクトの)malloc/free に約 300 ナノ秒かかったところ、TCMalloc では約 50 ナノ秒しかかからなかったという実験結果があります(2.8 GHz の P4 上での測定)。 TCMalloc は、大きく言って 2 つの特長を持ちます。1 つは、マルチスレッドプログラムにおけるロックの競合を削減しているという点です。サイズの小さなオブジェクト (<= 32K) の malloc/free においては、ロックの競合はほとんど発生せず、大きなオブジェクトにおいても、細粒度で効率的な spin lock を用いるようにしています。もう 1 つの特長は、サイズの小さなオブジェクトをメモリ効率の良い方法で表現するということです。単純な malloc/free の実装だと、各オブジェクトごとに(例えば 4 バイトの)ヘッダを用意し、そこにオブジェクトのサイズなどの情報を格納しておく必要があります。これは、オブジェクト解放時に、そのオブジェクトのアドレスから解放すべきメモリサイズを計算するためです。それに対してTCMalloc では、例えば 8 バイトのオブジェクトを N 個確保するのに約 8N * 1.01 バイトしか必要としません。 それでは、TCMalloc がどう実装されているかについて、簡単に説明します。TCMalloc によって管理されるメモリは、各スレッドごとに用意された「スレッドキャッシュ」と、全スレッドによって共有される「中央ヒープ」から成ります。基本的には、サイズが 32K 以下のオブジェクトはスレッドキャッシュ上に確保され、それより大きなオブジェクトは中央ヒープに確保されます。スレッドキャッシュ上ではロックを必要とせずにオブジェクトを確保することができるため、高速化が図れます。 スレッドキャッシュは、各オブジェクトをそのサイズに応じて「クラス」に分類することによって、効率的なメモリ管理を実現しています。例えば、サイズが 1 バイトから 8 バイトのオブジェクトはクラス 0 に、サイズが 9 バイトから 16 バイトのオブジェクトはクラス 1 に分類されます。そして、このクラスごとに、空きオブジェクトを管理するための連結リストが用意されています。 例えば、サイズが 14 バイトのオブジェクトを確保する際には、クラス 1 の空きリストから先頭の要素を取り出して、それを使うようにします。また、オブジェクトを解放する際には、そのオブジェクトのアドレス(ページ番号)から、クラスを計算できるようにしておきます。こうすることで、各オブジェクトごとにヘッダを用意して、サイズを記憶しておく必要がなくなります。まとめ
Google が公開している Performance tools、特に TCMalloc について説明しました。もし少しでも興味を持った方は、是非使ってみてください。より詳しい情報を知りたい方は、Wiki(英語) やソースコード などを参照して下さい。