パフォーマンスのトリック：楽観的チェック vs 悲観的チェック

プログラミングにおける文字列は、しばしば8ビットワードの配列として表現されます。文字列がASCIIであるのは、すべての8ビットワードの最上位ビットがセットされていない場合に限ります。つまり、バイト値は127以下（または0x7F）でなければなりません。

文字列がASCIIであることをチェックする適切なC関数は次のようになります。

bool is_ascii_pessimistic(const char *data, size_t length) {
  for (size_t i = 0; i < length; i++) {
    if (static_cast<unsigned char>(data[i]) > 0x7F) {
      return false;
    }
  }
  return true;
}

各文字を順に調べ、0x7Fと比較し、値が0x7F以下であれば続行します。文字列全体をスキャンし、すべてのテストに合格した場合、その文字列がASCIIであることがわかります。

この関数をpessimisticと呼んだことに注意してください。これはどういう意味でしょうか？ある意味で、非ASCII文字が見つかると予想しているということです。その場合、最善の選択肢は直ちに戻り、文字列全体をスキャンしないことです。

文字列がほぼ常にASCIIであると予想する場合はどうでしょうか？その場合の代替手段は、文字列のビット単位のOR縮約を効果的に行うことです。つまり、すべての文字をOR演算し、結果が0x7Fで抑えられているかどうかを一度だけチェックします。いずれかの文字の最上位ビットがセットされている場合、すべての文字のビット単位のOR結果も最上位ビットがセットされます。そのため、次のように関数を書くことができます。

bool is_ascii_optimistic(const char *data, size_t length) {
  unsigned char result = 0;
  for (size_t i = 0; i < length; i++) {
    result |= static_cast<unsigned char>(data[i]);
  }
  return result <= 0x7F;
}

すべての文字列が純粋なASCIIである場合、どちらの関数が最も速いでしょうか？意外かもしれませんが、楽観的（optimistic）な方が数倍速くなる可能性があります。ベンチマークを作成し、Intel Ice Lakeプロセッサ上でGCC 15で実行したところ、次のような結果が得られました。

楽観的（optimistic）な方が速い理由は何でしょうか？主に、コンパイラが最適化しやすくなるためです。その他の可能性として、自動ベクトル化を使用してデータレベルの並列化（SIMD命令など）を自動的に利用できることが挙げられます。

どちらの関数が優れているかは、ユースケースによって異なります。

非ASCII文字に遭遇したときに早期に戻るという悲観的（pessimistic）な関数を好むが、それでも高い速度を求める場合はどうでしょうか？その場合、simdutfのような専用ライブラリを使用することで、手書きのロジックを利用できます。simdutfでは、この悲観的関数はvalidate_ascii_with_errorsと呼ばれます。結果は環境によって異なりますが、楽観的関数と同等の速度が得られました。

したがって、悲観主義と楽観主義の利点を組み合わせることは可能ですが、少し注意が必要です。

Published by

Post navigation