C中交换值的最快方法是什么?

我想交换两个整数,我想知道这两个实现中的哪一个会更快:tempvariables的显而易见的方法:

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

似乎第一个使用额外的寄存器,但第二个是做三个加载和存储,而第一个只做两个。 有人能告诉我哪个更快,为什么? 为什么更重要。

如果a和b指向相同的地址,则XOR方法失败。 第一个异或将清除由这两个variables指向的内存地址处的所有位,所以一旦该函数返回(* a == * b == 0),无论初始值如何。

更多维基页面上的信息: XOR交换algorithm

虽然这个问题不大可能出现,但我总是更喜欢使用保证可行的方法,而不是在意外时刻失败的巧妙方法。

2号被经常引用为“聪明”的做法。 事实上,它很可能是慢的,因为它掩盖了程序员的明确目标 – 交换两个variables。 这意味着编译器不能优化它以使用实际的汇编器操作来交换。 它还假定能够对对象执行一个按位异或。

坚持数字1,这是最通用和最容易理解的交换,可以很容易地模板化/通用化。

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

在一个现代的处理器上,你可以在sorting大型数组时使用以下内容,并且看不到速度上的差异:

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

你问题中最重要的部分是'为什么? 部分。 现在回溯到20世纪8086年代,上述情况将成为一个真正的性能杀手,但在最新的奔腾处理器上,对于你所发布的两款游戏来说,这将是一个明智的select。

原因纯粹是内存,与CPU无关。

与内存速度相比,CPU速度已经上升了很多。 访问内存已成为应用程序性能的主要瓶颈。 所有交换algorithm将花费大部分时间等待数据从内存中获取。 现代操作系统可以有多达5级的内存:

  • 高速caching级别1 – 以与CPU相同的速度运行,访问时间可以忽略不计,但很小
  • 高速caching级别2 – 运行速度比L1慢一些,但比较大,访问开销较大(通常数据需要先移到L1)
  • 高速caching级别3 – (并不总是存在)通常在CPU外部,比L2慢和大
  • RAM–主系统内存,通常实现一个stream水线,所以在读请求(CPU请求数据,消息发送到RAM,RAM获取数据,RAM发送数据到CPU)
  • 硬盘 – 当没有足够的RAM时,数据被分页到HD,这非常慢,并不是真正在CPU控制之下。

sortingalgorithm会使内存访问更加糟糕,因为它们通常以非常无序的方式访问内存,从而导致从L2,RAM或HD获取数据的低效率开销。

因此,优化交换方法是毫无意义的 – 如果只调用了几次,那么由于调用次数较less,任何低效率都会被隐藏,如果调用次数很多,那么由于caching未命中次数而隐藏任何低效率CPU需要从L2(周期1),L3(10周期),RAM(100周期),HD(!))获取数据。

你真正需要做的是看看调用swap方法的algorithm。 这不是一个简单的练习。 尽pipeBig-O符号是有用的,但对于小的n,O(n)可以比O(log n)快得多。 (我确信有一个关于这个的CodingHorror文章。)另外,许多algorithm退化的情况下代码超过必要的(使用几乎sorting的数据上的qsort可能比早期检查泡沫sorting慢)。 所以,你需要分析你的algorithm和它使用的数据。

这导致如何分析代码。 分析器是有用的,但你需要知道如何解释结果。 永远不要使用单次运行来收集结果,总是在许多执行中平均结果 – 因为您的testing应用程序可能已被操作系统在半途中分页到硬盘。 始终configuration文件发布,优化构build,分析debugging代码是毫无意义的。

至于原来的问题 – 哪个更快? – 这就像试图通过观察后视镜的尺寸和形状来确定法拉利是否比Lambourgini更快。

第一个是更快,因为像xor这样的按位操作通常很难为读者显示。

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

@哈里:走到angular落,想想你的build议。 当你意识到你的方式的错误时回来。

