Swap (computer science)
Encyclopedia
In computer programming
, the act of swapping two variable
s refers to mutually exchanging the values of the variables. Usually, this is done with the data in memory
. For example, in a program
, two variables may be defined thus (in pseudocode
):
To swap them one might do
swap (x, y);
(In many programming language
s where the swap function
is built-in; in C++
, overloads are provided allowing std::swap to swap some large structures in O(1) time.)
After swap is performed, x will contain the value 0 and y will contain 1; their values have been exchanged. Of course, this operation may be generalized to other types of values, such as strings
, aggregated data type
s and possibly entire container
s.
s. For example, many of the sorting algorithm
s, especially comparison sort
s, utilize swaps to change the positions of data.
:
While this is conceptually simple and in many cases the only convenient way to swap two variables, it uses extra memory. Although this should not be a problem in most applications, the sizes of the values being swapped may be huge (which means the temporary variable may occupy a lot of memory as well), or the swap operation may need to be performed many times, as in sorting algorithms.
In addition, swapping two variables in object-oriented
languages such as C++
may involve one call to the class
constructor
and destructor
for the temporary variable, and three calls to the copy constructor. Some classes may allocate memory in the constructor and deallocate it in the destructor, thus creating expensive calls to the system. Copy constructors for classes containing a lot of data, e.g. in an array, may even need to copy the data manually.
XOR swap uses the XOR operation to swap two numeric variables. It is generally touted to be faster than the naive method mentioned above; however it does have disadvantages. XOR swap is generally used to swap low-level data types, like integer
s. However, it is, in theory, capable of swapping any two values which can be represented by fixed-length bitstrings.
This method swaps two variables by adding and subtracting their values. This is rarely used in practical applications, mainly because:
s which allocate memory from the heap using pointer
s may be swapped in a single operation, by swapping the pointers alone. This is usually found in programming languages supporting pointers, like C/C++
. For example, the STL
overloads its built-in swap function to exchange containers efficiently this way.
As pointer variables are usually of a fixed size (e.g., most desktop computers have pointers 32 bit
s long), and they are numeric, they can be swapped quickly using XOR swap.
s now provide the ability to swap variables directly through built-in instructions. x86
processors, for example, include an XCHG instruction to swap two register
s directly without requiring that a third temporary register is used. A CMPXCHG instruction, which compares and conditionally swaps two registers, is even provided in some processor architectures.
XCHG may not be as efficient as one may think. For example, in x86
processors, XCHG will implicitly lock access to any operands in memory to keep the operation atomic, and so may not be efficient when swapping memory. Such locking is important when it is used to implement thread-safe synchronization, as in mutexes. However, an XCHG is usually the fastest way to swap two machine-size words residing in register
s. Register renaming
may also be used to swap registers efficiently.
in modern computers and multi-core processor
s facilitating parallel computing
, two or more operations can be performed at once. This can speed up the lowly temporary-variable swap algorithm and give it an edge over other algorithms. For example, the XOR swap algorithm
requires sequential execution of three instructions. However, using two temporary registers, two processors executing in parallel can swap two variables in two clock cycles:
Step 1
Processor 1: temp_1 := X
Processor 2: temp_2 := Y
Step 2
Processor 1: X := temp_2
Processor 2: Y := temp_1
This uses fewer instructions; but other temporary registers may be in use, and four instructions are needed instead of three. In any case, in practice this could not be implemented in separate processors, as it violates Bernstein's conditions for parallel computing. It would be infeasible to keep the processors sufficiently in sync with one another for this swap to have any significant advantage over traditional versions. However, it can be used to optimize swapping for a single processor with multiple load/store units.
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
, the act of swapping two variable
Variable (programming)
In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...
s refers to mutually exchanging the values of the variables. Usually, this is done with the data in memory
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....
. For example, in a program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
, two variables may be defined thus (in pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
):
data_item x := 1
data_item y := 0
To swap them one might do
swap (x, y);
(In many programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s where the swap function
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
is built-in; in C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, overloads are provided allowing std::swap to swap some large structures in O(1) time.)
After swap is performed, x will contain the value 0 and y will contain 1; their values have been exchanged. Of course, this operation may be generalized to other types of values, such as strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
, aggregated data type
Data type
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
s and possibly entire container
Container (data structure)
In computer science, a container is a class, a data structure, or an abstract data type whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules...
s.
Swap methods
Swapping data is a very important component of numerous algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s. For example, many of the sorting algorithm
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
s, especially comparison sort
Comparison sort
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation that determines which of two elements should occur first in the final sorted list...
s, utilize swaps to change the positions of data.
Using a temporary variable
The simplest and probably most widely used method to swap two variables is to use a third temporary variableTemporary variable
In computer programming, a temporary variable is a variable whose purpose is short-lived, usually to hold temporary data that will soon be discarded, or before it can be placed at a more permanent memory location. Because it is short-lived, it is usually declared with local scope...
:
define swap (x, y)
temp := x
x := y
y := temp
While this is conceptually simple and in many cases the only convenient way to swap two variables, it uses extra memory. Although this should not be a problem in most applications, the sizes of the values being swapped may be huge (which means the temporary variable may occupy a lot of memory as well), or the swap operation may need to be performed many times, as in sorting algorithms.
In addition, swapping two variables in object-oriented
Object-oriented programming
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
languages such as C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
may involve one call to the class
Class (computer science)
In object-oriented programming, a class is a construct that is used as a blueprint to create instances of itself – referred to as class instances, class objects, instance objects or simply objects. A class defines constituent members which enable these class instances to have state and behavior...
constructor
Constructor (computer science)
In object-oriented programming, a constructor in a class is a special type of subroutine called at the creation of an object. It prepares the new object for use, often accepting parameters which the constructor uses to set any member variables required when the object is first created...
and destructor
Destructor (computer science)
In object-oriented programming, a destructor is a method which is automatically invoked when the object is destroyed...
for the temporary variable, and three calls to the copy constructor. Some classes may allocate memory in the constructor and deallocate it in the destructor, thus creating expensive calls to the system. Copy constructors for classes containing a lot of data, e.g. in an array, may even need to copy the data manually.
XOR swap
XOR swap uses the XOR operation to swap two numeric variables. It is generally touted to be faster than the naive method mentioned above; however it does have disadvantages. XOR swap is generally used to swap low-level data types, like integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s. However, it is, in theory, capable of swapping any two values which can be represented by fixed-length bitstrings.
Swap through addition and subtraction
This method swaps two variables by adding and subtracting their values. This is rarely used in practical applications, mainly because:
- It can only swap numeric variables; it may not be possible or logical to add or subtract complex data types, like containersContainer (data structure)In computer science, a container is a class, a data structure, or an abstract data type whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules...
. - When swapping variables of a fixed size, arithmetic overflowArithmetic overflowThe term arithmetic overflow or simply overflow has the following meanings.# In a computer, the condition that occurs when a calculation produces a result that is greater in magnitude than that which a given register or storage location can store or represent.# In a computer, the amount by which a...
becomes an issue.
Swapping containers
ContainerContainer (data structure)
In computer science, a container is a class, a data structure, or an abstract data type whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules...
s which allocate memory from the heap using pointer
Data pointer
In computer science, a pointer is a programming language data type whose value refers directly to another value stored elsewhere in the computer memory using its address...
s may be swapped in a single operation, by swapping the pointers alone. This is usually found in programming languages supporting pointers, like C/C++
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
. For example, the STL
Standard Template Library
The Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...
overloads its built-in swap function to exchange containers efficiently this way.
As pointer variables are usually of a fixed size (e.g., most desktop computers have pointers 32 bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s long), and they are numeric, they can be swapped quickly using XOR swap.
Dedicated instructions
Because of the many applications of swapping data in computers, most processorCentral processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
s now provide the ability to swap variables directly through built-in instructions. x86
X86 architecture
The term x86 refers to a family of instruction set architectures based on the Intel 8086 CPU. The 8086 was launched in 1978 as a fully 16-bit extension of Intel's 8-bit based 8080 microprocessor and also introduced segmentation to overcome the 16-bit addressing barrier of such designs...
processors, for example, include an XCHG instruction to swap two register
Processor register
In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...
s directly without requiring that a third temporary register is used. A CMPXCHG instruction, which compares and conditionally swaps two registers, is even provided in some processor architectures.
XCHG may not be as efficient as one may think. For example, in x86
X86 architecture
The term x86 refers to a family of instruction set architectures based on the Intel 8086 CPU. The 8086 was launched in 1978 as a fully 16-bit extension of Intel's 8-bit based 8080 microprocessor and also introduced segmentation to overcome the 16-bit addressing barrier of such designs...
processors, XCHG will implicitly lock access to any operands in memory to keep the operation atomic, and so may not be efficient when swapping memory. Such locking is important when it is used to implement thread-safe synchronization, as in mutexes. However, an XCHG is usually the fastest way to swap two machine-size words residing in register
Processor register
In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...
s. Register renaming
Register renaming
In computer architecture, register renaming refers to a technique used to avoid unnecessary serialization of program operations imposed by the reuse of registers by those operations.-Problem definition:...
may also be used to swap registers efficiently.
Parallel execution
With the advent of instruction pipeliningInstruction pipeline
An instruction pipeline is a technique used in the design of computers and other digital electronic devices to increase their instruction throughput ....
in modern computers and multi-core processor
Multi-core (computing)
A multi-core processor is a single computing component with two or more independent actual processors , which are the units that read and execute program instructions...
s facilitating parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
, two or more operations can be performed at once. This can speed up the lowly temporary-variable swap algorithm and give it an edge over other algorithms. For example, the XOR swap algorithm
XOR swap algorithm
In computer programming, the XOR swap is an algorithm that uses the XOR bitwise operation to swap values of distinct variables having the same data type without using a temporary variable...
requires sequential execution of three instructions. However, using two temporary registers, two processors executing in parallel can swap two variables in two clock cycles:
Step 1
Processor 1: temp_1 := X
Processor 2: temp_2 := Y
Step 2
Processor 1: X := temp_2
Processor 2: Y := temp_1
This uses fewer instructions; but other temporary registers may be in use, and four instructions are needed instead of three. In any case, in practice this could not be implemented in separate processors, as it violates Bernstein's conditions for parallel computing. It would be infeasible to keep the processors sufficiently in sync with one another for this swap to have any significant advantage over traditional versions. However, it can be used to optimize swapping for a single processor with multiple load/store units.