シルメラ プロジェクト | thilmera project ...       Site Viewer / Auto Update / Version
Windows汎用 多機能システムモニター - あなたの七つ道具
- Download (Japanese) -
Vector 窓の杜
フリーソフト100
- Download (English) -
Softpedia DIGITAL DIGEST
FileCroco MajorGeeks.Com
- Donation -
寄付 - paypal.me
thilmera7s ライセンス
*先日追加されたモニターオフキープ機能は、「モニターオフキープ」を実行しない限りPCに影響を与えることは一切関係ありません。

エンゲージメント
開発録
レビュー
PC周辺機器レビュー / HDD難民
軽さこそ命
ビット逆転の早いコードを目指す
並列処理は軽くなるわけではない
書き方を変えても速くならないコード例
std::vectorのpush_backはとても重い
悩みの種
Visual Studioでファンクションキーが動かなくなった
COMODOジャパンのデジタル署名の実状
strcmpに両方空文字列をいれると0以外を返す
Windows Defender誤検出の原因コード例
雷と停電
  アマゾン情報 - こちらのリンクを通して何らかをご購入頂くことで当サイトの運営、開発を応援頂けます
ビット逆転の早いコードを目指す (2017/10/11)


 FFT(高速フーリエ変換)にはビットを逆転(たとえば2進数で 010111 だったら 111010 にするみたいな。XORではない)させる必要があります。
 シルメラの音声可視化は当然リアルタイムで処理をするので、一瞬で大量の数値を逆転させていかないといけないわけですが、パフォーマンスモニターとして生まれたシルメラがパフォーマンス落とすほど重かったらだれが使うんだよというわけで、サウンドアナライザーを最初に開発した2011年3月から早6年半が経過して未だに完成度は微妙でした。

 先日の大改良 0b147 に引き続き、きたる 0b148 (この時点では開発中) においては、スペクトグラムっぽいやつをついに導入し、まるでPCの全ての音声がDTMソフトのピアノロールのように流れるという事態にまで発展しました。



 まぁそれはさておき、ここからはC言語のビット逆転やら代入やらの速度の話。
 今回はプログラムをすでにある程度勉強してる人向け。


今回のポイント


・inline 関数と関数内に書くのでは関数内のほうが圧倒的 ビットリバースを関数内部にじかに書くのと inline 関数にして呼び出すのとで速度を比べてみたら、inline関数のほうが2倍以上遅かった。なので多少冗長的になっても使用頻度の高いコードはベタ書きしたほうがいい。はず。

・代入(変数になにかを入れる)のはものすごく遅い 実体験での話だが、高速なコードを書きたい場合、最も遅く足枷となるのが、変数を変更する事(代入など)や乗算除算らしい。
 反対に計算途中であれば何回同じ変数を参照したりシフトしたりANDしたりしても大して重くない。
 アセンブラレベルの知識はよくわからないが、要は扱うのがレジスタかメモリかの差なんだろうと大して勉強もせずに納得していたりする。



 以下は6年間だらだらと変遷してきたビット逆転のC言語コード集。

変数定義

int reverse_bits = 14;//ビット数 今回の例では14ビットの逆転
int reverse_val = ?;//ビット逆転したい値
int y;//逆転後の値


パターン1


y = 0;
while (reverse_bits--) {
y <<= 1;
y |= (reverse_val & 1);
reverse_val >>= 1;
}


汎用性は極めて高い…だろうが、死ぬほど遅い。
十回とか百回しか処理しない部分ならべつにいいが、正直FFTではかなりしんどい。
たとえばこれ14ビットとするならば14x4の56+1回も代入(=)をしているので、代入がとにかく重いことを考えると明らかに悪手。
そもそも今見返してみれば y <<= 1;y |= (reverse_val & 1);
y = y << 1 | (reverse_val & 1); にまとめりゃいいじゃんかよと。


パターン2


case 14:
y = ( reverse_val >> 8 ) | ( reverse_val << 8 );
y = ( ( y & 0xF0F0) >> 4 ) | ( ( y & 0x0F0F ) << 4 );
y = ( ( y & 0xCCCC) >> 2 ) | ( ( y & 0x3333 ) << 2 );
y = ( ( ( y & 0xAAAA) >> 1 ) | ( ( y & 0x5555 ) << 1 ) ) >> 2;

ビット数の固定打ち計算。計算回数の根本的な削減によりかなり高速。
パターン1とは比べるまでもなく早いが、重たい代入(=)がこれも4回あるので少し重く、最適解とは言い難い。が、まぁ体感10倍くらい早い。



