University of Washington
Section 5: Arrays & Other Data Structures
óð Array allocation and access in memory
óð Multi-dimensional or nested arrays
óð Multi-level arrays
óð Other structures in memory
óð Data structures and alignment
Structures and Alignment
University of Washington
Structures & Alignment
óð Unaligned Data
struct S1 {
char c;
c i[0] i[1] v
int i[2];
p p+1 p+5 p+9 p+17
double v;
} *p;
óð Aligned Data
żð Primitive data type requires K bytes
żð Address must be multiple of K
c 3 bytes i[0] i[1] 4 bytes v
p+0 p+4 p+8 p+16 p+24
Multiple of 4 Multiple of 8
Multiple of 8 Multiple of 8
Structures and Alignment
University of Washington
Alignment Principles
óð Aligned Data
żð Primitive data type requires K bytes
żð Address must be multiple of K
óð Aligned data is required on some machines; it is advised on IA32
żð Treated differently by IA32 Linux, x86-64 Linux, and Windows!
óð What is the motivation for alignment?
Structures and Alignment
University of Washington
Alignment Principles
óð Aligned Data
żð Primitive data type requires K bytes
żð Address must be multiple of K
óð Aligned data is required on some machines; it is advised on IA32
żð Treated differently by IA32 Linux, x86-64 Linux, and Windows!
óð Motivation for Aligning Data
żð Physical memory is accessed by aligned chunks of 4 or 8 bytes (system-
dependent)
żð Inefficient to load or store datum that spans quad word boundaries
żð Also, virtual memory is very tricky when datum spans two pages (later& )
óð Compiler
żð Inserts padding in structure to ensure correct alignment of fields
żð sizeof() should be used to get true size of structs
Structures and Alignment
University of Washington
Specific Cases of Alignment (IA32)
óð 1 byte: char, &
żð no restrictions on address
óð 2 bytes: short, &
żð lowest 1 bit of address must be 02
óð 4 bytes: int, float, char *, &
żð lowest 2 bits of address must be 002
óð 8 bytes: double, &
żð Windows (and most other OSs & instruction sets): lowest 3 bits 0002
żð Linux: lowest 2 bits of address must be 002
żð i.e., treated the same as a 4-byte primitive data type
óð 12 bytes: long double
żð Windows, Linux: lowest 2 bits of address must be 002
Structures and Alignment
University of Washington
Satisfying Alignment with Structures
struct S1 {
óð Within structure:
char c;
int i[2];
żð Must satisfy every member s alignment requirement
double v;
óð Overall structure placement
} *p1;
żð Each structure has alignment requirement K
żð K = Largest alignment of any element
żð Initial address & structure length must be multiples of K
óð Example (under Windows or x86-64): K = ?
żð K = 8, due to double member
c 3 bytes i[0] i[1] 4 bytes v
p1+0 p1+4 p1+8 p1+16 p1+24
Multiple of 4 Multiple of 8
Multiple of 8 Multiple of 8
Structures and Alignment
University of Washington
Different Alignment Conventions
struct S1 {
char c;
óð IA32 Windows or x86-64:
int i[2];
żð K = 8, due to double member
double v;
} *p1;
c 3 bytes i[0] i[1] 4 bytes v
p1+0 p1+4 p1+8 p1+16 p1+24
óð IA32 Linux: K = ?
żð K = 4; double aligned like a 4-byte data type
c 3 bytes i[0] i[1] v
p1+0 p1+4 p1+8 p1+12 p1+20
Structures and Alignment
University of Washington
Saving Space
óð Put large data types first:
struct S1 { struct S2 {
char c; double v;
int i[2]; int i[2];
double v; char c;
} *p1; } *p2;
óð Effect (example x86-64, both have K=8)
c 3 bytes i[0] i[1] 4 bytes v
p1+0 p1+4 p1+8 p1+16 p1+24
Unfortunately, doesn t
satisfy requirement
v i[0] i[1] c
that struct s total size
is a multiple of K
p2+0 p2+8 p2+16
Structures and Alignment
University of Washington
Arrays of Structures
óð Satisfy alignment requirement
struct S2 {
double v;
for every element
int i[2];
char c;
} a[10];
a[0] a[1] a[2]
" " "
a+0 a+24 a+48 a+72
v i[0] i[1] c 7 bytes
a+24 a+32 a+40 a+48
Structures and Alignment
University of Washington
// Global:
Accessing Array Elements
struct S3 {
short i;
float v;
óð Compute array offset 12i (sizeof(S3))
short j;
óð Element j is at offset 8 within structure
} a[10];
óð Since a is static array, assembler gives offset a+8
a[0] " " " a[i] " " "
a+0 a+12i
i 2 bytes v j 2 bytes
a+12i a+12i+8
short get_j(int idx)
{
# %eax = idx
return a[idx].j;
leal (%eax,%eax,2),%eax # 3*idx
// return (a + idx)->j;
movswl a+8(,%eax,4),%eax # a+12*idx+8
}
Structures and Alignment