Data structure alignment

Data structure alignment is the way data is arranged in physical memory.

Definition

An address a, is said to be n-byte aligned when a is a multiple of n bytes.

Problems

Because of the way computer memory works, it is highly desirable for all memory accesses to meet certain alignment requirements. As a rule of thumb, the alignment for a primitive data type should be the same as the size of the data to be accessed, rounded up to a power of two. This avoids crossing any word, cache-line, or page boundaries.

Some of the problems caused by unaligned access are:

Extra transistors on the CPU are required to support accesses which are not word-aligned
Reads not aligned to the width of the memory bus require two reads.
Writes not aligned to the width of the memory bus require two reads and two writes.
Accesses across cache-lines require evicting two cache-lines.
Accesses across page boundaries can incur two TLB misses and could even require swaping in both pages from disk

Compatibility

The advantage to supporting unaligned access is that it is easier to write compilers that do not need to align memory, at the expense of the cost of slower access. One way to increase performance in RISC processors which are designed to maximize raw performance is to require data to loaded or stored on a word boundary. So though memory is commonly addressed by 8 bit bytes, loading a 32 bit integer or 64 bit floating point number would be required to be start at every 64 bits on a 64 bit machine. The processor could flag a fault if it were asked to load a number which was not on such a boundary, but this would result in a slower call to a routine which would need to figure out which word or words contained the data and extract the equivalent value.

This caused difficulty when the team from Mosaic Software ported their Twin Spreadsheet to the 68000 based Atari ST. The Intel 8086 architecture had no such restrictions.

It would also cause difficulties in porting Microsoft Office to Windows NT on MIPS and PowerPC for NEC and IBM. Since the software was not written with such restrictions in mind, designers had to set a bit in the O/S to enable non-aligned data. However since this bit was masked with other flags which were used elsewhere, it was impossible to keep the O/S in a state from faulting on non-aligned data. Both platforms ulimately failed as platforms for hosting Windows applications. This small detail may be one reason for the continued dominance of the x86 architecture over rivals.

Typical alignment of C structs on x86

Data structure members are stored sequentially in a memory so that in the structure below the member Data1 will always precede Data2 and Data2 will always precede Data3:

struct MyData
{
	short	Data1;
	short	Data2;
	short	Data3;
};

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, Borland, and GNU when compiling for 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 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.

Here is a structure with members of various types, totaling 8 bytes before compilation:

struct MixedData
{
	char	Data1;
	short	Data2;
	int	Data3;
	char	Data4;
};

After compilation the data structure will be supplemented with padding bytes to ensure a proper alignment for each of its member:

struct MixedData (after compilation)
{
	char	Data1;
	char	Padding0[1];
	short	Data2;
	int	Data3;	
	char	Data4;
	char	Padding1[3];
};

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 to conform to the largest type of the structure. In this case 3 bytes are added to the last member to pad the structure to the size of a long word.

It’s possible to change the alignment of structures to reduce the memory they require (or to conform to an existing format) by changing the compiler’s alignment (or “packing”) of structure members.

Requesting that the “MixedData” structure above be aligned to a one byte boundary will have the compiler discard the pre-determined alignment of the members and no padding bytes would be inserted.

While there is no standard way of defining the alignment of structure member, some compilers use #pragma 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
{
	byte	Data1;
	long	Data2;
	byte	Data3;
};
#pragma pack( pop )		; restore original alignment from stack

This structure would have a compiled size of 6 bytes. The above directives are available in compilers from Microsoft, Borland and many others.

References

Bryant, Randal and O'Hallaron, David. [2003] 2001 Computer Systems: A Programmer's Perspective. Prentice Hall. ISBN 0-13-034074-X.