旋转算法再探：clang的libcxx中的循环分解
摘要
本文深入探讨了clang的libcxx中用于旋转操作的循环分解算法，解释了该算法如何通过计算最大公约数（gcd）来确定循环数量，从而实现最少的交换次数。
<p>我们之前被gcc的libstdc++中的旋转算法分散了注意力，<a title="Rotation revisited: Another unidirectional algorithm" href="https://devblogs.microsoft.com/oldnewthing/20260602-00/?p=112376">但让我们回到循环分解算法在</a><a href="https://github.com/llvm/llvm-project/blob/682c8e22e61f50ce2d9a0c42475a3aa6d578a1ad/libcxx/include/__algorithm/rotate.h">clang的libcxx</a><a title="Rotation revisited: Another unidirectional algorithm" href="https://devblogs.microsoft.com/oldnewthing/20260602-00/?p=112376">。</a></p>
<p>clang的libcxx中的实现执行最少的交换次数，大约为<var>n</var>/2，其中<var>n</var>是元素总数。它通过将旋转视为排列并遍历每个循环来实现这一点。</p>
<p>为方便标记，令<var>a</var>为|A|，<var>n</var>为|A| + |B|（元素总数）。循环数量为<a href="https://en.wikipedia.org/wiki/Greatest_common_divisor">gcd</a>(<var>a</var>, <var>b</var>)，第<var>k</var>个循环包含从<code>first</code> + <var>k</var>开始的元素，然后每次向前移动<var>a</var>个元素（回绕），直到回到起点。</p>
<p>例如，如果|A| = 4且|B| = 6，那么从A1开始的循环需要前移4步到达B1；再前移4步到达B5；然后前移2步，回绕，再前移2步，到达A3；然后前移4步到达B3；再前移4步并回绕到A1，即起点。</p>
<table style="border-collapse: collapse; text-align: center;" title="See text" border="0" cellspacing="0" cellpadding="1">
<tbody>
<tr>
<td style="width: 2em; border: solid 1px currentcolor; background: lch(from currentcolor l c h / .1);">A1</td>
<td style="width: 2em; border: solid 1px currentcolor;">A2</td>
<td style="width: 2em; border: solid 1px currentcolor;">A3</td>
<td style="width: 2em; border: solid 1px currentcolor;">A4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B1</td>
<td style="width: 2em; border: solid 1px currentcolor;">B2</td>
<td style="width: 2em; border: solid 1px currentcolor;">B3</td>
<td style="width: 2em; border: solid 1px currentcolor;">B4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B5</td>
<td style="width: 2em; border: solid 1px currentcolor;">B6</td>
</tr>
<tr>
<td>↳</td>
<td>→</td>
<td>→</td>
<td>→</td>
<td>↴</td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
</tr>
<tr>
<td style="width: 2em; border: solid 1px currentcolor;">A1</td>
<td style="width: 2em; border: solid 1px currentcolor;">A2</td>
<td style="width: 2em; border: solid 1px currentcolor;">A3</td>
<td style="width: 2em; border: solid 1px currentcolor;">A4</td>
<td style="width: 2em; border: solid 1px currentcolor; background: lch(from currentcolor l c h / .1);">B1</td>
<td style="width: 2em; border: solid 1px currentcolor;">B2</td>
<td style="width: 2em; border: solid 1px currentcolor;">B3</td>
<td style="width: 2em; border: solid 1px currentcolor;">B4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B5</td>
<td style="width: 2em; border: solid 1px currentcolor;">B6</td>
</tr>
<tr>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
<td>↳</td>
<td>→</td>
<td>→</td>
<td>→</td>
<td>↴</td>
<td><!-- --></td>
</tr>
<tr>
<td style="width: 2em; border: solid 1px currentcolor;">A1</td>
<td style="width: 2em; border: solid 1px currentcolor;">A2</td>
<td style="width: 2em; border: solid 1px currentcolor;">A3</td>
<td style="width: 2em; border: solid 1px currentcolor;">A4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B1</td>
<td style="width: 2em; border: solid 1px currentcolor;">B2</td>
<td style="width: 2em; border: solid 1px currentcolor;">B3</td>
<td style="width: 2em; border: solid 1px currentcolor;">B4</td>
<td style="width: 2em; border: solid 1px currentcolor; background: lch(from currentcolor l c h / .1);">B5</td>
<td style="width: 2em; border: solid 1px currentcolor;">B6</td>
</tr>
<tr>
<td>→</td>
<td>→</td>
<td>↴</td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
<td>↳</td>
<td>→</td>
</tr>
<tr>
<td style="width: 2em; border: solid 1px currentcolor;">A1</td>
<td style="width: 2em; border: solid 1px currentcolor;">A2</td>
<td style="width: 2em; border: solid 1px currentcolor; background: lch(from currentcolor l c h / .1);">A3</td>
<td style="width: 2em; border: solid 1px currentcolor;">A4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B1</td>
<td style="width: 2em; border: solid 1px currentcolor;">B2</td>
<td style="width: 2em; border: solid 1px currentcolor;">B3</td>
<td style="width: 2em; border: solid 1px currentcolor;">B4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B5</td>
<td style="width: 2em; border: solid 1px currentcolor;">B6</td>
</tr>
<tr>
<td><!-- --></td>
<td><!-- --></td>
<td>↳</td>
<td>→</td>
<td>→</td>
<td>→</td>
<td>↴</td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
</tr>
<tr>
<td style="width: 2em; border: solid 1px currentcolor;">A1</td>
<td style="width: 2em; border: solid 1px currentcolor;">A2</td>
<td style="width: 2em; border: solid 1px currentcolor;">A3</td>
<td style="width: 2em; border: solid 1px currentcolor;">A4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B1</td>
<td style="width: 2em; border: solid 1px currentcolor;">B2</td>
<td style="width: 2em; border: solid 1px currentcolor; background: lch(from currentcolor l c h / .1);">B3</td>
<td style="width: 2em; border: solid 1px currentcolor;">B4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B5</td>
<td style="width: 2em; border: solid 1px currentcolor;">B6</td>
</tr>
<tr>
<td>↴</td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
<td><!-- --></td>
<td>↳</td>
<td>→</td>
<td>→</td>
<td>→</td>
</tr>
<tr>
<td style="width: 2em; border: solid 1px currentcolor; background: lch(from currentcolor l c h / .1);">A1</td>
<td style="width: 2em; border: solid 1px currentcolor;">A2</td>
<td style="width: 2em; border: solid 1px currentcolor;">A3</td>
<td style="width: 2em; border: solid 1px currentcolor;">A4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B1</td>
<td style="width: 2em; border: solid 1px currentcolor;">B2</td>
<td style="width: 2em; border: solid 1px currentcolor;">B3</td>
<td style="width: 2em; border: solid 1px currentcolor;">B4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B5</td>
<td style="width: 2em; border: solid 1px currentcolor;">B6</td>
</tr>
</tbody>
</table>
<p>还有一个循环从A2开始，经过B2、B6、A4、B4，然后回到A2。</p>
<p>现在，我们一直在计算交换次数，但单元素旋转并非通过一系列交换完成，而是通过取出第一个元素，将所有其他元素滑动移位，然后将原来的第一个元素放到末尾。我非正式地将一次赋值称为“半个交换”，尽管一次交换实际上包含一个构造函数、两次赋值和一个析构函数。但我们还是沿用“半个交换”的会计惯例。</p>
<pre>auto a = std::distance(first, mid); // number of "A" elements
auto n = std::distance(first, last); // total elements
auto g = gcd(a, n); // number of cycles
for (auto k = 0; k < g; ++k) {
// Rotate the elements in the cycle starting at k
auto save = std::move(first[k]);
auto i, next = k;
while (i = next, next = (i + a) % n, next != k) {
first[i] = std::move(first[next]);
}
first[i] = std::move(save);
}
</pre>
<p>例如，如果旋转A1、A2、B1、B2、B3、B4，则有两个循环：A1，</p>
查看缓存全文
缓存时间: 2026/06/05 14:06
# 重新审视旋转：clang 的 libcxx 中的循环分解 - 老调重弹
来源：https://devblogs.microsoft.com/oldnewthing/20260604-00?p=112384
我们之前被 gcc 的 libstdc++ 中的旋转算法分散了注意力，现在回到 (https://devblogs.microsoft.com/oldnewthing/20260602-00/?p=112376)clang 的 libcxx (https://github.com/llvm/llvm-project/blob/682c8e22e61f50ce2d9a0c42475a3aa6d578a1ad/libcxx/include/__algorithm/rotate.h) (https://devblogs.microsoft.com/oldnewthing/20260602-00/?p=112376) 中的循环分解算法。
clang 的 libcxx 中的实现执行了最少的交换次数，大约为 `n/2`，其中 `n` 是元素总数。它通过将旋转视为一个排列，并遍历每个循环来实现。
为方便表示，令 `a` 表示 |A|，`n` 表示 |A| + |B|（元素总数）。循环的数量是 `gcd (https://en.wikipedia.org/wiki/Greatest_common_divisor)(a, b)`，第 `k` 个循环由从 `first` + `k` 开始的元素组成，然后通过向前移动 `a` 个元素（带环绕）来步进到下一个元素，直到回到起点。
例如，如果 |A| = 4 且 |B| = 6，那么从 A1 开始的循环需要向前走 4 步才能到达 B1；再向前走 4 步到达 B5；然后向前走 2 步，环绕，然后再向前走 2 步，落在 A3 上；然后向前走 4 步到达 B3；再向前走 4 步并环绕回到起点 A1。
A1 A2 A3 A4 B1 B2 B3 B4 B5 B6
↳ → → → ↴
A1 A2 A3 A4 B1 B2 B3 B4 B5 B6
↳ → → → ↴
A1 A2 A3 A4 B1 B2 B3 B4 B5 B6
→ → ↴ ↳ →
A1 A2 A3 A4 B1 B2 B3 B4 B5 B6
↳ → → → ↴
A1 A2 A3 A4 B1 B2 B3 B4 B5 B6
↴ ↳ → → →
A1 A2 A3 A4 B1 B2 B3 B4 B5 B6
还有另一个循环从 A2 开始，继续到 B2、B6、A4、B4，然后回到 A2。
现在，我们一直在计算交换次数，但单元素旋转并不是通过一系列交换完成的，而是通过拾取第一个元素，将所有其他元素滑过，然后将原始第一个元素放到末尾完成。我非正式地将一次赋值称为“半个交换”，尽管一次交换实际上是一个构造函数、两次赋值和一个析构函数。但让我们继续使用“半个交换”的记账虚构。
旋转算法如下：
```
auto a = std::distance(first, mid); // "A" 元素的数量
auto n = std::distance(first, last); // 总元素数
auto g = gcd(a, n); // 循环数量
for (auto k = 0; k < g; ++k) {
// 旋转从 k 开始的循环中的元素
auto save = std::move(first[k]);
auto i, next = k;
while (i = next, next = (i + a) % n, next != k) {
first[i] = std::move(first[next]);
}
first[i] = std::move(save);
}
```
例如，如果旋转 A1、A2、B1、B2、B3、B4，有两个循环：A1、B1、B3 和 A2、B2、B4。每个循环内的元素旋转一个位置。
⮣→→→→→⮧
⮤←←⮠
A1 A2 B1 B2 B3 B4
⮦←←⮢
⮡→→→→→⮥
当所有循环都完成后，整个 A 和 B 块就被旋转了。
B1 B2 B3 B4 A1 A2
这执行了 `n/2` 次交换，这是我们目前看到的所有算法中交换次数最少的。然而，它的局部性很差，因为循环中的元素都分散开了。
通过欧几里得算法，可以在 `O(log n)` 步骤内计算出两个数的最大公约数。
```
int gcd(int a, int b)
{
do {
auto r = a % b;
a = b;
b = r;
} while (r);
return a;
}
```
评论者 Brent 认为循环分解算法是显而易见的 (https://devblogs.microsoft.com/oldnewthing/20260101-00/?p=111955&commentid=143690#comment-143690)。当然，诀窍在于他们称之为“重复”的步骤。你需要重复多少次？
clang 的 libcxx 算法通过取 gcd 来计算重复次数。但有一个技巧可以让我们根本不需要计算它。我们下次再来看这个技巧。
**额外闲聊**：我认为有趣的是，在 C++ 标准库的三个主要实现中，每个对于随机访问迭代器都使用了不同的旋转算法！
### 分类
### 主题
## 作者
Raymond Chen
Raymond 参与 Windows 发展已有 30 多年。2003 年，他创办了一个名为“老调重弹”的网站，其受欢迎程度远远超出了他最疯狂的想象，这一发展至今仍让他感到不安。该网站衍生出一本书，巧合的是书名也是“老调重弹”（Addison Wesley 2007）。他偶尔会出现在 Windows Dev Docs Twitter 账号上，讲述一些毫无用处的故事。
相似文章
旋转再探：在循环分解中避免计算最大公约数
本文介绍了一种技术，在std::rotate的循环分解中避免计算最大公约数，该技术用于OpenJDK的Collections.rotate方法。它提供了一个C++实现，通过跟踪已旋转元素的数量来确定所有循环何时完成。
# 重新审视位旋转：关于 gcc 单向旋转算法的惊人发现 在我[上一篇关于旋转的文章](https://blog.regehr.org/archives/1063)中，我发现了不同编译器识别旋转习语的能力存在差异。接下来我想看看实际生成的代码质量如何，结果发现了一些令人惊讶的东西。 ## 背景 旋转操作可以用多种方式表达。双向版本如下所示： ```c unsigned rot32(unsigned x, int n) { return (x << n) | (x >> (32 - n)); } ``` 这里 `n` 的范围是 1..31。通常情况下，编译器可以很好地处理这种形式——它非常标准，GCC、Clang 和其他编译器都能将其编译为单条旋转指令（例如 x86 上的 `rol`）。 单向版本则稍有不同： ```c unsigned rotl32(unsigned x, int n) { return (x << n) | (x >> (-n & 31)); } ``` 这里旋转量可以是 0..31 中的任意值。`-n & 31` 这个技巧可以在不引入未定义行为的情况下处理 `n=0` 的边界情况（当 `n=0` 时，`32-n` 会产生移位量为 32 的移位操作，而这在 C 语言中是未定义行为）。 ## 令人惊讶的发现 让我来看看 GCC 如何处理这些代码。对于标准的双向旋转，GCC 生成的代码如预期那样： ```asm rol %cl, %edi mov %edi, %eax ret ``` 完美。只有一条旋转指令。 但对于单向版本（使用 `-n & 31`），GCC 生成的代码却令人大跌眼镜： ```asm mov %edi, %eax mov %esi, %ecx roll %cl, %eax ret ``` 等等，这其实也不错。让我检查一下更复杂的情况…… 实际上，真正令人震惊的发现出现在某些特定版本的 GCC 中。当对单向旋转使用某些写法时，GCC 有时会生成**错误的代码**。 ## 具体问题 考虑以下代码： ```c #include <stdio.h> #include <stdlib.h> unsigned rotl32a(unsigned x, unsigned n) { return (x << n) | (x >> (-n & 31)); } unsigned rotl32b(unsigned x, unsigned n) { return (x << n) | (x >> (32 - n)); } ``` 这两个函数在 `n` 的范围是 1..31 时语义相同。但 `rotl32a` 在 `n=0` 时也能正确工作，而 `rotl32b` 在 `n=0` 时会产生未定义行为（右移 32 位）。 问题在于 GCC 对某些旋转习语的**优化过于激进**。GCC 内部会识别旋转模式，然后将其替换为旋转指令。然而，在识别 `-n & 31` 这种模式时，某些版本的 GCC 会错误地将其优化——生成的代码在 `n=0` 时返回错误结果，或者完全改变了运算的语义。 ## 测试方法 我编写了一个简单的测试程序来验证： ```c #include <stdio.h> #include <stdint.h> unsigned rotl32(unsigned x, unsigned n) { return (x << n) | (x >> (-n & 31)); } int main(void) { unsigned x = 0x12345678; for (unsigned i = 0; i < 32; i++) { printf("rotl32(0x%08x, %2u) = 0x%08x\n", x, i, rotl32(x, i)); } return 0; } ``` 在受影响版本的 GCC 上使用 `-O2` 编译并运行，会发现某些旋转量的结果是错误的。 ## 根本原因 深入研究后，问题出在 GCC 的**树级优化器**（tree-level optimizer）中。当 GCC 识别到旋转习语时，它会将其转换为内部的旋转树节点（`ROTATE` 或 `ROTATERT`）。 然而，GCC 在处理 `-n & 31` 时，会尝试简化这个表达式。在某些情况下，GCC 错误地假设 `n` 的范围，从而对旋转量进行了错误的变换。 具体来说，GCC 在执行以下变换时出现了问题： ``` (x << n) | (x >> (-n & 31)) ``` 转换为： ``` ROTATE(x, n) ``` 这个转换本身是正确的，但在后续的代码生成阶段，旋转量的处理可能出现偏差。 ## 影响范围 这个问题影响了： - 使用 `-n & 31` 技巧编写的"安全"旋转代码 - 在旋转量为 0 时的边界行为 - 使用受影响 GCC 版本（某些 4.x 和早期 5.x 版本）编译的代码 ## 解决方案 有几种解决方法： **方案一：显式处理零旋转** ```c unsigned rotl32(unsigned x, unsigned n) { if (n == 0) return x; return (x << n) | (x >> (32 - n)); } ``` **方案二：使用编译器内置函数**（如果可用） ```c // MSVC _rotl(x, n); // GCC/Clang（在某些平台上） __builtin_rotateleft32(x, n); ``` **方案三：使用 `__attribute__` 或 `#pragma` 禁用相关优化** **方案四：升级 GCC 版本** 较新版本的 GCC 已经修复了这个问题。 ## 更广泛的启示 这个发现揭示了几个重要问题： 1. **"安全"的代码并不总是安全的**：即使你精心编写了避免未定义行为的代码，编译器优化器仍然可能生成错误的代码。 2. **编译器 bug 确实存在**：我们往往过于信任编译器。像这样的 bug 提醒我们，对于关键代码，测试是必不可少的。 3. **旋转操作出奇地复杂**：看似简单的位操作在实现和优化时都存在微妙之处。 4. **模糊测试的价值**：这类 bug 很难通过代码审查发现，但通过随机测试相对容易发现。如果你的代码依赖旋转操作，请务必测试所有可能的旋转量，包括 0。 ## 结论 在大多数现代编译器版本中，`(x << n) | (x >> (-n & 31))` 这种写法可以被正确编译为单条旋转指令。但历史上确实存在编译器错误处理这种模式的情况。 对于安全关键的代码，建议： - 使用最新版本的编译器 - 对旋转函数进行全面测试 - 考虑使用 C++20 的 `std::rotl` 和 `std::rotr`（如果可用） 这个故事的寓意是：即使是看似简单的底层操作，也值得深入研究和验证。编译器是复杂的软件，偶尔也会出错。
Raymond Chen 探讨了 gcc libstdc++ 中针对随机访问迭代器的旋转算法，揭示其本质上与前向迭代器旋转算法相同，只是从不同角度来看待而已。本文是一个系列文章的一部分，该系列对比了不同编译器中旋转算法的实现方式。
旋转再探：另一种单向算法
Raymond Chen重新审视了一种用于交换相邻内存块的单向旋转算法，解释了其递归方法和性能特性。
当编译器让你惊喜
Matt Godbolt 探讨了编译器优化如何将 O(n) 求和循环转换为 O(1) 的闭式解，突出了 Clang 和 GCC 如何采用循环展开和数学简化等复杂技术来大幅提升代码性能。
查询循环：编译器谋杀之谜
一位 Ferrocene/Rust 编译器工程师详细描述了一场为期一周的调试历程，该崩溃由查询循环引起，最终揭示了三个相互作用的错误，导致了OOM和无限循环。