専用命令でビット演算を高速化したい

Question

質問させてください。

**対象ビット列から、キーワードビット列の検索をしたいと考えています。**ここで、バイト内部のビットオフセットについては予めシフトパターンを用意して対応しています。専用命令を使って高速化できないかご教示ください。

私は以下の通りの方法を考えました。

対象ビット、キーワードビット、マスクビットをそれぞれ、t,k,mとします。論理式m and (t xor k)を計算することで、このビットに相違があるか判定します。これをビット長まで繰り返して、全てゼロとなったら検索にヒットしたとします。

この論理式は繰り上がり下がりがなく、他ビットに影響がないので一斉計算できると考えています。また、マスクビットを使うことで端数や中途ビットをワイルドカードにできます。

これを使って多ビットを一斉計算できないか考えています。汎用レジスタ長までであれば、cのポインタキャストでいけそうですが、他に方法があればお教えください。

以下追記

とりあえず、作りかけのプログラム案のイメージです。動作未確認

typedef char T;
//typedef long long T;
//多バイト一斉処理できるように、型はすぐ変えられるようにする。

int search(T targets[], T keyword[], T mask[], int target_size, int keyword_size)
{
  for(int i = 0; i + keyword_size < target_size; i++){
    for(int j = 0; j < keyword_size; j++){
      if(mask[j] & (targets[i + j] ^ keyword[j]) ){
        //相違ビットを検出した。外ループについてcontinueしたいが
        //Cではラベル付きcontinue,breakが使えないので苦渋のgoto
        goto label; 
      }
    }
    //targes[i]が検索にヒット
    return i;
    label:;//余談ですけど、この場合はgotoも悪くないと思います。
  }
  return -1;//検索ヒットせず
}


キーワードファイルは以下のような形を想定、一行ずつ読み取って、リストを予め用意しておきます。実際は2000ワード弱ほどあり、１ワードは最大で2000ビット弱です。

word_number
length0 keyword0
length1 keyword1
・・・


例
1
4 00x1

xはワイルドカード、これを読み取って、初期化時には以下のようなリストがメモリ上に作っておきます。
１バイトは８ビットですので、キーワード１ワードにつき８パターンが作られます。

ビット長　バイト長 ビット列　   　　　    マスク
4        1       00010000            11010000
5        1       00001000            01101000
6        1       00000100            00110100
7        1       00000010            00011010
8        1       00000001            00001101
9        2       00000000 10000000   00000110 10000000
10       2       00000000 01000000   00000011 01000000
11       2       00000000 00100000   00000001 10100000

Comments

[a_saitoh]

コードを視る限り「ビット列検索じゃなくてバイト列マッチ。ただしバイト合致じゃなくてmask位置のビットだけ合致してれば良い。」に見えます。本当にビット列検索したいのなら1ビットずつシフトしながらマッチングするコードになるはずですが､どっちでしょう？

[HogeAnimalLover]

はい。その通り後者です。バイト内部のビットオフセットの対応については、この関数内に書くと複雑になるので省略しました。あらかじめキーワードビットとマスクビットを8通りビットシフトしたシフトパターンを用意し、関数外でループすると想定しました。このループ構成も高速化の対象にできるならばお教えください。

Answer 1

案ずるより産むが易し、ということで取りあえず作ってみました。

ビット列検索 | gist

shiftは愚直に毎回シフトするもの、prepはあらかじめシフト済みのsearchとmaskを用意しておくものです。avx2がついているのだけ、AVX2で__m256i(256bit整数)を使っています。同じようにSSEで128bit、AVX-512で512bitも作れると思います、たぶん。

SIMDはアセンブラを使わなくても可能です。
参考: SIMDの組み込み関数のことはじめ - koturnの日記
コンパイラによって注意点がありますが、それさえ注意していれば大丈夫です。上のコードの実行環境はWSL上のUbuntuです。AVX2に対応したCPUで試して見てください。その他、リトルエンディアンが前提など、環境依存が多々ありますので、ご注意ください。

手元での結果では速い順で(単位は秒)

prep_avx2　 5.64 (user  5.40, system 0.18)
shift_ll    6.22 (user  6.04, system 0.17)
prep_ll     6.53 (user  6.39, system 0.14)
prep_int    7.83 (user  7.64, system 0.18)
shift_int   8.85 (user  8.71, system 0.14)
prep_char  14.75 (user 14.46, system 0.20)
shift_char 21.48 (user 21.15, system 0.28)

という感じでした。AVX2の256bitとlong longではそれほど差が出ていないのは、AVX2には_m265iをそのままシフトする関数がない(64bit整数4つそろぞれシフトならある)ため、面倒だったので、uint64_tで作って、そのままキャストしているところだと思います。ここを四つ同時にシフトしてうまくするように書き直せばもう少し速くなると思います。

