Data structure alignment: Difference between revisions

Revision as of 00:03, 28 October 2006

Revision as of 04:19, 28 October 2006

Line 1:

{{context}}

'''Data structure alignment''' is the way [[Data (computing)|data]] is arranged and accessed in [[physicalcomputer memory]].

== Definitions ==

A [[computer memory]] address ''a'', is said to be ''n-byte aligned'' when ''n'' is a power of two and ''a'' is a multiple of ''n'' [[byte|bytes]]. In this context a byte is the smallest unit of memory access, i.e. each memory address specifies a different byte. An ''n''-byte aligned address would have n least-significant zeros when expressed in [[Binary numeral system|binary]].

A memory access is said to be ''aligned'' when the datum being accessed is ''n'' bytes long and the datum address is ''n''-byte aligned. When a memory access is not aligned, it is said to be ''misaligned''. Note that by definition byte memory accesses are always aligned.

Line 22:

* Extra logic on the CPU is required to support accesses which are not word-aligned.

* Accesses across [[cache-lines]] may require evicting two cache-lines.

* Accesses across page boundaries can incur two [[translation lookaside buffer|TLB]] misses and could even require swapping in both pages from disk

==Unaligned Pointer Support==

Most RISC processors will generate an alignment fault when a load or store instruction accesses a misaligned address. This allows the operating system to emulate the misaligned access using other instructions. For example, the alignment fault handler might use byte loads or stores (which are always aligned) to emulate a larger load or store instruction.

Some architectures like [[MIPS]] have special unaligned load and store instructions. One unaligned load instruction gets the bytes from the memory word with the lowest byte address and another gets the bytes from the memory word with the highest byte address. Similarly, store-high and store-low instructions store the appropriate bytes in the higher and lower memory words respectively.

The [[DEC Alpha]] architecture has a two-step approach to unaligned loads and stores. The first step is to load the upper and lower memory words into separate registers. The second step is to extract or modify the memory words using special low/high instructions similar to the MIPS instructions. An unaligned store is completed by storing the modified memory words back to memory. The reason for this complexity is that the original Alpha architecture could only read or write 32-bit or 64-bit values. This proved to be a severe limitation that often led to code bloat and poor performance. Later Alpha processors added byte and double-byte load and store instructions.

Because these instructions are larger and slower than the normal memory load and store instructions they should only be used when necessary. Most C and C++ compilers have an “unaligned” attribute that can be applied to pointers that need the unaligned instructions.

==Compatibility==