7

私は現在、ソリューションの速度と効率に大きな影響を与える大学のプロジェクトを行っています。私が書いている特定の関数は何十万回も呼び出されるため、コードに加えた小さな変更は大きな影響を及ぼします。

私は今、私のプロジェクトの主な機能を書き、現在、可能な限りすべてを最適化する過程にあります。私が質問しているコードの特定の部分は次のようになります。

array[i] *= -1;

私が最適化を検討していたのは次のとおりです。

array[i] = 0 - array[i];

このコードを変更すると、実際に速度に影響しますか？減算演算は乗算演算よりも高速ですか？それとも、この種の問題は過去のものですか？

4

6 に答える 6

19

おそらく代わりにこれを使用する必要があるという事実を見落としています：

array[i] = -array[i];

IMOは意図を直接示しているため、はるかに明確なので、このプログラムに対してコンパイラーが何を実行するか（x86-64ではGCC 4.7.2）を確認してみましょう。

#include <stdio.h>
#include <time.h>

int main(void)
{
    time_t t = time(NULL);
    t *= -1;
    return 0;
}

gcc -S mult.c -o 1.s

そしてこれのために：

#include <stdio.h>
#include <time.h>

int main(void)
{
    time_t t = time(NULL);
    t = 0 - t;
    return 0;
}

gcc -S sub.c -o 2.s

次に、2つのアセンブリ出力を比較します。

diff 1.s 2.s

何も印刷されません。コンパイラーは、両方のバージョンでまったく同じコードを生成しました。つまり、答えは次のとおりです。何を使用するかは問題ではありません。コンパイラは最も速いものを選択します。これは非常に簡単に行うことができる最適化であるため（最適化と呼ぶこともできます）、事実上すべてのコンパイラーが特定のCPUアーキテクチャーに対して最速の方法を選択すると想定できます。

参考までに、生成されるコードは次のとおりです。

