关于性能：在C中交换值的最快方法是什么？

What is the fastest way to swap values in C?

我想交换两个整数，并且我想知道这两个实现中的哪个会更快：
带有临时变量的明显方法是：

1
2
3
4
5
6

void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}

或大多数人都看过的xor版本：

1
2
3
4
5
6

void swap(int* a, int* b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}

似乎第一个使用了一个额外的寄存器，但是第二个执行了三个加载和存储，而第一个只执行了两个。有人可以告诉我哪个更快，为什么？为什么更重要。

数字2通常被引用为这样做的"灵巧"方式。实际上，它很可能会变慢，因为它掩盖了程序员的明确目标-交换两个变量。这意味着编译器无法对其进行优化以使用实际的汇编程序op进行交换。它还假定可以对对象执行按位异或。

坚持第一，这是最通用，最易懂的交换，可以轻松地进行模板化/通用化。

这个维基百科部分很好地解释了这些问题：
http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice

如果a和b指向相同的地址，则XOR方法将失败。第一个XOR将清除两个变量所指向的存储器地址上的所有位，因此一旦函数返回(* a == * b == 0)，无论初始值如何。

Wiki页面上的更多信息：
XOR交换算法

尽管不太可能出现此问题，但我总是更喜欢使用保证有效的方法，而不是在意外情况下失败的聪明方法。

在现代处理器上，对大型数组进行排序时可以使用以下命令，但速度没有差别：

1
2
3
4
5
6
7
8
9
10
11

void swap (int *a, int *b)
{
for (int i = 1 ; i ; i <<= 1)
{
if ((*a & i) != (*b & i))
{
*a ^= i;
*b ^= i;
}
}
}

您问题中最重要的部分是"为什么？"部分。现在，可以追溯到2086年的8086天，上面的内容确实是性能的杀手,，但是在最新的Pentium上，这是与您发布的两款产品相匹配的速度。

原因仅在于内存，与CPU无关。

与内存速度相比，CPU速度有了天文数字的增长。访问内存已成为应用程序性能的主要瓶颈。所有交换算法将花费大部分时间等待从内存中获取数据。现代操作系统最多可以具有5种内存级别：

缓存级别1-以与CPU相同的速度运行，访问时间可以忽略，但是很小
缓存级别2-运行速度比L1慢一点，但更大，并且具有更大的访问开销(通常，数据需要先移至L1)
缓存级别3-(并非始终存在)通常在CPU外部，比L2慢且更大
RAM-主系统内存，通常实现管道，因此读取请求中存在延迟(CPU请求数据，发送到RAM的消息，RAM获取数据，RAM向CPU发送数据)
硬盘-当没有足够的RAM时，数据被分页到HD，这确实很慢，实际上不受CPU的控制。

排序算法将使内存访问变得更糟，因为它们通常以非常无序的方式访问内存，从而导致从L2，RAM或HD获取数据的开销很低。

因此，优化交换方法实际上是没有意义的-如果只调用几次，则由于调用数量少而导致任何低效率被隐藏，如果被调用很多，则由于高速缓存未命中的数量而导致任何低效率被隐藏(其中CPU需要从L2(1个周期)，L3(10个周期)，RAM(100个周期)，HD(！)中获取数据。

您真正需要做的是查看调用swap方法的算法。这不是一件小事。尽管Big-O表示法很有用，但对于小n而言，O(n)可能比O(log n)快得多。 (我肯定有关于此的CodingHorror文章。)而且，许多算法在简并的情况下，代码的作用超出了必要(在几乎有序的数据上使用qsort可能比带有早期检查的冒泡排序要慢)。因此，您需要分析算法及其使用的数据。

这导致了如何分析代码。探查器很有用，但您确实需要知道如何解释结果。切勿使用单次运行来收集结果，始终将多次执行中的结果平均化-因为测试应用程序可能已在操作系统中途被分页到硬盘。始终进行概要文件发布，优化构建，分析调试代码都是没有意义的。

至于最初的问题-哪个更快？ -就像通过观察后视镜的大小和形状来找出法拉利是否比兰博基尼更快。

第一种是更快的，因为按位运算(例如xor)通常很难让读者看到。

当然更快地理解，这是最重要的部分;)