パターン3


case 14:
y = ( reverse_val & 1 ) << 13
| ( ( reverse_val >> 1 ) & 1 ) << 12
| ( ( reverse_val >> 2 ) & 1 ) << 11
| ( ( reverse_val >> 3 ) & 1 ) << 10
| ( ( reverse_val >> 4 ) & 1 ) << 9
| ( ( reverse_val >> 5 ) & 1 ) << 8
| ( ( reverse_val >> 6 ) & 1 ) << 7
| ( ( reverse_val >> 7 ) & 1 ) << 6
| ( ( reverse_val >> 8 ) & 1 ) << 5
| ( ( reverse_val >> 9 ) & 1 ) << 4
| ( ( reverse_val >> 10 ) & 1 ) << 3
| ( ( reverse_val >> 11 ) & 1 ) << 2
| ( ( reverse_val >> 12 ) & 1 ) << 1
| ( ( reverse_val >> 13 ) & 1 );

ビット数の固定打ち計算。なんか冗長的で一見だめな見た目だがパターン2より早い。
代入が一回しかないのでパターン2よりも確実に勝る。ただ見たとおり見た目がわかりやすいだけで無駄がかなりあるコード。



パターン4


case 14:
y = ( reverse_val & 1 ) << 13
| ( reverse_val & 2 ) << 11 //>> 1 << 12
| ( reverse_val & 4 ) << 9 //>> 2 << 11
| ( reverse_val & 8 ) << 7 //>> 3 << 10
| ( reverse_val & 16 ) << 5 //>> 4 << 9
| ( reverse_val & 32 ) << 3 //>> 5 << 8
| ( reverse_val & 64 ) << 1 //>> 6 << 7
| ( reverse_val & 128 ) >> 1 //>> 7 << 6
| ( reverse_val & 256 ) >> 3 //>> 8 << 5
| ( reverse_val & 512 ) >> 5 //>> 9 << 4
| ( reverse_val & 1024 ) >> 7 //>> 10 << 3
| ( reverse_val & 2048 ) >> 9 //>> 11 << 2
| ( reverse_val & 4096 ) >> 11 //>> 12 << 1
| ( reverse_val & 8192 ) >> 13;//>> 13

パターン3の無駄を気合いで省いたコード。メモ書いとかないと絶対間違えそう。
パターン3よりちょびっとだけ早い気がするだけで、そもそもコンパイルの最適化後のアセンブラコード同じじゃんかよと。
まぁ努力はしました的な感じで、実質パターン3と大差はない。




パターン5


_asm {                      ; C言語的に書くとこんな感じの意味↓ BX と CX はレジスタ
mov ebx, reverse_val ; BX = reverse_val
xchg  bh, bl ; BX = BX >> 8 | BX << 8
mov cx, bx ; CX = BX
and bx, 0xF0F0 ; BX = BX & 0xF0F0
ror bx, 4 ; BX = BX >> 4
and cx, 0x0F0F ; CX = CX & 0x0F0F
rol cx, 4 ; CX = CX << 4
or bx, cx ; BX = BX | CX
mov cx, bx ; CX = BX
and bx, 0xCCCC ; BX = BX & 0xCCCC
ror bx, 2 ; BX = BX >> 2
and cx, 0x3333 ; CX = CX & 0x3333
rol cx, 2 ; CX = CX << 2
or bx, cx ; BX = BX | CX
mov cx, bx ; CX = BX
and bx, 0xAAAA ; BX = BX & 0xAAAA
ror bx, 1 ; BX = BX >> 1
and cx, 0x5555 ; CX = CX & 0x5555
rol cx, 1 ; CX = CX << 1
or bx, cx ; BX = BX | CX
ror bx, 2 ; BX = BX >> 2
mov y, ebx ; y = BX
}

ってCじゃないし。
アセンブラがだめだめな私が必死に書いてみたパターン2のうちの重たい代入を省いたパターン。
そもそもレジスタの使い方ちげーよとかつっこまれそう… たしかCXは計算用じゃなかったような。
たぶんこれが局所的に見たら一番早いのかもしれないが、64ビットアプリではそもそもアセンブラで書くなということになってるし、
コンパイル時に前後関係の最適化がばっさり切られるので、結局いいのかどうかは分からない。


なので現在のところは誤打を恐れてパターン3でいくことに決定。
ちなみにパターン1は論外として、パターン2のFFT全体の速度を1とすると、パターン3と4が0.7くらいのタイム。





Copyright © 弦生ささと(Gakuto Matsumura) All Rights Reserved.