HOME

TheInfoList



OR:

Data structure alignment is the way data is arranged and accessed in
computer memory In computing, memory is a device or system that is used to store information for immediate use in a computer or related computer hardware and digital electronic devices. The term ''memory'' is often synonymous with the term '' primary storag ...
. It consists of three separate but related issues: data alignment, data structure padding, and packing. The
CPU A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, a ...
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 uses three quarters as much memory. 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 Ada may refer to: Places Africa * Ada Foah, a town in Ghana * Ada (Ghana parliament constituency) * Ada, Osun, a town in Nigeria Asia * Ada, Urmia, a village in West Azerbaijan Province, Iran * Ada, Karaman, a village in Karaman Province, T ...
,
PL/I PL/I (Programming Language One, pronounced and sometimes written PL/1) is a procedural, imperative computer programming language developed and published by IBM. It is designed for scientific, engineering, business and system programming. I ...
,
Pascal Pascal, Pascal's or PASCAL may refer to: People and fictional characters * Pascal (given name), including a list of people with the name * Pascal (surname), including a list of people and fictional characters with the name ** Blaise Pascal, Frenc ...
, certain C and C++ implementations, D,
Rust Rust is an iron oxide, a usually reddish-brown oxide formed by the reaction of iron and oxygen in the catalytic presence of water or air moisture. Rust consists of hydrous iron(III) oxides (Fe2O3·nH2O) and iron(III) oxide-hydroxide (FeO( ...
, C#, and
assembly language In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence b ...
allow at least partial control of data structure padding, which may be useful in certain special circumstances.


Definitions

A memory address ''a'' is said to be ''n-
byte The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable uni ...
aligned'' when ''a'' is a multiple of ''n'' (where ''n'' is a power of 2). 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 a minimum of least-significant zeros when expressed in binary. The alternate wording ''b-bit aligned'' designates a ''b/8 byte aligned'' address (ex.
64-bit In computer architecture, 64-bit integers, memory addresses, or other data units are those that are 64 bits wide. Also, 64-bit CPUs and ALUs are those that are based on processor registers, address buses, or data buses of that size. A ...
aligned is 8 bytes aligned). A memory access is said to be ''aligned'' when the data 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. A memory pointer that refers to primitive data that is ''n'' bytes long is said to be ''aligned'' if it is only allowed to contain addresses that are ''n''-byte aligned, otherwise it is said to be ''unaligned''. A memory pointer that refers to a data aggregate (a data structure or array) is ''aligned'' if (and only if) each primitive datum in the aggregate is aligned. Note that the definitions above assume that each primitive datum is a power of two bytes long. When this is not the case (as with 80-bit floating-point on x86) the context influences the conditions where the datum is considered aligned or not. Data structures can be stored in memory on the stack with a static size known as ''bounded'' or on the heap with a dynamic size known as ''unbounded''.


Problems

The CPU accesses memory by a single memory word at a time. As long as the memory word size is at least as large as the largest primitive data type supported by the computer, aligned accesses will always access a single memory word. This may not be true for misaligned data accesses. 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 TLB miss or a
page fault In computing, a page fault (sometimes called PF or hard fault) is an exception that the memory management unit (MMU) raises when a process accesses a memory page without proper preparations. Accessing the page requires a mapping to be added t ...
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. 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 MMU exception (if MMU hardware is present), or to silently yield other potentially unpredictable results. The ARMv6 and later architectures support unaligned access in many circumstances, but not necessarily all. 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.


Data structure padding

Although 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 ...
(or interpreter) normally allocates individual data items on aligned boundaries, data structures often have members with different alignment requirements. To maintain proper alignment the translator normally inserts additional unnamed data members so that each member is properly aligned. In addition, the data structure as a whole may be padded with a final unnamed member. This allows each member of an array of structures to be properly aligned. Padding is only inserted when a
structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such a ...
member is followed by a member with a larger alignment requirement or at the end of the structure. By changing the ordering of members in a structure, it is possible to change the amount of padding required to maintain alignment. For example, if members are sorted by descending alignment requirements a minimal amount of padding is required. The minimal amount of padding required is always less than the largest alignment in the structure. Computing the maximum amount of padding required is more complicated, but is always less than the sum of the alignment requirements for all members minus twice the sum of the alignment requirements for the least aligned half of the structure members. Although C and C++ do not allow the compiler to reorder structure members to save space, other languages might. It is also possible to tell most C and C++ compilers to "pack" the members of a structure to a certain level of alignment, e.g. "pack(2)" means align data members larger than a byte to a two-byte boundary so that any padding members are at most one byte long. Likewise, in
PL/I PL/I (Programming Language One, pronounced and sometimes written PL/1) is a procedural, imperative computer programming language developed and published by IBM. It is designed for scientific, engineering, business and system programming. I ...
a structure may be declared UNALIGNED to eliminate all padding except around bit strings. One use for such "packed" structures is to conserve memory. For example, a structure containing a single byte and a four-byte integer would require three additional bytes of padding. A large array of such structures would use 37.5% less memory if they are packed, although accessing each structure might take longer. This compromise may be considered a form of
space–time tradeoff A space–time trade-off or time–memory trade-off in computer science is a case where an algorithm or program trades increased space usage with decreased time. Here, ''space'' refers to the data storage consumed in performing a given task (RA ...
. Although use of "packed" structures is most frequently used to conserve memory space, it may also be used to format a data structure for transmission using a standard protocol. However, in this usage, care must also be taken to ensure that the values of the struct members are stored with the
endianness In computing, endianness, also known as byte sex, is the order or sequence of bytes of a word of digital data in computer memory. Endianness is primarily expressed as big-endian (BE) or little-endian (LE). A big-endian system stores the mos ...
required by the protocol (often
network byte order In computing, endianness, also known as byte sex, is the order or sequence of bytes of a word of digital data in computer memory. Endianness is primarily expressed as big-endian (BE) or little-endian (LE). A big-endian system stores the most s ...
), which may be different from the endianness used natively by the host machine.


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 In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is ...
operator): padding = (align - (offset mod align)) mod align aligned = offset + padding = offset + ((align - (offset mod align)) mod align) For example, the padding to add to offset 0x59d for a 4-byte aligned structure is 3. The structure will then start at 0x5a0, which is a multiple of 4. However, when the alignment of ''offset'' is already equal to that of ''align'', the second modulo in ''(align - (offset mod align)) mod align'' will return zero, therefore the original value is left unchanged. Since the alignment is by
definition A definition is a statement of the meaning of a term (a word, phrase, or other set of symbols). Definitions can be classified into two large categories: intensional definitions (which try to give the sense of a term), and extensional definiti ...
a power of two, the modulo operation can be reduced to a bitwise boolean AND operation. The following formulas produce the correct values (where ''&'' is a
bitwise AND In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic oper ...
and ''~'' a
bitwise NOT In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operat ...
) -- providing the offset is unsigned or the system uses
two's complement Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
arithmetic: padding = (align - (offset & (align - 1))) & (align - 1) = -offset & (align - 1) aligned = (offset + (align - 1)) & ~(align - 1) = (offset + (align - 1)) & -align


Typical alignment of C structs on x86

Data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, ...
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: struct MyData ; If the type "short" is stored in two bytes of memory then each member of the data structure depicted above would be 2-byte aligned. Data1 would be at offset 0, Data2 at offset 2, and Data3 at offset 4. The size of this structure would be 6 bytes. 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 Microsoft Corporation is an American multinational technology corporation producing computer software, consumer electronics, personal computers, and related services headquartered at the Microsoft Redmond campus located in Redmond, Washi ...
(
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 ...
),
Borland Borland Software Corporation was a computer technology company founded in 1983 by Niels Jensen, Ole Henriksen, Mogens Glad and Philippe Kahn. Its main business was the development and sale of software development and software deployment product ...
/
CodeGear CodeGear is a wholly owned division of Embarcadero Technologies. CodeGear develops software development tools such as the Delphi Integrated development environment, the programming language Delphi, and the database server InterBase. Original ...
(
C++Builder C++Builder is a rapid application development (RAD) environment, originally developed by Borland and owned by Embarcadero Technologies (a subsidiary of Idera), for writing programs in the C++ programming language currently targeting Windows (bo ...
), Digital Mars (DMC), and
GNU GNU () is an extensive collection of free software (383 packages as of January 2022), which can be used as an operating system or can be used in parts with other operating systems. The use of the completed GNU tools led to the family of operat ...
( 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. Here is a structure with members of various types, totaling 8 bytes before compilation: struct MixedData ; After compilation the data structure will be supplemented with padding bytes to ensure a proper alignment for each of its members: struct MixedData /* After compilation in 32-bit x86 machine */ ; The compiled size of the structure is now 12 bytes. It is important to note that the last member is padded with the number of bytes required so that the total size of the structure should be a multiple of the largest alignment of any structure member (alignment(int) in this case, which = 4 on linux-32bit/gcc). In this case 3 bytes are added to the last member to pad the structure to the size of 12 bytes (alignment(int) × 3). struct FinalPad ; In this example the total size of the structure , not 5 (so that the size is a multiple of 4 (alignment of float)). struct FinalPadShort ; In this example the total size of the structure , not 5 (not 8 either) (so that the size is a multiple of 2 (alignment(short) = 2 on linux-32bit/gcc)). It is possible to change the alignment of structures to reduce the memory they require (or to conform to an existing format) by reordering structure members or changing the compiler's alignment (or “packing”) of structure members. struct MixedData /* after reordering */ ; The compiled size of the structure now matches the pre-compiled size of 8 bytes. Note that has been replaced (and thus eliminated) by and is no longer necessary as the structure is already aligned to the size of a long word. The alternative method of enforcing the structure to be aligned to a one byte boundary will cause the pre-processor to discard the pre-determined alignment of the structure members and thus no padding bytes would be inserted. While there is no standard way of defining the alignment of structure members, some compilers use directives to specify packing inside source files. Here is an example: #pragma pack(push) /* push current alignment to stack */ #pragma pack(1) /* set alignment to 1 byte boundary */ struct MyPackedData ; #pragma pack(pop) /* restore original alignment from stack */ This structure would have a compiled size of 6 bytes on a 32-bit system. The above directives are available in compilers from
Microsoft Microsoft Corporation is an American multinational technology corporation producing computer software, consumer electronics, personal computers, and related services headquartered at the Microsoft Redmond campus located in Redmond, Washi ...
,
Borland Borland Software Corporation was a computer technology company founded in 1983 by Niels Jensen, Ole Henriksen, Mogens Glad and Philippe Kahn. Its main business was the development and sale of software development and software deployment product ...
,
GNU GNU () is an extensive collection of free software (383 packages as of January 2022), which can be used as an operating system or can be used in parts with other operating systems. The use of the completed GNU tools led to the family of operat ...
, and many others. Another example: struct MyPackedData __attribute__((packed));


Default packing and

On some Microsoft compilers, particularly for RISC processors, there is an unexpected relationship between project default packing (the /Zp directive) and the directive. The directive can only be used to reduce the packing size of a structure from the project default packing. This leads to interoperability problems with library headers which use, for example, , if the project packing is smaller than this. For this reason, setting the project packing to any value other than the default of 8 bytes would break the directives used in library headers and result in binary incompatibilities between structures. This limitation is not present when compiling for x86.


Allocating memory aligned to cache lines

It would be beneficial to allocate memory aligned to
cache line A CPU cache is a hardware cache used by the central processing unit (CPU) of a computer to reduce the average cost (time or energy) to access data from the main memory. A cache is a smaller, faster memory, located closer to a processor core, whi ...
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. #include double *foo(void)


Hardware significance of alignment requirements

Alignment concerns can affect areas much larger than a C structure when the purpose is the efficient mapping of that area through a hardware address translation mechanism (PCI remapping, operation of a MMU). For instance, on a 32-bit operating system, a 4 
KiB The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable unit ...
(4096 Bytes) page is not just an arbitrary 4 KiB chunk of data. Instead, it is usually a region of memory that's aligned on a 4 KiB boundary. This is because aligning a page on a page-sized boundary lets the hardware map a virtual address to a physical address by substituting the higher bits in the address, rather than doing complex arithmetic. 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(n+1) - 1 always has one sub-block of size 2n aligned on 2n bytes. 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. // Example: get 4096 bytes aligned on a 4096 byte buffer with malloc() // unaligned pointer to large area void *up = malloc((1 << 13) - 1); // well-aligned pointer to 4 KiB void *ap = aligntonext(up, 12); where aligntonext(''p'', ''r'') works by adding an aligned increment, then clearing the ''r'' least significant bits of ''p''. A possible implementation is // Assume `uint32_t p, bits;` for readability #define alignto(p, bits) (((p) >> bits) << bits) #define aligntonext(p, bits) alignto(((p) + (1 << bits) - 1), bits)


Notes


References


Further reading

* *


External links


IBM developerWorks article on data alignment

Article on data alignment and performance

MSDN article on data alignment

Article on data alignment and data portability




- discusses stack alignment for x86-64 calling conventions
The Lost Art of Structure Packing by Eric S. Raymond
{{DEFAULTSORT:Data Structure Alignment Compiler construction Composite data types