2

これは、低レベルの最適化手法について説明し、著者が高価な分割を安価な比較に変換する例を示す素晴らしい記事です。 https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920

クリックしたくない人のために、基本的に彼はこれを変換しました：

uint32_t digits10(uint64_t v) {
    uint32_t result = 0;
    do {
        ++result;
         v /= 10;
    } while (v);
     return result;
}

これに：

uint32_t digits10(uint64_t v) {
  uint32_t result = 1;
  for (;;) {
    if (v < 10) return result;
    if (v < 100) return result + 1;
    if (v < 1000) return result + 2;
    if (v < 10000) return result + 3;
    // Skip ahead by 4 orders of magnitude
    v /= 10000U;
    result += 4;
  }
}

その結果、最大 6 倍のスピードアップが実現しました。

比較は非常に安価ですが、ブランチはパイプラインの停止を引き起こす可能性があるため、非常に高価であるといつも聞いています。分岐に関する一般的な通念のため、このようなアプローチを考えたことはありませんでした。

この場合、分岐がボトルネックにならないのはなぜですか? それぞれの比較の直後に戻るからですか? ここのコード サイズが小さいため、プロセッサが予測を誤る可能性があまりないためでしょうか。それがボトルネックになり、部門のコストを支配し始めるのはどのような場合ですか? 著者はこれについて決して話しません。

安価な比較と高価なブランチの間の明らかな競合を解決できる人はいますか? もちろん、最適化の黄金律は、常に測定しなければならないということです。ただし、コードを高速化するための新しいアプローチを考え出すときに、比較を賢く使用できるように、この問題についてある程度の直感を持っているとよいでしょう。

ありがとう！

4

3 に答える 3

10

ブランチは必ずしも高価ではありません - 高価なのは実際には予測を誤ったブランチです1。

それでは、ループから始めましょう。無限なので常に取られます。常に取られるので、常に取られると予測されるため、安価です。

任意の入力に対して、他の 1 つの分岐のみが実行されます。つまり、次から次へとテストを実行し、入力数値の大きさに一致するテストに到達するまで、すべての分岐は行われません (つまり、if条件が false になります)。

たとえば、最大 16 桁の入力数値のランダムな組み合わせを想定すると、ループの 4 回の繰り返しのうちの 1 回で、4 つのブランチのうちの約 1 つを取ることになります。私たちは (平均して) 16 回のテストのうち約 1 回しか分岐を取りません。その結果、計算全体で予測を誤った分岐が1 つだけ発生する可能性があります。

経験則として、正しく予測された分岐には約 1 クロック、誤って予測された分岐には約 20 ～ 30 クロックかかると考えてください。したがって、16 桁の数値の場合、最終的には 15 桁 + 4 回のループ反復 = 19 の正しく予測された分岐 + 1 つの誤って予測された分岐、合計 39 ～ 49 クロックのようなものになります。たとえば、2 桁の数字の場合、約 1+20=21 クロックになります。

明らかな代替手段は、10 で除算し、反復ごとに剰余をチェックすることです。除算は比較的コストがかかります。たとえば、i7 では 64 ビットの除算には約 26 ～ 86 サイクルかかります。簡単にするために、平均を 40 と仮定しましょう。したがって、16 桁の数値の場合、除算だけで約 16*40 = ~640 クロックと予想できます。せいぜい 2 桁の数値で 1 目盛りあたり 26 クロックしか必要としないと仮定すると、合計 52 クロックになります。

結論: 除算は、最良のケースに非常に近い場合でも、比較のほぼ最悪のケースよりも遅くなります。ほとんどの比較は最終的に正しく予測されるため、通常、高価な (誤って予測された) 分岐は 1 つだけになります。

1. もちろん、これは最新の比較的ハイエンドなプロセッサを想定しています。非常に古いプロセッサ (またはローエンドの組み込みプロセッサ) では、おそらく分岐予測子がまったくないため、すべての分岐が非常に高価になる傾向があります。同時に、そのようなプロセッサには除算命令がまったくない場合があり、もしあるとしても、おそらくかなり遅いでしょう。要するに、分岐と除算の両方が最新のプロセッサよりも多くのクロックを必要としますが、分岐は通常、除算よりもかなり高速です。

于 2013-08-07T02:32:45.107 に答える
1

最初の実装では、分岐点が 1 つしかない場合でも、実際にはさらに分岐します。

ただし、コーディング スタイルの好みの問題として、最初の実装を使用します。似たようなブランチを集めた方がパフォーマンスは良いかもしれませんが、それでもコードが多く、思慮分別なく書かれているように見えます (実際のところ、なぜ結果が保持されたのでしょうか?)。また、5 桁以上が必要な場合はどうすればよいですか? :|

于 2013-08-07T03:30:40.730 に答える
-1

アルゴリズムは主に比較です。唯一の明示的な分岐は戻るときです。

利益は主に、それぞれ 100 クロック サイクル以上かかる可能性がある桁あたりのコストのかかる除算を回避することによるものです。uint64_t の最大値は 22 桁の 10 進数であるため、ループを 22 回の比較に展開するのが最も効率的な方法であると考えることができます。

于 2013-08-07T01:12:23.117 に答える