C++中交换值的最有效方法是什么？

Question

我想知道在C++中交换整数的最高效方法是什么，从操作的角度来看，为什么？类似以下代码是否可行：

int a =..., b = ...;
a = a + b;
b = a - b;
a = a - b;

比使用临时变量更高效的方法是什么？还有其他更高效的方法吗？（不仅仅是交换整数的其他方法），为什么它们会更高效？

- Mara Jade

---

我会建议使用std::swap。 - NathanOliver

在现代计算机上，这可能是交换整数最慢的方式。如果你有一台有两个寄存器的机器，特别是它有一个鼓式存储器，那么这可能是一个好主意。 - molbdnilo

Answer 1

赋值操作总是比算术运算更快。

C++实现std::swap的代码如下：

template<typename T> void swap(T& t1, T& t2) {
    T temp = std::move(t1); // or T temp(std::move(t1));
    t1 = std::move(t2);
    t2 = std::move(temp);
}

因此，使用临时变量比进行算术技巧更好。
而使用std::swap甚至更好，因为在编程中重新发明轮子从来不是一个好主意

- afzalex

---

这是一种可能的实现方式，没错。但并不一定适用于整数。它只是一个合理的默认值。 - StoryTeller - Unslander Monica

它也可以这样完成：t1 = std::exchange(t2, t1); - StoryTeller - Unslander Monica

Answer 2

最好的方法是相信你的编译器并使用C++标准库函数，它们是为彼此设计的。

std::swap会胜出。

您可以使用XOR交换int（不需要临时变量），但现在仍然比std::swap表现差。

- Bathsheba

---

好的，谢谢。我没有意识到标准函数比几行代码更快。 - Mara Jade

我想补充一点，它的性能不如std::swap，因为在某些架构上，std::swap可以使用单个机器指令进行交换。 - StoryTeller - Unslander Monica

@MaraJade 我的经验法则是先尝试使用标准提供的函数/结构。如果你进行性能分析后发现它们不够高效，那么再寻找替代方案。 - NathanOliver

还要注意，在手写代码表现优于执行相同操作的标准库函数的罕见情况下，很可能是发现了性能缺陷。因此，在这种情况下，不要害怕联系编译器作者/标准库维护者。 - ComicSansMS

如果您不小心尝试交换一个值和它本身，XOR交换将失败。 - Pete Becker

Answer 3

在我的情况下，std::swap 比以下代码慢了5%（都使用了 O3 优化）。一般来说，std::swap() 函数会调用复制构造函数，这可能总是比仅仅复制内存的操作要慢。

#include <cstring>

size_t objectSize = sizeof(Object);
char temp[objectSize];

loop {
    loop {
        memcpy(temp, a, objectSize);
        memcpy(a, b, objectSize);
        memcpy(b, temp, objectSize);
    }
}

编辑：使用栈而不是堆内存分配。

- Thomas.

---

我能否使用它来交换数百万次的 uint64_t，或者它只对大型对象元素有益？ - Kari

我认为，在这种情况下，标准的值交换会更快。但你必须试一试。 - Thomas.

但是在C++中，memcpy可能会破坏对象的一致性。 - Qwertiy

@Qwertiy，您能否解释一下对象一致性将如何被破坏？ - Thomas.

Answer 4

最有效的方法是不要自己尝试去做。 这真的取决于你为什么/在哪里想要这样做。试图聪明地在C++中编写晦涩的代码只会降低编译器正确优化的机会。

假设我们使用你写的±-方法： 首先，需要从内存中加载值a和b。 然后你进行三个算术操作来"交换"它们的内容。 最后，两个值必须再次存储在内存中。 （不会使用实际的汇编代码，因为我对此不熟悉，而这个伪汇编语言更容易理解概念）

load a into register rA
load b into register rB
add rB to rA and store in rA
subtract rB from rA and stor in rB
subtract rB from rA and store in rA
store register rA to memory b
store register rB to memory a

如果编译器完全按照您的意愿执行（可能会忽略并使其更好），那将是：2次加载，3个简单的数学函数，2次存储 - 7个操作。

此外，由于加法/减法可以使用内存中的1个值来完成，因此它也可以稍微优化。

load 'a' into register rA
add b to rA and store in rA
subtract b from rA and store in rB
subtract rB from rA and store in rA
store rA to a
store rB to b

如果我们使用一个额外的tmp变量：

int a =..., b = ...;
int tmp = a;
a = b;
b = tmp;

编译器可能会认识到“tmp”只是用于交换两个值的临时变量，因此它不会分配内存位置，而只使用寄存器。 在这种情况下，它将执行以下操作：

load a into register rA
load b into register rB
store register rA to memory b
store register rB to memory a

仅有4个操作 - 基本上是它能够做到的最快速度，因为您需要加载2个值并存储2个值，没有其他操作。（对于现代nx86_64处理器，没有命令可以只交换内存中的2个值 - 其他体系结构可能具有此功能，并且在这种情况下速度更快）。

执行这些算术运算（或异或技巧）是一个不错的练习，但在现代x86 CPU上，除了最基本的编译器外，它不会以任何形式“更有效率”。 它将使用相同数量的寄存器，相同数量的变量内存，但需要更多指令来完成相同的工作。 通常情况下，您不应尝试超越编译器，除非您已经检查了代码，测试和基准测试，并发现生成的汇编代码不如可能的好。

但是，几乎永远不需要达到那个优化级别，您的时间最好花在考虑更大的画面上。

- ABaumstumpf

Answer 5

#include <iostream>
using namespace std;

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

int main() {
    int a=1,b=6;
    swap(a,b);
    cout<<a<<b;
    return 0;
}

- Prakhar Dev Gupta

---

这是未定义的行为。 - Qwertiy