int main（）
{{
    time_t t = time（NULL）;
       mov edi、0x0
       12に電話
       mov QWORD PTR [rbp-0x8]、rax

    t * = -1;
       ネガティブQWORDPTR[rbp-0x8]

    t = 0-t;
       ネガティブQWORDPTR[rbp-0x8]

    0を返します。
       mov eax、0x0
}

どちらの場合も、NEGを使用して値を否定します。t *= -1そしてt = 0 - t両方が生成します：

ネガティブQWORDPTR[rbp-0x8]
于 2012-11-22T13:48:39.810 に答える
14

最適化を行うための正しい方法は1つだけです。それは、アプリケーションのパフォーマンスを測定することです。優れたプロファイラーは多くのことを教えてくれますが、プログラムの実行とさまざまな変更のタイミングを計るだけでも非常に役立ちます。ボトルネックがどこにあるかを見つけるために、私は最初にプロファイラーを使います。

あなたの特定の質問に関しては、他の人が指摘しているように、これはアーキテクチャに大きく依存します。

于 2012-11-22T13:42:38.533 に答える
5

コンパイラは、これを効率的な操作に変換するのに十分賢いです。例えば

Cソース

void f()
{
    int a = 7, b = 7;
    a *= -1;
    b = -b;
}

を使用して与えるgcc -S a.c

    .file    "a.c"
    .text
    .globl    f
    .type    f, @function
f:
.LFB0:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    $7, -8(%rbp) ; assign 7
    movl    $7, -4(%rbp) ; assign 7
    negl    -8(%rbp)     ; negate variable
    negl    -4(%rbp)     ; negate variable
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size    f, .-f
    .ident    "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
    .section    .note.GNU-stack,"",@progbits

これは、Ubuntu12.04とgcc4.6.3を使用しているPC上にあります。アーキテクチャが異なる場合があります。

于 2012-11-22T13:45:20.383 に答える
4

ほぼすべてのデバイスで乗算が遅くなります。より複雑な操作です。

ただし、コンパイラは、それ自体で変換を実行するのに十分賢い場合があります。また、最近のCPUでは、命令の余分な時間が他の作業と重複するために実行時間が増加しないように、操作が重複する可能性があります。そして、おそらくそれはあなたが何百万回もそれをしていなければ、大きな努力なしでは測定できないほど小さな違いです。

一般に、最初に明確なコードを記述し、後で必要になった場合は最適化します。変数の負の値が必要な場合は、単に計算する方法ではなく、意図をより正確に反映するため、「-1*value」ではなく「-value」と記述します。

于 2012-11-22T13:45:08.777 に答える
2

gcc4.6.1が-Oで行うことは次のとおりです。

double a1(double b) { return -b; }       // xors sign bit with constant, 2 instr
                                         // movsd   .LC0(%rip), %xmm1   (instr 1)
                                         // xorpd   %xmm1, %xmm0        (instr 2)
                                         // ret                     (not counted)
double a2(double b) { return -1.0*b; }   // xors sign bit with constant, 2 instr
                                         // same code as above
double a3(double b) { return 0.0-b; }    // substract b from 0,  3 instructions
                                         // xorpd   %xmm1, %xmm1
                                         // subsd   %xmm0, %xmm1
                                         // movapd  %xmm1, %xmm0    (+ret)
int a4(int a){return -a;}                // neg rax   (+ret)  1 instruction
int a5(int a){return a*(-1);}            // neg rax
int a6(int a){return 0-a;}               // neg rax
double a7(double b) { return 0-b;}       // same as a3() -- 3 instructions

したがって、提案された最適化は、このコンパイラではさらに悪化します（配列タイプによって異なります）。

次に、乗算が加算よりも遅いという問題について。経験則では、乗算が加算と同じくらい速い場合、DSPアーキテクチャまたはDSP拡張について話します：Texas C64、Arm NEON、Arm VFP、MMX、SSE。同じことが、FADDとFMULの両方が3サイクルのレイテンシーと1サイクルあたり1命令のスループットを持つ、Pentiumから始まる多くの浮動小数点拡張にも当てはまります。ARM整数コアも1サイクルで乗算を実行します。

于 2012-11-22T13:57:44.457 に答える
1

さて、私の混乱を一掃し、私の愚かさを自分自身だけでなく他の人にとっても有用な知識に変えようとしています。

主な結論と要約：

この種の最適化はコンパイラーによって自動的に実行されます。この場合、両方のアプローチがx86上の単一のASM命令にコンパイルされます。（上記の投稿を参照）コンパイラーの作業を必要以上に難しくしないでください。ロジックが意味することを実行してください。

いくつかの回答は、これが両方の方法でまったく同じ命令にコンパイルされていることを示しています。

TL; DR

このトピックに関して私が犯した過ちを改善するために、私はこれを自分自身のために、そしてこの質問に奇跡的に悪い答えで答えたときのように精神的な停止に苦しむ人々のために、いくつかの努力を捧げることに決めました...

数値の否定は、アーキテクチャーとデータの表現方法によって異なります。

符号と大きさの表現

どういうわけか、私はこの実装が使用されていると思いました-そうではありません。これは、数値を1つの符号ビットとして表し、残りはすべて値として表します。したがって、-2n - 1-1から2n -1-1までの数値を表すことができ、負のゼロ値もあります。この種の表現では、符号ビットを反転するだけで十分です。

input ^ -0; // as the negative zero has all bits but the MSB as zero

1の補数表現

1の補数の整数表現は、正の表現のビット単位の否定として負の数を表します。ただし、これは実際には使用されていません。8080以降、2つの褒め言葉が使用されます。この表現の奇妙な結果は負のゼロであり、これは多くの問題を引き起こす可能性があります。また、表される数値の範囲は-2n - 1-1から2n- 1-1です。ここで、nは数値が格納されているビット数です。

この場合、数値を否定する最も簡単な「手動」の方法は、符号を表すすべてのビットを反転することです。

input ^ 0xFFFFFFFF; //assuming 32 bits architecture

また

input ^ -0; //as negative zero is a "full one" binary value

2の補数表現

より広く（常に？）使用される表現は、2の補数システムです。これは、-2n -1から2n-1 -1までの数値を表し、ゼロ値は1つだけです。これは、正の範囲を通常のバイナリ表現として表します。ただし、1を2に追加すると（MSB以外のすべてのビットに1があることで表されます）、-2 n -1（MSBでは1になり、他のすべてのビットは0になります）になります。

2の補数を手動で否定するには、すべてのビットを否定して1を加算する必要があります。

(input ^ -1) + 1 //as -1 is represented by all bits as 1

ただし、負の値の範囲は正の値の範囲よりも広いため、この表現では最も負の数に正の数がありません。これらの数を処理するときは、これを考慮に入れる必要があります。最も負の値を反転すると、ゼロの場合と同じように、それ自体が結果になります（簡単にするために、8ビットで）

most negative number: -128, represented as 10000000
inverting all bits: 01111111
adding one: 10000000 -> -128 again

しかし、どうぞ、誰もが*覚えておいてください：時期尚早の最適化はすべての悪の根源です！（オプティマイザーを使用すると、これらはリソースの豊富なアーキテクチャでは過去のものになります）

*：OPはすでにこれを通過しているので、これは私のような他のすべての人のためのものです。

（自己への注意:(時期尚早に）愚かであることは、すべての（正当な）反対票の根源です。）

于 2012-11-22T13:42:21.873 に答える