23

STL 实现了一个通用std::swap函数来交换 2 个值。可以通过以下方式呈现：

template <class T> void swap (T& a, T& b)
{
  T c(std::move(a));
  a=std::move(b);
  b=std::move(c);
}

但是，有一个 XOR 交换算法来交换 2 个整数（http://en.wikipedia.org/wiki/XOR_swap_algorithm）：

void swap_u( size_t& x, size_t& y )
{
   x = x^y;
   y = x^y;
   x = x^y;
}

我的问题：

  1. 现在是优化（onx86还是arm）？
  2. C++ 标准是否支持这种优化？
  3. 在野外有没有std::swap专门针对整数的真正 STL 实现？
4

4 回答 4

35

在绝大多数情况下，异或交换不是优化。

请参阅此wiki 条目。

在大多数实际场景中，使用临时寄存器的普通交换算法效率更高。XOR 交换可能可行的有限情况包括：

  • 在指令集编码允许 XOR 交换以较少字节数编码的处理器上；
  • 在具有高寄存器压力的区域中，它可以允许寄存器分配器避免溢出寄存器。
  • 在可用 RAM 非常有限的微控制器中。

因为这些情况很少见，所以大多数优化编译器不会生成 XOR 交换代码。

另请注意，您的 XOR 交换实现已损坏。您需要首先检查 x 和 y 是否没有别名。这个检查肯定会让 XOR 交换变慢。

我不知道任何使用 XOR 交换的标准库实现。

请注意，无论标准库实现什么，如果 XOR 交换确实比普通交换快，那么优化编译器将进行窥孔优化以将其转换为 XOR 交换。这确实是让编译器为您选择的情况。

于 2013-08-17T10:00:19.133 回答
8

XOR 交换实际上只是一个噱头，在某些情况下可能会失败（例如，两个变量都是对同一对象的引用）。

XOR 交换也不是特别有效，因为它具有串行依赖关系，因此它总是需要至少三个指令周期。使用带临时的直接交换具有较少的依赖性，允许在现代超标量 CPU 上进行一些并行性 - 在某些 CPU 上，它甚至可以在一条指令中实现，但即使没有特殊指令，它也可能在两个周期内执行。

于 2013-08-17T10:02:01.310 回答
4

在 X86 上，内存位置（不是 CPU 寄存器）之间的三重异或交换需要与三重复制相同的处理器周期。如果临时是一个寄存器，它们可能会更少。

于 2013-08-17T10:08:02.743 回答
0

正如在大多数情况下已经解释的那样，XOR 位摆弄会更慢。

但这也很大程度上取决于周围的代码。假设这种交换是单独完成的，远离任何其他需要这些值的代码（因此它们不会加载到寄存器中），并且我们在这里使用“普通”x86 处理器。

任何交换这 2 个值的算法至少需要 2 次操作将值从内存加载到寄存器中，另外 2 次操作将这些值再次存储到内存中（x86 没有直接交换 2 个内存位置内容的操作）。

当使用像这样的临时变量时：

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

基本上任何编译器都会认识到“temp”仅在本地用于交换并且不会给它一个内存位置。由于它只保存“a”的值，它甚至不会是一个单独的寄存器。

它的汇编代码看起来像这样（伪汇编）：

load a to rA
load b to rB
store rA to b
store rB to a

因此，在大多数情况下，这在内存访问、指令数量和寄存器数量方面可能是最有效的。

只有当编译器无法识别“temp”没有用于其他任何事情并将其存储在单独的寄存器（或该死的实际内存）中时，XOR 变体才能在任何事情上更有效。

但这仍然是理论上的，因为您的交换将被其他代码包围，而这将在那里更为重要。如果这些值不再使用，那么整个交换将被忽略。如果在其他计算之后直接使用这些值，那么可能只是以下代码交换了 2 个寄存器，因此它本身的交换有 0 条指令。而且您将很难找到比实际上无事可做更有效的任何解决方案。

当然还有其他更晦涩的指令集，它们可能具有直接交换 2 个内存位置内容的指令。

于 2020-12-16T15:09:25.497 回答