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

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

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

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

回答

第一种方法比较快，因为按位运算(例如xor)通常很难让读者看到。

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

回答

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

话虽如此，我们最好有一个很好的理由选择＃2而不是＃1. ＃1中的代码更具可读性，因此应始终首先选择该代码。如果可以证明需要进行此更改，并且要对它进行注释以解释正在发生的事情以及为什么以非显而易见的方式进行更改，请仅切换到第二。

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

回答

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

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

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

回答

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

PUSH A
A=B
POP B

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

回答

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

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

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

回答

要回答我们提出的问题，需要深入研究将在其上运行该代码的特定CPU的指令时序，因此，我需要对系统中缓存的状态以及由系统发出的汇编代码做出一系列假设编译器。从理解我们选择的处理器实际如何工作的角度来看，这将是一个有趣且有用的练习，但在现实世界中，这种差异是可以忽略的。

回答

回答

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

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

我们问题中最重要的部分是"为什么？"部分。现在，可以追溯到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方法的人。我们应该考虑内联函数或者使用宏以避免函数调用的开销：

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

回答

@哈里：走到拐角处，想想你的建议。当我们意识到自己的方式错误时，请回来。

出于以下原因，切勿将函数实现为宏：

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

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

模板化函数将始终是正确的类型(为什么不将警告视为错误？)。编辑：由于C中没有模板，因此我们需要为每种类型编写一个单独的交换或者使用一些简单的内存访问。

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

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

• 这不是一个功能。因此，不能将其用作qsort之类的参数。
• 编译器很聪明。我的意思是非常聪明。由真正聪明的人制造。他们可以内联函数。甚至在链接时(更聪明)。不要忘记，内联会增加代码大小。大代码意味着在获取指令时出现更多的高速缓存未命中的机会，这意味着代码会变慢。
• 副作用。宏有副作用！考虑：

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

在这里，f1和f2将被调用两次。编辑：具有令人讨厌的副作用的C版本：

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

宏：只是说不！

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

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

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

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

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

bytes = C(p) + C(f)

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

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

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

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

size = n.C(f)

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

void GetValue () { return m_value; }

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

回答

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

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

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

像这样的东西：

mov eax,[ecx + offsetof (m_value)]

使用其他编译器，或者如果我们需要严格遵守标准C89 / 99，则必须为每种类型创建一个单独的宏。

一个好的编译器会在给定上下文的情况下(如果使用本地/全局变量作为参数)进行优化。

回答

在我看来，仅应将此类本地优化与平台紧密相关。如果要在16位uC编译器或者以x64为目标的gcc上进行编译，则差异很大。

如果我们有一个特定的目标，则只需尝试这两个目标，然后查看生成的asm代码，或者使用这两种方法来分析应用，然后查看在平台上实际上哪个更快。

回答

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

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

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

#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 */
}

swap_traditional()的ASM输出采用>>> 11 <<<指令(不包括" leave"，" ret"，" size")：

#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_xor()的ASM输出采用>>> 11 <<<指令，不包括" leave"和" ret"：

.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_traditional()需要11条指令
swap_xor()需要11条指令

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

学过的知识：
当代码片段很小时，查看asm输出有助于快速迭代代码并提出最快(即最少指令)的代码。即使我们不必每次更改代码都运行程序，也可以节省时间。我们只需要在结尾使用分析器运行代码更改即可显示代码更改更快。

对于需要速度的沉重DSP代码，我经常使用这种方法。

回答

如果编译器支持嵌入式汇编程序，并且目标是32位x86，则XCHG指令可能是实现此目标的最佳方法……如果我们确实非常在意性能。

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

.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

回答

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

//我的C有点生锈，所以我希望*正确:)

回答

另一种美丽的方式。

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

优势

无需函数调用且方便。

退税：

当两个输入都是相同的变量时，此操作将失败。它只能用于整数变量。

代码数量不匹配