コードのボトルネックに達したので、この質問の主な問題はパフォーマンスです。

16進数のチェックサムがあり、charの配列の先行ゼロをチェックしたいと思います。これは私がしていることです：

bool starts_with (char* cksum_hex, int n_zero) {
  bool flag {true};
  for (int i=0; i<n_zero; ++i)
    flag &= (cksum_hex[i]=='0');
  return flag;
}

上記の関数は、cksum_hexにn_zero先行ゼロがある場合にtrueを返します。ただし、私のアプリケーションの場合、この関数は非常に高価です（合計時間の60％）。言い換えれば、それは私のコードのボトルネックです。だから私はそれを改善する必要があります。

またstd::string::starts_with、C ++ 20で利用できるものを確認しましたが、パフォーマンスに違いは見られませんでした。

// I have to convert cksum to string
std::string cksum_hex_s (cksum_hex);
cksum_hex_s.starts_with("000");     // checking for 3 leading zeros

私が使用g++ -O3 -std=c++2aしている詳細については、私のgccバージョンは9.3.1です。

質問

• char配列の先頭文字をチェックするより速い方法は何ですか？
• それを行うためのより効率的な方法はありstd::string::starts_withますか？
• ここでビット演算は役に立ちますか？

関数を変更して早期に戻る場合

bool starts_with (char* cksum_hex, int n_zero) {
  for (int i=0; i<n_zero; ++i)
  {
    if (cksum_hex[i] != '0') return false;
  }
  return true;
}

大きくn_zeroてfalse結果の場合は速くなります。それ以外の場合は、文字のグローバル配列を割り当てて、次'0'を使用することができますstd::memcmp。

// make it as big as you need
constexpr char cmp_array[4] = {'0', '0', '0', '0'};
bool starts_with (char* cksum_hex, int n_zero) {
    return std::memcmp(cksum_hex, cmp_array, n_zero) == 0;
}

ここでの問題は、可能な最大値を想定する必要があることですn_zero。

実例

===編集===

提案されたアプローチを正当化するためのプロファイリングデータがないことについての不満を考慮して、ここに行きます：

• アーリーリターンの実装とmemcmp実装を比較したベンチマーク結果
• memcmp実装とOPの元の実装を比較したベンチマーク結果

使用したデータ：

const char* cs1 = "00000hsfhjshjshgj";
const char* cs2 = "20000hsfhjshjshgj";
const char* cs3 = "0000000000hsfhjshjshgj";
const char* cs4 = "0000100000hsfhjshjshgj";

memcmpすべての場合で最速ですがcs2、早期リターンの実装があります。

おそらく、バイナリチェックサムもありますか？最初にASCIIテキストに変換する代わりに、4*n上位ビットを調べて、バイトが。と等しいかどうかをチェックnするので0はなく、ニブルを直接チェックしnます'0'。

たとえば、ハッシュ（またはその上位8バイト）をuint64_tまたはとして使用している場合はunsigned __int128、右にシフトして上位のnニブルのみを保持します。

両方の入力がランタイム変数である場合にx86-64用にコンパイルする方法の例をいくつか示しましたが、これらはAArch64などの他のISAにも適切にコンパイルされます。このコードはすべてポータブルISOC ++です。

bool starts_with (uint64_t cksum_high8, int n_zero)
{
    int shift = 64 - n_zero * 4;       // A hex digit represents a 4-bit nibble
    return (cksum_high8 >> shift) == 0;
}

clangは、-O3 -march=haswellBMI1 / BMI2を有効にするためにx86-64で素晴らしい仕事をします

high_zero_nibbles(unsigned long, int):
        shl     esi, 2
        neg     sil                  # x86 shifts wrap the count so 64 - c is the same as -c
        shrx    rax, rdi, rsi        # BMI2 variable-count shifts save some uops.
        test    rax, rax
        sete    al
        ret

これはn=16（shift = 0）でも機能し、64ビットすべてをテストします。どのn_zero = 0ビットもテストできません。uint64_tシフトカウント> =その幅だけaをシフトすることによってUBに遭遇します。（範囲外のシフトカウントをラップするx86のようなISAでは、他のシフトカウントで機能するcode-genは、16ビットすべてをチェックすることになります。コンパイル時にUBが表示されない限り、...）うまくいけばn_zero=0とにかくこれを呼び出す予定はありません。

その他のオプション：上位n*4ビットのみを保持するマスクを作成します。それcksum_high8が後で準備ができている場合は、クリティカルパスを短縮する可能性がありn_zeroます。特に、n_zeroがインライン化後のコンパイル時定数である場合、これはチェックと同じくらい高速になりますcksum_high8 == 0。（例：x86-64 test reg, immediate。）

bool high_zero_nibbles_v2 (uint64_t cksum_high8, int n_zero) {
    int shift = 64 - n_zero * 4;         // A hex digit represents a 4-bit nibble
    uint64_t low4n_mask = (1ULL << shift) - 1;
    return cksum_high8 & ~low4n_mask;
}

または、ビットスキャン機能を使用して先行ゼロビットをカウントし、を比較し>= 4*nます。残念ながら、それはISO C ++を取ったC ++ 20まで<bit>のcountl_zero最後に移植性（例えば386数十年の周りされています。この共通のCPU機能を公開するためにbsf/ bsr）。その前は、GNUCのようなコンパイラ拡張としてのみ__builtin_clz。

これは、特定のカットオフしきい値がいくつあるかを知りたい場合に最適です。

bool high_zero_nibbles_lzcnt (uint64_t cksum_high8, int n_zero) {
    // UB on cksum_high8 == 0.  Use x86-64 BMI1 _lzcnt_u64 to avoid that, guaranteeing 64 on input=0
    return __builtin_clzll(cksum_high8) > 4*n_zero;
}