なお、long longではprepとshfitが逆転しました。mallocを64回も呼び出すこと自体が重いのかも知れません。一気に巨大なメモリ領域を確保などの工夫をすれば、速くなる可能性はあります。

その他多数の所で、最適化の余地はかなりあると思います。

Comments

[HogeAnimalLover]

おお！これはわざわざ有り難うございます。プログラムの書き方も含めて参考にさせていただきます。やはりSIMDによる高速化が期待できそうですね。Cの標準機能外なので見積もれないところ（そもそもコンパイラの最適化に吸収されるんじゃないかとか）だったので助かります。しかし、こうなるとmemcmpとかの標準関数も内部的にどうなっているのか興味が湧きますね。（もちろん、本件ではマスクがあるのでmemcmpを使うことはできません）

Answer 2

専用命令もいいですが、アルゴリズムで高速化するのも有効ですよ。
ビットパターンの10001000(無視するビットはない場合)を100010010001000内で探すときに、最初のチェックで先頭7ビットまではOKで8ビット目でマッチしません。このときパターンを1～7ビットずらしても絶対マッチしないので次に調べるべきは8ビットシフトしたパターンです。

このように、「このパターンとマスクの場合何ビット目でマッチしなかったら次回のチェックは何ビットぶん飛ばして良いか」をあらかじめパターンを解析して表にしておきます。

Comments

[HogeAnimalLover]

ご回答ありがとうございます。ソフトウェア的にも検討してみます。

Answer 3

こんにちは。

専用命令とは、インテルCPUなどが実装しているSIMDのことでしょうか？
私自身はSIMDを直接使ったことはありませんが、内容的にSIMDを使えば高速化できそうな印象です。
しかし、自動的に SIMD コードを出力するコンパイラはないかもしれません。アセンブラで記述するかライブラリを使うかのどちらかではないかと思います。

さて、SIMDを使う方法は、コンパイラー最適化入門： 第1回 SIMD 命令とプロセッサーの関係から始まるシリーズが詳しそうです。
もし、インテルCPU限定（amdを含むかどうかは把握していません）であれば、インテルのコンパイラが優れているそうです。また、IPPというSIMDを使いこなすようなライブラリもインテルが出しています。
IPPは昔ちょっとだけ触ったことがありますが、今回提示されているような処理のライブラリです。andとxorの組み合わせまでできるかどうか記憶にないですが、少なくともandやxorをSIMDで処理できました。
昔はIPP単独で評価版があった（それをOpenCVに組み込んで高速化できた）のですが、今は確かインテルコンパイラに同梱されるようになった筈です。
上記Wikipediaによると「OpenCV 3.0にて、Intel IPPのサブセットがIPPCVとして寄贈された。」そうですので、OpenCV 3.0の該当部分を呼び出すことができればご希望のことができるかも知れません。

Comments

[HogeAnimalLover]

はい。ここではSIMDを想定しています。アセンブラを使うことに抵抗はありません。資料ありがとうございます。読んでみます。

Answer 4

汎用レジスタ長までであれば、

C言語はここまでサポートしているでしょうか?
また、汎用レジスタ長と言った時点で、CPU(または、コンパイラ)依存となります。この辺を検討されていますか?
単純に long の bit演算ではダメ?
それ以上はインラインアセンブラの出番となると思います。

Comments

[HogeAnimalLover]

質問追記しました。追記のとおり、typedefを切り替えればコンパイラの対応するビット長までは一斉処理できるようにしてあります。ポインタを使ってキャストしているので、C言語でも多バイトを一斉処理できる記述にしました。とりあえず64bitまでは目処が立ちました。

もちろん、インラインアセンブラでも一斉処理の方法があればお教えください。

[pepperleaf]

ちょっと時間が無いので、簡単に、、、
アセンブラの出力見られたでしょうか? この程度の演算なら、大した量でないので、追うのは難しくないと思います。で、
まず、配列 mask[] とかで forループを回していますが、なぜ、ポインタにしないのでしようか? コンパラにもよりますが、ポインタの方が速い筈。特に targets[i + j] 。他にもありそう。
また、環境によって型が変わっていますが、呼び出す場合、どう使うのでしょう? データ境界がアライメントに一致しない場合は? 等々。
アルゴリズムの詳細はまだです。

[HogeAnimalLover]

ご意見ありがとうございます。追記したソースはイメージです。もちろん、添字を使うよりもポインタのほうが速いとは思いますが、ご意見をいただくためにイメージを掴みやすい記述をしております。再追記検討します。