由于以下原因,切勿将函数实现为macros:

  1. types安全。 空无一人。 以下仅在编译时生成警告,但在运行时失败:

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

    模板化的函数将始终是正确的types(为什么不把警告当作错误?)。

    编辑:因为在C中没有模板,你需要为每个types写一个单独的交换或使用一些hacky内存访问。

  2. 这是一个文本replace。 以下内容在运行时失败(这次没有编译器警告):

     int a=1,temp=3; swap (a,temp); 
  3. 这不是一个function。 所以,它不能用作qsort之类的参数。

  4. 编译器很聪明。 我的意思是非常聪明。 由聪明的人制造。 他们可以做function的内联。 即使在链接的时候(这更聪明)。 不要忘记,内联增加了代码的大小。 大的代码意味着在取指令时caching未命中的机会更多,这意味着较慢的代码。
  5. 副作用。 macros有副作用! 考虑:

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

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

    编辑:AC版本与讨厌的副作用:

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

macros: 只是说不!

编辑:这就是为什么我更喜欢在大写中定义macros名称,以便它们在代码中脱颖而出,作为小心使用的警告。

编辑2:回答Leahn Novash的评论:

假设我们有一个非内联函数f,它被编译器转换成一个字节序列,那么我们就可以定义字节数:

 bytes = C(p) + C(f) 

其中C()给出了产生的字节数,C(f)是函数的字节数,C(p)是“内务”代码的字节数,编译器加到函数中的前导码和后导码并破坏函数的堆栈框架等)。 现在,调用函数f需要C(c)个字节。 如果该函数被调用n次,那么总的代码大小是:

 size = C(p) + C(f) + nC(c) 

现在我们来内联函数。 由于函数可以使用调用者的堆栈框架,所以函数的“内务”C(p)变为零。 C(c)也是零,因为现在没有调用操作码。 但是,f被复制到有电话的地方。 所以,现在总的代码大小是:

 size = nC(f) 

现在,如果C(f)小于C(c),那么整个可执行文件的大小就会减小。 但是,如果C(f)大于C(c),那么代码大小将会增加。 如果C(f)和C(c)是相似的,那么你也需要考虑C(p)。

那么C(f)和C(c)产生多less个字节呢? 那么,最简​​单的C ++函数将是一个getter:

 void GetValue () { return m_value; } 

这可能会产生四字节指令:

 mov eax,[ecx + offsetof (m_value)] 

这是四个字节。 一个呼叫指令是五个字节。 所以,有一个整体大小节省。 如果函数比较复杂,比如索引器(“return m_value [index];”)或计算(“return m_value_a + m_value_b;”),那么代码会更大。

对于那些绊倒这个问题,并决定使用XOR方法。 您应该考虑内联函数或使用macros来避免函数调用的开销:

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

你正在优化错误的东西,两者都应该如此之快,以至于为了得到任何可衡量的差异,你必须运行数十亿次。

几乎任何事情都会对你的性能产生更大的影响,例如,如果你正在交换的值在内存中接近你刚刚触摸的最后一个值,他们就会处于处理器caching中,否则你将不得不访问内存 – 这比你在处理器内部进行的任何操作都要慢几个数量级。

无论如何,你的瓶颈更可能是一个低效的algorithm或不适当的数据结构(或通信开销),那么你如何交换数字。

从来没有理解对macros的讨厌。 正确使用时,它们可以使代码更加紧凑和可读。 我相信大多数程序员知道macros应该谨慎使用,重要的是明确指出一个特定的调用是macros而不是函数调用(全部大写)。 如果SWAP(a++, b++); 是一个一致的问题来源,也许编程不适合你。

不可否认,XOR技巧在你看到的前5000次是完整的,但是它所做的只是以牺牲可靠性为代价来保存一次。 看看上面生成的程序集,它会保存一个寄存器,但会创build依赖关系。 另外我不会推荐xchg,因为它有一个隐含的锁前缀。

最后我们都来到了同一个地方,经过无数个小时浪费在由我们最聪明的代码引起的非生产性优化和debugging上 – 保持简单。

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

要真正知道的唯一方法就是testing它,答案甚至可能取决于你所在的编译器和平台。 现代编译器现在非常善于优化代码,除非你能certificate你的方法真的很快,否则你绝对不应该试图超越编译器。

就这样说,你最好有一个很好的理由select#1超过#2。 #1中的代码更可读,因此应该首先select。 如果你能certificate你需要做出这样的改变,那么只能切换到#2,如果你这么做 – 评论它来解释发生了什么,以及为什么你这样做是不明显的。

作为一个轶事,我和一些喜欢过早优化的人一起工作,这使得代码非常糟糕,不可维护。 我也愿意打赌,更多的时候是因为他们已经损害了编译器以非直接的方式编写代码来优化代码的能力。

