OSU CSE 2421
Required Reading:
Computer Systems: A Programmer’s Perspective, 3rd Edition Chapter 3, Sections 3.9.1 and 3.9.3; 3.9.2 is optional
J.E.Jones
OSU CSE 2421
Arrays
One-dimensional Multi-dimensional (nested) Multi-level
Structures ◦ Allocation ◦ Access
◦ Alignment
J. E. Jones
OSU CSE 2421
struct rec { int a[4];
r a[0]|a[1]|a[2]|a[3]
size_t i;
i next
16 24 32
struct rec *next; }r;
0
Structure represented as block of memory ◦ Big enough to hold all fields
Fields ordered according to declaration
◦ Even if another ordering could yield a more compact
representation
Compiler determines overall size + positions of fields
◦ Machine-level program has no understanding of the structures in the source code
J. E. Jones
OSU CSE 2421
From Wikipedia:
According to the 1999 ISO C standard (C99), size_t is an unsigned
integer type of at least 16 bits (see sections 7.17 and 7.18.3).
size_t is an unsigned data type defined by several C/C++ standards, (e.g., the C99 ISO/IEC 9899 standard) that is defined in stddef.h. It can be further imported by inclusion of stdlib.h as this file internally sub includes stddef.h.
This type is used to represent the size of an object. Library functions that take or return sizes expect them to be of type or have the return type of size_t. Further, the most frequently used compiler-based operator sizeof should evaluate to a constant value that is compatible with size_t.
As an implication, size_t is a type guaranteed to hold any array index.
J. E. Jones
OSU CSE 2421
struct rec { int a[4];
r r+4*idx a[0]|a[1]|a[2]|a[3]
size_t i;
i next
16 24 32
struct rec *next; };
0
Generating Pointer to an Array Element
int *get_ap(struct rec *r, size_t idx) {
◦ Offset of each structure member determined at compile time
return &(r->a[idx]); }
◦ Compute as
r + 4*idx
# r in %rdi, idx in %rsi leaq (%rdi,%rsi,4), %rax ret
J. E. Jones
OSU CSE 2421
struct rec { int a[4];
r r+4*idx a[0]|a[1]|a[2]|a[3]
size_t i;
i next
16 24 32
struct rec *next; };
0
Generating Pointer to an Array Element
int *get_ap(struct rec *r, size_t idx) {
◦ Offset of each structure member determined at compile time
return &(r->a[idx]); }
◦ Compute as
r + 4*idx
# r in %rdi, idx in %rsi leaq (%rdi,%rsi,4), %rax ret
Anyone curious about this?
J. E. Jones
OSU CSE 2421
} }
i next
C Code
struct rec { int a[4]; size_t i;
void set_val(struct rec *r, int val) {
struct rec *next; };
while (r!=NULL) { int i = r->i; r->a[i] = val;
r = r->next;
r
loop:
movzlq 16(%rdi), %rax
Element i # loop:
movl movq testq
jne loop
%esi, (%rdi,%rax,4) 24(%rdi), %rdi
%rdi r %rsi val
%rdi, %rdi
#movslq=>Fig 3.6, move sign-extended double to quad
J. E. Jones
0
a[0]|a[1]|a[2]|a[3]
16 24 32
# i = M[r+16]
# M[r+4*i] = val
# r = M[r+24]
# Test r
# if !=0 goto loop
Register Value
OSU CSE 2421
Unaligned Data
c i[0] p p+1
i[1]
v
p+9 p+17
c 3 bytes i[0] p+0 p+4
i[1]
4 bytes
v
p+24
Multiple of 4 Multiple of 8
Multiple of 8
p+5
Aligned Data
◦ Primitive data type requires K bytes
struct S1 { char c; int i[2]; double v;
◦ Address must be multiple of K
◦ Structure beginning always starts at address multiple of 8
p+8
p+12 p+16 Multiple of 8
} *p, S1_r; p=&S1_r;
J. E. Jones
OSU CSE 2421
Aligned Data
◦ Primitive data type requires K bytes
◦ Address must be multiple of K
◦ Required on some machines; advised on x86-64
Motivation for Aligning Data
◦ Memory accessed by (aligned) chunks of 4 or 8 bytes (system
dependent)
Inefficient to load or store datum that spans quad word boundaries
Virtual memory trickier when datum spans 2 pages (Systems II topic)
C Compiler
◦ Inserts gaps in structure to ensure correct alignment of fields
J. E. Jones
OSU CSE 2421
1 byte: char, …
◦ no restrictions on address
2 bytes: short, …
◦ lowest 1 bit of address must be 02
4 bytes: int, float, …
◦ lowest 2 bits of address must be 002
8 bytes: double, long, char *, … ◦ lowest 3 bits of address must be 0002
16 bytes: long long, long double (gcc on Linux) ◦ lowest 4 bits of address must be 00002
J. E. Jones
OSU CSE 2421
Within structure:
◦ Must satisfy each element’s alignment requirement
struct S1 { char c; int i[2]; double v;
Overall structure placement
◦ Each structure has alignment requirement K
} *p;
K = Largest alignment of any element
◦ Initial address & structure length must be multiples of K
Example:
◦ K = 8, due to double element
c 3 bytes i[0] p+0 p+4
i[1]
4 bytes
v
p+24
Multiple of 4 Multiple of 8
Multiple of 8
p+8
p+16 Multiple of 8
J. E. Jones
OSU CSE 2421
For largest alignment requirement K
Overall structure must be multiple of K
p+0
p+8
p+24
S2[0]
S2[1]
struct S2 { double v; int i[2]; char c;
} *p, S2[10];
v
i[0] i[1] c p+16
7bytes
Multiple of K=8
J. E. Jones
OSU CSE 2421
+24
a+48
Overall structure length multiple of K Satisfy alignment requirement
struct S2 { double v; int i[2]; char c;
for every element
} a[10];
a+0
a+24
v
i[0] i[1] c a+32 a+40
7bytes
a[0]
a[1] a[2]
a+48
• • • a+72
J. E. Jones
OSU CSE 2421
Compute array offset 12*idx
◦ sizeof(S3), including alignment spacers
struct S3 { short i; float v; short j;
Element j is at offset 8 within structure Assembler gives offset a+8
} a[10];
◦ Resolved during linking
a[0] ••• a[idx]
•••
a+0 a+12
a+12*idx
short get_j(int idx) {
# %rdi = idx
}
J. E. Jones
return a[idx].j;
movzwl a+8(,%rax,4),%eax
#Fig 3.5,move zero-extended word to double
i a+12*idx
2 bytes v j 2 bytes a+12*idx+8
leaq (%rdi,%rdi,2),%rax # 3*idx
OSU CSE 2421
Put large data types first
Effect (K=4) c 3bytes
i
d 3bytes
struct S4 { char c; int i; char d;
struct S5 { int i; char c; char d;
} *p;
} *p;
icd
2 bytes
J. E. Jones
OSU CSE 2421
Arrays
◦ Elements packed into contiguous region of memory ◦ Use index arithmetic to locate individual elements
Structures
◦ Elements packed into single region of memory
◦ Access using offsets determined by compiler
◦ Possible to require internal and external padding to ensure alignment
Combinations
◦ Can nest structure and array code arbitrarily
J. E. Jones