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

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

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

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

1> 小智..：

---

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

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

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

---

我完全同意.此外,如果价值交换确实是一个瓶颈(通过测量证明),并且无法避免,那么实现每一种方法都可以实现,并且可以更快地测量哪些_for_ _you_(您的机器,操作系统,编译器和应用程序) .低级别的东西没有通用的答案.

2> Ant..：

---

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

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

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

---

然后你的交换函数有一个分支.尽管这是一个愚蠢的问题,如果OP在速度之后然后引入分支可能是一个坏主意.

---

如果有一些聪明的技巧可以加快速度,那么你的邻居编译器已经听说过并且正在背后使用它.这样的微优化(特别是如果手工完成)只是今天没有得到任何东西,内存访问比执行指令慢很多.混淆代码中的"性能"会在等式中最昂贵的部分中受到伤害:程序员时间.

---

@mamama,它也应该是!= b而不是*a!=*b; 如果地址相同而不是值,则失败.

3> Skizz..：

---

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

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更快.

---

+1为不必要的优化提及.如果您实际上已经分析了代码,那么您最担心的是这两种交换方式中的哪一种更快,您编写了一个非常快的应用程序.在那之前,谁在乎互换呢？

4> Sander..：

---

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

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

5> Skizz..：

---

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

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

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

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

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

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

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

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

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

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

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

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;")则代码会更大.

---

您的副作用代码是C++,而不是C(C中没有引用).C程序员没有模板化的功能......这可能具有一些类型安全性,但绝对是解析和实现的噩梦.C++!= C.它们具有不同类型和程度的抽象和约定.

6> Harry..：

---

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

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

---

呃...为什么你会使用不能自己内联的编译器？尽可能使用函数,必要时使用宏.函数类型安全更容易理解.这个宏会用"swap(a ++,b ++)"做正确的事情吗？会有功能吗？

---

+1.当你需要速度时,这是用C语言完成的方法.如果你使用GNU C提供的typeof()扩展,宏甚至可以变成类型灵活的.

7> Nir..：

---

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

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

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

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