Rotation revisited: A shocking discovery about gcc’s unidirectional rotation algorithm
Summary
Raymond Chen explores gcc libstdc++'s rotation algorithm for random-access iterators, revealing it is fundamentally the same as the forward-iterator rotation algorithm, just viewed from a different perspective. The post is part of a series comparing rotation implementations across compilers.
<p>Last time, we looked at <a title="Rotation revisited: Another unidirectional algorithm" href="https://devblogs.microsoft.com/oldnewthing/20260602-00/?p=112376"> the rotation algorithm used by gcc libstdc++ for random-access iterators</a>, and I concluded by noting that we’re going to make a shocking discovery.</p>
<p>As with all shocking discoveries, this one will <span style="text-decoration: line-through;">shock</span> <span style="border: solid 1px currentcolor;">disappoint</span> you.</p>
<p>The discovery is that the gcc libstdc++ algorithm is the same as <a title="How can you swap two non-adjacent blocks of memory using only forward iterators?" href="https://devblogs.microsoft.com/oldnewthing/20260105-00/?p=111962"> the forward-iterator algorithm</a>!</p>
<p>Let’s run both algorithms on a problem where the two blocks are A1, A2, A3, B1, B2, B3, B4, B5. I’ll put the old forward iterator algorithm on top and the new gcc libstdc++ algorithm below.</p>
<table style="border-collapse: collapse; text-align: center;" title="A1, A2, A3, B1, B2, B3, B4, B5" border="0" cellspacing="0" cellpadding="1">
<tbody>
<tr>
<td colspan="2" align="left">first</td>
<td> </td>
<td colspan="2" align="left">mid</td>
<td> </td>
<td> </td>
<td> </td>
<td align="left">last</td>
</tr>
<tr>
<td align="left">↓</td>
<td> </td>
<td> </td>
<td align="left">↓</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td align="left">↓</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; background: lch(from currentcolor l c h / .1);">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;">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>
</tr>
<tr>
<td align="left">↑</td>
<td> </td>
<td> </td>
<td align="left">↑</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td align="left">↑</td>
</tr>
<tr>
<td colspan="2" align="left">first</td>
<td> </td>
<td colspan="2" align="left">mid</td>
<td> </td>
<td> </td>
<td> </td>
<td align="left">last</td>
</tr>
</tbody>
</table>
<p>We swap at <code>first</code> and <code>mid</code>, then advance both pointers. The two algorithms agree until <code>first</code> reaches the end of the original A block.</p>
<table style="border-collapse: collapse; text-align: center;" title="A1, A2, A3, B1, B2, B3, B4, B5" border="0" cellspacing="0" cellpadding="1">
<tbody>
<tr>
<td> </td>
<td> </td>
<td> </td>
<td colspan="2" align="left">first</td>
<td> </td>
<td>mid</td>
<td> </td>
<td>last</td>
</tr>
<tr>
<td> </td>
<td> </td>
<td> </td>
<td align="left">↓</td>
<td> </td>
<td> </td>
<td align="left">↓</td>
<td> </td>
<td align="left">↓</td>
</tr>
<tr>
<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; background: lch(from currentcolor l c h / .1);">A1</td>
<td style="width: 2em; border: solid 1px currentcolor; background: lch(from currentcolor l c h / .1);">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;">B4</td>
<td style="width: 2em; border: solid 1px currentcolor;">B5</td>
</tr>
<tr>
<td> </td>
<td> </td>
<td> </td>
<td align="left">↑</td>
<td> </td>
<td> </td>
<td align="left">↑</td>
<td> </td>
<td align="left">↑</td>
</tr>
<tr>
<td> </td>
<td> </td>
<td> </td>
<td colspan="2" align="left">first</td>
<td> </td>
<td>mid</td>
<td> </td>
<td>last</td>
</tr>
</tbody>
</table>
<p>The old algorithm recurses in order to exchange A1, A2, A3 with B4, B4. This happens by exchanging A1 with B4 and A2 with B5.</p>
<p>The new algorithm just keeps swapping <code>first</code> with <code>mid</code>, which also exchanges A1 with B4 and A2 with B5.</p>
<table style="border-collapse: collapse; text-align: center;" title="A1, A2, A3, B1, B2, B3, B4, B5" border="0" cellspacing="0" cellpadding="1">
<tbody>
<tr>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td colspan="2" align="left" valign="bottom">first</td>
<td> </td>
<td>mid<br />
last</td>
</tr>
<tr>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td align="left">↓</td>
<td> </td>
<td> </td>
<td align="left">↓</td>
</tr>
<tr>
<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; background: lch(from currentcolor l c h / .1);">A3</td>
<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; background: lch(from currentcolor l c h / .1);">A2</td>
</tr>
<tr>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td align="left">↑</td>
<td> </td>
<td> </td>
<td align="left">↑</td>
</tr>
<tr>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td colspan="2" align="left" valign="baseline">first</td>
<td> </td>
<td>last<br />
mid</td>
</tr>
</tbody>
</table>
<p>The old algorithm now recurses to swap the A3 block with the A1+A2 block. And that’s what the new algorithm does, too.</p>
<p>So it’s the same algorithm, just with a different point of view. It’s another case of <a title="The geeky thrill of discovering that two things are really the same thing, just with different labels" href="https://devblogs.microsoft.com/oldnewthing/20140414-01/?p=1253"> the geeky thrill of discovering that two things are really the same thing, just with different labels</a>.</p>
<p>Now, the two algorithms are not identical. The new algorithm is symmetric and performs its swaps from right to left if the larger block is on the right. The old algorithm always operates from left to right.</p>
<p>But the similarity is striking.</p>
<p>Next time, we’ll look at how clang performs rotation by decomposing into cycles.</p>
<p>The post <a href="https://devblogs.microsoft.com/oldnewthing/20260603-00/?p=112378">Rotation revisited: A shocking discovery about gcc’s unidirectional rotation algorithm</a> appeared first on <a href="https://devblogs.microsoft.com/oldnewthing">The Old New Thing</a>.</p>
View Cached Full Text
Cached at: 06/05/26, 02:19 AM
# Rotation revisited: A shocking discovery about gcc's unidirectional rotation algorithm - The Old New Thing
Source: [https://devblogs.microsoft.com/oldnewthing/20260603-00?p=112378](https://devblogs.microsoft.com/oldnewthing/20260603-00?p=112378)
Last time, we looked at[the rotation algorithm used by gcc libstdc\+\+ for random\-access iterators](https://devblogs.microsoft.com/oldnewthing/20260602-00/?p=112376), and I concluded by noting that we’re going to make a shocking discovery\.
As with all shocking discoveries, this one willshockdisappointyou\.
The discovery is that the gcc libstdc\+\+ algorithm is the same as[the forward\-iterator algorithm](https://devblogs.microsoft.com/oldnewthing/20260105-00/?p=111962)\!
Let’s run both algorithms on a problem where the two blocks are A1, A2, A3, B1, B2, B3, B4, B5\. I’ll put the old forward iterator algorithm on top and the new gcc libstdc\+\+ algorithm below\.
firstmidlast↓↓↓A1A2A3B1B2B3B4B5↑↑↑firstmidlastWe swap at`first`and`mid`, then advance both pointers\. The two algorithms agree until`first`reaches the end of the original A block\.
firstmidlast↓↓↓B1B2B3A1A2A3B4B5↑↑↑firstmidlastThe old algorithm recurses in order to exchange A1, A2, A3 with B4, B4\. This happens by exchanging A1 with B4 and A2 with B5\.
The new algorithm just keeps swapping`first`with`mid`, which also exchanges A1 with B4 and A2 with B5\.
firstmid
last↓↓B1B2B3B4B5A3A1A2↑↑firstlast
midThe old algorithm now recurses to swap the A3 block with the A1\+A2 block\. And that’s what the new algorithm does, too\.
So it’s the same algorithm, just with a different point of view\. It’s another case of[the geeky thrill of discovering that two things are really the same thing, just with different labels](https://devblogs.microsoft.com/oldnewthing/20140414-01/?p=1253)\.
Now, the two algorithms are not identical\. The new algorithm is symmetric and performs its swaps from right to left if the larger block is on the right\. The old algorithm always operates from left to right\.
But the similarity is striking\.
Next time, we’ll look at how clang performs rotation by decomposing into cycles\.
### Category
### Topics
## Author
Raymond has been involved in the evolution of Windows for more than 30 years\. In 2003, he began a Web site known as The Old New Thing which has grown in popularity far beyond his wildest imagination, a development which still gives him the heebie\-jeebies\. The Web site spawned a book, coincidentally also titled The Old New Thing \(Addison Wesley 2007\)\. He occasionally appears on the Windows Dev Docs Twitter account to tell stories which convey no useful information\.
Similar Articles
Rotation revisited: Another unidirectional algorithm
Raymond Chen revisits a unidirectional rotation algorithm for swapping adjacent memory blocks, explaining its recursive approach and performance characteristics.
Rotation revisited: Cycle decomposition in clang’s libcxx
The article delves into the cycle decomposition algorithm used in clang's libcxx for rotation, explaining how it achieves the minimum number of swaps by computing the greatest common divisor (gcd) to determine the number of cycles.
Rotation revisited: Avoiding having to calculate the gcd when doing cycle decomposition
This article explains a technique to avoid calculating the greatest common divisor when performing cycle decomposition in std::rotate, as used in OpenJDK's Collections.rotate method. It provides a C++ implementation that tracks the count of rotated elements to determine when all cycles are complete.
Neoclassical C++: segmented iterators revisited
Revisits Matt Austern's 2000 paper on segmented iterators, which enable hierarchical algorithms to exploit data structure segmentation for performance, and discusses modern adoption in libc++ and Boost libraries.
When compilers surprise you
Matt Godbolt explores compiler optimizations that convert an O(n) summation loop into an O(1) closed-form solution, highlighting how Clang and GCC employ sophisticated techniques like loop unrolling and mathematical simplification to dramatically improve code performance.