3

この男は、（Cコンパイラでの）バイナリ検索は、生成されたコードからのハードコードされたifブランチよりも遅いと異常に主張しています。（Clojureコードと奇抜なタイトルを許してください-これは、この男が作るのは一般的にコンパイラーに関連していると主張しています）。

彼は書く

私はこの種のコードを時々暗い場所で見ました。男性が自分のプロセッサがどのように機能するか、Cコンパイラがどのように機能するか、データ構造を知っているとき、そして実際にループを高速にする必要があるとき、彼は時々この種のことを書きます。

これは、RealProgrammersが作成する一種のコードです。

これは二分探索の例です（Clojureを許してください）

Start: (1 2 3 4 6 8 9 10 11 12)
Finish: ((((1) (2)) ((3) ((4) (6)))) (((8) (9)) ((10) ((11) (12)))))

次に、ハードコードされた値に基づいている場合、バイナリ検索を分岐された生成コードに置き換えます。

(defn lookup-fn-handwritten [x]
  (if (< x 6) 
    (if (< x 3)                         ; x is < 6
      (if (< x 2)                       ; x is < 3
        (if ( < x 1)                    ; x is < 2
          0                             ; < 1
          1)                            ; 1 <= x < 2
        3)                              ; 2 <= x < 3
      (if (< x 4)                       ; 3 <= x < 6
        4                               ; 3 <= x < 4
        2))                             ; 4 <= x < 6
    (if (< x 10)                        ; 6 <= x < 10
      (if (< x 9)                       ; 6 <= x < 9
        (if (< x 8) 
          2                             ; 6 <= x < 8
          3)                            ; 8 <= x < 9
        3)                              ; 9 <= x < 10
      (if (< x 11)                      ; 10 < x
        (if (< x 12)                    ; 11 <= x
          1                             ; 11 <= x < 12
          0)
        0))))                           ; 12 <= x

http://www.learningclojure.com/2010/09/clojure-faster-than-machine-code.html

私の質問は-生成されたコードとハードコード値からの分岐ハードコードがバイナリ検索よりも効率的であるかどうかです。（どの言語でも-しかし、作者はこれがCで機能すると主張しています-そして、JVMでのみそれを示しているようです）。

（リンクされた投稿の風変わりなタイトルをもう一度失礼します-それはただの狂気です。）

4

4 に答える 4

9

ええと、if-cascadeはおそらく二分探索と同じことをします。つまり、同じ比較を行いますが、関連する「二分探索管理」はありません。これは展開されたループであり、コンパイラーがループを展開する理由は確かにあります。そうです、それはより速くなります。

しかし、それは本当に速くなるでしょうか？今、「キャッシュ」と呼ばれる問題があります。ループを展開するかどうかに関係なく、コードは大きくなるため、コードを実行するためのメモリアクセスが増えることでメリットが相殺される可能性があります。

さらに、コンパイラがコードを最適化するためにどのような種類の命令を使用しているのか、手動でループを展開するときに使用されていない可能性があるのか​​、まったくわかりません。または逆に'ラウンド、誰が知っている。バイナリ検索が「組み込まれている」言語ではさらにそうなので、コンパイラはそれが何を扱っているかを知ることができます。

したがって、「私はすべての比較を行い、他のものはどれも持っていない」などの操作を数えるだけでは不十分な場合があります。実行時間に影響を与える他の要因があります。また、あるCPUでプロファイルを作成して、「展開されたバージョンの方が速い」ことを確認した場合でも、別のCPUが同意しない可能性があります。

最適化は一言ですが、ここで詳しく説明できるかどうかはわかりません:-)

于 2012-07-05T12:12:44.170 に答える
2

「ハードコードされた」バージョンもバイナリ検索であり、ほとんどのバイナリ検索実装よりもはるかに効率的に記述されています。私はその主張を並外れたものとはまったく見ていません。ただし、一般的な実装の非効率性のほとんどを回避すれば、一般的なバイナリ検索を比較的高速に実行できる場合があります。

于 2012-07-05T13:04:59.827 に答える
2

この種の比較は、最近のJVMでは非常に難しい場合があります。HotSpotコンパイラは、クラスが何度も実行されていることを検出すると、
実行時に多くの動的最適化を行うため、関数呼び出しのインライン化を広範囲に開始し、ネストされたif式のツリーを生成します。

この種の比較を行うときは、そのクラスのJVMを数百万回「ウォームアップ」して、この種のインライン化を終了させることが重要です。違いがあまり目立たないと思います。

于 2012-07-05T19:12:34.007 に答える
1

カスケードifは事実上特定の二分探索であるため、一般的な二分探索を実装するコードがなくても節約できます。事実上、巻き戻されたループであるため、常に高速になります。

一般的な状況（つまり、特定の構成をターゲットにしていない場合）では、ループがキャッシュに対して大きすぎると、CPUキャッシュが展開されたループのパフォーマンスを低下させることがよくあります。

最適化の最初のルールは、問題を測定し、見つけて、それに応じて最適化することです。元のリンクは、特定の構成に適合するこの優れた例です。

そうです、コンパイラ、インタプリタ、CPUに関係なく、良いアルゴリズムは常に悪いアルゴリズムを打ち負かします。それが元のリンクで指摘されていることです。

アルゴリズムの効率

于 2012-07-05T12:11:33.300 に答える