Smart Pointer Timings

2000年1月の後半に、Mark Borgerding は boost にスマートポインタの新しい設計を提案した。 それは、 与えられた生ポインタを共有する全てのスマートポインタのインスタンスを、 双方向リンクリスト で結合することによって所有権を共有するというものである。 現在のバージョンの boost::shared_ptr では、 最初の構築の際に参照カウントをヒープに割り当てるコストが発生するが、 Mark Borgerding が提案したスマートポインタでは、そのコストを回避することが可能となる。 もちろん、何の代償もなしにこのメリットを得られるということはなく、 この新しいスマートポインタは、コピーの際にサイズが増加し、より大きなコストが生じる。 boost のメーリングリストでの議論と、このページで述べる幾つかのテストが、 現在及び将来のスマートポインタの実装戦略に関するガイドとなるだろう。

Dave Abrahams と Gavin Collings、 Greg Colvin、 Beman Dawes によるテストコードと実験的な実装の最終バージョンが .zip 形式で ここ に置いてある。

Description

2つのテストが実行された: そのうちの一つ目は、2種類の基本的な単独の操作における速度を測ることを目的とするテストである:

1. 生ポインタからの最初のスマートポインタ構築。
2. コピー構築と代入(assignment)を半分ずつ含めた、償却的なコピー操作 - 平均的な使用法を反映したもの。

2つ目のテストは、 より実際的な使用法を考慮し、 様々なスマートポインタで満たされたベクタ(vector)とリスト(list)に対して、 ソート及びフィル(fill)アルゴリズムを適用したときの速度を測るというものであった。

次に挙げる 5 種類のスマートポインタの実装戦略がテストされた:

1. ヒープに割り当てられた参照カウンタによりポインタをカウントするもの。 以後、simple counted と呼ぶ。
2. 参照カウンタ専用のアロケータを利用してポインタをカウントするもの。 - special counted と呼ぶ。
3. 埋め込み参照カウンタを用いてポインタをカウントするもの。 - intrusive と呼ぶ。
4. 上述されたリンクリストで結合されたポインタを用いるもの。 - linked と呼ぶ。
5. ポインタの循環のガベージコレクションとウィークポインタを提供し、 アロケーションのために std::deque を用いた循環ポインタを使うもの。 - cyclic と呼ぶ。

2つのコンパイラにて:

1. MSVC 6.0 service pack 3 、デフォルトの最適化レベル (/O2 - 速度で最適化、 inline 属性が明示されている物を除きクラス本体定義の外で定義された関数をインライン展開しない。)
2. gcc 2.95.2 完全な最適化 (-O3 -DNDEBUG).

更に、生成されたポインタのサイズ (taking into account struct alignment) が比較された。 主に MSVC にて生成されたアセンブラコードを手作業で調べることにより - 関数がインライン展開される為 - ポインタのサイズを調べた

全てのテストが Windows NT 4.0 がインストールされた PII-200 のPCで実行された。

Operation Timing Test Results

以下に示すグラフは、 デフォルトコンストラクションによるポインタの作成、 n 償却されるコピー演算、 ポインタの解放、 これら3つのテストの全体的な時間をナノ秒単位で表す。 スマートポインタに収められる生ポインタを割り当てる時間は含まないが、 その割り当て解除(解放)の時間は含むものとする。 生ポインタが指すクラスは特に目的を持たないクラスであるが、 埋め込み参照カウントを用いた共有ポインタのメリットを活かすために 埋め込み参照カウントを包含する。 比較のために、 消極的ポインタ (例えば、内包している生ポインタの獲得と解放に余分なオーバーヘッドが全く掛からないようなスマートポインタ) や生ポインタもテストに含めた。

上図のグラフにプロットされた各線に対して、近似直線を適合させることにより、以下の表が得られる。 この表は、それぞれのコンパイラでの初期化と償却コピー演算の結果を示している。 (ナノ秒単位、誤差は二つの標準偏差によって表現する) : -

MSVC

GCC

上記の時間には for each によるループのオーバーヘッドなども含まれることに注意しよう。 スマートポインタに対する演算のオーバーヘッドの純粋な時間は、 dumb または raw の項目の値を差し引くことで求められる。

Detail

このテストは、生ポインタを作成するループの繰り返しを含む。 それらの生ポインタは、(サイズ指定によって変化する)任意の数のスマートポインタの間で共有される。 サイズ指定の範囲は、近似直線を求める際に初期化とコピー演算の数と伴に一次の相関係数として利用される。 近似直線を求め、上で示したパフォーマンスのグラフを作成するために、スプレッドシートを用いた。

Container Test Results

現実のプログラムにおけるスマートポインタの動作の洞察を得るために、 このテストが考案された。 これは、標準コンテナをスマートポインタで満たし、ソートするというものである。

こちらのテストでスマートポインタに収められるポインタは、 プライベートなデータメンバを持つクラスを指す。 このクラスのプライベートなデータメンバは、デフォルトコンストラクタにより ランダムな値で初期化される。 この値は、その直ぐ後にソート比較テストに使われる。 このクラスはまた、 埋め込み参照カウントを用いた共有ポインタのメリットを活かすために 埋め込み参照カウントを包含する。

以下に示される時間はコンテナに格納された30万個のポインタに対する数値であり、 全て秒単位である。

GCC

MSVC

Code Size

以下に示すコードのサイズは MSVC によって生成されたコードを精査する事により測定された。 サイズは N / M / I の3つの数値の構成で表現され、 N / M / I はそれぞれ以下の意味を持つ:

• N は或る処理に含まれる命令の数を表す。
• M はコードのサイズをバイト単位で表す。
• I は生成されたコードがインライン展開されたかどうかを表す。I = inline, O = "outline"

コードの解析の中で、二つの小さなポイントが浮き彫りになった: -

• 関数のインライン展開はパフォーマンスに重大な影響を与える。
• MSVC では、 たった1つの "delete 0" 命令が、 関数呼び出しも含む11個のアセンブリ命令に展開された。 これは場合によると、余分な手作業のテストを挿入するのに匹敵するくらいの 大きなパフォーマンスの低下を招くかも知れない。

Data Size

以下に示されるスマートポインタのサイズはバイト単位で与えられる

Summary

計測結果の時間自体が、結論(summary)に相応しい: 埋め込みポインタ(intrusive)が他のスマートポインタよりも性能が良いことと、 ヒープに確保した参照カウントを用いるポインタ(simple counted) が他のスマートポインタの実装よりも性能が劣ることは明かである。 しかし、埋め込み型以外のスマートポインタの実装の中で最善の物を選択するとなると、 より用法に依存することになる。 少数しかコピーされないと予想される物は、 リンクリストを用いた実装のスマートポインタ(linked)が好ましいだろうし、 多量にコピーされるのであれば専用のアロケータを用いたスマートポインタ(special counted)の方が適しているだろう。 他に考慮される因子としては以下のものがある: -

• 償却的な実行時間に対立する、単一の処理の決定論的な時間。 アロケータに依存する幾つかの実装を考慮する。
• マルチスレッドでの同期性能。 リンクリストを用いるケースなどでは、 同期のための情報の伝達の実装を考慮する。

Revised 19 August 2001

(c) Copyright Gavin Collings 2000. Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.

Japanese Translation Copyright (C) 2003 Ryo Kobayashi.
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の 複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」 に提供されており、いかなる明示的、暗黙的保証も行わない。また、 いかなる目的に対しても、その利用が適していることを関知しない。