雑記/2009-12-15

2009-12-15[火] ソートについて２

test1　補足

やねう版の結果がちょっと気になったので、手元ですぐ動くvc以外の コンパイラでも試してみた。
mingw32-gcc(3.4.5, 4.4.0TDP-1), dmc8.51(beta), open watcom 1.8, bcc5.82(フリーのTurboC++) あたり. (手元に残っていたものなので、最新版というわけでない)

プログラムのほうも時間計測の関数変えたり結果出力編集するの面倒だったので若干修正.
(ソース:sort_test1.cpp)

実行環境は athron64x2 5200+ 8GB(Vista64)環境.

実行結果は 1回目、 2回目

(だいたい似たようなもんだけれど、それなりに誤差があるので雰囲気見るために)
(あと表にはしてないけれどvcは2003,2010β2ともvc2008と同様の結果だった)

やねう版挿入ソートについては、mingw-gcc,bccの場合は効果があるよう. 他はどちらともいえない感じ。 このへんは、このテストの偶然の部分が多そうなので判別付かず.
どちらかというと gcc4.4.0 のinsert sortの結果が抜き出て悪い..これは コンパイラのバージョン上がれば直る?(駄目?). 3.4.5のほうは素直な結果に思える.

さらに quick sort の一部として使った場合の結果は、微妙.
傾向は現れてそうな感じもあるけどひっくり返ることあるし、そもそも測定誤差の振れ幅を思うと気にしても仕方ないレベルかもで.

でもまあ、基本どんぐりの背比べ、だけどよくなるコンパイラもある、んだから、汎用的に書く場合は やねう版 でいいかも、と。

（下手な書き方してでっかい要素をそのままソートする場合にはやねう版のほうが有利な気もするし）

※ と結論にしたけれど、後のtest2～は test1補足を試す前に調査してたのでやねう版になってません
※追記: こっちで結局結論変えてしまった.

ついでに std::sort。 gccやwatcomだと他の結果がいまいちのことがあっても 付属stlのstd::sortは速いので、 基本的には付属のを使うのが吉のよう. vcのは若干、bccのは結構、遅いけれど...

bccについては使ったのは数年前のもので最新じゃないし、 borlandのc++はその時々に付属するstl(の元)が変わったりするので… てみたらdinkumwareだった(VCと同じ元ネタ)...orz

※追記: std::sortの実装は単純なquick+挿入なだけじゃなくスタック溢れ対策?もあるよう.

前回もちょこっと書いたquick sortの10000000個時の時間が極端に悪くなっている件はvcだけでなく他のコンパイラでも同様のよう. スタック拡張とか何か極端なことが起こったのかとも思うけどわからず. このCソースバージョンの元にしたC++テンプレートバージョンでは10000000個実行しても正常な時間だったので、深入りしないで放置中.

※追記: vcのコンパイルオプションが不味く、スタック等のチェックルーチンが結構生成されていた. (関数分割や分岐が多いと不利だった模様). チェックを生成しない設定でコンパイルしたら、 結論がかわるほどの大きな違いはなかったけれど、 std::sort等ややねう版の結果も心持よくなったような気も.

test2　引数の数の違いの影響

関数呼び出しオーバーヘッドが性能に影響する、状況だろうから、 じゃあ、2引数版(<専用) と 3引数版（比較ファンクタ指定） でどれくらいの差がでるか、と思い、試した.（引数の数というより、ループの最内側で使われる引数で渡された'比較'が、ちゃんインライン展開されているや否や）

(ソース:sort_test2.cpp)

cでなくc++のテンプレートで実装. std::sortに引数をあわせている. また quick sort とかいているけど実際には挿入ソートを使ったバージョン. (以後単にquick sortと書いていても同様)

vcでの結果(単位:μ秒)

他のコンパイラもだいたい同様の傾向.

引数が2個か3個かの違いは、(ちゃんとオプティマイズされてたら)気になるような 差は見受けられず.
(オプティマイズ無しだと当然2引数のほうが速くなる)

てことで、実体つくるなら3引数版をつくってそれを呼び出す2引数版を作る、で よいのだろう.

表の下２つは、次のテストの前準備として軽く確認実行してみたもの.
bidiとなっているのは、引数として random iterator でなく bidirectional iterator を受け取れるようにしたバージョン（ようは std::list をソートできるようにしたもの).

