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

Question

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

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

看起来第一个使用额外的寄存器,但第二个使用三个加载和存储,而第一个只执行两个.有人能告诉我哪个更快,为什么？为什么更重要.

Answer 1

2号经常被引用为"聪明"的方式.实际上它很可能更慢,因为它模糊了程序员的明确目标 - 交换两个变量.这意味着编译器无法优化它以使用实际的汇编程序操作来交换.它还假设能够对对象执行按位xor.

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

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

Answer 2

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

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

虽然这个问题不太可能出现,但我总是更喜欢使用保证工作的方法,而不是在意外时刻失败的聪明方法.

Answer 3

在现代处理器上,您可以在对大型数组进行排序时使用以下内容,并且看不出速度上的差异:

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

你问题中真正重要的部分是'为什么？' 部分.现在,回到2086年到8086天,上面将是一个真正的性能杀手,但在最新的奔腾,它将是你发布的两个匹配速度明智.

原因完全取决于内存,与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可能比使用早期检查的冒泡排序慢).因此,您需要分析算法及其使用的数据.

这导致了如何分析代码.分析器很有用,但您需要知道如何解释结果.永远不要使用单次运行来收集结果,总是通过多次执行来得到平均结果 - 因为您的测试应用程序可能已被操作系统中途分页到硬盘.总是发布配置文件,优化的构建,分析调试代码是没有意义的.

至于原来的问题 - 哪个更快？ - 这就像试图通过观察后视镜的大小和形状来判断法拉利是否比Lambourgini更快.

Answer 4

第一个更快,因为像xor这样的按位操作通常很难为读者可视化.

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

Answer 5

@Harry:站在角落里想想你的建议.当你意识到自己的方式错误时,请回来.

永远不要将函数实现为宏,原因如下:

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

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

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

   编辑:由于C中没有模板,您需要为每种类型编写单独的交换或使用一些hacky内存访问.

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

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

3. 这不是一个功能.因此,它不能用作qsort之类的参数.

4. 编译器很聪明.我的意思是非常聪明.由非常聪明的人制作.他们可以做内联功能.即使在链接时(更聪明).不要忘记内联会增加代码大小.大代码意味着在获取指令时更有可能出现缓存未命中,这意味着代码更慢.

5. 副作用.宏有副作用!考虑:

   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++]);
   

宏:说不!

编辑:这就是为什么我更喜欢在UPPERCASE中定义宏名称,以便它们在代码中脱颖而出,作为警告使用.

EDIT2:回答Leahn Novash的评论:

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

bytes = C(p) + C(f)

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

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

现在让我们内联函数.C(p),函数的'housekeeping'变为零,因为函数可以使用调用者的堆栈帧.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++函数就是getter:

void GetValue () { return m_value; }

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

mov eax,[ecx + offsetof (m_value)]

这是四个字节.呼叫建立是五个字节.因此,总体尺寸节省.如果函数更复杂,比如说索引器("return m_value [index];")或计算("return m_value_a + m_value_b;")则代码会更大.

Answer 6

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

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

Answer 7

你正在优化错误的东西,这两者都应该是如此之快,你必须运行它们数十亿次才能获得任何可衡量的差异.

几乎任何事情都会对你的表现产生更大的影响,例如,如果您交换的值在内存中接近您触及的最后一个值,那么它们将处于处理器缓存中,否则您将不得不访问内存 - 比处理器内部的任何操作慢几个数量级.

无论如何,你的瓶颈更可能是一个低效的算法或不适当的数据结构(或通信开销),然后你如何交换数字.

Answer 8

永远不理解对宏的仇恨.如果使用得当,它们可以使代码更紧凑和可读.我相信大多数程序员都知道应该谨慎使用宏,重要的是要明确特定的调用是宏而不是函数调用(全部大写).如果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);
}

Answer 9

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

话虽如此，您最好有一个该死的充分理由选择 #2 而不是 #1。#1 中的代码更具可读性，因此应始终首先选择。只有在你能证明你需要做出改变时才切换到#2 ，如果你这样做了 - 评论它以解释发生了什么以及你为什么以不明显的方式这样做。

作为一个轶事，我和几个喜欢过早优化的人一起工作，这会产生非常可怕、不可维护的代码。我也愿意打赌，他们往往是在自责，因为他们以不直接的方式编写代码，削弱了编译器优化代码的能力。

Answer 10

对于现代 CPU 架构，方法 1 会比方法 2 更快，并且可读性更高。

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

编辑：方法2是一种就地交换的方法（即不使用额外的变量）。为了使这个问题完整，我将使用+/-.

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