关于@Harry：
由于以下原因，切勿将函数实现为宏：

类型安全。空无一人。以下内容仅在编译时生成警告，但在运行时失败：

1 2	float a=1.5f,b=4.2f; swap (a,b);

模板函数将始终是正确的类型(为什么不将警告视为错误？)。

编辑：由于C中没有模板，因此您需要为每种类型编写一个单独的交换或使用一些简单的内存访问。

这是文本替换。以下内容在运行时失败(这次，没有编译器警告)：

1 2	int a=1,temp=3; swap (a,temp);

这不是功能。因此，它不能用作qsort之类的参数。

编译器很聪明。我的意思是非常聪明。由真正聪明的人制造。他们可以内联函数。即使在链接时(这更加聪明)。不要忘记，内联会增加代码大小。大代码意味着在提取指令时出现更多的高速缓存未命中的机会，这意味着代码会变慢。

副作用。宏有副作用！考虑：

1
2
3
4
5
6

int &f1 ();
int &f2 ();
void func ()
{
swap (f1 (), f2 ());
}

在这里，f1和f2将被调用两次。

编辑：具有令人讨厌的副作用的C版本：

1 2	int a[10], b[10], i=0, j=0; swap (a[i++], b[j++]);

宏：只是说不！

编辑：这就是为什么我更喜欢在大写字母中定义宏名称，以便它们在代码中脱颖而出，作为谨慎使用的警告。

编辑2：回答莱恩·诺瓦什的评论：

假设我们有一个非内联函数f，它由编译器转换为字节序列，然后我们可以定义字节数：

1	bytes = C(p) + C(f)

其中C()给出产生的字节数，C(f)是该函数的字节，C(p)是``管家''代码的字节，编译器添加到函数的前同步码和后同步码(创建并破坏函数的堆栈框架等)。现在，调用函数f需要C(c)个字节。如果该函数被调用n次，则总代码大小为：

1	size = C(p) + C(f) + n.C(c)

现在让我们内联函数。由于函数可以使用调用方的堆栈框架，因此函数的"内务处理" C(p)变为零。 C(c)也是零，因为现在没有调用操作码。但是，无论哪里有电话，f都会被复制。因此，总代码大小为：

1	size = n.C(f)

现在，如果C(f)小于C(c)，则将减小整个可执行文件的大小。但是，如果C(f)大于C(c)，则代码大小将增加。如果C(f)和C(c)相似，则还需要考虑C(p)。

因此，C(f)和C(c)产生多少字节。好吧，最简单的C ++函数就是吸气剂：

1	void GetValue () { return m_value; }

这可能会生成四字节指令：

1	mov eax,[ecx + offsetof (m_value)]

这是四个字节。呼叫指令为五个字节。因此，总体上节省了空间。如果函数更复杂，例如说一个索引器(" return m_value [index];")或计算(" return m_value_a + m_value_b;")，则代码将更大。

对于那些偶然发现此问题并决定使用XOR方法的人。您应该考虑内联函数或使用宏以避免函数调用的开销：

1
2
3
4
5
6

#define swap(a, b) \
do { \
int temp = a; \
a = b; \
b = temp; \
} while(0)

您正在优化错误的东西，这两者都应该如此之快，以至于您必须运行数十亿次才能获得任何可测量的差异。

几乎任何事情都会对您的性能产??生更大的影响，例如，如果要交换的值在内存中接近您所触摸的最后一个值，则它们很可能存在于处理器缓存中，否则，您将必须访问内存-这比您在处理器内部执行的任何操作都要慢几个数量级。

无论如何，与交换数字的方式相比，瓶颈更有可能是效率低下的算法或不合适的数据结构(或通信开销)。

从不了解对宏的憎恨。如果使用得当，它们可以使代码更紧凑，更易读。我相信大多数程序员都知道应谨慎使用宏，重要的是要明确指出特定的调用是宏而不是函数调用(全部大写)。如果SWAP(a++, b++);是一致的问题根源，则可能不适合您进行编程。

诚然，xor技巧在您看到的头5000次中就很整齐，但是它真正要做的只是节省一个临时性，而牺牲了可靠性。查看上面生成的程序集可以保存寄存器，但会创建依赖项。另外，我不建议xchg，因为它具有隐式锁前缀。

