Content deleted Content added
typo |
|||
| (12 intermediate revisions by 8 users not shown) | |||
Line 1:
{{Short description|Way in which data is arranged and accessed in computer memory}}
{{Redirect|Memory layout|broader usage|memory management}}
{{multiple issues|
{{original research|date=January 2018}}
Line 9 ⟶ 10:
'''Data structure alignment''' is the way data is arranged and accessed in [[computer memory]]. It consists of three separate but related issues: '''data alignment''', '''data structure padding''', and '''packing'''.
The [[central processing unit|CPU]] in modern computer hardware performs reads and writes to memory most efficiently when the data is ''naturally aligned'', which generally means that the data's memory address is a multiple of the data size. For instance, in a 32-bit architecture, the data may be aligned if the data is stored in four consecutive bytes and the first byte lies on a 4-byte boundary.
''Data alignment'' is the aligning of elements according to their natural alignment. To ensure natural alignment, it may be necessary to insert some ''padding'' between structure elements or after the last element of a structure. For example, on a 32-bit machine, a data structure containing a 16-bit value followed by a 32-bit value could have 16 bits of ''padding'' between the 16-bit value and the 32-bit value to align the 32-bit value on a 32-bit boundary. Alternatively, one can ''pack'' the structure, omitting the padding, which may lead to slower access, but
Although data structure alignment is a fundamental issue for all modern computers, many computer languages and computer language implementations handle data alignment automatically. [[Fortran]], [[Ada (programming language)|Ada]],<ref>{{cite book
Line 38 ⟶ 39:
}}</ref> certain [[C (programming language)|C]] and [[C++]] implementations, [[D (programming language)|D]],<ref>{{cite web
| url = http://dlang.org/attribute.html#align
| title = Attributes
| access-date = 2012-04-13
}}</ref> [[Rust (programming language)|Rust]],<ref>{{cite web
| url = https://doc.rust-lang.org/nomicon/other-reprs.html
| title = The Rustonomicon
| access-date = 2016-06-19
}}</ref> [[C Sharp (programming language)|C#]],<ref>{{Cite web|url=https://docs.microsoft.com/en-us/dotnet/api/system.runtime.interopservices.layoutkind|title=LayoutKind Enum (System.Runtime.InteropServices)|website=docs.microsoft.com|language=en-us|access-date=2019-04-01}}</ref> and [[assembly language]] allow at least partial control of data structure padding, which may be useful in certain special circumstances.
Line 64 ⟶ 65:
If the highest and lowest bytes in a datum are not within the same memory word, the computer must split the datum access into multiple memory accesses. This requires a lot of complex circuitry to generate the memory accesses and coordinate them. To handle the case where the memory words are in different memory pages the processor must either verify that both pages are present before executing the instruction or be able to handle a [[translation lookaside buffer|TLB]] miss or a [[page fault]] on any memory access during the instruction execution.
Some processor designs deliberately avoid introducing such complexity, and instead yield alternative behavior in the event of a misaligned memory access. For example, implementations of the ARM architecture prior to the ARMv6 ISA require mandatory aligned memory access for all multi-byte load and store instructions.<ref>{{Cite web|url=https://medium.com/@iLevex/the-curious-case-of-unaligned-access-on-arm-5dd0ebe24965|title=The curious case of unaligned access on ARM|last=Kurusa|first=Levente|date=2016-12-27|website=Medium|language=en|access-date=2019-08-07}}</ref> Depending on which specific instruction was issued, the result of attempted misaligned access might be to round down the least significant bits of the offending address turning it into an aligned access (sometimes with additional caveats), or to throw an [[
When a single memory word is accessed the operation is atomic, i.e. the whole memory word is read or written at once and other devices must wait until the read or write operation completes before they can access it. This may not be true for unaligned accesses to multiple memory words, e.g. the first word might be read by one device, both words written by another device and then the second word read by the first device so that the value read is neither the original value nor the updated value. Although such failures are rare, they can be very difficult to identify.
Line 81 ⟶ 82:
===Computing padding===
The following formulas provide the number of padding bytes required to align the start of a data structure (where ''mod'' is the [[modulo operator]]):
padding = (align - (offset mod align)) mod align
aligned = offset + padding
Line 89 ⟶ 91:
Since the alignment is by [[#Definitions|definition]] a power of two,{{efn|On modern computers where the target alignment is a power of two. This might not be true, for example, on a system using 9-bit bytes or 60-bit words.}} the modulo operation can be reduced to a [[bitwise AND]] operation.
The following formulas produce the correct values (where ''&'' is a bitwise AND and ''~'' is a [[bitwise NOT]])
padding = (align - (offset & (align - 1))) & (align - 1)
= -offset & (align - 1)
Line 96 ⟶ 99:
==Typical alignment of C structs on x86==
[[Data structure]] members are stored sequentially in memory so that, in the structure below, the member Data1 will always precede Data2; and Data2 will always precede Data3:
Line 112 ⟶ 114:
The type of each member of the structure usually has a default alignment, meaning that it will, unless otherwise requested by the programmer, be aligned on a pre-determined boundary. The following typical alignments are valid for compilers from [[Microsoft]] ([[Visual C++]]), [[Borland]]/[[CodeGear]] ([[C++Builder]]), [[Digital Mars]] (DMC), and [[GNU]] ([[GNU Compiler Collection|GCC]]) when compiling for 32-bit x86:
* A '''char''' (one byte) will be 1-byte aligned.
* A '''short''' (two bytes) will be 2-byte aligned.
* An '''int''' (four bytes) will be 4-byte aligned.
* A '''long''' (four bytes) will be 4-byte aligned.
* A '''float''' (four bytes) will be 4-byte aligned.
* A '''double''' (eight bytes) will be 8-byte aligned on Windows and 4-byte aligned on Linux (8-byte with ''-malign-double'' compile time option).
* A '''long long''' (eight bytes) will be 8-byte aligned on Windows and 4-byte aligned on Linux (8-byte with ''-malign-double'' compile time option).
* A '''long double''' (ten bytes with C++Builder and DMC, eight bytes with Visual C++, twelve bytes with GCC) will be 8-byte aligned with C++Builder, 2-byte aligned with DMC, 8-byte aligned with Visual C++, and 4-byte aligned with GCC.
* Any '''pointer''' (four bytes) will be 4-byte aligned. (e.g.: char*, int*)
The only notable differences in alignment for an [[LP64]] 64-bit system when compared to a 32-bit system are:
* A '''long''' (eight bytes) will be 8-byte aligned.
* A '''double''' (eight bytes) will be 8-byte aligned.
* A '''long long''' (eight bytes) will be 8-byte aligned.
* A '''long double''' (eight bytes with Visual C++, sixteen bytes with GCC) will be 8-byte aligned with Visual C++ and 16-byte aligned with GCC.
* Any '''pointer''' (eight bytes) will be 8-byte aligned.
Some data types are dependent on the implementation.
Line 150 ⟶ 152:
{
char Data1; /* 1 byte */
char Padding1[1]; /* 1 byte for the following 'short' to be aligned on a 2
assuming that the address where structure begins is an even number */
short Data2; /* 2 bytes */
Line 203 ⟶ 205:
<syntaxhighlight lang="c">
#pragma pack(push) /* push current alignment to stack */
#pragma pack(1) /* set alignment to 1
struct MyPackedData
Line 241 ⟶ 243:
==Allocating memory aligned to cache lines==
It would be beneficial to allocate memory aligned to [[cache line]]s. If an array is partitioned for more than one thread to operate on, having the sub-array boundaries unaligned to cache lines could lead to performance degradation. Here is an example to allocate memory (double array of size 10) aligned to cache of 64 bytes.
<syntaxhighlight lang="c">
#include <stdlib.h>
Line 255 ⟶ 258:
Alignment concerns can affect areas much larger than a C structure when the purpose is the efficient mapping of that area through a hardware [[CPU cache#Address translation|address translation]] mechanism (PCI remapping, operation of a [[memory management unit|MMU]]).
For instance, on a 32-bit operating system, a 4 [[KiB]] (4096
Example: Assume that we have a TLB mapping of virtual address 0x2CFC7000 to physical address 0x12345000. (Note that both these addresses are aligned at 4 KiB boundaries.) Accessing data located at virtual address va=0x2CFC7ABC causes a TLB resolution of 0x2CFC7 to 0x12345 to issue a physical access to pa=0x12345ABC. Here, the 20/12-bit split luckily matches the hexadecimal representation split at 5/3 digits. The hardware can implement this translation by simply combining the first 20 bits of the physical address (0x12345) and the last 12 bits of the virtual address (0xABC). This is also referred to as virtually indexed (ABC) physically tagged (12345).
A block of data of size 2<sup>(n+1)</sup>
This is how a dynamic allocator that has no knowledge of alignment, can be used to provide aligned buffers, at the price of a factor two in space loss.
<syntaxhighlight lang="c">
// Example: get 4096 bytes aligned on a 4096
// unaligned pointer to large area
Line 288 ⟶ 291:
==Further reading==
* {{cite book |author-last1=Bryant |author-first1=Randal E. |author-link1=Randal Bryant |author-last2=David |author-first2=O'Hallaron |title=Computer Systems: A Programmer's Perspective |place=Upper Saddle River, New Jersey, USA |publisher=[[Pearson Education]] |date=2003 |edition=2003 |url=http://csapp.cs.cmu.edu/ |isbn=0-13-034074-X}}
* {{cite book |title=8086 Family Utilities
==External links==
* [https://developer.ibm.com/articles/pa-dalign/ IBM
* [https://fylux.github.io/2017/07/11/Memory_Alignment/ Article on data alignment and performance]
* [
* [
* [
*
* [http://www.catb.org/esr/structure-packing/ The Lost Art of Structure Packing by Eric S. Raymond]
| |||