Mersenne Twisterのライブラリ作ってたんだけどな･･･
Mersenne Twister のライブラリ作っていたのに知らぬ間にRed Black Treeのライブラリを作っていました。
なぜか！？
それはSSEを使うためのmallocで確保したmemoryを16byteにalignするライブラリを作ろうとしていた。
offset計算でインクリメントとかされて汚されてしまったポインタでも上手く開放できるようにするライブラリを作るためでその為にはすでにmalloc済みのメモリの保存領域とその他の情報を保存するコンテナ機構が必要だった。*1
なのでここは一つSTLPortにも採用されているRed Black Tree*2をC言語で自分好みに実装して見ようと思った次第だ。
で、どうにかこうにか移植が完了したのでちょっと性能テストしてみた。
ranking_tiemr / clock type : QueryPerformanceClock / compile mode : DEBUG
1 / red black tree insert / 10731
2 / STLport red black tree insert / 30380
3 / STLport red black tree delete / 43562
4 / red black tree delete / 65766
私の組んだ奴はdeletingが遅いし、Releaseモードにして最適化するとSTLPortはなかなか速いし･･･。
ranking_tiemr / clock type : QueryPerformanceClock / compile mode : RELEASE
1 / red black tree insert / 7738
2 / STLport red black tree insert / 8721
3 / STLport red black tree delete / 31770
4 / red black tree delete / 63972
今度Up予定のdkutil_cにdkcRedBlackTreeとしてぶち込む予定なのでもうちょっとお待ちを･･･
そういえば、このコンテナを使うとメモリリークチェックライブラリも組めそうだ。
追記：STLportでのテスト環境がちょっと不公平だったので公平になるようにしてテストしてみた結果。
ヨッシャ！
ranking_tiemr / clock type : QueryPerformanceClock / compile mode : RELEASE
1 / red black tree insert / 7276
2 / STLport red black tree insert / 22908
3 / red black tree delete / 64269
4 / STLport red black tree delete / 79985
*1:いまさらながらこれは無駄な機構だと思える。
