char配列の先頭文字をチェックする最速の方法は何ですか?

29
Ali 2020-08-13 22:12.

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

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_hexn_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ますか?
  • ここでビット演算は役に立ちますか?

7 answers

25
pptaszni 2020-08-13 22:32.

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

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_zerofalse結果の場合は速くなります。それ以外の場合は、文字のグローバル配列を割り当てて、次'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、早期リターンの実装があります。

11
Peter Cordes 2020-08-14 02:28.

おそらく、バイナリチェックサムもありますか?最初に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 ++から使用できます。

8
I S 2020-08-13 22:31.

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

const char *zeroBuffer = "000000000000000000000000000000000000000000000000000";

if (memcmp(zeroBuffer, cksum_hex, n_zero) == 0) {
   // ...
}
6
Guillaume Gris 2020-08-13 23:00.

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

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

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

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

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

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

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

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

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

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

3
Artelius 2020-08-14 19:06.

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

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

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

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

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

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

開始し、検索する文字列の末尾に、そしてゼロの文字列に関数ポインタを渡すこの作品は、特異的にイテレータbeginendendゼロの希望数の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が、それでも高速であり(ゼロの数が少ない誤った結果を除く)、元のコードよりも一貫性があります。

0
phuclv 2020-08-13 22:41.

使用する std::all_of

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

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

モンサントは世界で最も強力な遺伝子編集ツールにアクセスできるようになりました

モンサントは世界で最も強力な遺伝子編集ツールにアクセスできるようになりました

画像:AP通信の農業会社であるモンサントは、MITのブロード研究所とハーバード大学からCRISPR / Cas9遺伝子編集システムを使用するための非独占的なグローバルライセンス契約を取得しました。同社はこれを使用して新しい種子や植物を設計および栽培しますが​​、モンサントがこの革新的な新技術を悪用するのを防ぐために、その使用には重要な制限があります。

グーグルのAIが囲碁世界チャンピオンの李世ドルとの最初の試合に勝った

グーグルのAIが囲碁世界チャンピオンの李世ドルとの最初の試合に勝った

画像提供:Linh Nguyen一連の試合の最初の試合で、Google Deepmindの強力な人工知能AlphaGoが囲碁の世界チャンピオンであるリーセドルを打ち負かしました。セドルとDeepMindの試合(実際には5つのうちの最初の試合)がYouTubeで生放送されました。 3月9日。

アマゾンのタイルスポーツとタイルプロブラックフライデーのお得な情報には無料のエコードットが付属しています

アマゾンのタイルスポーツとタイルプロブラックフライデーのお得な情報には無料のエコードットが付属しています

タイルトラッカーは、鍵を見つけることができないためにいつも遅れている友人に素晴らしい贈り物をします(真剣に、彼らはとても時間厳守です、誰もがいつもそれを言っています、彼らは彼らの鍵を見つけることができませんでした!)、そしてAmazonのタイルブラックフライデーのお得な情報彼ら(またはあなた自身)のためにいくつかを購入するのは簡単です。ここでは3つの選択肢があります:私のお金のために、それはプロを取得する価値があります。

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

Tomorrow's Kitchen シリコンストレッチ蓋 12個パック | $14 | アマゾン | プロモーション コード 20OFFKINJALids は基本的にキッチンの靴下です。常に迷子になり、二度と閉じられない孤立したコンテナーが残ります。しかし、蓋が伸びて、残った容器、鍋、フライパン、さらには大きなスライスされた果物のすべてに適合するとしたらどうでしょうか? その非常に特殊な蓋を失うことを二度と心配する必要はありません。

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

ロシアのフィギュアスケーター、カミラ・バリエバが関与したドーピング事件が整理されているため、チームは2022年北京冬季オリンピックで獲得したメダルを待っています。

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

何千人ものAmazonの買い物客がMulberry Silk Pillowcaseを推奨しており、現在販売中. シルクの枕カバーにはいくつかの色があり、髪を柔らかく肌を透明に保ちます。Amazonで最大46%オフになっている間にシルクの枕カバーを購入してください

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

ラファイエット警察署は、「不審な男性が女性に近づいた」という複数の苦情を受けて、12 月にパデュー大学の教授の捜査を開始しました。

コンセプト ドリフト: AI にとって世界の変化は速すぎる

コンセプト ドリフト: AI にとって世界の変化は速すぎる

私たちの周りの世界と同じように、言語は常に変化しています。以前の時代では、言語の変化は数年または数十年にわたって発生していましたが、現在では数日または数時間で変化する可能性があります。

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

犯罪擁護派のオークランドが暴力犯罪者のロミオ・ロレンゾ・パーハムを釈放

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

認知症を患っている 91 歳のアジア人女性が最近、47 番街のアウター サンセット地区でロメオ ロレンゾ パーハムに襲われました。伝えられるところによると、被害者はサンフランシスコの通りを歩いていたところ、容疑者に近づき、攻撃を受け、暴行を受けました。

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

メリック・ガーランドはアメリカに失敗しましたか?

バイデン大統領の任期の半分以上です。メリック・ガーランドは何を待っていますか?

メリック・ガーランドはアメリカに失敗しましたか?

人々にチャンスを与えることは、人生で少し遅すぎると私は信じています。寛大に。

Language