8

答えはおそらくハードウェア固有のものだと思いますが、私が見逃しているより一般的な直感があったかどうか知りたいですか?

私はこの質問をして答えを与えられたので、「(2*i + 1)」の代わりに「(i << 1|1)」を使用するように一般的なアプローチを変更する必要があるかどうか疑問に思っています??

4

8 に答える 8

13

ISO 標準は実際にはパフォーマンス要件を義務付けていないため、これは実装、選択したコンパイラ フラグ、ターゲット CPU、およびおそらく月の満ち欠けに依存します。

この種の最適化 (2、3 サイクルの節約) は、アルゴリズム選択のようなマクロレベルの最適化に対して、ほとんどの場合、投資収益率の点で取るに足らないものになります。

何よりもまず、コードの読みやすさを目指してください。ビット と をシフトすることが目的の場合はOR、ビット シフト バージョンを使用します。あなたの意図が倍増することである場合は、*バージョンを使用してください。問題があることを確認してから、パフォーマンスについてのみ心配してください。

とにかくまともなコンパイラは、あなたができるよりもはるかにうまく最適化します:-)

于 2010-12-07T04:50:20.797 に答える
8

LEA「... it'll use 」について与えられた回答に関する単なる実験:
次のコード:

int main(int argc, char **argv)
{
#ifdef USE_SHIFTOR
return (argc << 1 | 1);
#else
return (2 * argc + 1);
#endif
}

(32 ビットまたは 64 ビットの場合) を使用するとgcc -fomit-frame-pointer -O8 -m{32|64}、次のアセンブリ コードにコンパイルされます。

  1. x86、32 ビット:
    080483a0 <メイン>:
80483a0: 8b 44 24 04 mov 0x4(%esp),%eax
80483a4: 8d 44 00 01 lea 0x1(%eax,%eax,1),%eax
80483a8: c3 ret
  2. x86、64 ビット:
    00000000004004c0 <メイン>:
4004c0: 8d 44 3f 01 lea 0x1(%rdi,%rdi,1),%eax
4004c4: c3 retq
  3. x86、64 ビット、-DUSE_SHIFTOR:
    080483a0 <メイン>:
80483a0: 8b 44 24 04 mov 0x4(%esp),%eax
80483a4: 01 c0 追加 %eax,%eax
80483a6: 83 c8 01 または $0x1,%eax
80483a9: c3 ret
  4. x86、32 ビット、-DUSE_SHIFTOR:
    00000000004004c0 <メイン>:
4004c0: 8d 04 3f レア (%rdi、%rdi、1)、%eax
4004c3: 83 c8 01 または $0x1,%eax
4004c6: c3 retq

実際、ほとんどの場合にLEA. ただし、コードは2 つのケースで同じではありません。これには 2 つの理由があります。

  1. 加算はオーバーフローしてラップアラウンドできますが、ビット操作は好き<<または|できません
  2. (x + 1) == (x | 1)!(x & 1)加算が次のビットに引き継がれる場合のみ真です。一般に、1 つだけ追加すると、半分のケースで最下位ビットが設定されます。

私たち (そしておそらくコンパイラー) は、2 番目が必ず適用可能であることを知っていますが、1 番目はまだ可能性があります。「or-version」ではビット 0 を強制的に 1 にする必要があるため、コンパイラは異なるコードを作成します。

于 2010-12-07T16:14:15.823 に答える
5

ほとんどの脳死したコンパイラー以外は、これらの式を同等と見なし、同じ実行可能コードにコンパイルします。

通常、これらのような単純な算術式の最適化についてあまり心配する価値はありません。これは、コンパイラが最適化するのに最も適している種類のものだからです。(「スマート コンパイラ」が正しいことを行うことができる他の多くのケースとは異なりますが、実際のコンパイラは失敗します。)

ちなみに、これは、PPC、Sparc、および MIPS の同じ命令のペアで機能します: シフトの後に加算が続きます。ARM では、融合された 1 つの shift-add 命令に分解されます。x86 では、おそらく 1 つの操作になりますLEA。

于 2010-12-07T04:48:27.197 に答える
4

-S オプションを指定した gcc の出力 (コンパイラ フラグは指定されていません):

.LCFI3:
        movl    8(%ebp), %eax
        addl    %eax, %eax
        orl     $1, %eax
        popl    %ebp
        ret

.LCFI1:
        movl    8(%ebp), %eax
        addl    %eax, %eax
        addl    $1, %eax
        popl    %ebp
        ret

どちらがどちらかはわかりませんが、それは問題ではないと思います。

コンパイラが最適化をまったく行わない場合、2 番目はおそらくより高速なアセンブリ命令に変換されます。各命令にかかる時間は、完全にアーキテクチャに依存します。ほとんどのコンパイラは、同じアセンブリ レベルの命令になるように最適化します。

于 2010-12-07T04:54:12.610 に答える
1

FrankHのソースを使用してgcc-4.7.1でこれをテストしたところ、生成されたコードは

lea    0x1(%rdi,%rdi,1),%eax
retq

シフトまたは乗算バージョンが使用されているかどうかは関係ありません。

于 2012-08-19T10:27:04.270 に答える
0

誰も気にしない。また、そうすべきではありません。
それについて心配するのをやめて、コードを正しく、シンプルに、そして完成させましょう。

于 2010-12-07T06:02:09.537 に答える
0

i + i + 1加算は乗算よりも高速で、シフトよりも高速になる可能性があるため、他の 2 つよりも高速である可能性があります。

于 2010-12-07T11:18:29.857 に答える
-2

高速なのは最初の形式 (右シフトを伴うもの) です。実際、shr 命令は最悪の場合で完了するのに 4 クロック サイクルかかりますが、mul は最良の場合で 10 クロック サイクルかかります。ただし、最適な形式は、他の (アセンブリ) 命令の完全なビューを持っているため、コンパイラによって決定される必要があります。

于 2010-12-07T14:11:19.283 に答える