« 好きな風景 | メイン | goo スクリーンセーバ »
2004年07月29日
高速 memchr
1 なまえ：yoffy：2004/07/29 01:49:47 [りんく] [へんじ]非 SIMD 環境でも数 byte まとめて比較する方法があったんだけど、詳細を忘れてしまったので資料探しの旅に。というのも自作文字列ライブラリが大雑把な処理では速度的に限界に近づいてきたので。
で、ちょろっと探したら VC++ 6.0 に入ってる memchr のソースが見事な造り。この時ばかりは M$ と言えど「流石 OS メーカ」と思ってしまった。
かといって M$ のコードをパクったら問題だろうし、日記のネタにもしたかったので FreeBSD の核、libc のソースを拝見させてもらうことに。実は GPL だったらパクれないんだけど、オープンソースだから日記のネタには出来ると思って。
が、見事に撃沈。以前 libc の memcmp の造りがイマイチだと思ったんだけど、memchr はもっと酷いっていうか超素直。せっかくわざわざ各 CPU 向けに最適化コードがあるのに、超素直なコードをアセンブラにしてあるだけ。読みにくくするだけならやるなボケ。
オープンソースは遅い、富豪的だ、って言われがちだけど、まぁほんの一握りのソフトを除けば得てしてこんなもんです。仕事でやってるわけじゃないし。でも、C と同じ事をするだけのアセンブラコードがある時点で「読みやすさによる安定性重視」なんていうフザけた理由は絶対認めないけど。
ってことで日本語でググってみたら 1 件だけヒット。なんと Mac プログラミングでは知られてる Iimori さんのサイト。
アルゴリズムは以下の通り。
- キャラクタとメモリの xor を得る。
- a から 1 を引いた物 (a - 1) を得る。
- a の not 値の符号 (~a & 0x80) を得る。
- b と c の符号が同じであればヒット
仮にキャラクタとメモリが 0x85 とすると、
a = 0x85 ^ 0x85 = 0x00
b = 0x00 - 1 = 0xff
c = ~0x00 & 0x80 = 0xff & 0x80 = 0x80
d = 0xff & 0x80 = 0x80 // ヒット！
となり、メモリが 0x74 とすると、
a = 0x85 ^ 0x74 = 0x81
b = 0x81 - 1 = 0x80
c = ~0x81 & 0x80 = 0x7e & 0x80 = 0x00
d = 0x80 & 0x00 = 0x00 // ヒットせず
ってな感じで正しく分けられる。
なんでかっていうと、以前 分岐を減らす とセットで解説した 飽和演算その 2 のように、0 から繰り下がると最上位ビット(符号)が変わってしまう事を利用している。
上の b の処理で繰り下がる(符号が変わる)のは a の結果が 0 だった時のみで、a の結果が 0 になるのは探索するキャラクタと対象のメモリが同じ値だった場合のみ。
そして、c の処理では not で a の符号を反転しているので (& 0x80 してるのは符号以外をクリアする為)、b と c の符号が同じになるのは b が繰り下がった場合のみになる。
ポイントは、この処理がキャラクタ単位でパラレルだということ。つまり、レジスタのサイズ ( sizeof(int) ) が許す限り、いくらでも連ねてまとめてチェック出来る。この処理でヒットすれば、その中のどれかが目的のキャラクタ。
しかし繰り下がると左の bit を壊してしまうのでは? と思ったアナタは鋭いけどよく考えてみよう。
繰り下がるのは探索するキャラクタとメモリの内容が一致していた場合のみで、今回数 byte (32bit なら 4 byte) の中に一致するものが「あるか／ないか」を探したいだけなのだから、左の bit が壊れても構わない。つまりどれだけ連鎖して繰り下がっても一番右のキャラクタは壊れないから検出できるってわけ。
トラックバック
このエントリーのトラックバックURL:
http://yoffy.dyndns.org/cgi-bin/mt/mt-tb.cgi/101