スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

大小比較の関数の最適化

大小比較して1,0,-1のいずれかを返す関数の最適化ネタ。

2つの整数を比較して、大きければ1、小さければ-1、同じなら0を返す関数を下記のように書いていたのだけど

某所で下記のようなコードをみつけて、わざわざこんな書き方するからには速度が違う筈、とか考えて速度比較してみた。

VisualStudio2008 + -O2 + Corei7 で実験したところ後者のほうが3割ぐらい速かった。
後者の書き方だとset??ていう条件レジスタを見て1or0をセットする命令が使われてジャンプが消えるのが原因のよう。
この命令boolの仕様(0or1をセット)と親和性が高いなーと思った。むしろこの命令があるからboolの仕様がこうなった?条件レジスタを見てあれこれしてくれるのはARMだけだと思ってた。

でも場合によっては美味しくない書き方である気がする。大抵の場合、比較だけじゃ終わらずに比較結果に基づいた後に続くコードがそれぞれある筈。
・比較結果(1,0,-1)をメモリに書き込んで終わる場合
・比較結果を何らかの算術演算に使用する(=結果にかかわらず後に続くコードが同じ)場合
・比較用の関数が外部関数として定義しなくちゃいけなくて(関数ポインタで参照できなければいけないとか)比較関数の速度だけが問われる場合
とかなら後者のほうが美味しいんだろうけど、上記のようなパターンに当てはまらず、比較の後に実行されるコードが異なるパターンだと素直にifで書いたほうが、そっちへ直接ジャンプできるぶん速くなりそう。

前者のアセンブラ

後者のアセンブラ

スポンサーサイト

赤黒木 高速化版

以前の赤黒木の高速化版。15~25%ぐらい速い。
高速化版といってもアルゴリズムの変更ではなく余分なストアとロードを削っただけ。

SetParentは色を読み込むためにロードが発生し結構重い。
色が確定されている状況だとストアだけにできる。
また、値を上書きすることが分かっている場合、先に行う方のストアはいらないので削ることができる。

rbtree.h


rbtree.cpp

C++での簡易コルーチン(2)

BEGIN~ENDで囲む、というのが前時代的でいやだったのでboostっぽく書き直し。
コルーチンとか使ってる時点であまり気にすることでもないのだけど、前のと比べて比較と分岐が多分1個ずつ増える。あとforやifで囲っちゃってるので、ブロックの外と内をまたぐような最適化がかからなくなるかも。

C++での簡易コルーチン

switch-caseを利用した、C++での簡易コルーチン。
元ネタはboostのcoroutine.hpp
とか書くと、func1() は 1,2,3,0,0… を順次返す関数に、func2()はa,b,c,a,b,c,…を出力し続ける関数になる。
ローカル変数の保持はできないので、本物(?)のコルーチンと比べて使い勝手が悪いけど
・ポータビリティがある
switch-caseしか使ってないので、インラインアセンブラが使えないorコンテキストにアクセスする手段が無いような環境でも使える。
・コンテキストの保存に4byte(sizeof(int))しか食わない
というメリットがある。
例外やネストに未対応。
__COUNTER__を使うことを試みたり、___base___を減算しているのは、0から始まる連続した数値によるcaseのほうがコンパイラによる最適化が期待できる為。
例外で抜け、再度突入した場合は前回の状態からスタートしてしまう。
intを状態の保存に使っているけど、これをclassに変えて、デストラクタで値を操作するようにすれば、例外で抜けた場合にも対応できる。

何に使えるかというと、たとえばある非同期処理があって、その非同期処理の終了がコールバックで帰ってくる、なんてときに1関数内に連続して処理を記述できるのでソースコードの見通しがかなり良くなる。
非同期処理に限らず、逐次的な処理と、その逐次的な処理と処理の間に別の処理を挟む必要があるものに使える。
下記は、処理A->非同期処理->処理B と書いた場合の例。普通に書いた場合だと処理の数が増えたり分岐が複雑になると、関数&コールバックが増えすぎてgotoだらけのヤバイコードと大差ないものになったりする。

普通に書いた場合:コルーチン使った場合:

FixedAllocator メモ

・std::vector<> を使っている実装がある
良いことが何も無い。
 確保に失敗したら例外がでる&リカバリー不可。
 std::vectorのバッファは寿命がかなり長くなったりするので(コンソールだと)メモリ断片化の原因になる。
 OSのメモリ確保関数の呼び出し回数が増える

・ブロックにチャンクの情報をつける
ブロックの手前か後ろにチャンクのポインタをつけてやるとFreeでのチャンク検索が不要になる。
その代わりメモリ使用量がかなり増える。例えば 8byte のブロックにポインタを1個つけると50%の増加になる。
ほかにもブロックのサイズとアライメントを 16byte にしたい場合、余計なポインタを1個つけるとアライメントを保つためにパティングを入れる羽目になりメモリ消費量が倍になる。

・チャンクの初期化
最初にフリーリストでブロックを繋いでしまうという方法以外にも、確保時にチャンクからブロックを1個ずつ切り崩していくという方法がある。初期化のコストが減る代わりに、何処まで切り崩したかを保持しておかなければならない、切崩しが可能かどうかを判定しなければならないなど、少しだけ煩雑になる。doom3のidHeapの小さいブロックの確保がこの方法だった。
検索フォーム
ユーザータグ

ICPC 2009 国内予選 ゲームプログラミング 

カテゴリ
最新記事
月別アーカイブ
最新コメント
最新トラックバック
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。