イテレータの大小チェック代わりにカウンタを追加してるため、大きくはないけれど若干遅くなっているのは現れている模様.

test3　std::listのソート

(追記: マージソート失念して間抜けなことしてます..orz)

std::list のソートのテスト. 比較のため、

• std::vectorをソート
• std::listをquick_sort|bidi版でソート
• std::list.sort()でソート
• listの要素へのポインタのvectorをつくってそれをソート

してみた。
（ソース:sort_test3.cpp） 　(コンパイルはvc2008)

SmpClass版(mallocポインタやstd::vectorを持つ適当なクラス) (単位:μ秒)

std::string版

int版

基本的には SmpClass版の結果が、実使用に近いものだと思う.

で、みてのとおり、std::list でソートしたくなったら、

　std::list のメンバーの sort() を使う

という当たり前の結論.

intやdoubleのような小さい要素で少量のときは逆転してるけど、 そもそも個数がn個程度と限定されているならばlistでなくvectorあたりでよく.

無理に bidirectional iterator を受け取れる quick sort 作ってまで やることじゃない、と.

あと、そのものstd::list自体のソートが必要なく、 途中の処理として整列された順番でデータ舐めたいだけならば、 ４つ目のように、 要素へのポインタを集めてそれをソートして使うのが吉かも.

test4　大きめのオブジェクトのソート、スマートポインタのソート

普通は、大きめのオブジェクトの実体を直接ソートしない。しないですむように作る。
　整列状態で処理する箇所用に別途ポインタ配列を作ってそれをソート、
という感じ。

もっとも、大きめのオブジェクトはポインタなりハンドルなりで扱い そのまま管理/やりとりすることはないだろうで、 c++だとスマートポインタの類による管理も増えている.

じゃあスマートポインタのソートはどう？ってことで、試した.
（ソース：sort_test4.cpp）

以下 SmpClass (mallocポインタ,std::vectorメンバー有り)の結果(単位μ秒)

vc2008版(64バイト)

mingw32-gcc(4.4.0)版(56バイト)

上から順に.

• 本体のソートが不要であれば、やっぱりポインタの配列作ってソートしちまうのが一番安そう.
• 実体の直接ソートは桁違いに時間を食うはめに.
• 一旦ポインタ配列ソートしてからだと結構ましになる. でもポインタだけの管理にくらべれば桁がやっぱり大きい.
• c++0xで入る予定のstd::shared_ptrの場合. 実体にくらべ小さいとは言え、生のポインタにくらべれば複雑なので、実装方法次第だろうけれど、この例ではちょっと気になる程度のペナルティが発生している感じ.
• boost::intrusive_ptrを使った例. 生のポインタにくらべ時間は数割増といった感じで、思ったよりもペナルティは少ない感じ.
  10,20個程度だとポインタ配列を作るコストのほうが高くなることもあるのか、intrusive_ptr直ソートのほうが速くなることもあるよう.
• boost::intrusive_ptrで管理しているものを、一旦生のポインタ配列を作ってソートし、その結果を元に返す例. 一定以上ソートするならば intrusive_ptr のままよりもこのほうが速い.

shared_ptrはいろいろ便利だけれど、やっぱりその分実行時コストがかかってしまう。 それが気にならない箇所ならいいけれど、 ソートのような場合は考えたほうがよさそう.

intrusive_ptrは、ポイント先になるクラス側に参照カウンタ処理が必要となり、 shared_ptrより使い勝手は落ちるけれど、 参照カウンタの処理自体は shared_ptr よりも素直な状態なので、 実行時コストは小さい.

で intrusive_ptr のほうは、ソート済の生ポインタをも一度intrusive_ptrに することができる(もちろん、このへん、操作をあやまると参照カウンタ管理を 破綻しかねないので注意深く...)が、 shared_ptrは生ポインタ化してソートした結果を元のshared_ptrに戻す方法が なさそう. (shared_ptrの指す先でなくshared_ptr自体のアドレスでソートすればだが不本意)

追記:比較条件が単純でソートキーが値一つですむようならば、 ポインタのみの配列でなくソートキーとポインタのペアの配列を ソートしたほうが速くなりやすいと思われる(test5)

ソース＆実行ファイル

とりあえず、今回のソース等を固めたもの.

[download]