高速に1バイトから1bitを取得するには？

Question

1バイトのデータから任意の位置のビット値を取得するプログラムを下記のように作成しました。

戻り値は　ビットが1の場合は1を。0の場合は-1を返すものです。

戻り値の型がDoubleなのは仕様です。

VBまたはC#を使用してより高速に処理する方法があれば、お教え頂け無いでしょうか？

    Function GetBit(ByVal ByteData As Byte, ByVal Pos As Byte) As Double
        If (ByteData >> (Pos - 1)) And 1 = 1 Then
            Return 1
        Else
            Return -1
        End If
    End Function

Answer 1

外池と申します。確実に速くなるかどうか、まったく保証の限りではありませんが・・・、

「分岐命令を使わない」という工夫はいかがでしょうか？　C#で書けば

return (double)((ByteData >> (Pos-1) And 1) << 2) - 1.0

という感じです。（もとのままの方が良さそうにも思う・・・。）

ただ、このレベルの工夫は、中間言語（IL）へのコンパイルの段階、ILからネイティブへ実行時コンパイルの段階、あと、プロセッサが命令を実行する段階、それぞれで最適化がどうなるかによって速さは変ってしまうと思うので、なんとも難しいと思います。

以下は、余談ですが、

この関数を呼び出す側で、どのような処理を行っているのかにもよると思います。

例えば、Byte型配列に蓄えられたビット列をDouble型配列に変換するというような、何か順序だった繰り返し処理を行うのであれば、呼び出し側で工夫する余地もイロイロあるかと思います。

---

（ホームページを再開しました）

Answer 2

> 「分岐命令を使わない」という工夫はいかがでしょうか？

配列、使った方が速いでしょうか? 形式が怪しいですが、

 double ResultValue[] = {-1, 0}

 return  ResultValue[(ByteData >> (Pos -1) And 1)]

一昔前の Cでは定番手法かと。 ついでに 256の配列を使えば、シフト演算も消えるけど、やりすぎか。  ただ、

> ただ、このレベルの工夫は、中間言語（IL）へのコンパイルの段階、ILからネイティブへ実行時コンパイルの段階、あと、プロセッサが命令を実行する段階、それぞれで最適化がどうなるかによって速さは変ってしまうと思うので、なんとも難しいと思います。

なので、何が速いかはコンパイル後のコードとか、実際に測定するとかする必要がありそうで、他の場所の高速化を考えた方が、結果的に速くならないでしょうか。 関数(メソッド)呼出しを減らすとか。。。

# 余談ですが、昔、整数演算より、浮動小数点演算が速いと言うシステムもあったのを思い出しました。

Answer 3

>配列、使った方が速いでしょうか? 形式が怪しいですが、

> double ResultValue[] = {-1, 0}

> return  ResultValue[(ByteData >> (Pos -1) And 1)]

なるほど。その手がありましたか。

後ほど試してみたいと思います。

私の手法が極端に悪いということでなければ、この部分はあまりこだわらず他の場所を検討したほうが良いかもしれませんね。

.NET Frameworkで1ビットを高速に扱うライブラリなどあるかも？と思いましたが、そうではないようですね。

Answer 4

基本的にはその書き方で十分です。それよりはこの関数がどのような場面で使われるか、呼び出し元と一体にしてより効率的な動きにできないか、の方が重要です。BitVector32構造体なんてのもありますが、速くなるわけではありません。

外池さんへ：
C#なら And ではなく & です。 << 2 ではなく << 1 なのでは？ だったら右シフト回数を１つ減らせば。なるべく int で演算して最後にdoubleにキャストした方がいいかも。

pepperleaf01さんへ：
分岐は除去できても配列アクセス（メモリアクセス）が増えてはそれはそれでペナルティがあります。

Answer 5

外池です。

佐祐理さんのご指摘、まったくそのとおりです。「And」と「&」は、まぁ、意味はご理解頂けるマチガイですが、<< 2としたのは弁解の余地ありません。「２倍」するために「<<1」するのが正しいです。すいません、無造作に書いてしまいました。

「右シフト回数を１つ減らす」というのは、ちょっとマズイのでは？　一番右側のビットのテストをする場合と、そうでない場合と書き分けが必要になるかと。

ところで、

「短い関数」は、インライン展開される場合もあると聞いたことがありますがどうなんでしょう。ラムダ式で定義してやれば、必ずインライン展開される・・・、わけではないのかな？　このあたりも大きく影響しそうに思います。

---

（ホームページを再開しました）

Answer 6

佐祐理さん、

> 分岐は除去できても配列アクセス（メモリアクセス）が増えてはそれはそれでペナルティがあります。

確かにそうかも知れません。最近のコンパイラの吐き出すコードとCPUの処理の組合せにあまり詳しくないので。ただ、一昔(大昔?)前のパイプラインサポートしだした頃だったら、こちらが速かったと記憶してます。固定配列にすれば、コードと同じ場所にデータがあるし、(と昔の Cでの話です) 最初にも書きましたが、ここで凝るよりは、まずは、インラインにした方が確実に速そうで、上位のモジュールと合わせた最適化を検討すべきではないかと。

昔、多重ループの高速化を色々と考えたのですが、最後のオチは、そもそもそのループは不要だったと言うのがありました。

呼出し回数を減らせないかもあるし、そもそも最近のCPUでは、この程度の分岐でのペナルティはほとんど無いとか言う事はあるのでしょうか? また、この程度のビット処理を少々速くしても全体の処理にどの程度影響するでしょうか? 中間言語で動いているだけにちょっと疑問。

Answer 7

外池さんのアプローチなら

return (double)((ByteData >> (Pos-2) & 2) - 1);

ってコードをイメージしました。

ラムダ式は短い関数を書くためのものですが、コンパイル後、自動生成されたクラス＋メソッドになるだけですから、パフォーマンス的には同じかむしろ遅くなるかも。

Answer 8

そうですね。コードセグメントに固定配列を用意すれば…という意図はわかります。ただし、.NET FrameworkではすべてのデータがGCに管理されマネージドなヒープに配置されます。ですので、どこまで効率よくなれるか疑問です。