To be fair, it originates from a time when memory was tighter. Is discussed with some motivating text in Programming Pearls. I can't remember the context, but I think it was in a text editor. I can look it up, if folks want some of that context here.

The problem seems less arbitrary if the chunks being rotated are large enough. Implicit in the problem is that any method that would require additional memory to be allocated would probably require memory proportional to the sizes of stuff being swapped. That could be unmanageable.

As for whether std::rotate() uses allocations, I can't say without looking. But I know it could be implemented without allocations. Maybe it's optimal in practice to use extra space. I don't think a method involving reversal of items is generally going to be the fastest. It might be the only practical one in some cases or else better for other reasons.

No - std::rotate is just doing this with in-place swaps.

Say you have "A1 A2 B1" and want to rotate (swap) adjacent blocks A1-A2 and B1, where WLOG the smaller of these is B1, and A1 is same size as B1.

What you do is first swap B1 with A1 (putting B1 into it's final place).

B1 A2 A1

Now recurse to swap A2 and A1, giving the final result:

B1 A1 A2

Swapping same-size blocks (which is what this algorithm always chooses to do) is easy since you can just iterate though both swapping corresponding pairs of elements. Each block only gets moved once since it gets put into it's final place.

> But even with that constraint ... std::rotate allocates memory! It'll throw std::bad_alloc when it can't.

This feels kinda crazy. Is there a reason why this is the case?

That's probably true for small primitive types, but if your objects are expensive to move (like a large struct) it might be beneficial to minimize swaps.

Java chooses to use the cycle method mostly. They also reference Bentley.

https://github.com/openjdk/jdk/blob/f1e0e0c25ec62a543b9cbfab...

It is discussed in that book. Very fun read, all told. Highly recommended if folks find this sort of thing fun. I think I should thumb through it again. :D

The XOR trick was sometimes useful in the past, on weird CPUs that had non-equivalent registers and which also lacked register exchange instructions (the Intel/AMD CPUs have non-equivalent registers, but they have a register exchange instruction, so they do not need this trick).

The XOR trick is not useful on modern CPUs for swapping memory blocks, because on modern CPUs the slowest operations are the memory accesses and the XOR trick needs too many memory accesses.

For swapping memory, the fastest way needs 4 memory accesses: load X, load Y, store X where Y was, store Y where X was. Each "load" and "store" in this sequence may consist of multiple load or store instructions, if multiple registers are used as the intermediate buffer. Ideally, an intermediate register buffer matching the cache line size should be used, with accesses aligned to cache lines.

Hopefully, std::rotate is written in such a way that it is compiled into such a sequence of machine instructions.

How does that work for swapping two blocks of memory with different sizes (which may require shifting the data inbetween)?

Isn't he also using 2N operations?

To swap B and D, with intervening C (i.e. B C D), what he his doing is individually reversing each of B C, and D (= total N swaps), then reversing the combined B' C' D' (= another N swaps).