Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How fast is std::swap for integer types?

Tags:

STL implements a generic std::swap function to swap 2 values. It can be presented in the following way:

template <class T> void swap (T& a, T& b) {   T c(std::move(a));   a=std::move(b);   b=std::move(c); } 

However, there is a XOR swap algorithm to swap 2 integers (http://en.wikipedia.org/wiki/XOR_swap_algorithm):

void swap_u( size_t& x, size_t& y ) {    x = x^y;    y = x^y;    x = x^y; } 

My questions:

  1. Is it an optimization nowadays (on x86 or arm)?
  2. Does C++ standard favor this kind of optimization?
  3. Are there any real STL implementations in the wild that have std::swap specialization for integers?
like image 412
Sergey K. Avatar asked Aug 17 '13 09:08

Sergey K.


People also ask

What is the time complexity of swap function in C++?

Complexity. For arrays the function has N complexity as the operation of swapping is individually performed on each element. For non array the function has constant complexity.

Is XOR swap faster?

On modern CPU architectures, the XOR technique can be slower than using a temporary variable to do swapping.

What does std :: swap do?

The function std::swap() is a built-in function in the C++ Standard Template Library (STL) which swaps the value of two variables. Parameters: The function accepts two mandatory parameters a and b which are to be swapped. The parameters can be of any data type.

Why do we use swap in C++?

swap() function in C++ The swap() function is used to swap two numbers. By using this function, you do not need any third variable to swap two numbers.


2 Answers

In the vast majority of situations, XOR swap is not an optimisation.

See this wiki entry.

In most practical scenarios, the trivial swap algorithm using a temporary register is more efficient. Limited situations in which XOR swapping may be practical include:

  • On a processor where the instruction set encoding permits the XOR swap to be encoded in a smaller number of bytes;
  • In a region with high register pressure, it may allow the register allocator to avoid spilling a register.
  • In microcontrollers where available RAM is very limited.

Because these situations are rare, most optimizing compilers do not generate XOR swap code.

Also note that your implementation of XOR swap is broken. You need to first check that x and y aren't aliased. This check will definitely make XOR swap slower.

I'm not aware of any standard library implementation that uses XOR swap.

Note that, regardless of what the standard library implements, if XOR swap were really faster than normal swap then optimizing compilers would do a peephole optimization to turn it into an XOR swap. This really is a case of just letting the compiler choose for you.

like image 141
Peter Alexander Avatar answered Oct 23 '22 16:10

Peter Alexander


XOR swap is really only a gimmick and can fail in certain cases (e.g. both variables are references to the same object).

XOR swap is also not particularly efficient as it has serial dependencies so it will always take at least three instruction cycles. Using a straightforward swap with a temporary has fewer dependencies, allowing for some parallelism on modern superscalar CPUs - on some CPUs it can even be implemented in one instruction, but even without special instructions it may well execute in two cycles.

like image 27
Paul R Avatar answered Oct 23 '22 17:10

Paul R