Memory ordering

Memory ordering is the order of accesses to computer memory by a CPU. Memory ordering depends on both the order of the instructions generated by the compiler at compile time and the execution order of the CPU at runtime. However, memory order is of little concern outside of multithreading and memory-mapped I/O, because if the compiler or CPU changes the order of any operations, it must necessarily ensure that the reordering does not change the output of ordinary single-threaded code. The memory order is said to be strong or sequentially consistent when either the order of operations cannot change or when such changes have no visible effect on any thread. Conversely, the memory order is called weak or relaxed when one thread cannot predict the order of operations arising from another thread. Many naïvely written parallel algorithms fail when compiled or executed with a weak memory order. The problem is most often solved by inserting memory barrier instructions into the program. In order to fully utilize the bandwidth of different types of memory such as caches and memory banks, few compilers or CPU architectures ensure perfectly strong ordering. Among the commonly used architectures, x86-64 processors have the strongest memory order, but may still defer memory store instructions until after memory load instructions.…

Memory ordering is the order of accesses to computer memory by a CPU. Memory ordering depends on both the order of the instructions generated by the compiler at compile time and the execution order of the CPU at runtime. However, memory order is of little concern outside of multithreading and memory-mapped I/O, because if the compiler or CPU changes the order of any operations, it must necessarily ensure that the reordering does not change the output of ordinary single-threaded code. The memory order is said to be strong or sequentially consistent when either the order of operations cannot change or when such changes have no visible effect on any thread. Conversely, the memory order is called weak or relaxed when one thread cannot predict the order of operations arising from another thread. Many naïvely written parallel algorithms fail when compiled or executed with a weak memory order. The problem is most often solved by inserting memory barrier instructions into the program. In order to fully utilize the bandwidth of different types of memory such as caches and memory banks, few compilers or CPU architectures ensure perfectly strong ordering. Among the commonly used architectures, x86-64 processors have the strongest memory order, but may still defer memory store instructions until after memory load instructions. On the other end of the spectrum, DEC Alpha processors make practically no guarantees about memory order. 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 of addition, it might instead generate: sum = b + c; sum = a + sum; If the compiler is also permitted to exploit the commutative property 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 and that floating-point arithmetic on the floating point data type available in most programming languages is not associative due to intermediate rounding, 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; sum = f(a) + g(b) + h(c); At the machine level, calling a function usually involves setting up a stack frame 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. sum = *a + *b + *c; Evaluating the expression *x is termed "dereferencing" 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 programming, it is very common to have memory-mapped I/O 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: 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. A safe reordering of the previous program is as follows: // declare a temporary local variable '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 functions 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. 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).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378180057 under CC BY-SA 4.0; modifications have been made.