2017年2月20日
どれだけ速く文字列からスペースを削除できるのか
本記事は、原著者の許諾のもとに翻訳・掲載しております。
時によってプログラマは文字列から不要な文字を取り除きたい場合があります。例えば、テキストの一部からすべての行の末尾文字を削除したいとします。
その時、全スペース(‘ ‘)や改行コード(‘\n’および‘\r’)を削除する問題を考えてみましょう。
効率的に実行するにはどのような方法がいいのでしょうか。
size_t despace(char * bytes, size_t howmany) {
size_t pos = 0;
for(size_t i = 0; i < howmany; i++) {
char c = bytes[i];
if (c == '\r' || c == '\n' || c == ' ') {
continue;
}
bytes[pos++] = c;
}
return pos;
}上記のコードはUTF-8でエンコードされた文字列で動作します。UTF-8がASCIIのスーパーセットであることを考えるとインターネット上で見る文字列の大半はUTF-8になります。
このコードは簡単で高速なはずです。このコードを様々なコンパイラが処理するところはとても面白いです。最終的に処理された1バイトあたりの命令の数が少なくなります。
しかし、プロセッサは64ビットアーキテクチャを持っていますが、バイト単位で処理しています。 64ビットワード単位でデータを処理できるのでしょうか。
ワードにゼロバイトが含まれている場合は必ずtrueの値を返す、ちょっと神秘的なビット遊びの表現があります。
(((v)-UINT64_C(0x0101010101010101)) & ~(v)&UINT64_C(0x8080808080808080))機能することだけが分かっていれば十分です。このツールを使用すれば、さらに処理の速い関数をプログラミングできます。
uint64_t mask1 = ~UINT64_C(0) / 255 * (uint64_t)('\r');
uint64_t mask2 = ~UINT64_C(0) / 255 * (uint64_t)('\n');
uint64_t mask3 = ~UINT64_C(0) / 255 * (uint64_t)(' ');
for (; i + 7 < howmany; i += 8) {
memcpy(&word, bytes + i, sizeof(word));
uint64_t xor1 = word ^ mask1;
uint64_t xor2 = word ^ mask2;
uint64_t xor3 = word ^ mask3;
if (haszero(xor1) || haszero(xor2) || haszero(xor3)) {
// check each of the eight bytes by hand?
} else {
memmove(bytes + pos, bytes + i, sizeof(word));
pos += 8;
}
}8文字単位のブロックに空白がなければ、処理は速くなります。
この時何が起きているかというと、ある程度コストのかかるチェックに対し、スーパースカラプロセッサで高速に処理ができるため、基本的には64ビットのワードを1つ1つコピーするだけになります。
結局、64ビットのワードを使用しなくても良いのです。
// table with zeros at indexes corresponding to white spaces
int jump_table[256] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
0, 1, 1, 0, 1, ...};
size_t faster_despace( char* bytes, size_t howmany ) {
size_t i = 0, pos = 0;
while( i < howmany )
{
bytes[pos] = bytes[i++];
pos += jump_table[ (unsigned char)bytes[pos] ];
}
return pos;
}上記はRobin Leffmannによって提案された、とても巧妙な方法です。
分岐誤予測ミスによるペナルティを回避できるため、非常に速いアプローチとなります。
さらに改善はできるのでしょうか。もちろんできます。Pentium 4（2001年）以降128ビット(SIMD)命令が存在します。
Intelの(醜い？) intrinsicを使って、この128バイトのSSEによる素早い命令で同じ問題を解決してみましょう。
__m128i spaces = _mm_set1_epi8(' ');
__m128i newline = _mm_set1_epi8('\n');
__m128i carriage = _mm_set1_epi8('\r');
size_t i = 0;
for (; i + 15 < howmany; i += 16) {
__m128i x = _mm_loadu_si128((const __m128i *)(bytes + i));
__m128i xspaces = _mm_cmpeq_epi8(x, spaces);
__m128i xnewline = _mm_cmpeq_epi8(x, newline);
__m128i xcarriage = _mm_cmpeq_epi8(x, carriage);
__m128i anywhite = _mm_or_si128(_mm_or_si128(xspaces,
xnewline), xcarriage);
int mask16 = _mm_movemask_epi8(anywhite);
x = _mm_shuffle_epi8(
x, _mm_loadu_si128(despace_mask16 + mask16));
_mm_storeu_si128((__m128i *)(bytes + pos), x);
pos += 16 - _mm_popcnt_u32(mask16);
}IntelプロセッサのSIMDの命令に馴染みがあるならば、このコードは極めて理解しやすいでしょう。私はこのコードを最適化する努力は何もしていません。ですから、より速く実行させられる可能性が高いのです。私のオリジナルのSIMDコードには分岐がありましたが、Nathan Kurzはコードを単純化して分岐を削除することが一番良いと気付きました。
では、どれだけ速く実行するか見てみましょう。
ほんの少しの空白ががあるテキスト入力に関して、新しいIntelプロセッサ（Skylake）を使ってベンチマークを設計しました。
| 標準コード | 5.5サイクル/バイト |
| 64ビットのワードを使用 | 2.56サイクル/バイト |
| ジャンプテーブルを使用 | 1.7 サイクル/バイト |
| SIMD（128ビット）のコード | 0.39サイクル/バイト |
memcpy |
0.08サイクル/バイト |
つまり、ベクトル化されたコードは標準コードの14倍近く速いことになります。これはなかなかの結果でしょう。
それでも、いくつかのスペースを削除するには、 memcpy でデータをコピーするよりも5倍の時間がかかります。従って、さらに速くすることが可能かもしれません。どこまで速められるでしょうか。
ヒント：私たちのIntelプロセッサは256ビットのレジスタを（AVX/AVX2の命令によって）実際に処理することができます。つまり、2倍の速さを実現することが可能ということです。悲しいことに、x64プロセッサ上における256ビットのSIMDの命令は、2つの128ビットの独立型のlane上で動作し、アルゴリズムの設計をより一層大変にします。
LeffmannのアプローチはSIMDの命令と同じほど速くはありませんが、より一般的で可搬性のあるものです。そしてさらに、標準コードの3倍もの速さです。
関連した投稿：
* Variable-length strings can be expensive（可変長の文字列は高くつくことがある）
* Intel will add deep-learning instructions to its processors
（Intelはプロセッサに深層学習の命令を追加するだろう）
* How fast is tabulation-based hashing? The downsides of…
（集計ベースのハッシングはどのくらい速いのか。ｚobristの欠点）
株式会社リクルート プロダクト統括本部 プロダクト開発統括室 グループマネジャー 株式会社ニジボックス デベロップメント室 室長 Node.js 日本ユーザーグループ代表
- Twitter: @yosuke_furukawa
- Github: yosuke-furukawa
