most efficient way of swapping values c++

Question

I was wondering what the most efficient, in terms of operations, way of swapping integers is in c++, and why? Is something like:

int a =..., b = ...;
a = a + b;
b = a - b;
a = a - b;

more efficient than using a temporary? Are there any other more efficient ways? (not asking for just other ways to swap the ints) and why would they be more efficient?

Answer 1

Assigning values is always faster than doing arithmetic operations.

C++ implementation for std::swap is

template<typename T> void swap(T& t1, T& t2) {
    T temp = std::move(t1); // or T temp(std::move(t1));
    t1 = std::move(t2);
    t2 = std::move(temp);
}

So to use a temporary variable is better than doing arithmetic trick.
And to use std::swap is even better because To reinvent the wheel in programming is never a good idea

Answer 2

The best way is to trust your compiler and use the C++ standard library functions. They are designed for each other.

std::swap will win.

You could use an XOR swap for an int (which doesn't require a temporary), but these days it would still perform less well than std::swap.

Answer 3

In my case, std::swap is 5% slower than the following (both with O3 optimization). In general, std::swap() function calls copy constructor that will be probably always slower than just copy part of memory.

#include <cstring>

size_t objectSize = sizeof(Object);
char temp[objectSize];

loop {
    loop {
        memcpy(temp, a, objectSize);
        memcpy(a, b, objectSize);
        memcpy(b, temp, objectSize);
    }
}

Edit: Using stack instead of heap memory allocation.

Answer 4

Most efficient way is to NOT try to do it yourself. It really depends on why/were you want to do this. Trying to be clever and writing obscure code in C++ only reduces the chance of the compiler to optimize it correctly.

Lets say we use the ±-way you wrote: First the values a and b have to be loaded from memory. Then you are doing 3 arithmetic-operations to "swap" their content. And lastly the 2 values have to be stored in memory again. (Not gonna use actual assembly-code as i am not well versed with it and this pseudo-assembly is easier to get the concept accross )

load a into register rA
load b into register rB
add rB to rA and store in rA
subtract rB from rA and stor in rB
subtract rB from rA and store in rA
store register rA to memory b
store register rB to memory a

If the compiler would do exactly what you wanted (likely he will ignore it and make it better) that would be: 2 loads, 3 simple math-funtions, 2 stores - 7 operations.

It could also do slightly better as addition/subtraction can be done with 1 value from memory.

load 'a' into register rA
add b to rA and store in rA
subtract b from rA and store in rB
subtract rB from rA and store in rA
store rA to a
store rB to b

If we use an extra tmp-variable:

int a =..., b = ...;
int tmp = a;
a = b;
b = tmp;

The compiler will likely recognize that "tmp" is only a temporary variable only used for swapping the 2 values so it would not assign it a memory location btu only use registers. In that case what it would do is something along the lines of:

load a into register rA
load b into register rB
store register rA to memory b
store register rB to memory a

Only 4 operations - Basically the fastest it can do it as you need to load 2 values and you need to store 2 values and nothing else. (for moder nx86_64 processors there is no command that would just swap 2 values in memory - other architectures might have it and be even faster in that case).

Doing those arithmetic operations (or the xor-trick) is a nice excercise but on modern x86 CPUs with all but the most basic compilers it will not be "more efficient" in any form. It will user just as many registers, the same amount of memory for the variables, but require more instructions to do the same job. In general you should not attempt to outsmart the compiler unless you have checked your code, tested and benchmarked it and found that the generated assembly is not as good as it can be.

But it is nearly never needed to go to that level for optimisation and your time is better spent looking at the larger picture.

Answer 5

#include <iostream>
using namespace std;

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

int main() {
    int a=1,b=6;
    swap(a,b);
    cout<<a<<b;
    return 0;
}