Swaptimizationでmove先取り？その２

続きです。

vectorのresize時に各要素についてコピー操作が発生すると前回書きました。

T* newarea = new T[newsize];
for ( size_t i = 0 ; i < oldsize ; ++i ) {
　newarea[i] = area[i]; // コピー操作
}
delete [] area;
area = newarea;

これをswapにするとこうなります。

T* newarea = new T[newsize];
for ( size_t i = 0 ; i < oldsize ; ++i ) {
　std::swap(newarea[i], area[i]); // swap操作
}
delete [] area;
area = newarea;

新領域(newarea)の各要素は、デフォルトコンストラクタで作成されていますから、最初の確保時点では中身はデフォルト状態です。

これを旧領域の各要素とswapしていくので、結局、新領域の各要素には旧要素の各要素が入り、旧要素の各要素はデフォルト状態になります。

swapでmoveができそうです！

さて、問題は、これを vector::resize() にやってもらう方法です。vectorは当然ながらコピー方式で実装されています。 vector<MyClass> とやったときには swap 方式の resize を使って欲しいのです・・・

(1)stlのヘッダファイルを書き換える・・・やりたくない
(2)自分用vectorクラスを作成する・・・やりたくない（STLのコンテナクラスの要件を満たすのはのは難易度がとても高いです！）

さてどうしたものか。。。と、VC++(VS2005SP1)のvectorヘッダファイルを見ると、こんな定義があります。ま、これを見つけたからこんなエントリ書いてるんですけども。

　// vector implements a performant swap
template <class _Ty, class _Ax>
　class _Move_operation_category<vector<_Ty, _Ax> >
　{
　public:
　　typedef _Swap_move_tag _Move_cat;
　};

これはなにやらキナクサイですぞ・・・！

結論を言いますと、この _Move_operation_category クラスを特殊化し、_Swap_move_tag を _Move_cat として typedef すると、いくつかのコンテナクラスは、moveで済む場合にswapを呼び出すようになります。イヤッホウ！

swapによる最適化だから「Swaptimization」と呼んでいるわけですね！

適用して意味のあるケースを調べたのですが、VS2005 SP1では、vector の resize で領域を再確保したときだけでした。もうちょっとあるかと思ったんですけどね。

ということで、現状では、vectorに直接突っ込むクラスが以下のようなものの場合、「swap使って移動してね」宣言しておくとよさそうです。

デカいメモリを動的に確保し、コピー操作ではそれらのコピーが行われる

メンバ変数にデカいコンテナを持つ(vector, list, map, basic_string, etc)

メンバが全てPOD(intとか)で、コピーがmemcpyで済む場合は、swapでやるとかえって遅くなるかもしれません。swapを要素数だけ呼ぶより、全体をmemcpyするほうがおそらく早いでしょう。

本当はここでベンチマークするといいんですけどね・・・

しかし、上記のようなテンプレート（タグ？）の宣言がなくても、swapがあれば勝手にやってよさそうなモンですけどねえ。なぜこのようなまどろっこしい事態になっているのか・・・あんまり書くとボロが出そうなのでやめておきます。

こんなところで。

---

注意１

この仕組みはドキュメント化されていません。また、私の理解不足や、実装の不備などにより不都合があるかもしれません。使用は自己責任でオネガイシマス。

この機構は標準化されたものではありません。今のところVC専用のようです。アンダースコアで始まってますからね・・・

VCの2005と2008にはあるようですが、継続的にサポートされるかどうかは分かりません。

---

注意２

要素型についてのstd::swapは、自分で特殊化したものを定義しておく必要があります。こんな感じです。

namespace std {
　inline void swap(MyClass& Left, MyClass& Right) {
　　// 各メンバ変数についてstd::swapを呼ぶか、独自の効率のよいswap処理を書く
　}
}

vector, list, basic_stringなどの標準ライブラリに含まれるタイプについてはあらかじめswapが定義されていますので、通常は各メンバについてstd::swapを呼ぶだけでよいはずです。

---

注意３

_Move_operation_category の特殊化は、おそらく、std名前空間内で行わないとマズいと思います。理由をシャキっと説明できるとカッコイイのですが、ごめんなさいできません。