std::rotate: how libstdc++ and libc++ actually differ
Raymond Chen wrote a three-part series on The Old New Thing (June 2-4, 2026) that surprised even his regular readers: std::rotate is implemented with two completely different algorithms in libstdc++ and libc++, and the trade-off is not what most engineers assume.
If you have std::rotate in a hot path, this matters.
What libstdc++ (GCC) does
GCC’s libstdc++ uses a unidirectional swap loop. Given the rotation point mid splitting the range into a left half A and a right half B, it repeatedly swaps the element at first with the element at mid, then advances both pointers. When mid reaches last, it resets mid to the new boundary and continues.
The cost: n - 1 swaps for a range of length n. Locality is good – first advances monotonically through memory and mid jumps at most O(log(min(|A|, |B|))) times. The cache prefetcher likes this pattern.
The “shocking discovery” in Chen’s Jun 3 post: the random-access specialization in libstdc++ is mathematically the same algorithm as its forward-iterator version. The two paths produce identical swap sequences on the same input. The “specialization” is really just a direction-aware framing of the same loop.
What libc++ (Clang) does
Clang’s libc++ uses cycle decomposition. Think of the rotation as a permutation: each element at index i ends up at index (i - a) mod n, where a = |A|. This permutation decomposes into exactly gcd(a, n) disjoint cycles, and you can walk each cycle with a single saved temporary.
The pseudocode (adapted from Chen’s Jun 4 post):
auto a = std::distance(first, mid);
auto n = std::distance(first, last);
auto g = gcd(a, n);
for (auto k = 0; k < g; ++k) {
auto save = std::move(first[k]);
auto i = k, next = k;
while (i = next, next = (i + a) % n, next != k) {
first[i] = std::move(first[next]);
}
first[i] = std::move(save);
}The cost: n - gcd(a, n) move-assignments plus gcd(a, n) saved temporaries. For typical rotation amounts where gcd(a, n) is small, that’s roughly n/2 swap-equivalents – about half of libstdc++. But locality is terrible: each cycle jumps by a (mod n) on every step. On a large range with a small a, you stride-walk through memory and the prefetcher misses every time.
Which one wins?
It depends entirely on the input.
libc++ wins when:
- The range fits in L2 cache (locality penalty is small)
- Moves are expensive (custom types, non-trivially-movable)
- You’re move-bound, not memory-bound
libstdc++ wins when:
- The range is large enough that cache locality dominates
- Moves are cheap (POD, trivial types)
- You’re memory-bound
Chen’s series doesn’t include benchmarks. The internet has them. The pattern that keeps showing up: for int ranges over ~64KB, libstdc++ is 1.5-2x faster despite doing more swaps. For ranges under 4KB or for expensive-to-move types, libc++ wins by a similar margin.
What this means for portable code
If std::rotate is in a hot path:
-
Don’t assume “stdlib is stdlib.” The same call on the same input runs different algorithms with measurably different performance on the same machine, just by swapping compiler.
-
Benchmark on your actual stdlib. Microbenchmark with the workload shape you actually have. If you only test on libstdc++, the libc++ numbers will surprise you (or vice versa).
-
Consider writing the cycle-decomposition variant explicitly if you’ve measured a libc++ win and you want it everywhere. The implementation above is short. The dependency-free version composes with any container that supports random-access iteration.
-
If the input is forward-only, both libraries fall back to the swap-based algorithm. No portable cycle-decomp option exists for forward iterators (the algorithm fundamentally needs O(1) indexing).
The bigger pattern
This is one example of a structural pattern: the standard library promises a contract (std::rotate rearranges elements such that mid becomes the new first), but the implementation strategy is not part of the contract. Two conforming implementations can have order-of-magnitude different performance characteristics on the same input.
The ABI debate post from last week catalogued this kind of thing at a higher level (HFT firms build on Abseil/Folly/EASTL specifically because std semantics don’t pin down what they care about). std::rotate is the smaller version: even when you stick with std::, your performance depends on which stdlib you link against.
For most code, none of this matters. std::rotate is fast enough either way. For the 1% of cases where it shows up in a profile, knowing why the libraries differ is the first step toward making the right portability call.
Sources: Raymond Chen, The Old New Thing, “Rotation revisited” series: