5

私はハッシュ関数について読んでいました（私は中級のCS学生です）、これに出くわしました：

int hash (const string & key, int tableSize) {
    int hasVal = 0;

    for (int i = 0; i < key.length(); i++)
        hashVal = 37 * hashVal + key[i];

    .....
    return hashVal;
}

私はこのコードを見ていて、代わりにこれを行うたびに key.length() を呼び出す代わりに、for ループ内にある方が高速であることに気付きました。

int n = key.length();
for (int i = 0; i < n; i++)

私の質問は、これはパフォーマンスをわずかに改善するための非常に明白な方法であるため、コンパイラは自動的にこれを行うのでしょうか? コンパイラについてはまだよくわかりませんが、この質問の答えに興味がありました。より少ない操作を使用するコードを作成するとき、私が行うことはコンパイラによって既に行われていることが多いため、インライン関数などを実行して時間を無駄にしていると指摘されることがよくあります。私は物理処理が効率的である必要があるゲームをプログラミングしているので、物事がぎこちなく感じられないようにしています。

4

4 に答える 4

3

簡単な答え: 場合によっては...

長い答え:

コンパイラが、ループ自体に基づいて key.length() が「定数」値であると判断できる場合、呼び出しを最適化できます。これは、使用されるクラスの定義に依存します (この場合string、「適切に記述されている」ことが期待できます)。keyまた、ループが を変更するような方法で を変更していないことをコンパイラが理解していることにも依存していますkey.length()。

これが機能するための重要な要素は、関数がinline(またはテンプレート関数でinlineあり、異なるコンパイル ユニットに複数回含めることができるようにするために必要である - または同じソース ファイル内で使用可能である) ことと、ソース コードがヘッダーにあることです。コンパイル単位によって含まれるファイル。

そしてもちろん、コンパイラがこれを行うという C++ 標準の要件はありません。毎回関数を呼び出すことは完全に標準準拠の範囲内です。

于 2013-11-13T08:32:43.117 に答える
2

key.length()純粋な関数、つまり副作用のない関数である場合にのみ、ループから抜けても安全です。コンパイラがこれを検出できれば、最適化を実行する可能性が高いと言えます。

残念ながら、Fortran とは異なり、C++ には何かをピュアとしてマークする標準的な方法がありません。関数がinline（またはインライン化可能である）場合、コンパイラは定義を持っており、おそらくそれ自体で解決するか、少なくとも関数呼び出しを排除できます。

メンバー関数をマークするconstと、現在のインスタンスに影響を与えないことが保証されますが、原則として、key.length()一部のグローバル変数を変更できない理由はないため、これだけで十分であるとは思えません。

(GCC や互換コンパイラ (Clang、Intel) のように、関数をピュアと宣言するコンパイラ固有の方法がいくつ__attribute__((pure))かあります。おそらくこれらを試して、違いがあるかどうかを確認してください。)

于 2013-11-13T08:40:55.557 に答える
0

それは非常にコンパイラに依存する答えです。確実にする唯一の方法は、アセンブラーを生成し、それが作成するものを突き刺すことです (コンパイラーでそれを行う方法を学び、とにかく試してみることをお勧めします。非常に有益です*)。

最適化はそれほど明白ではありません - コンパイラはその最適化を実行できますが、それが.length()変更されないことが確実な場合のみです - つまり、他のスレッドがデータにアクセスできず、ループ内の何も変更されないと判断できる場合に限ります.length()。後者は const 文字列なのでチェックしやすいですが、前者はそうではありません。そうは言っても、適度なレベルの最適化では、どこでも const であるとコンパイラが想定すると思います。

*意図的なしゃれ; ごめん。

于 2013-11-13T08:30:47.703 に答える
0

最適化が開始される場所は 2 つあります。

  1. ifよりスマートなコンパイラは、短い関数をイントロスペクトして、句に影響があるかどうかを確認します。おそらくほとんどのコンパイラはinline呼び出しを行い、あなたが書いたものと同等になります。

  2. CPUレベルでの分岐予測は、「ランダム」よりも（実質的に）高速になりifます。上のトップの質問の 1 つは、SOこれの素晴らしい筋金入りの例を示しています。

編集:メソッドを宣言するlength() constだけで十分だと以前に想定しました。でも弱すぎる。メソッドは、オブジェクトの状態を変更せずにランダムなものをスローできます。しかし、まともなコンパイラは、私が説明したような関数とメソッドをイントロスペクトすることを 100% 確信しています。

于 2013-11-13T08:28:31.520 に答える