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++];

  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倍もの速さです。

私のCコードはこちらのリンクから入手できます

Node.jsのパフォーマンス最適化を阻むものの見つけ方

どれだけ速く文字列からスペースを削除できるのか

Previous Post