Discussion on: How can you swap two variables without using a third?

[Dustin King]

x, y = y, x #

[Dustin King]

To be a little bit sneaky, use part of the function itself as swap space. This would only work if that space could be after the return instruction.

In pseudo-C:

#define NOP {32 bits of assembly NOP instructions};

void swap(int* a, int* b){

    *&yep = *a;
    *a = *b;
    *b = *&yep;

    return;

    yep:
    NOP;
}

This isn't thread-safe though, and a decent operating system might throw exceptions if you try to have executable code modify itself.

[Nick Karnik]

It creates more memory though.

[Zuodian Hu]

The NOPs don't actually give you any memory. Those NOPs are wherever the executable image was loaded in memory, and the variable yep is on the stack. Assuming your standard C memory model.

[Nick Karnik]

I misread the post on the phone, but I see what the code is doing. Although, I'm not sure what assigning to NOP does?

[Dustin King]

C memory layout:

(source)

The function code itself is in the text segment. The variables for a particular invocation of the function are on the stack. Padding out the function with NOP creates space within the function, which I'm using as a variable. Basically I'm interpreting the "working memory" part of the post to mean "variables allocated on the stack". Now that I think of it, what I'm doing is basically a static variable, which (according to the link) C puts in the initialized data segment if you do it the right way, but then it would legitimately be a variable so I'd lose.

It's probably not a legit way to do things (and might be impossible if the text segment is read-only as the link says it might be), but people had already posted the legit ways.

[Nick Karnik]

Thanks for that explanation. It's been a while since I've written C/C++, but this approach makes sense. I love the thought process of cleverly using that available memory, even if it doesn't work out. 👏👏👏

[Zuodian Hu]

The variable yep is declared within a function body without a static qualifier, which means it's what the C standard calls an automatic storage duration variable. This means its duration is between the curly braces, and most compilers will use a register or put it on the stack.

Being completely nitpicky here, but the variable yep is declared after its use and also without a type. I'm sure modern compilers wouldn't even let you do that.

Modern operating systems load the text segment into a virtual memory page marked as read-only. So yes, even if this compiles, it will generate a segfault on modern operating systems.

[Dustin King]

yep isn't a variable, though, it's a label, representing an offset from the start of the function.

I agree compilers and OS's will tend to prevent this. I said as much before, and trying to create a proof of concept in assembly has born that out.

It wasn't a completely fruitless exercise though, as it was a chance to learn some assembly, which provided some insights about the challenge that I might make a post about. Basically, swapping using math might not actually be more memory-efficient (however you define that, and without the kind of cheating I've been talking about) than swapping using "a variable".