if (a < 901)より速いですif (a <= 900)か？
この単純な例とまったく同じではありませんが、ループの複雑なコードではパフォーマンスがわずかに変化します。これが本当の場合、生成されたマシンコードで何かをしなければならないと思います。
質問する
138102 次
14 に答える
1792
いいえ、ほとんどのアーキテクチャでは速くなりません。指定しませんでしたが、x86 では、通常、すべての整数比較は 2 つのマシン命令で実装されます。
- 設定する
testorcmp命令EFLAGS - 比較タイプ (およびコード レイアウト) に応じた
Jcc(ジャンプ) 命令: jne- 等しくなければジャンプ -->ZF = 0jz- ゼロ (等しい) ならジャンプ -->ZF = 1jg- 大きければジャンプ -->ZF = 0 and SF = OF- （等...）
例（簡潔にするために編集）でコンパイル$ gcc -m32 -S -masm=intel test.c
if (a < b) {
// Do something 1
}
コンパイルすると:
mov eax, DWORD PTR [esp+24] ; a
cmp eax, DWORD PTR [esp+28] ; b
jge .L2 ; jump if a is >= b
; Do something 1
.L2:
と
if (a <= b) {
// Do something 2
}
コンパイルすると:
mov eax, DWORD PTR [esp+24] ; a
cmp eax, DWORD PTR [esp+28] ; b
jg .L5 ; jump if a is > b
; Do something 2
.L5:
したがって、この 2 つの唯一の違いはjg、命令とjge命令です。どちらも同じくらいの時間がかかります。
異なるジャンプ命令に同じ時間がかかることを示すものは何もないというコメントに対処したいと思います。これは答えるのが少し難しいですが、ここに私が与えることができるものがあります: Intel Instruction Set Referenceでは、それらはすべて 1 つの共通の命令Jcc(条件が満たされた場合にジャンプ) の下にグループ化されています。Optimization Reference Manualの Appendix C. Latency and Throughput では、同じグループ化が行われています。
レイテンシ— 実行コアが命令を形成するすべての μop の実行を完了するために必要なクロック サイクル数。
スループット— 発行ポートが同じ命令を再び受け入れられるようになるまで待機するのに必要なクロック サイクル数。多くの命令では、命令のスループットはそのレイテンシーよりも大幅に低くなる可能性があります
の値は次のJccとおりです。
Latency Throughput
Jcc N/A 0.5
に次の脚注を付けJccます。
- 条件付きジャンプ命令の選択は、セクション 3.4.1「分岐予測の最適化」の推奨事項に基づいて、分岐の予測可能性を向上させる必要があります。分岐が正常に予測されると、 のレイテンシ
jccは事実上ゼロになります。
したがって、インテルのドキュメントには、1 つのJcc命令を他の命令とまったく異なる方法で扱うものはありません。
命令を実装するために使用される実際の回路について考えるとEFLAGS、条件が満たされているかどうかを判断するために、 のさまざまなビットに単純な AND/OR ゲートがあると想定できます。したがって、2 つのビットをテストする命令が、1 つだけをテストする命令よりも多かれ少なかれ時間がかかる理由はありません (クロック周期よりもはるかに短いゲート伝搬遅延を無視します)。
編集：浮動小数点
これは x87 浮動小数点にも当てはまります: (上記とほとんど同じコードですが、double代わりにint.)
fld QWORD PTR [esp+32]
fld QWORD PTR [esp+40]
fucomip st, st(1) ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS
fstp st(0)
seta al ; Set al if above (CF=0 and ZF=0).
test al, al
je .L2
; Do something 1
.L2:
fld QWORD PTR [esp+32]
fld QWORD PTR [esp+40]
fucomip st, st(1) ; (same thing as above)
fstp st(0)
setae al ; Set al if above or equal (CF=0).
test al, al
je .L5
; Do something 2
.L5:
leave
ret
于 2012-08-27T02:13:38.163 に答える
613
歴史的に (1980 年代から 1990 年代初頭にかけて)、これが当てはまるアーキテクチャがいくつかありました。根本的な問題は、整数比較が整数減算によって本質的に実装されていることです。これにより、次のようなケースが発生します。
Comparison Subtraction
---------- -----------
A < B --> A - B < 0
A = B --> A - B = 0
A > B --> A - B > 0
ここでA < B、減算を正しく行うために上位ビットを借用する必要がある場合は、手で加算および減算するときにキャリーと借用を行うのと同じです。この「借りた」ビットは、通常、キャリー ビットと呼ばれ、分岐命令でテストできます。ゼロ ビットと呼ばれる 2 番目のビットは、減算が等しいことを意味するゼロである場合に設定されます。
通常、少なくとも 2 つの条件付き分岐命令があり、1 つはキャリー ビットで分岐し、もう 1 つはゼロ ビットで分岐します。
さて、問題の核心をつかむために、前の表を拡張して、キャリーとゼロ ビットの結果を含めてみましょう。
Comparison Subtraction Carry Bit Zero Bit
---------- ----------- --------- --------
A < B --> A - B < 0 0 0
A = B --> A - B = 0 1 1
A > B --> A - B > 0 1 0
したがって、分岐の実装A < Bは 1 つの命令で実行できます。これは、キャリー ビットがこの場合にのみクリアされるためです。つまり、
;; Implementation of "if (A < B) goto address;"
cmp A, B ;; compare A to B
bcz address ;; Branch if Carry is Zero to the new address
しかし、より小さいか等しい比較を行いたい場合は、等しい場合をキャッチするためにゼロ フラグの追加チェックを行う必要があります。
;; Implementation of "if (A <= B) goto address;"
cmp A, B ;; compare A to B
bcz address ;; branch if A < B
bzs address ;; also, Branch if the Zero bit is Set
そのため、一部のマシンでは、「より小さい」比較を使用すると、マシン命令が 1 つ節約される場合があります。これは、サブメガヘルツのプロセッサ速度と 1:1 の CPU 対メモリ速度比の時代には関係がありましたが、今日ではほとんどまったく関係ありません。
于 2012-08-27T17:53:13.620 に答える
97
内部整数型について話していると仮定すると、一方が他方より高速になる可能性はありません。それらは明らかに意味的に同一です。どちらもコンパイラにまったく同じことを要求します。これらのいずれかに対して劣悪なコードを生成するのは、ひどく壊れたコンパイラだけです。
単純な整数型<よりも高速なプラットフォームがあった場合、コンパイラは常に定数に変換する必要があります。そうでないコンパイラは、(そのプラットフォームにとって)単に悪いコンパイラになります。<=<=<
于 2012-08-27T02:31:30.983 に答える
69
どちらも速くないことがわかります。コンパイラは、異なる値を持つ各条件で同じマシン コードを生成します。
if(a < 901)
cmpl $900, -4(%rbp)
jg .L2
if(a <=901)
cmpl $901, -4(%rbp)
jg .L3
私の例ifは、Linux の x86_64 プラットフォームの GCC からのものです。
コンパイラの作成者は非常に賢い人であり、これらのことや、私たちのほとんどが当然のことと思っている他の多くのことを考えています。
定数でない場合は、どちらの場合も同じマシン コードが生成されることに気付きました。
int b;
if(a < b)
cmpl -4(%rbp), %eax
jge .L2
if(a <=b)
cmpl -4(%rbp), %eax
jg .L3
于 2012-08-27T02:16:43.623 に答える
54
浮動小数点コードの場合、<= 比較は、最新のアーキテクチャーでも実際に (1 命令分) 遅くなる場合があります。最初の関数は次のとおりです。
int compare_strict(double a, double b) { return a < b; }
PowerPC では、最初に浮動小数点比較 (cr条件レジスタを更新) を実行し、次に条件レジスタを GPR に移動し、「比較された未満」ビットを所定の位置にシフトしてから戻ります。4 つの命令が必要です。
代わりに、次の関数を検討してください。
int compare_loose(double a, double b) { return a <= b; }
これには上記と同じ作業が必要ですが、compare_strictここで注目すべき点が 2 つあります。「より小さかった」と「等しかった」です。これには、これら 2 つのビットを 1 つに結合するための追加の命令 ( cror- 条件レジスタ ビットごとの OR) が必要です。したがってcompare_loose、5 つの命令がcompare_strict必要ですが、4 つの命令が必要です。
コンパイラは次のように 2 番目の関数を最適化できると考えるかもしれません。
int compare_loose(double a, double b) { return ! (a > b); }
ただし、これは NaN を正しく処理しません。両方とも false と評価される必要がありますNaN1 <= NaN2。NaN1 > NaN2
于 2012-08-27T18:32:32.573 に答える
34
たぶん、その名前のない本の著者は、それa > 0よりも速く実行a >= 1され、それが普遍的に真実であると考えている本を読んだことがあります。
ただし、これはa0が関係しているためであり（CMPアーキテクチャによっては、などで置き換えることができるORため）、ではありません<。
于 2012-08-27T13:05:52.293 に答える
30
少なくとも、これが真実である場合、コンパイラーはa <= bを！（a> b）に簡単に最適化できるため、比較自体が実際に遅くても、最も単純なコンパイラーを除いて、違いに気付くことはありません。 。
于 2012-08-27T09:23:48.673 に答える
17
TL;DR回答
アーキテクチャ、コンパイラ、および言語のほとんどの組み合わせでは、<は よりも高速ではありません<=。
完全な答え
他の回答はx86アーキテクチャに集中しており、生成されたコードについて具体的にコメントするのに十分なARMアーキテクチャ（あなたの例のアセンブラのようです）をよく知りませんが、これは非常にアーキテクチャであるマイクロ最適化の例です具体的であり、最適化であるのと同じくらい最適化防止である可能性があります。
そのため、この種のマイクロ最適化は、最高のソフトウェア エンジニアリング プラクティスではなく、カーゴ カルトプログラミングの一例であることをお勧めします。
反例
これが最適化であるアーキテクチャはおそらくいくつかありますが、私は少なくとも 1 つのアーキテクチャを知っています。由緒あるTransputerアーキテクチャには、等しいおよびより大きいか等しいのマシン コード命令しかなかったため、すべての比較はこれらのプリミティブから構築する必要がありました。
それでも、ほとんどすべての場合、コンパイラは、実際にはどの比較も他の比較よりも有利になるような方法で評価命令を順序付けることができました。ただし、最悪の場合、オペランド スタックの上位 2 つの項目を交換するために反転命令 (REV) を追加する必要がある場合があります。これは、実行に 1 サイクルかかる 1 バイト命令であったため、オーバーヘッドが最小でした。
概要
このようなマイクロ最適化が最適化であるかアンチ最適化であるかは、使用している特定のアーキテクチャに依存するため、通常、アーキテクチャ固有のマイクロ最適化を使用する習慣を身につけるのは悪い考えです。そうしないと、本能的にそうすることが不適切であり、これがまさにあなたが読んでいる本が主張していることのように見えるときに使用してください.
于 2012-08-31T18:33:16.977 に答える
15
彼らは同じ速度を持っています。たぶん、いくつかの特別なアーキテクチャでは、彼/彼女が言ったことは正しいですが、x86ファミリでは、少なくとも私はそれらが同じであることを知っています。これを行うために、CPUは減算（a --b）を実行してから、フラグレジスタのフラグをチェックします。そのレジスタの2ビットはZF（ゼロフラグ）およびSF（符号フラグ）と呼ばれ、1回のマスク操作で実行されるため、1サイクルで実行されます。
于 2012-08-27T08:25:11.757 に答える
14
これは、C がコンパイルされる基盤となるアーキテクチャに大きく依存します。一部のプロセッサーおよびアーキテクチャーには、異なるサイクル数で実行される等しい、または以下および等しいという明示的な命令がある場合があります。
ただし、コンパイラがそれを回避して無関係にする可能性があるため、これはかなり珍しいことです。
于 2012-08-27T02:15:06.053 に答える
6
違いがあっても気が付かないはずです。さらに、実際には、いくつかの魔法の定数を使用する場合を除き、追加a + 1またはa - 1条件を維持する必要があります。これは、非常に悪い習慣です。
于 2012-08-27T02:17:05.393 に答える
5
a < 901この回答の最初のバージョンを書いたとき、定数vs.の具体的な例ではなく、 < vs. <= 一般的なタイトルの質問だけを見ていましたa <= 900。<多くのコンパイラは常にとの間で変換することにより定数の大きさを縮小します<=。たとえば、x86 即値オペランドは -128..127 の 1 バイト エンコーディングが短いためです。
ARM の場合、即値としてエンコードできるかどうかは、狭いフィールドを単語内の任意の位置に回転できるかどうかにかかっています。cmp r0, #0x00f000そのため、エンコード可能ですが、そうでcmp r0, #0x00efffはありません。そのため、比較とコンパイル時の定数の小さくするルールは、ARM に常に適用されるわけではありません。AArch64 は、32 ビット ARM および Thumb モードとは異なり、cmpおよびのような命令に対して、任意のローテーションではなく、12 ずつシフトするかどうかのいずれかです。cmn
< vs. <= 一般に、実行時変数の条件を含む
ほとんどのマシンのアセンブリ言語では、 の比較と<=の比較のコストは同じです<。これは、分岐するか、ブーリアン化して 0/1 整数を作成するか、分岐なしの選択操作 (x86 CMOV など) の述語として使用するかに関係なく適用されます。他の回答は、質問のこの部分のみに対処しています。
しかし、この質問は、オプティマイザへの入力である C++ 演算子に関するものです。 通常、どちらも同じように効率的です。コンパイラは asm で実装する比較を常に変換できるため、この本のアドバイスは完全に偽物に聞こえます。<=ただし、コンパイラが最適化できないものを using が誤って作成する可能性があるという例外が少なくとも 1 つあります。
ループの条件として、ループが無限でないことをコンパイラが証明するのを止める場合、<=と質的に異なる場合があります。< これにより、自動ベクトル化が無効になり、大きな違いが生じる可能性があります。
符号なしオーバーフローは、符号付きオーバーフロー (UB) とは異なり、基数 2 のラップ アラウンドとして明確に定義されています。符号付きループ カウンターは、一般に、符号付きオーバーフロー UB が発生しないことに基づいて最適化するコンパイラを使用すると安全++i <= sizeです。最終的には常に false になります。(すべての C プログラマーが未定義の動作について知っておくべきこと)
void foo(unsigned size) {
unsigned upper_bound = size - 1; // or any calculation that could produce UINT_MAX
for(unsigned i=0 ; i <= upper_bound ; i++)
...
コンパイラは、未定義の動作につながるものを除いて、可能なすべての入力値に対して C++ ソースの (定義され、法的に観察可能な) 動作を維持する方法でのみ最適化できます。
(単純なi <= sizeものも問題を引き起こしますが、上限を計算することは、気にしないがコンパイラーが考慮しなければならない入力の無限ループの可能性を誤って導入するより現実的な例だと思いました。)
この場合、size=0は につながりupper_bound=UINT_MAX、i <= UINT_MAXは常に真です。したがって、このループは に対して無限でsize=0あり、コンパイラーはそれを尊重する必要があります。プログラマーはおそらく size=0 を渡すつもりはありませんが。コンパイラがこの関数を呼び出し元にインライン化して、size=0 が不可能であることを証明できる場合、素晴らしいことですi < size。
Asm likeは、ループ内で の実際の値が必要ない場合にif(!size) skip the loop; do{...}while(--size);、ループを最適化するための通常効率的な方法の 1 つです (なぜループは常に "do...while" スタイル (テール ジャンプ) にコンパイルされるのですか? )。for( i<size )i
ただし、それを無限にすることはできません。{} を指定して入力するとsize==0、2^n 回の繰り返しになります。 {} ( for ループ C ですべての符号なし整数を反復すると、ゼロを含むすべての符号なし整数のループを表現できますが、asm のようにキャリー フラグがないと簡単ではありません。)
ループ カウンターのラップアラウンドが発生する可能性があるため、最新のコンパイラはしばしば「あきらめ」、積極的に最適化することはありません。
例: 1 から n までの整数の合計
unsigned を使用i <= nsum(1 .. n)n * (n+1) / 2すると、Gauss の式に基づいて閉じた形式でループを最適化する clang のイディオム認識が無効になります。
unsigned sum_1_to_n_finite(unsigned n) {
unsigned total = 0;
for (unsigned i = 0 ; i < n+1 ; ++i)
total += i;
return total;
}
Godbolt コンパイラ エクスプローラでの clang7.0 および gcc8.2 からの x86-64 asm
# clang7.0 -O3 closed-form
cmp edi, -1 # n passed in EDI: x86-64 System V calling convention
je .LBB1_1 # if (n == UINT_MAX) return 0; // C++ loop runs 0 times
# else fall through into the closed-form calc
mov ecx, edi # zero-extend n into RCX
lea eax, [rdi - 1] # n-1
imul rax, rcx # n * (n-1) # 64-bit
shr rax # n * (n-1) / 2
add eax, edi # n + (stuff / 2) = n * (n+1) / 2 # truncated to 32-bit
ret # computed without possible overflow of the product before right shifting
.LBB1_1:
xor eax, eax
ret
しかし、単純なバージョンでは、clang からダム ループが発生するだけです。
unsigned sum_1_to_n_naive(unsigned n) {
unsigned total = 0;
for (unsigned i = 0 ; i<=n ; ++i)
total += i;
return total;
}
# clang7.0 -O3
sum_1_to_n(unsigned int):
xor ecx, ecx # i = 0
xor eax, eax # retval = 0
.LBB0_1: # do {
add eax, ecx # retval += i
add ecx, 1 # ++1
cmp ecx, edi
jbe .LBB0_1 # } while( i<n );
ret
GCC はどちらの方法でもクローズド フォームを使用しないため、ループ条件の選択は実際には問題になりません。iXMM レジスターの要素で 4 つの値を並列に実行して、SIMD 整数加算で自動ベクトル化します。
# "naive" inner loop
.L3:
add eax, 1 # do {
paddd xmm0, xmm1 # vect_total_4.6, vect_vec_iv_.5
paddd xmm1, xmm2 # vect_vec_iv_.5, tmp114
cmp edx, eax # bnd.1, ivtmp.14 # bound and induction-variable tmp, I think.
ja .L3 #, # }while( n > i )
"finite" inner loop
# before the loop:
# xmm0 = 0 = totals
# xmm1 = {0,1,2,3} = i
# xmm2 = set1_epi32(4)
.L13: # do {
add eax, 1 # i++
paddd xmm0, xmm1 # total[0..3] += i[0..3]
paddd xmm1, xmm2 # i[0..3] += 4
cmp eax, edx
jne .L13 # }while( i != upper_limit );
then horizontal sum xmm0
and peeled cleanup for the last n%3 iterations, or something.
nまた、非常に小さい、および/または無限ループの場合に使用すると思われる単純なスカラーループもあります。
ところで、これらのループは両方とも、ループ オーバーヘッドで命令 (および Sandybridge ファミリの CPU では uop) を浪費します。 sub eax,1/ cmp/jccjnzの代わりに/ のadd eax,1方が効率的です。2 つではなく 1 つの uop (sub/jcc または cmp/jcc のマクロ融合後)。両方のループの後のコードは、EAX を無条件に書き込むため、ループ カウンターの最終値を使用していません。
于 2019-01-20T11:30:11.860 に答える
4
余分な文字があるとコード処理が少し遅くなるため、この行はほとんどのスクリプト言語で正しいと言えます。ただし、一番上の回答が指摘したように、C++ では効果がないはずであり、スクリプト言語で行われることはおそらく最適化についてそれほど心配する必要はありません。
于 2012-08-29T02:47:03.703 に答える