パフォーマンスが重要な場合は、文字ごとの処理を避けてください #C++

文字列を処理するとき、文字列を文字（またはバイト）の配列として表示し、そのように処理したくなるでしょう。

文字列がASCIIであるかどうかを判別したいとします。ASCIIでは、すべての文字は128より小さいバイト値である必要があります。文字列がASCIIであることを確認するための優れたC ++ 17アプローチは、次のようになります。

bool is_ascii_branchy(const std::string_view v) {
   for (size_t i = 0; i < v.size(); i++) {
     if (uint8_t(v[i]) >= 128) {
       return false;
     }
   }
   return true;
}

このコードのロジックを考慮することが重要です。コンパイラーに指示しているのは、すべての文字に順番にアクセスし、それがASCII文字であるかどうかを確認し、そうでない場合はベイルアウトすることです。したがって、文字列にASCII文字が含まれていない場合は、最初の文字のみを読み取る必要があります。

文字列がほとんどASCII以外の文字で始まることを期待している場合は、高性能のコードである可能性があります。ただし、文字列がほとんど常にASCIIであると予想している場合、このコードは最適ではありません。

コンパイラーがそれを最適化できるはずだと不平を言うかもしれませんが、それはあなたが提供したコードの制約の範囲内でのみです。コンパイラーは通常、アルゴリズムを再設計することを目的としていません。

ASCII入力を期待している場合は、できるだけ少ない手順で文字列を実行する必要があります。次のコードは、プロセッサが単一の命令を使用して64ビットブロックを処理できるという事実に依存しています。

bool is_ascii_branchless(const std::string_view v) {
  uint64_t running = 0;
  size_t i = 0;
  for(; i + 8 <= v.size(); i+=8) {
    uint64_t payload;
    memcpy(&payload, v.data() + i, 8);
    running |= payload;
  }
  for(; i < v.size(); i++) {
      running |= v[i];
  }
  return (running & 0x8080808080808080) == 0;  
}

これは楽観的な機能です。早い段階で非ASCII文字に遭遇した場合、文字列が長いと、多くの不必要な作業を行うことになります。

あなたは2つの間のハイブリッドを試すことができます。8文字を読み、ASCIIであるかどうかを確認し、ASCIIでない場合はベイルアウトします。

bool is_ascii_hybrid(const std::string_view v) {

  size_t i = 0;
  for(; i + 8 <= v.size(); i+=8) {
    uint64_t payload;
    memcpy(&payload, v.data() + i, 8);
    if((payload & 0x8080808080808080) != 0) return false;
  }
  for(; i < v.size(); i++) {
      if((v[i] & 0x80) != 0) return false;
  }
  return true;
}

これらの関数はどのように比較されますか？短いASCII文字列（128文字未満）を使用して簡単なベンチマークを作成しました。文字ごとの速度は約半分です。結果はさまざまです。コンパイラを使用して、マシンでベンチマークを自由に実行してください。

character-by-character	2.0GB/s
optimistic	3.5GB/s
hybrid	3.4GB/s

いくつかの作業を行うことで、おそらくはるかに速く進むことができますが、私が意図的に小さな断片化された文字列を含むベンチマークを選択したという事実に注意してください。

英語原稿：https://lemire.me/blog/2020/07/21/avoid-character-by-character-processing-when-performance-matters/