Memory ordering describes the order of accesses to computer memory by a CPU. The term can refer either to the memory ordering generated by the
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...
during
compile time
In computer science, compile time (or compile-time) describes the time window during which a computer program is compiled.
The term is used as an adjective to describe concepts related to the context of program compilation, as opposed to concep ...
, or to the memory ordering generated by a CPU during
runtime.
In modern
microprocessor
A microprocessor is a computer processor where the data processing logic and control is included on a single integrated circuit, or a small number of integrated circuits. The microprocessor contains the arithmetic, logic, and control circ ...
s, memory ordering characterizes the CPU's ability to reorder memory operations – it is a type of
out-of-order execution. Memory reordering can be used to fully utilize the bus-bandwidth of different types of memory such as
cache
Cache, caching, or caché may refer to:
Places United States
* Cache, Idaho, an unincorporated community
* Cache, Illinois, an unincorporated community
* Cache, Oklahoma, a city in Comanche County
* Cache, Utah, Cache County, Utah
* Cache County ...
s and
memory bank
A memory bank is a logical unit of storage in electronics, which is hardware-dependent. In a computer, the memory bank may be determined by the memory controller along with physical organization of the hardware memory slots. In a typical synchro ...
s.
On most modern
uniprocessors memory operations are not executed in the order specified by the program code. In single threaded programs all operations appear to have been executed in the order specified, with all out-of-order execution hidden to the programmer – however in multi-threaded environments (or when interfacing with other hardware via memory buses) this can lead to problems. To avoid problems,
memory barrier
In computing, a memory barrier, also known as a membar, memory fence or fence instruction, is a type of barrier instruction that causes a central processing unit (CPU) or compiler to enforce an ordering constraint on memory operations issued b ...
s can be used in these cases.
Compile-time memory ordering
Most programming languages have some notion of a thread of execution which executes statements in a defined order. Traditional compilers translate high-level expressions to a sequence of low-level instructions relative to a
program counter at the underlying machine level.
Execution effects are visible at two levels: within the program code at a high level, and at the machine level as viewed by other threads or processing elements in
concurrent programming
Concurrent means happening at the same time. Concurrency, concurrent, or concurrence may refer to:
Law
* Concurrence, in jurisprudence, the need to prove both ''actus reus'' and ''mens rea''
* Concurring opinion (also called a "concurrence"), ...
, or during debugging when using a hardware debugging aid with access to the machine state (some support for this is often built directly into the CPU or microcontroller as functionally independent circuitry apart from the execution core which continues to operate even when the core itself is halted for static inspection of its execution state). Compile-time memory order concerns itself with the former, and does not concern itself with these other views.
General issues of program order
Program-order effects of expression evaluation
During compilation, hardware instructions are often generated at a finer granularity than specified in the high-level code. The primary observable effect in a
procedural programming
Procedural programming is a programming paradigm, derived from imperative programming, based on the concept of the '' procedure call''. Procedures (a type of routine or subroutine) simply contain a series of computational steps to be carrie ...
is assignment of a new value to a named variable.
sum = a + b + c;
print(sum);
The print statement follows the statement which assigns to the variable sum, and thus when the print statement references the computed variable
sum
it references this result as an observable effect of the prior execution sequence. As defined by the rules of program sequence, when the
print
function call references
sum
, the value of
sum
must be that of the most recently executed assignment to the variable
sum
(in this case the immediately previous statement).
At the machine level, few machines can add three numbers together in a single instruction, and so the compiler will have to translate this expression into two addition operations. If the semantics of the program language restrict the compiler into translating the expression in left-to-right order (for example), then the generated code will look as if the programmer had written the following statements in the original program:
sum = a + b;
sum = sum + c;
If the compiler is permitted to exploit the
associative property
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacemen ...
of addition, it might instead generate:
sum = b + c;
sum = a + sum;
If the compiler is also permitted to exploit the
commutative property
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
of addition, it might instead generate:
sum = a + c;
sum = sum + b;
Note that the integer data type in most programming languages only follows the algebra for the mathematics integers in the absence of
integer overflow
In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is outside of the range that can be represented with a given number of digits – either higher than the maximum or lower ...
and that
floating-point arithmetic on the floating point data type available in most programming languages is not commutative in rounding effects, making effects of the order of expression visible in small differences of the computed result (small initial differences may however cascade into arbitrarily large differences over a longer computation).
If the programmer is concerned about integer overflow or rounding effects in floating point, the same program may be coded at the original high level as follows:
sum = a + b;
sum = sum + c;
Program-order effects involving function calls
Many languages treat the statement boundary as a
sequence point A sequence point defines any point in a computer program's execution at which it is guaranteed that all side effects of previous evaluations will have been performed, and no side effects from subsequent evaluations have yet been performed. They are ...
, forcing all effects of one statement to be complete before the next statement is executed. This will force the compiler to generate code corresponding to the statement order expressed. Statements are, however, often more complicated, and may contain internal
function call
In computer programming, a function or subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed.
Functions may ...
s.
sum = f(a) + g(b) + h(c);
At the machine level, calling a function usually involves setting up a
stack frame
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or mach ...
for the function call, which involves many reads and writes to machine memory. In most compiled languages, the compiler is free to order the function calls
f
,
g
, and
h
as it finds convenient, resulting in large-scale changes of program memory order. In a pure functional programming language, function calls are forbidden from having side effects on the visible program state (other than its
return value) and the difference in machine memory order due to function call ordering will be inconsequential to program semantics. In procedural languages, the functions called might have side-effects, such as performing an
I/O operation, or updating a variable in global program scope, both of which produce visible effects with the program model.
Again, a programmer concerned with these effects can become more pedantic in expressing the original source program:
sum = f(a);
sum = sum + g(b);
sum = sum + h(c);
In programming languages where the statement boundary is defined as a sequence point, the function calls
f
,
g
, and
h
must now execute in that precise order.
Specific issues of memory order
Program-order effects involving pointer expressions
Now consider the same summation expressed with pointer indirection, in a language such as C or C++ which supports
pointers
Pointer may refer to:
Places
* Pointer, Kentucky
* Pointers, New Jersey
* Pointers Airport, Wasco County, Oregon, United States
* The Pointers, a pair of rocks off Antarctica
People with the name
* Pointer (surname), a surname (including a lis ...
:
sum = *a + *b + *c;
Evaluating the expression
*x
is termed "
dereferencing
In computer programming, the dereference operator or indirection operator, sometimes denoted by "*" (i.e. an asterisk), is a unary operator (i.e. one with a single operand) found in List of C-family programming languages, C-like languages that in ...
" a pointer and involves reading from memory at a location specified by the current value of
x
. The effects of reading from a pointer are determined by architecture's
memory model. When reading from standard program storage, there are no side-effects due to the order of memory read operations. In
embedded system
An embedded system is a computer system—a combination of a computer processor, computer memory, and input/output peripheral devices—that has a dedicated function within a larger mechanical or electronic system. It is ''embedded'' ...
programming, it is very common to have
memory-mapped I/O
Memory-mapped I/O (MMIO) and port-mapped I/O (PMIO) are two complementary methods of performing input/output (I/O) between the central processing unit (CPU) and peripheral devices in a computer. An alternative approach is using dedicated I/O pr ...
where reads and writes to memory trigger I/O operations, or changes to the processor's operational mode, which are highly visible side effects. For the above example, assume for now that the pointers are pointing to regular program memory, without these side-effects. The compiler is free to reorder these reads in program order as it sees fit, and there will be no program-visible side effects.
What if ''assigned'' value is also pointer indirected?
*sum = *a + *b + *c;
Here the language definition is unlikely to allow the compiler to break this apart as follows:
// as rewritten by the compiler
// generally forbidden
*sum = *a + *b;
*sum = *sum + *c;
This would not be viewed as efficient in most instances, and pointer writes have potential side-effects on visible machine state. Since the compiler is not allowed this particular splitting transformation, the only write to the memory location of
sum
must logically follow the three pointer reads in the value expression.
Suppose, however, that the programmer is concerned about the visible semantics of integer overflow and breaks the statement apart as the program level as follows:
// as directly authored by the programmer
// with aliasing concerns
*sum = *a + *b;
*sum = *sum + *c;
The first statement encodes two memory reads, which must precede (in either order) the first write to
*sum
. The second statement encodes two memory reads (in either order) which must precede the second update of
*sum
. This guarantees the order of the two addition operations, but potentially introduces a new problem of address
aliasing
In signal processing and related disciplines, aliasing is an effect that causes different signals to become indistinguishable (or ''aliases'' of one another) when sampled. It also often refers to the distortion or artifact that results when ...
: any of these pointers could potentially refer to the same memory location.
For example, let's assume in this example that
*c
and
*sum
are aliased to the same memory location, and rewrite both versions of the program with
*sum
standing in for both.
*sum = *a + *b + *sum;
There are no problems here. The original value of what we originally wrote as
*c
is lost upon assignment to
*sum
, and so is the original value of
*sum
but this was overwritten in the first place and it's of no special concern.
// what the program becomes with *c and *sum aliased
*sum = *a + *b;
*sum = *sum + *sum;
Here the original value of
*sum
is overwritten before its first access, and instead we obtain the algebraic equivalent of:
// algebraic equivalent of the aliased case above
*sum = (*a + *b) + (*a + *b);
which assigns an entirely different value into
*sum
due to the statement rearrangement.
Because of possible aliasing effects, pointer expressions are difficult to rearrange without risking visible program effects. In the common case, there might not be any aliasing in effect, so the code appears to run normally as before. But in the edge case where aliasing is present, severe program errors can result. Even if these edge cases are entirely absent in normal execution, it opens the door for a malicious adversary to contrive an input where aliasing exists, potentially leading to a computer security
exploit
Exploit means to take advantage of something (a person, situation, etc.) for one's own end, especially unethically or unjustifiably.
Exploit can mean:
*Exploitation of natural resources
*Exploit (computer security)
* Video game exploit
*Exploitat ...
.
A safe reordering of the previous program is as follows:
// declare a temporary
local variable
In computer science, a local variable is a variable that is given ''local scope''. A local variable reference in the function or block in which it is declared overrides the same variable name in the larger scope. In programming languages with o ...
'temp' of suitable type
temp = *a + *b;
*sum = temp + *c;
Finally consider the indirect case with added function calls:
*sum = f(*a) + g(*b);
The compiler may choose to evaluate
*a
and
*b
before either function call, it may defer the evaluation of
*b
until after the function call
f
or it may defer the evaluation of
*a
until after the function call
g
. If the function
f
and
g
are free from program visible side-effects, all three choices will produce a program with the same visible program effects. If the implementation of
f
or
g
contain the side-effect of any pointer write subject to aliasing with pointers
a
or
b
, the three choices are liable to produce different visible program effects.
Memory order in language specification
In general, compiled languages are not detailed enough in their specification for the compiler to determine formally at compile time which pointers are potentially aliased and which are not. The safest course of action is for the compiler to assume that all pointers are potentially aliased at all times. This level of conservative pessimism tends to produce dreadful performance as compared to the optimistic assumption that no aliasing exists, ever.
As a result, many high-level compiled languages, such as C/C++, have evolved to have intricate and sophisticated semantic specifications about where the compiler is permitted to make optimistic assumptions in code reordering in pursuit of the highest possible performance, and where the compiler is required to make pessimistic assumptions in code reordering to avoid semantic hazards.
By far the largest class of side effects in a modern procedural language involve memory write operations, so rules around memory ordering are a dominant component in the definition of program order semantics. The reordering of the functions calls above might appear to be a different consideration, but this usually devolves into concerns about memory effects internal to the called functions interacting with memory operations in the expression which generates the function call.
Additional difficulties and complications
Optimization under as-if
Modern compilers sometimes take this a step further by means of an
as-if rule, in which any reordering is permitted (even across statements) if no effect on the visible program semantics results. Under this rule, the order of operations in the translated code can vary wildly from the specified program order. If the compiler is permitted to make optimistic assumptions about distinct pointer expressions having no alias overlap in a case where such aliasing actually exists (this would normally be classified as an ill-formed program exhibiting
undefined behavior
In computer programming, undefined behavior (UB) is the result of executing a program whose behavior is prescribed to be unpredictable, in the language specification to which the computer code adheres. This is different from unspecified behavior ...
), the adverse results of an aggressive code-optimization transformation are impossible to guess prior to code execution or direct code inspection. The realm of undefined behavior has nearly limitless manifestations.
It is the responsibility of the programmer to consult the language specification to avoid writing ill-formed programs where the semantics are potentially changed as a result of any legal compiler optimization.
Fortran traditionally places a high burden on the programmer to be aware of these issues, with the
systems programming Systems programming, or system programming, is the activity of programming computer system software. The primary distinguishing characteristic of systems programming when compared to application programming is that application programming aims to pr ...
languages C and C++ not far behind.
Some high-level languages eliminate pointer constructions altogether, as this level of alertness and attention to detail is considered too high to reliably maintain even among professional programmers.
A complete grasp of memory order semantics is considered to be an arcane specialization even among the subpopulation of professional systems programmers who are typically best informed in this subject area. Most programmers settle for an adequate working grasp of these issues within the normal domain of their programming expertise. At the extreme end of specialization in memory order semantics are the programmers who author
software frameworks in support of
concurrent computing models.
Aliasing of local variables
Note that local variables can not be assumed to be free of aliasing if a pointer to such a variable escapes into the wild:
sum = f(&a) + g(a);
There is no telling what the function
f
might have done with the supplied pointer to
a
, including leaving a copy around in global state which the function
g
later accesses. In the simplest case,
f
writes a new value to the variable
a
, making this expression ill-defined in order of execution.
f
can be conspicuously prevented from doing this by applying a
const qualifier to the declaration of its pointer argument, rendering the expression well defined. Thus the modern culture of C/C++ has become somewhat obsessive about supplying const qualifiers to function argument declarations in all viable cases.
C and C++ permit the internals of
f
to
type cast the constness attribute away as a dangerous expedient. If
f
does this in a way that can break the expression above, it should not be declaring the pointer argument type as const in the first place.
Other high-level languages tilt toward such a declaration attribute amounting to a strong guarantee with no loop-holes to violate this guarantee provided within the language itself; all bets are off on this language guarantee if your application links a library written in a different programming language (though this is considered to be egregiously bad design).
Compile-time memory barrier implementation
These barriers prevent a compiler from reordering instructions during compile time – they do not prevent reordering by CPU during runtime.
* Any of these GNU inline assembler statements forbids the
GCC compiler to reorder read and write commands around it:
asm volatile("" ::: "memory");
__asm__ __volatile__ ("" ::: "memory");
* This C11/C++11 function forbids the compiler to reorder read and write commands around it:
atomic_signal_fence(memory_order_acq_rel);
*
Intel ICC compiler uses "full compiler fence" intrinsics:
__memory_barrier()
*
Microsoft Visual C++
Microsoft Visual C++ (MSVC) is a compiler for the C, C++ and C++/CX programming languages by Microsoft. MSVC is proprietary software; it was originally a standalone product but later became a part of Visual Studio and made available in both tri ...
Compiler:
_ReadWriteBarrier()
Combined barriers
In many programming languages different types of barriers can be combined with other operations (like load, store, atomic increment, atomic compare and swap), so no extra memory barrier is needed before or after it (or both). Depending on a CPU architecture being targeted these language constructs will translate to either special instructions, to multiple instructions (i.e. barrier and load), or to normal instruction, depending on hardware memory ordering guarantees.
Runtime memory ordering
In symmetric multiprocessing (SMP) microprocessor systems
There are several memory-consistency models for
SMP systems:
* Sequential consistency (all reads and all writes are in-order)
* Relaxed consistency (some types of reordering are allowed)
** Loads can be reordered after loads (for better working of cache coherency, better scaling)
** Loads can be reordered after stores
** Stores can be reordered after stores
** Stores can be reordered after loads
*Weak consistency (reads and writes are arbitrarily reordered, limited only by explicit
memory barrier
In computing, a memory barrier, also known as a membar, memory fence or fence instruction, is a type of barrier instruction that causes a central processing unit (CPU) or compiler to enforce an ordering constraint on memory operations issued b ...
s)
On some CPUs
*
Atomic operation
In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events (event), that may be extended by adding response events such that:
# The extended list can be re-e ...
s can be reordered with loads and stores.
* There can be incoherent instruction cache pipeline, which prevents
self-modifying code
In computer science, self-modifying code (SMC) is code that alters its own instructions while it is executing – usually to reduce the instruction path length and improve performance or simply to reduce otherwise repetitively similar code, ...
from being executed without special instruction cache flush/reload instructions.
* Dependent loads can be reordered (this is unique for Alpha). If the processor fetches a pointer to some data after this reordering, it might not fetch the data itself but use stale data which it has already cached and not yet invalidated. Allowing this relaxation makes cache hardware simpler and faster but leads to the requirement of memory barriers for readers and writers. On Alpha hardware (like multiprocessor
Alpha 21264
The Alpha 21264 is a Digital Equipment Corporation RISC microprocessor launched on 19 October 1998. The 21264 implemented the Alpha instruction set architecture (ISA).
Description
The Alpha 21264 is a four-issue superscalar microprocessor with o ...
systems) cache line invalidations sent to other processors are processed in lazy fashion by default, unless requested explicitly to be processed between dependent loads. The Alpha architecture specification also allows other forms of dependent loads reordering, for example using speculative data reads ahead of knowing the real pointer to be dereferenced.
; RISC-V memory ordering models:
:; WMO: Weak memory order (default)
:; TSO: Total store order (only supported with the Ztso extension)
; SPARC memory ordering modes:
:; TSO: Total store order (default)
:; RMO: Relaxed-memory order (not supported on recent CPUs)
:; PSO: Partial store order (not supported on recent CPUs)
Hardware memory barrier implementation
Many architectures with SMP support have special hardware instruction for flushing reads and writes during
runtime.
*
x86
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was intr ...
,
x86-64
x86-64 (also known as x64, x86_64, AMD64, and Intel 64) is a 64-bit version of the x86 instruction set, first released in 1999. It introduced two new modes of operation, 64-bit mode and compatibility mode, along with a new 4-level paging ...
lfence (asm), void _mm_lfence(void)
sfence (asm), void _mm_sfence(void)
[SFENCE — Store Fence](_blank)
/ref>
mfence (asm), void _mm_mfence(void)
/ref>
* PowerPC
sync (asm)
* MIPS
sync (asm)
*Itanium
Itanium ( ) is a discontinued family of 64-bit Intel microprocessors that implement the Intel Itanium architecture (formerly called IA-64). Launched in June 2001, Intel marketed the processors for enterprise servers and high-performance comput ...
mf (asm)
*POWER
Power most often refers to:
* Power (physics), meaning "rate of doing work"
** Engine power, the power put out by an engine
** Electric power
* Power (social and political), the ability to influence people or events
** Abusive power
Power may a ...
dcs (asm)
*ARMv7
ARM (stylised in lowercase as arm, formerly an acronym for Advanced RISC Machines and originally Acorn RISC Machine) is a family of reduced instruction set computer (RISC) instruction set architectures for computer processors, configured ...
[Data Memory Barrier, Data Synchronization Barrier, and Instruction Synchronization Barrier.](_blank)
/ref>
dmb (asm)
dsb (asm)
isb (asm)
Compiler support for hardware memory barriers
Some compilers support builtins that emit hardware memory barrier instructions:
* GCC, version 4.4.0 and later, has __sync_synchronize
.
*Since C11 and C++11 an atomic_thread_fence()
command was added.
*The Microsoft Visual C++
Microsoft Visual C++ (MSVC) is a compiler for the C, C++ and C++/CX programming languages by Microsoft. MSVC is proprietary software; it was originally a standalone product but later became a part of Visual Studio and made available in both tri ...
compiler has MemoryBarrier()
.
*Sun Studio Compiler Suite
Oracle Developer Studio, formerly named Oracle Solaris Studio, Sun Studio, Sun WorkShop, Forte Developer, and SunPro Compilers, is Oracle Corporation's flagship software development product for the Solaris and Linux operating systems. It includ ...
[Handling Memory Ordering in Multithreaded Applications with Oracle Solaris Studio 12 Update 2: Part 2, Memory Barriers and Memory Fenc]
/ref> has __machine_r_barrier
, __machine_w_barrier
and __machine_rw_barrier
.
See also
* Memory model (programming)
In computing, a memory model describes the interactions of threads through memory and their shared use of the data.
History and significance
A memory model allows a compiler to perform many important optimizations. Compiler optimizations like l ...
References
Further reading
* ''Computer Architecture — A quantitative approach''. 4th edition. J Hennessy, D Patterson, 2007. Chapter 4.6
* Sarita V. Adve, Kourosh Gharachorloo
Shared Memory Consistency Models: A Tutorial
Intel 64 Architecture Memory Ordering White Paper
Memory ordering in Modern Microprocessors part 1
Memory ordering in Modern Microprocessors part 2
* {{YouTube, id=WUfvvFD5tAA, title=IA (Intel Architecture) Memory Ordering - Google Tech Talk
Computer architecture
Computer memory
Consistency models
Compiler construction
Programming language design
Run-time systems
Concurrency (computer science)