[HN Gopher] Swapping two blocks of memory inside a larger block,...
___________________________________________________________________
Swapping two blocks of memory inside a larger block, in constant
memory
Author : paulmooreparks
Score : 40 points
Date : 2026-01-02 09:19 UTC (4 days ago)
(HTM) web link (devblogs.microsoft.com)
(TXT) w3m dump (devblogs.microsoft.com)
| praptak wrote:
| I think this was discussed in Jon Bentley "programming pearls"?
|
| Also in the same book it was mentioned that the disjoint cycles
| method (also mentioned in the article) was worse for
| paging/caching than the three reverses method.
| ot wrote:
| 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.
| praptak wrote:
| Yeah, it might be interesting to run some profiling of both
| algorithms and see how they perform dependent on the size of
| the blocks being swapped (which doesn't even have to be equal
| to the size of the object in the array).
| taeric wrote:
| 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
| jnellis wrote:
| Java chooses to use the cycle method mostly. They also
| reference Bentley.
|
| https://github.com/openjdk/jdk/blob/f1e0e0c25ec62a543b9cbfab...
| j4cobgarby wrote:
| You can also use the XOR trick, not sure what's faster though.
| adrian_b wrote:
| 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.
| Someone wrote:
| > with accesses aligned to cache lines.
|
| You want that, but can be tricky because the _from_ and _to_
| regions may have different alignment.
|
| Also, the XOR trick introduces data dependencies. That slows
| down pipelined CPUs.
| SkiFire13 wrote:
| How does that work for swapping two blocks of memory with
| different sizes (which may require shifting the data
| inbetween)?
| jhatax wrote:
| As a commenter noted as well, you can perform the swap using two
| std::rotate calls vs. three (less than 2N operations). This said,
| Raymond's use of reverse is still most efficient at N operations
| (not considering paging/caching issues).
| HarHarVeryFunny wrote:
| 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).
| TrainedMonkey wrote:
| Apparently the trick is two std::rotates :
| https://devblogs.microsoft.com/oldnewthing/20260101-00/?p=11...
|
| As a side note, love how Raymond handled that, no fluff and
| straight to the point. Beginners mind and all that.
| trjordan wrote:
| There's something about this that's unsatisfying to me. Like it's
| just a trivia trick.
|
| My first read of this was "this seems impossible." You're asked
| to move bits around without any working space, because you're not
| allowed to allocate memory. I guess you could interpret this
| pedantically in C/C++ land and decide that they mean no
| additional usage of the heap, so there's other places (registers,
| stack, etc.) to store bits. The title is "in constant memory" so
| I guess I'm allowed some constant memory, which is vaguely at
| odds with "can you do this without allocating additional memory?"
| in the text.
|
| But even with that constraint ... std::rotate allocates memory!
| It'll throw std::bad_alloc when it can't. It's not using it for
| the core algorithm (... which only puts values on the heap ...
| which I guess is not memory ...), but that function can 100%
| allocate new memory in the right conditions.
|
| It's cool you can do this simply with a couple rotates, but it
| feels like a party trick.
| SkiFire13 wrote:
| > 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?
| HarHarVeryFunny wrote:
| 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.
| hacker_homie wrote:
| You are thinking of std::swap, std::rotate does throw
| bad_alloc
| HarHarVeryFunny wrote:
| I see it says that it may throw bad_alloc, but it's not
| clear why, since the algorithm itself (e.g see "Possible
| implementation" below) can easily be done in-place.
|
| https://en.cppreference.com/w/cpp/algorithm/rotate.html
|
| I'm wondering if the bad_alloc might be because a single
| temporary element (of whatever type the iterators point to)
| is going to be needed to swap each pair of elements, or
| maybe to allow for an inefficient implementation that chose
| not to do it in-place?
| taeric wrote:
| 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.
| osullivj wrote:
| Also useful for cache locality, a more recent trend. But I
| guess that's just another slighlty diff case of tight mem;
| this time in the cache rather than RAM generally.
| HarHarVeryFunny wrote:
| I did something similar back in the day to support block-move
| for an editor running on a memory constrained 8-bit micro
| (BBC Micro). It had to be done in-place since there was no
| guarantee you'd have enough spare memory to use a temporary
| buffer, and also more efficient to move each byte once rather
| than twice (in/out of temp buffer).
| HarHarVeryFunny wrote:
| Couldn't this be done in 2 rotates rather than 3 :
|
| A B C D E
|
| A C B D E -- after rotate B, C
|
| A D C B E -- after rotate C-B, D
|
| Complexity would seem to be the same as the reverse method, since
| every element in the original B-D range is getting moved twice.
___________________________________________________________________
(page generated 2026-01-06 23:10 UTC)