除非必须,否则我不会用指针来做。 编译器不能很好地优化它们,因为可能存在指针别名 (尽pipe如果你能保证指针指向非重叠的位置,GCC至less有扩展来优化这个)。

而且我不会用函数来完成它,因为这是一个非常简单的操作,函数调用的开销很大。

最好的方法是使用macros,如果原始速度和优化的可能性是你所需要的。 在GCC中,你可以使用typeof()内build器来创build一个适用于任何内置types的灵活版本。

像这样的东西:

 #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,则必须为每种types制作一个单独的macros。

一个好的编译器将会尽可能地优化它,给定上下文,如果用本地/全局variables作为参数调用的话。

所有评分最高的答案都不是确切的“事实”……他们是正在猜测的人!

您可以确切地知道哪个代码需要执行较less的汇编指令,因为您可以查看由编译器生成的输出程序集,并查看哪些代码在较less的汇编指令中执行!

这里是我编译的C代码,标志为“gcc -std = c99 -S -O3 lookingAtAsmOutput.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 

assembly输出总结:
swap_traditional()需要11条指令
swap_xor()需要11条指令

结论:
两种方法都使用相同数量的指令来执行,因此在这个硬件平台上的速度大致相同。

学过的知识:
当你有小的代码片段时,查看asm输出有助于快速迭代你的代码,并提出最快的(即最less的指令)代码。 而且即使因为不必为每个代码更改而运行程序,也可以节省时间。 您只需要使用一个分析器运行代码更改,以显示您的代码更改速度更快。

对于需要速度的重型DSP代码,我使用这种方法很多。

为了回答你所说的问题,需要深入研究这个代码将运行的特定CPU的指令时序,因此需要我围绕系统中的高速caching的状态以及由编译器。 从理解你select的处理器如何实际工作的angular度来看,这将是一个有趣而有用的练习,但在现实世界中,差异将是微不足道的。

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

在现代CPU架构上,XOR技术比使用临时variables进行交换要慢很多。 一个原因是现代的CPU努力通过指令stream水线并行执行指令。 在XOR技术中,每个操作的input取决于前一个操作的结果,因此必须严格按照顺序执行。 如果效率非常令人担忧,build议在目标体系结构上testingXOR技术和临时variables交换的速度。 在这里查看更多信息。


编辑:方法2是就地交换 (即不使用额外的variables)的一种方式。 为了完成这个问题,我将使用+/-添加另一个就地交换。

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

在我看来,像这样的本地优化只应该被认为与平台紧密相关。 如果你在16位的uC编译器上编译,或者在以x64为目标的gcc上编译,这会产生巨大的影响。

如果你有一个特定的目标,那么就试试这两个方法,看看生成的asm代码,或者用这两种方法分析你的应用程序,看看你的平台上哪个实际上更快。

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; 

如果您可以使用一些内联汇编程序并执行以下操作(psuedo汇编程序):

 PUSH A A=B POP B 

你会节省很多的parameter passing和堆栈代码等。

我只是把两个交换(像macros一样)放在手写的quicksort中,我一直在玩。 XOR版本要快得多(0.1秒),然后是临时variables(0.6秒)。 然而XOR却破坏了数组中的数据(可能与Ant提到的地址相同)。

由于这是一个胖枢轴快速sorting,XOR版本的速度可能是由于使大部分的数组相同。 我尝试了第三个版本的交换,这是最容易理解的,它和单一的临时版本有相同的时间。

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

[我只是在每个交换周围放一个if语句,所以它不会尝试与自己交换,异或现在与其他(0.6秒)的时间相同]

如果你的编译器支持内联汇编程序,而你的目标是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; } 

下面的一段代码将做同样的事情。 这段代码是编程的最佳方式,因为它不使用任何第三个variables。

  x = x ^ y; y = x ^ y; x = x ^ y; 
 void swap(int* a, int* b) { *a = (*b - *a) + (*b = *a); } 

//我的C有点生锈,所以我希望我有*右:)

另一个美丽的方式

 #define Swap( a, b ) (a)^=(b)^=(a)^=(b) 

优点

无需function调用,方便。

退税:

当两个input是相同的variables时,这失败。 它只能用于整型variables。