strlen()とmemchr()のSIMD版を作ってみました．
今回は最速よりもお手軽さを重視したのでアセンブリ言語ではなくintrinsic関数を使っています．そのためVisual Studio 2008, gcc 4.xの両方でコンパイルでき32-bit, 64-bit OS上で動作します．
WindowsとLinuxでのみ確認していますが恐らくIntel Mac OS X上でも動作するでしょう(sample source)．
ベンチマークはランダムな長さの文字列の平均長(average length)を変化させつつ取りました．数値は1byteあたりにかかった処理時間比で小さいほど速いことを表します．
strlenが3種類(ANSI, BLOG, SSE2)とmemchrが2種類(ANSI, SSE2)あります．BLOGというのは今回試してみようというきっかけになったCounting Characters in UTF-8 Strings Is Fastの中のCバージョンです．
結果は極端に短いところではSIMDが使えず，かつそのチェックのためのオーバーヘッドがありそれほど速くなりませんが，32文字以上ではは2～5倍高速であることが分かります．
なお，gccのstrlen()は今となっては遅い命令を使っているためよくありません(なぜこうなっているのかちょっと理解に苦しみます)．
一つ細かい注意点としては，高速化のために与えられた範囲外の空間を少しアクセスします(readはするがその値は捨てます)．16byteアライメントされたところを超えることはないのでバグで16byte超えることがあったのですが修正しましたのでページングエラーにはなりませんが，purifyなどのツールを使うと警告がでるかもしれません．
intrinsic関数はVCとgccとで共通化され，しかも32bit, 64bit両対応なため汎用性も高いです．strlenSSE2のように30行未満の関数でも十分は効果はでます．利用しない手はないと思われます．
size_t strlenSSE2(const char *p)
{
const char *const top = p;
__m128i c16 = _mm_set1_epi8(0);
/* 16 byte alignment */
size_t ip = reinterpret_cast(p);
size_t n = ip & 15;
if (n > 0) {
ip &= ~15;
__m128i x = *(const __m128i*)ip;
__m128i a = _mm_cmpeq_epi8(x, c16);
unsigned long mask = _mm_movemask_epi8(a);
mask &= 0xffffffffUL << n;
if (mask) {
return bsf(mask) - n;
}
p += 16 - n;
}
/*
thanks to egtra-san
*/
assert((reinterpret_cast(p) & 15) == 0);
if (reinterpret_cast(p) & 31) {
__m128i x = *(const __m128i*)&p[0];
__m128i a = _mm_cmpeq_epi8(x, c16);
unsigned long mask = _mm_movemask_epi8(a);
if (mask) {
return p + bsf(mask) - top;
}
p += 16;
}
assert((reinterpret_cast(p) & 31) == 0);
for (;;) {
__m128i x = *(const __m128i*)&p[0];
__m128i y = *(const __m128i*)&p[16];
__m128i a = _mm_cmpeq_epi8(x, c16);
__m128i b = _mm_cmpeq_epi8(y, c16);
unsigned long mask = (_mm_movemask_epi8(b) << 16) | _mm_movemask_epi8(a);
if (mask) {
return p + bsf(mask) - top;
}
p += 32;
}
}
| average length | 2 | 5 | 7 | 10 | 12 | 16 | 20 | 32 | 64 | 128 | 256 | 512 | 1024 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| strlenANSI | 683.8 | 406.3 | 308.8 | 234.5 | 203.3 | 168.0 | 148.3 | 113.3 | 86.0 | 70.5 | 62.5 | 58.5 | 54.5 |
| strlenBLOG | 835.8 | 449.3 | 347.5 | 269.5 | 234.3 | 195.3 | 175.8 | 140.5 | 109.3 | 89.8 | 82.0 | 78.3 | 82.3 |
| strlenSSE2 | 765.8 | 355.5 | 269.5 | 199.3 | 172.0 | 133.0 | 109.5 | 78.3 | 47.0 | 27.3 | 19.8 | 15.5 | 7.8 |
| memchrANSI | 1046.8 | 648.5 | 515.8 | 390.5 | 347.8 | 273.3 | 226.5 | 164.0 | 105.5 | 74.3 | 62.5 | 50.8 | 50.8 |
| memchrSSE2 | 773.5 | 375.0 | 285.0 | 214.8 | 179.5 | 144.8 | 121.3 | 82.0 | 54.5 | 31.3 | 19.5 | 15.8 | 11.8 |
| average length | 2 | 5 | 7 | 10 | 12 | 16 | 20 | 32 | 64 | 128 | 256 | 512 | 1024 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| strlenANSI | 2019.6 | 933.9 | 728.7 | 576.8 | 512.3 | 430.5 | 386.6 | 316.5 | 261.2 | 235.6 | 219.4 | 214.0 | 212.9 |
| strlenBLOG | 692.6 | 397.4 | 331.0 | 242.5 | 216.7 | 194.3 | 152.2 | 124.7 | 110.3 | 81.5 | 76.3 | 82.2 | 70.0 |
| strlenSSE2 | 560.0 | 275.6 | 214.3 | 159.2 | 135.7 | 104.4 | 87.5 | 65.1 | 41.5 | 25.3 | 16.6 | 14.0 | 9.3 |
| memchrANSI | 1152.4 | 609.5 | 487.4 | 375.0 | 325.6 | 260.5 | 229.9 | 152.4 | 95.5 | 72.8 | 56.8 | 49.3 | 48.0 |
| memchrSSE2 | 574.6 | 282.1 | 224.3 | 161.0 | 139.1 | 108.5 | 90.0 | 63.3 | 45.1 | 23.9 | 15.8 | 10.0 | 11.3 |
| average length | 2 | 5 | 7 | 10 | 12 | 16 | 20 | 32 | 64 | 128 | 256 | 512 | 1024 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| strlenANSI | 1039.4 | 568.0 | 460.9 | 353.7 | 306.9 | 254.9 | 212.2 | 145.2 | 82.0 | 50.3 | 35.3 | 26.4 | 24.5 |
| strlenBLOG | 795.4 | 474.9 | 366.4 | 291.0 | 263.9 | 227.6 | 201.7 | 178.3 | 144.5 | 125.9 | 117.2 | 112.0 | 110.5 |
| strlenSSE2 | 703.0 | 340.0 | 267.6 | 196.3 | 167.2 | 131.6 | 108.9 | 78.7 | 47.4 | 30.2 | 20.4 | 15.0 | 14.5 |
| memchrANSI | 1280.7 | 736.4 | 594.2 | 472.2 | 423.8 | 338.0 | 294.3 | 211.0 | 127.2 | 90.4 | 67.3 | 55.4 | 55.1 |
| memchrSSE2 | 1001.4 | 456.3 | 336.4 | 241.3 | 206.4 | 159.5 | 138.5 | 93.0 | 57.5 | 35.6 | 23.3 | 17.0 | 15.7 |
追記(2008/6/13)
64bit Windowsで_BitScanForwardの引数の型を勘違いしていたので修正．
ソースにライセンスを修正BSDライセンスと明記．
追記(2008/7/16)
strlenSSE2でループアンロールのため32byte単位で読み込んでいたため，ページングの境界を超えてしまうことがあったバグを修正(thanks to egtraさん)．
コメント (10)
一応、 32bit/64bit MacOSX でも動作して、同様に速い感じみたいでした、と報告させてもらいます。
投稿者: shinh | 2008年06月08日 02:02
日時: 2008年06月08日 02:02
こんにちは。
SSE2を用いたstrlenのコードをRubyにとりこみたいのですが、
ライセンスはどのようになるのでしょうか。
よろしくお願いいたします。
投稿者: 成瀬 | 2008年06月12日 08:10
日時: 2008年06月12日 08:10
>ライセンスはどのようになるのでしょうか。
ソースに書いたつもりがアップし忘れていました．ご指摘ありがとうございます．修正BSDライセンスでお願いします．
とは言え単なるコード片ですのでもっと緩くしても構いません．何かご希望のライセンスはありますでしょうか．
投稿者: へるみ | 2008年06月13日 15:05
日時: 2008年06月13日 15:05
RubyはGPLなので、修正BSDLならば十分です、ありがとうございました。
投稿者: 成瀬 | 2008年06月13日 23:42
日時: 2008年06月13日 23:42
こんばんは。手元のプログラムに適用したところ、運悪く境界に引っかかったようで落っこちてしまいました。こうすると再現できるのですがどうでしょうか。
int main()
{
DWORD old;
char* p = (char*)VirtualAlloc(0, 8192, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);
VirtualProtect(p + 4096, 4096, PAGE_NOACCESS, &old);
memset(p, 1, 4095);
p[4095] = 0;
strlenSSE2(p + 16);
}
投稿者: egtra | 2008年07月13日 21:20
日時: 2008年07月13日 21:20
そっか，ループアンロールしたので最大32byte読んでしまうため，そういうケースでは落ちてしまいますね．うかつでした．
ご指摘ありがとうございます．
明日修正します．
=>修正しました．
投稿者: へるみ | 2008年07月15日 23:30
日時: 2008年07月15日 23:30
初投稿失礼します。
実はSSE2を使った実装は私も以前（5月末）書いて某サイトに投稿したことがあったのですが、pcmpeqb→pextrw→判定→bsfって言う流れがそのまんま同じで思わず苦笑してしまいました。
やっぱり速さを追求すると誰が組んでもそうなるもんなんですね（こちらは若干アンロールが甘いですが）
私のほうは
http://smallcode.weblogs.us/2006/08/22/fast-strlen-function/
から引っ張ってきたコードをベースに自分の書いたコードを入れて公開しておりました。
テスト用に改造したソース一式(VC2008+インラインアセンブラ)
http://download.kousaku.in/trip/fast_strlen_mod2.zip
（※なお、このソースで私が改変を入れた部分について私は一切の著作権・著作者人格権を行使しません）
こちらはE8500(Wolfdale)ですが、MSVCRTの2.5倍程度にはなっています。
ソースの通り、SSE4.1でpcmpeqb→ptestで判定する実装も用意しておりますが、なぜかSSE2と比べても速くならないです（むしろ若干遅い）。
アンロールして並列化してみれば多少は速くなるかもしれません。あと、極端に長い文字列ならmovntdqaを使うのもよさそうですね。
投稿者: 団子厨 | 2008年08月28日 16:08
日時: 2008年08月28日 16:08
お，既にされていましたか．存じませんでした．
ptestなんて便利な命令もあるんですね．
SSE 4.1使ってみたいのですが，家のメインマシンがいまだにPentiumDでして…．
投稿者: へるみ | 2008年08月29日 14:20
日時: 2008年08月29日 14:20
こちらでもいろいろ試してみましたがSSE4.1はそんなに速くなりませんでした。Intel C++だと若干優位なんですが。
恐れながら数点だけパフォーマンス面で指摘を。
おそらくどのコンパイラでも共通だと思いますが_mm_set1_epi8(0)は_mm_setzero_si128()のほうが速いです。アセンブリコードを吐いてみると一目瞭然です。
それとmemchrのほう、Core 2(SSSE3)以降前提になりますが、_mm_set1_epi8(n)は
_mm_shuffle_epi8(_mm_setzero_si128(), _mm_cvtsi32_si128(n))
に置き換えたほうが速いです。
投稿者: 団子厨 | 2008年09月12日 22:08
日時: 2008年09月12日 22:08
>_mm_set1_epi8(0)は_mm_setzero_si128()のほうが速いです
アドバイスありがとうございます．なるほどそのあたり，よきに払ってくれるわけではないのですね．
実は私は仕事では殆どNASMやXbyakで書いていたので，intrinsic関数は慣れてなかったりします(^^;
#大抵Win/Linuxどちらでも動かす必要があったのでインラインアセンブラ不可だし，intrinsicはもどかしいし...
今回の件では一応ループ内は出力コードの確認はしてたのですが，外側は抜かりました．
投稿者: へるみ | 2008年09月13日 21:57
日時: 2008年09月13日 21:57