文字列を処理するとき、文字列を文字（またはバイト）の配列として表示し、そのように処理したくなるでしょう。
文字列が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/