最终，在无数小时的浪费之后，我们所有人来到了同一个地方，这些浪费是由我们最聪明的代码导致的非生产性优化和调试所致-保持简单。

1
2
3
4
5
6
7
8
9
10
11
12

#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);
}

评分最高的答案实际上并不是确定的"事实"……他们是在猜测的人！

您可以确切地知道哪个代码需要执行较少的汇编指令，因为您可以查看由编译器生成的输出汇编，并查看以较少的汇编指令执行的输出！

这是我用标志" gcc -std = c99 -S -O3 lookingAtAsmOutput.c"编译的C代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#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")：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

.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"：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

.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代码，我经常使用这种方法。

对于现代CPU体系结构，方法1将比方法2更快，可读性也更高。

在现代CPU架构上，XOR技术比使用临时变量进行交换要慢得多。原因之一是现代CPU努力通过指令管道并行执行指令。在XOR技术中，每个操作的输入取决于前一个操作的结果，因此必须严格按顺序执行。如果效率非常令人关注，建议在目标体系结构上测试XOR技术和临时变量交换的速度。在此处查看更多信息。

编辑：方法2是就地交换的一种方式(即不使用额外的变量)。为了使这个问题更完整，我将使用+/-添加另一个就地交换。

1
2
3
4
5
6
7
8
9

void swap(int* a, int* b)
{
if (a != b) // important to handle a/b share the same reference
{
*a = *a+*b;
*b = *a-*b;
*a = *a-*b;
}
}

真正知道的唯一方法是对其进行测试，答案甚至可能取决于您所使用的编译器和平台。如今，现代的编译器确实擅长优化代码，除非您可以证明自己的方法确实更快，否则您永远不要试图超越编译器。

话虽如此，您最好有一个很好的理由选择＃2而不是＃1。＃1中的代码更具可读性，因此应始终首先选择它。仅在可以证明需要进行更改时才切换到＃2，并且如果需要，请进行更改-对其进行评论以解释发生了什么以及为什么以非显而易见的方式进行更改。

作为轶事，我与几个喜欢过早优化的人一起工作，它使代码变得非常丑陋，难以维护。我也很愿意打赌，他们经常不停地射击自己，因为他们阻碍了编译器通过非直接方式编写代码来优化代码的能力。

除非您必须使用指针，否则我不会这样做。由于存在指针混叠的可能性，编译器无法很好地优化它们(尽管如果可以保证指针指向不重叠的位置，则GCC至少具有扩展功能可以对此进行优化)。

而且我根本不会使用函数，因为这是一个非常简单的操作，并且函数调用的开销很大。

如果您需要原始速度和优化的可能性，则最好的方法是使用宏。在GCC中，您可以使用内置的typeof()来制作适用于任何内置类型的灵活版本。

像这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#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);

1
2
3
4
5
6
7

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代码，或使用这两种方法来分析您的应用，然后看看在您的平台上哪个实际上更快。

如果可以使用某些内联汇编程序并执行以下操作(伪汇编程序)：

1
2
3

PUSH A
A=B
POP B

您将节省大量参数传递和堆栈修复代码等。

如果您的编译器支持内联汇编器，并且目标是32位x86，则XCHG指令可能是实现此目标的最佳方法……如果您确实非常在意性能。

这是与MSVC ++一起使用的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#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

", a, b);
return 0;
}

我只是将两个交换(作为宏)放在我一直在玩的手写quicksort中。 XOR版本比带有临时变量的版本(0.6sec)快得多(0.1sec)。但是，XOR确实破坏了数组中的数据(可能与Ant提到的地址相同)。

由于XOR版本是繁琐的快速排序，因此XOR版本的速度可能来自使数组的大部分相同。我尝试了最容易理解的第三个交换版本，它与单个临时版本具有相同的时间。

1
2
3
4

acopy=a;
bcopy=b;
a=bcopy;
b=acopy;

[我只是在每次交换周围放置了一个if语句，因此它不会尝试自身交换，并且XOR现在与其他交换所花的时间相同(0.6秒)]

下面的代码将执行相同的操作。此代码段是经过优化的编程方式，因为它不使用任何第3个变量。

1
2
3

x = x ^ y;
y = x ^ y;
x = x ^ y;

1
2
3
4