2つの整数を交換したいのですが、これら2つの実装のどちらが高速になるかを知りたいです。一時変数を使用した明らかな方法：
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
または、ほとんどの人が見たことがあると確信しているxorバージョン：
void swap(int* a, int* b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
最初のレジスタは追加のレジスタを使用しているように見えますが、2番目のレジスタは3つのロードとストアを実行し、最初のレジスタはそれぞれ2つしか実行しません。誰かがどちらが速いのか、そしてその理由を教えてもらえますか？なぜもっと重要なのか。
2番は、それを行う「賢い」方法であるとよく言われます。実際には、プログラマーの明確な目的（2つの変数の交換）があいまいになるため、速度が遅くなる可能性があります。これは、コンパイラが実際のアセンブラ操作を使用してスワップするように最適化できないことを意味します。また、オブジェクトに対してビット単位のxorを実行する機能も前提としています。
1番に固執します。これは最も一般的で最も理解しやすいスワップであり、簡単にテンプレート化/一般化できます。
このウィキペディアのセクションでは、問題について非常によく説明しています。http: //en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice
a と b が同じアドレスを指している場合、XOR メソッドは失敗します。最初の XOR は、両方の変数が指すメモリ アドレスのすべてのビットをクリアするため、初期値に関係なく、関数が (*a == *b == 0) を返すと。
Wiki ページの詳細: XOR スワップ アルゴリズム
この問題が発生する可能性は低いですが、予期しない瞬間に失敗する巧妙な方法ではなく、動作が保証されている方法を使用することを常に好みます。
最新のプロセッサでは、大きな配列を並べ替えるときに次のものを使用でき、速度に違いはありません。
void swap (int *a, int *b)
{
for (int i = 1 ; i ; i <<= 1)
{
if ((*a & i) != (*b & i))
{
*a ^= i;
*b ^= i;
}
}
}
あなたの質問の本当に重要な部分は「なぜ？」です。部。さて、20年前の8086日にさかのぼると、上記は実際のパフォーマンスキラーでしたが、最新のPentiumでは、投稿した2つに匹敵する速度になります。
その理由は純粋にメモリにあり、CPUとは何の関係もありません。
メモリ速度と比較したCPU速度は、天文学的に上昇しています。メモリへのアクセスは、アプリケーションパフォーマンスの主要なボトルネックになっています。すべてのスワップアルゴリズムは、データがメモリからフェッチされるのを待つためにほとんどの時間を費やします。最新のOSには、最大5レベルのメモリを搭載できます。
並べ替えアルゴリズムは、通常、非常に順序付けられていない方法でメモリにアクセスするため、メモリアクセスを悪化させ、L2、RAM、またはHDからデータをフェッチする非効率的なオーバーヘッドが発生します。
したがって、スワップメソッドを最適化することは本当に無意味です-数回だけ呼び出された場合、呼び出しの数が少ないために非効率性が隠され、大量に呼び出された場合、キャッシュミスの数のために非効率性が隠されます（ CPUは、L2（1サイクル）、L3（10サイクル）、RAM（100サイクル）、HD（！））からデータを取得する必要があります。
本当に行う必要があるのは、swapメソッドを呼び出すアルゴリズムを調べることです。これは簡単なことではありません。Big-O表記は便利ですが、小さいnの場合、O（n）はO（log n）よりも大幅に高速になる可能性があります。（これに関するCodingHorrorの記事があると確信しています。）また、多くのアルゴリズムには、コードが必要以上に機能する縮退したケースがあります（ほぼ順序付けられたデータでqsortを使用すると、早期チェックを使用したバブルソートよりも遅くなる可能性があります）。したがって、アルゴリズムとそれが使用しているデータを分析する必要があります。
これは、コードを分析する方法につながります。プロファイラーは便利ですが、結果を解釈する方法を知っている必要があります。1回の実行で結果を収集することは絶対に避けてください。テストアプリケーションは、OSによって途中でハードディスクにページングされた可能性があるため、常に多くの実行で平均結果が得られます。常にプロファイルリリース、最適化されたビルド、プロファイリングデバッグコードは無意味です。
元の質問に関して-どちらが速いですか？-それは、ドアミラーのサイズと形状を見て、フェラーリがランブルジーニよりも速いかどうかを判断しようとするようなものです。
xorなどのビット演算は通常、読者が視覚化するのが非常に難しいため、最初の方が高速です。
もちろん、最も重要な部分である、より速く理解する;）
@Harry について: 次の理由により、関数をマクロとして実装しないでください。
タイプセーフティ。なにもない。次の例では、コンパイル時にのみ警告が生成されますが、実行時には失敗します。
float a=1.5f,b=4.2f;
swap (a,b);
テンプレート化された関数は常に正しい型になります (そして、警告をエラーとして扱わないのはなぜですか?)。
編集: C にはテンプレートがないため、型ごとに個別のスワップを記述するか、ハッキーなメモリ アクセスを使用する必要があります。
テキストの差し替えです。以下は実行時に失敗します (今回は、コンパイラの警告なし)。
int a=1,temp=3;
swap (a,temp);
関数ではありません。したがって、qsort などの引数として使用することはできません。
副作用。マクロには副作用があります！検討：
int &f1 ();
int &f2 ();
void func ()
{
swap (f1 (), f2 ());
}
ここで、f1 と f2 は 2 回呼び出されます。
編集：厄介な副作用のあるACバージョン：
int a[10], b[10], i=0, j=0;
swap (a[i++], b[j++]);
マクロ:ノーと言ってください!
編集:これが、注意して使用する警告としてコード内で目立つように、マクロ名を大文字で定義することを好む理由です。
EDIT2: Leahn Novash のコメントに答えるには:
コンパイラによってバイト シーケンスに変換されるインライン化されていない関数 f があると仮定すると、次のようにバイト数を定義できます。
bytes = C(p) + C(f)
ここで、C() は生成されるバイト数、C(f) は関数のバイト、C(p) は「ハウスキーピング」コードのバイト、コンパイラが関数に追加するプリアンブルとポストアンブル (作成関数のスタック フレームの破棄など)。ここで、関数 f を呼び出すには C(c) バイトが必要です。関数が n 回呼び出される場合、コードの合計サイズは次のようになります。
size = C(p) + C(f) + n.C(c)
次に、関数をインライン化しましょう。関数の「ハウスキーピング」である C(p) は、関数が呼び出し元のスタック フレームを使用できるため、ゼロになります。C(c) もゼロです。呼び出しオペコードがないからです。ただし、 f は呼び出しがあった場所に複製されます。したがって、コードの合計サイズは次のようになります。
size = n.C(f)
ここで、C(f) が C(c) より小さい場合、全体の実行可能サイズは縮小されます。ただし、C(f) が C(c) より大きい場合、コード サイズは増加します。C(f) と C(c) が類似している場合は、C(p) も考慮する必要があります。
したがって、C(f) と C(c) は何バイト生成しますか。最も単純な C++ 関数はゲッターです。
void GetValue () { return m_value; }
これにより、おそらく 4 バイトの命令が生成されます。
mov eax,[ecx + offsetof (m_value)]
これは 4 バイトです。呼び出し命令は 5 バイトです。したがって、全体的なサイズの節約があります。関数がより複雑な場合、たとえばインデクサー ("return m_value [index];") や計算 ("return m_value_a + m_value_b;") の場合、コードは大きくなります。
この質問に出くわし、XOR メソッドを使用することにした人のために。関数呼び出しのオーバーヘッドを回避するために、関数をインライン化するか、マクロを使用することを検討する必要があります。
#define swap(a, b) \
do { \
int temp = a; \
a = b; \
b = temp; \
} while(0)
マクロへの憎しみを理解していませんでした。適切に使用すると、コードをよりコンパクトで読みやすくすることができます。ほとんどのプログラマーは、マクロは注意して使用する必要があることを知っていると思います。重要なのは、特定の呼び出しが関数呼び出しではなくマクロであることを明確にすることです (すべて大文字)。が一貫して問題の原因である場合SWAP(a++, b++);、おそらくプログラミングはあなたに向いていません。
確かに、xor トリックは、最初の 5000 回表示されるまでは優れていますが、信頼性を犠牲にして一時的に保存するだけです。上記で生成されたアセンブリを見ると、レジスタは保存されますが、依存関係が作成されます。また、暗黙のロックプレフィックスがあるため、xchg はお勧めしません。
最も賢いコードによって引き起こされた非生産的な最適化とデバッグに数え切れないほどの時間を無駄にした後、最終的には全員が同じ場所にたどり着きます。
#define SWAP(type, a, b) \
do { type t=(a);(a)=(b);(b)=t; } while (0)
void swap(size_t esize, void* a, void* b)
{
char* x = (char*) a;
char* y = (char*) b;
char* z = x + esize;
for ( ; x < z; x++, y++ )
SWAP(char, *x, *y);
}
あなたは間違ったことを最適化しています。どちらも非常に高速であるため、測定可能な違いを得るために何十億回も実行する必要があります。
そして、ほぼすべてのものがパフォーマンスにはるかに大きな影響を及ぼします。たとえば、スワップしている値がメモリ内で最後に触れた値に近い場合、それらはプロセッサキャッシュにあるとは言えません。そうでない場合は、にアクセスする必要があります。メモリ-これは、プロセッサ内で実行する操作よりも数桁遅くなります。
とにかく、ボトルネックは、数値を交換する方法よりも、非効率的なアルゴリズムまたは不適切なデータ構造（または通信オーバーヘッド）である可能性がはるかに高くなります。
実際に知る唯一の方法はテストすることであり、その答えは使用しているコンパイラとプラットフォームによって異なる場合さえあります。最近の最新のコンパイラはコードの最適化に非常に優れており、自分の方法が本当に高速であることを証明できない限り、コンパイラの裏をかこうとするべきではありません。
そうは言っても、＃1よりも＃2を選択するのに十分な理由があるはずです. #1 のコードははるかに読みやすいため、常に最初に選択する必要があります。その変更を行う必要があることを証明できる場合にのみ #2 に切り替えてください。そうする場合は、何が起こっているのか、なぜそれを非自明な方法で行ったのかを説明するためにコメントしてください。
逸話として、私は時期尚早に最適化するのが好きな何人かの人々と一緒に仕事をしていますが、それは本当におぞましく保守不可能なコードを作ってしまいます。また、コードを単純ではない方法で記述して、コードを最適化するコンパイラーの機能を妨害しているため、多くの場合、彼らは自分自身を撃っていることに賭けても構わないと思っています。
最高評価の回答はすべて、実際には決定的な「事実」ではありません...彼らは推測している人々です！
コンパイラによって生成された出力アセンブリを調べて、どのコードがより少ないアセンブリ命令で実行されるかを確認できるため、どのコードの実行に必要なアセンブリ命令が少ないかを明確に知ることができます。
フラグ「gcc-std=c99-S-O3lookingAtAsmOutput.c」を使用してコンパイルしたcコードは次のとおりです。
#include <stdio.h>
#include <stdlib.h>
void swap_traditional(int * restrict a, int * restrict b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void swap_xor(int * restrict a, int * restrict b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
int main() {
int a = 5;
int b = 6;
swap_traditional(&a,&b);
swap_xor(&a,&b);
}
swap_traditional（）のASM出力は>>> 11 <<<命令（ "leave"、 "ret"、 "size"を含まない）を取ります：
.globl swap_traditional
.type swap_traditional, @function
swap_traditional:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %edx
movl 12(%ebp), %ecx
pushl %ebx
movl (%edx), %ebx
movl (%ecx), %eax
movl %ebx, (%ecx)
movl %eax, (%edx)
popl %ebx
popl %ebp
ret
.size swap_traditional, .-swap_traditional
.p2align 4,,15
swap_xor（）のASM出力は>>> 11 <<<「leave」と「ret」を含まない命令を取ります：
.globl swap_xor
.type swap_xor, @function
swap_xor:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %ecx
movl 12(%ebp), %edx
movl (%ecx), %eax
xorl (%edx), %eax
movl %eax, (%ecx)
xorl (%edx), %eax
xorl %eax, (%ecx)
movl %eax, (%edx)
popl %ebp
ret
.size swap_xor, .-swap_xor
.p2align 4,,15
アセンブリ出力の要約：
swap_traditional（）は11命令を取ります
swap_xor（）は11命令を取ります
結論：
どちらの方法も同じ量の命令を使用して実行するため、このハードウェアプラットフォームではほぼ同じ速度です。
教訓：
小さなコードスニペットがある場合、asm出力を確認することは、コードを迅速に反復し、最速の（つまり最小の命令）コードを見つけるのに役立ちます。また、コードを変更するたびにプログラムを実行する必要がないため、時間を節約できます。最後にプロファイラーを使用してコード変更を実行するだけで、コード変更がより高速であることを示すことができます。
私はこの方法を、速度を必要とする重いDSPコードによく使用します。
あなたがしなければならない場合を除いて、私はポインターでそれをしません。ポインターのエイリアシングの可能性があるため、コンパイラーはそれらをうまく最適化できません(ただし、ポインターが重複しない場所を指していることを保証できる場合、GCC には少なくともこれを最適化するための拡張機能があります)。
それは非常に単純な操作であり、関数呼び出しのオーバーヘッドが大きいためです。
生の速度と最適化の可能性が必要な場合は、マクロを使用するのが最善の方法です。GCC では、組み込み型を使用してtypeof()、任意の組み込み型で動作する柔軟なバージョンを作成できます。
このようなもの：
#define swap(a,b) \
do { \
typeof(a) temp; \
temp = a; \
a = b; \
b = temp; \
} while (0)
...
{
int a, b;
swap(a, b);
unsigned char x, y;
swap(x, y); /* works with any type */
}
他のコンパイラを使用する場合、または標準 C89/99 に厳密に準拠する必要がある場合は、タイプごとに個別のマクロを作成する必要があります。
優れたコンパイラは、ローカル/グローバル変数を引数として呼び出された場合、コンテキストを考慮して、これを可能な限り積極的に最適化します。
述べたようにあなたの質問に答えるには、このコードが実行される特定の CPU の命令タイミングを掘り下げる必要があるため、システム内のキャッシュの状態と、コンパイラ。選択したプロセッサが実際にどのように機能するかを理解するという観点からは、興味深い有用な演習ですが、現実の世界ではその違いはごくわずかです。
x=x+y-(y=x);
float x; cout << "X:"; cin >> x;
float y; cout << "Y:" ; cin >> y;
cout << "---------------------" << endl;
cout << "X=" << x << ", Y=" << y << endl;
x=x+y-(y=x);
cout << "X=" << x << ", Y=" << y << endl;
私の意見では、このようなローカルの最適化は、プラットフォームに密接に関連していると見なされるべきです. これを 16 ビット uC コンパイラーまたは x64 をターゲットとして gcc でコンパイルする場合、大きな違いが生じます。
特定のターゲットを念頭に置いている場合は、両方を試して、生成された asm コードを確認するか、両方の方法でアプリケーションをプロファイリングして、プラットフォームでどちらが実際に高速かを確認してください。
インラインアセンブラを使用して、次のことを実行できる場合 (疑似アセンブラ):
PUSH A
A=B
POP B
パラメータの受け渡しやスタックの修正コードなどを大幅に節約できます。
コンパイラがインライン アセンブラをサポートしていて、ターゲットが 32 ビット x86 である場合、XCHG 命令がおそらくこれを行うための最良の方法です...パフォーマンスを本当に気にするのであれば。
MSVC++ で動作するメソッドは次のとおりです。
#include <stdio.h>
#define exchange(a,b) __asm mov eax, a \
__asm xchg eax, b \
__asm mov a, eax
int main(int arg, char** argv)
{
int a = 1, b = 2;
printf("%d %d --> ", a, b);
exchange(a,b)
printf("%d %d\r\n", a, b);
return 0;
}
両方のスワップを（マクロとして）、私が遊んでいる手書きのクイックソートに配置しました。XOR バージョンは、一時変数を使用したバージョン (0.6 秒) よりもはるかに高速 (0.1 秒) でした。ただし、XOR は配列内のデータを破損しました (おそらく、Ant が言及したのと同じアドレスです)。
ファット ピボット クイックソートだったので、XOR バージョンの速度は、おそらく配列の大部分を同じにすることによるものです。私は、最も理解しやすいスワップの 3 番目のバージョンを試しましたが、単一の一時バージョンと同じ時間がありました。
acopy=a;
bcopy=b;
a=bcopy;
b=acopy;
[各スワップの周りに if ステートメントを配置しただけなので、それ自体とスワップしようとしません。XOR は他のものと同じ時間 (0.6 秒) かかります]
void swap(int* a, int* b)
{
*a = (*b - *a) + (*b = *a);
}
// 私の C は少し錆びているので、* が正しいことを願っています :)
別の美しい方法。
#define Swap( a, b ) (a)^=(b)^=(a)^=(b)
アドバンテージ
関数呼び出し不要で手軽。
欠点：
両方の入力が同じ変数の場合、これは失敗します。整数変数でのみ使用できます。