Swap (computer science)

Swap (computer science)

:"For other uses of "swap", see swap (disambiguation)."In computer programming, the act of swapping two variables 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):

data_item x := 1data_item y := 0

To swap them one might do swap (x, y);(In many programming languages 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 types and possibly entire containers.

wap methods

Swapping data is a very important component of numerous algorithms. For example, many of the sorting algorithms, especially comparison sorts, 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 variable:

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 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

:main|XOR swap algorithmXOR 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 integers. However, it is, in theory, capable of swapping any two values which can be represented by fixed-length bitstrings.

wap through addition and subtraction

:main|swap by addition and subtractionThis 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 containers.
* When swapping variables of a fixed size, arithmetic overflow becomes an issue.

wapping containers

Containers which allocate memory from the heap using pointers 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 specializes its built-in swap function to exchange containers efficiently this way. [http://www.sgi.com/tech/stl/swap.html#2]

As pointer variables are usually of a fixed size (e.g., most desktop computers have pointers 32 bits long), and they are numeric, they can be swapped quickly using XOR swap.

Facilitation of swapping in modern computers

Dedicated instructions

Because of the many applications of swapping data in computers, most processors now provide the ability to swap variables directly through built-in instructions. x86 processors, for example, include an "XCHG" instruction to swap two registers 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. However, an "XCHG" is usually the fastest way to swap two machine-size words residing in registers.

Register renaming may also be used to swap registers efficiently.

Parallel execution

With the advent of instruction pipelining in modern computers and multi-core processors 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 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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Thrash (computer science) — In computer science, thrash (verb), is the term used to describe a degenerate situation on a computer where increasing resources are used to do a decreasing amount of work. In this situation the system is said to be thrashing . Usually it refers… …   Wikipedia

  • Kernel (computer science) — In computer science, the kernel is the central component of most computer operating systems (OS). Its responsibilities include managing the system s resources (the communication between hardware and software components). As a basic component of… …   Wikipedia

  • Thread (computer science) — This article is about the concurrency concept. For the multithreading in hardware, see Multithreading (computer architecture). For the form of code consisting entirely of subroutine calls, see Threaded code. For other uses, see Thread… …   Wikipedia

  • Thrashing (computer science) — In computer science, thrashing is a situation where large amounts of computer resources are used to do a minimal amount of work, with the system in a continual state of resource contention.[1][2][3] Once started, thrashing is typically self… …   Wikipedia

  • Lock (computer science) — In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies. Contents 1 Types 2… …   Wikipedia

  • Garbage collection (computer science) — This article is about garbage collection in memory management. For garbage collection in an SSD, see garbage collection (SSD). For other uses, see garbage collection. In computer science, garbage collection (GC) is a form of automatic memory… …   Wikipedia

  • Swap — A swap is the barter of one thing for another. Swap may also refer to:* Swap (computer science), exchanging two variables in the memory of a computer * Swap (finance), a derivative in which two parties agree to exchange one stream of cash flows… …   Wikipedia

  • Computer multitasking — In computing, multitasking is a method where multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning… …   Wikipedia

  • Computer data storage — 1 GB of SDRAM mounted in a personal computer. An example of primary storage …   Wikipedia

  • Compare-and-swap — In computer science, the compare and swap (CAS) CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”