CODEWITHSUNDEEP
c++
user11337105
user11337105

Reputation:

Efficient Swap Using References?

I've been reading up on move semantics, and I believe that a really efficient swap is the following (we'll keep everything as int for now instead of using generics, for ease):

void swap(int& a, int& b) { 
    int tmp = std::move(a);
    a = std::move(b); 
    b = std::move(tmp);
}

That's the correct swap implementation (for ints) right? Line 2 doesn't create an extra item in RAM for tmp, right?

My other question is, does this same code using references instead of std::move also do just as well of a job (as in, not creating an extra variable for tmp) as the Move Semantics example above?

void swap(int& a, int& b) { 
    int tmp = &a;
    a = &b; 
    b = &tmp;
}

Does the above code create an extra variable for tmp? Does it correctly swap a and b?

Upvotes: 1

Views: 540

Answers (2)

Michael Kenzel
Michael Kenzel

Reputation: 15943

Built-in types do not have a move constructor or move assignment operator, so your first version is really no different from

void swap(int& a, int& b)
{ 
    int tmp = a;
    a = b; 
    b = tmp;
}

Your second version won't compile. Most likely, however, you just meant to write the same thing as my version above anyways. Both versions introduce a temporary variable named tmp to hold on to the value that needs to be assigned to one swappee while the other one has its value changed.

Do not operate under the assumption that every construct in your code, such as a variable, has exactly one corresponding construct in the generated machine code, such as an "extra item in RAM", that it will always result in. This is not how modern compilers work. The job of a compiler is not to take every line of source code and perform a 1:1 replacement with a specific sequence of machine instructions. The job of a compiler is to take the entire program that you have described in the C++ language and generate an equivalent program in, e.g., machine code, that, when executed, will behave in a way that is indistinguishable from the behavior of the program that your C++ source code described.

If you take a look at the assembly that's generated, you'll see that, in the case of plain integers being swapped, no sane compiler will move this temporary variable to memory but use registers to swap the values. You can trust your compiler to know what is the most efficient way to swap two integers on the given target architecture. If you can't trust your compiler to know that, then you should be looking for a better compiler…

Actually, it's hard to really say much about how "efficient" this swap function is just by looking at the code it generates in isolation. In practice, a function such as the swap above should normally be optimized away completely. The only trace it will normally leave in machine code is the effect it has on dataflow (example here), but there will never be an actual call instruction to invoke a separate piece of machine code to do the swapping. The really important thing to do when it comes to optimizing swap is to make sure that the compiler can actually optimize it away (which generally comes down to making sure that it's defintion is known wherever it is used).

Moral of the story: Focus not on describing how you think the machine code should work, but on expressing your intentions in a way that is readable to both you and the compiler, and, first and foremost, in a way that correctly describes the intended behavior based on the rules of the language, not the rules of the target hardware. Never rely on what you think a certain language construct maps to at the machine level. Rely on what the C++ language says about the behavior a certain language construct gives rise to. Modern C++ compilers are very good at translating complex C++ code into very lean and efficient machine code that does precisely what was expressed in C++. They do so, however, by aggressively exploiting the fact that the behavior that was expressed is also the only behavior that has to be respected. As a result, modern C++ compilers are very bad at generating machine code that does not what was written but merely thought at the moment of writing…

Upvotes: 3

Alecto
Alecto

Reputation: 10740

Swap using references would look like this:

void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

You only put the & when declaring that it’s a reference, but not when using it. References can be used like regular variables.

Because you’re working with ints, this swap is just as efficient as the swap with std::move. Move semantics only provide a benefit when you’re working with classes that own resources.

For example, a vector owns a pointer to an array, so moving a vector is much more efficient than copying a vector because when you copy a vector, you have to copy all the data in the vector’s internal array. If you move a vector, on the other hand, it doesn’t have to copy the internal array. It only has to copy the pointer to the array, and that’s much, much faster.

Upvotes: 2

Related Questions