#include <bit>
bool high_zero_nibbles_stdlzcnt (uint64_t cksum_high8, int n_zero) {
    return std::countl_zero(cksum_high8) > 4*n_zero;
}

コンパイル先（Haswellのclang）：

high_zero_nibbles_lzcnt(unsigned long, int):
        lzcnt   rax, rdi
        shl     esi, 2
        cmp     esi, eax
        setl    al                    # FLAGS -> boolean integer return value
        ret

これらの命令はすべてIntelとAMDで安価であり、lzcntとshlの間には命令レベルの並列性さえあります。

Godboltコンパイラエクスプローラで、これら4つすべてのasm出力を参照してください。Clangは1と2を同じasmにコンパイルします。の両方のlzcntウェイで同じです-march=haswell。それ以外のbsr場合は、入力= 0のコーナーケースを処理するために邪魔にならないようにする必要があります。これは、UBではないC ++ 20バージョンの場合です。

これらをより広いハッシュに拡張するには、高いuint64_tがすべてゼロであることを確認してから、次のuint64_tチャンクに進みます。

pcmpeqb文字列でSSE2比較を使用すると、pmovmskb->bsfは最初の1ビットの位置を見つけることができます。したがって、最初に'0'文字列表現に含まれる先頭文字の数を見つけることができます。したがって、x86 SIMDはこれを非常に効率的に行うことができ、組み込み関数を介してC ++から使用できます。

memcmpと比較するよりも、ゼロのバッファーを十分に大きくすることができます。

const char *zeroBuffer = "000000000000000000000000000000000000000000000000000";

if (memcmp(zeroBuffer, cksum_hex, n_zero) == 0) {
   // ...
}

アプリケーションを高速化するために確認したいこと：

1.コンパイラーは、呼び出された場所にこの関数をインライン化できますか？

関数をヘッダーでインラインとして宣言するか、関数が使用されるコンパイルユニットに定義を配置します。

2.何かを計算しない方が、何かをより効率的に計算するよりも高速です

この関数へのすべての呼び出しは必要ですか？高コストは、一般に、高周波ループ内または高価なアルゴリズムで呼び出される関数の兆候です。多くの場合、外部アルゴリズムを最適化することで、呼び出し数を減らし、関数に費やす時間を減らすことができます。

3.n_zero小さいですか、それとも一定ですか？

コンパイラーは、通常は小さい定数値のアルゴリズムを最適化するのに非常に優れています。定数がコンパイラーに認識されている場合、ループが完全に削除される可能性があります。

4.ビット演算はここで役立ちますか？

それは間違いなく効果があり、Clang（私が知る限りGCCではありません）が何らかのベクトル化を行うことを可能にします。ベクトル化は高速になる傾向がありますが、ハードウェアと処理される実際のデータによっては、常にそうであるとは限りません。それが最適化であるかどうかは、その大きさに依存する可能性がありますn_zero。チェックサムを処理していることを考えると、それはかなり小さいはずなので、潜在的な最適化のように聞こえます。既知のn_zeroビット演算の使用により、コンパイラはすべての分岐を削除できます。測定はしていませんが、これはもっと速いと思います。

std::all_ofの代わりにstd::string::starts_with使用することを除いて、実装とまったく同じようにコンパイルする必要が&&あり&ます。

n_zeroかなり高くない限り、プロファイラーの結果を誤って解釈している可能性があることに同意します。とにかく：

• データをディスクにスワップできますか？システムにRAMの負荷がかかっている場合、データがディスクにスワップアウトされる可能性があり、最初の操作を実行するときにRAMにロードして戻す必要があります。（このチェックサムチェックがしばらくしてデータに最初にアクセスすると仮定します。）

• マルチコアプロセッサを利用するために、複数のスレッド/プロセスを使用できる可能性があります。

• たぶん、入力データの統計/相関、または問題の他の構造的特徴を使用することができます。

  • たとえば、桁数が多く（たとえば、50）、後の桁がゼロ以外になる可能性が高いことがわかっている場合は、最初に最後の桁を確認できます。
  • 場合は、ほぼすべてのあなたのチェックサムのが一致している必要があり、あなたが使用することができます[[likely]]これが事実であることをコンパイラにヒントを得ました。（おそらく違いはありませんが、試してみる価値はあります。）

この興味深い議論に私の2セントを追加すると、ゲームに少し遅れますが、使用できると思いますstd::equal。これは、ゼロの数ではなく、ゼロの最大数を持つハードコードされた文字列を使用する、わずかに異なるアプローチの高速な方法です。 。

開始し、検索する文字列の末尾に、そしてゼロの文字列に関数ポインタを渡すこの作品は、特異的にイテレータbeginとend、endゼロの希望数の1人の過去の位置を指し、これらはでイテレータとして使用されますstd::equal：

サンプル

bool startsWith(const char* str, const char* end, const char* substr, const char* subend) {
    return  std::equal(str, end, substr, subend);
}

int main() {

    const char* str = "000x1234567";
    const char* substr = "0000000000000000000000000000";
    std::cout << startsWith(&str[0], &str[3], &substr[0], &substr[3]); 
}

@pptaszniの良い答えと同じテスト条件でテストケースを使用する：

const char* cs1 = "00000hsfhjshjshgj";
const char* cs2 = "20000hsfhjshjshgj";
const char* cs3 = "0000000000hsfhjshjshgj";
const char* cs4 = "0000100000hsfhjshjshgj";

次のような結果：

使用するよりも低速ですmemcmpが、それでも高速であり（ゼロの数が少ない誤った結果を除く）、元のコードよりも一貫性があります。

使用する std::all_of

return std::all_of(chsum_hex, chsum_hex + n_zero, [](char c){ return c == '0'; })