Brynhildr

KeroRemote

リモートデスクトップエンジニアのブログ。

if文
ちょっと技術ネタを。Brynhildrの映像圧縮コーデックの処理にif文があります。ま、if文なんてどんなソースにもあると思いますけど。で、それがどーもなんかしっくりこず。サブルーチンなんですけどね。そーいや、あんまり聞かなくなりましたかね、サブルーチン。

どんなサブルーチンかと言いますと、数値の範囲を整えるタイプのやつです。変数に値が入っているんですが、本来は0から255の範囲で納めたいのですが、どーしてもマイナスの値とか255を超える値が返ってくるんですよね。

で、if文でマイナスだったら0に、255を超えてたら255に、てな処理を入れてるんですが、何箇所でも使うのでサブルーチン化しております。そんなサブルーチンの中身は、

cmp eax ,0
jns STEP_1
mov eax ,0
STEP_1:
cmp eax ,255
jb STEP_2
mov eax ,255
STEP_2:


てな感じですかね。実際はちょっと違うんですけど大体こんな感じです。eaxに値が入ってる感じです。でもなんかこー分岐せずにできないものかと床屋とか風呂とかで考えた結果、

mov dl,255
ror eax,8
mul dl
rol eax,8
or al,ah
rol eax,8
not al
and ah,al
ror eax,8


とゆー方法を考えました。同じくeaxに値が入ってる感じです。dlも使ってますけど。

だが、遅い!てか、長い!

なんかこー4ステップくらいでまとまらないものでしょーか。教えて分かる人。




8件のコメント ... ( 管理人承認制 )



はじめまして


んー、不要なビットにマスクかけちゃうとかでできないですかね?


みるみる  2016/02/25


ビットにマスクすると0-255の範囲内に納める事はできるのですが、マイナス値を0、255を超える値を255、にしないといけないところがミソです。例えば0xffffffff(-1)の上位ビットにマスクすると0×000000ff(255)になってしまいますもので。


IchiGeki  2016/02/25


シフト→マスク→シフト戻し で出来そうな出来なさそうな


TK  2016/02/25


ソースを是非!


IchiGeki  2016/02/25


X86アセンブラは遥か過去でうろ覚えですが符号付き飽和演算でいけた気がします
的外れだったらすみませぬ


匿名  2016/02/26


MMXの拡張命令だったらいけそうですね!ありがとうございます!


IchiGeki  2016/02/26


ちょい古い記事だしMMXで解決するらしいから蛇足なんだろうけど興味を惹かれたので少し試してからコメント。
予測分岐が高確率で成功する場合は予測分岐させるのが正解らしいって話もありますが…
 参考:d.hatena.ne.jp/yuyarin/20101124/1290556216
 参考:iSUS インテル 64 および IA-32 アーキテクチャー最適化リファレンス・マニュアル参考訳
1、何も考えなければこうしてしまいたいコード。分岐は無いけどCMOVccってある意味分岐……
 xor edx,edx
 test eax,eax
 cmovs eax,edx
 mov edx,0ff
 cmp eax,0ff
 cmovnb eax,edx
2、シンプルに最上位にフラグを用意して算術シフトでマスク生成
 mov ecx,eax
 sar ecx,0×1f
 not ecx
 and eax,ecx
 mov ecx,eax
 add ecx,0×7fffff00
 sar ecx,0×1f
 or eax,ecx
3、上側飽和が16bit範囲に収まるのなら定数とコードサイズ削減
 mov ecx,eax
 sar ecx,1f
 not ecx
 and eax,ecx
 movzx ecx,ah
 dec ecx
 not ecx
 or al,ch
4、1のCMOVccの代わりにSETccを使って減算でマスク生成
 1を元にdecとか組み合わせただけだが遅かったので省略
i7-4790 Haswellにて、M系列を使って((M系列レジスタ&0×1ff)-0×80)の値(飽和発生率が上下とも全体の25%)を0×2000000個処理する時間を215セット計測して平均を出したところ、
 1位 125ms 上記1のCMOVcc演算コード(ほぼ等速の類似コード3パターン平均)
 2位 126ms 上記2のビット演算コード(同2パターン平均)
 3位 129ms 上記3の16bit範囲制限付きコード(同4パターン平均)
 4位 134ms 上記4のSETcc(同3パターン平均)
 5位 144ms 記事内のMULを使うコード
 6位 325ms 記事内の元々のコード
となりました。
CMOVccが最速で、素直なビット演算が誤差レベルで同着。定数とコードサイズの削減は僅かに逆効果で、
SETcc+マスク生成は互いに利点を殺し合うのか少し不利。MULは乗算が重いのか少し遅く、
条件分岐は合計50%のミスヒットで順当に爆死、という結果となりました。


値を((M系列レジスタ%(255+2))-1)にして分岐率を上下ともに1/257まで落とすと全コードの速度差がほぼ消滅し、
予測分岐のおかげか記事内の元々のコードが辛うじて一番早いかも程度の状態になりました。
記事にある非分岐コードはMULで若干不利だと思ったのだけどその速度差も消滅。
入力値生成の為のDIVでMUL有り/無しの速度差要因が打ち消されたのでしょうか?(言い換えると周辺コード次第ではMUL無しでも優位性は無い?)


やねうらお氏の「Windowsプロフェッショナルゲームプログラミング2」を思い出して楽しく考えてたけど、
結論何も考えずCMOVccが優秀だからそれ使えば問題ないっていう残念な結果に……


それと、動作テスト組んでいる時に気付いたのですが、
記事にあるMULを使うコードって許容される値の範囲が結構制限されているんですね。
3の16bit制約のコードはそれ見て書いたんですが、私に書けたコードでは意味がなかったとです……


通りすがり  2018/09/05


ありがとうございます!


ちょっと凄すぎて私も理解できない部分も多々ありますので勉強させて頂きながらも参考にさせて頂きます!最近全然ですけど以前やねさんとはサシでお会いした事がありますのでまたお話でもお聞きしてみようかと。


> 記事にあるMULを使うコードって許容される値の範囲が結構制限されているんですね


そうですね、ほぼ0~255の範囲内なのですが、演算上たまにはみ出る程度ですね。


IchiGeki  2018/09/05




... 不具合報告の際は、アプリのバージョンやOS等の動作環境の記載を御願い致します。

表記されている会社名・製品名・システム名などは、各社の商標、または登録商標です。
当サイトはAmazon.co.jpアソシエイトプログラムに参加しています。
© 2010 IchiGeki