Introduction to Computer Systems 15-213/18-243, spring 2009
CSE 2421
Array and Structure Storage and Access: Part 3
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1
Today
Arrays
One-dimensional
Multi-dimensional (nested)
Multi-level
Structures
Allocation
Access
Alignment
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
2
Structure Representation
Structure represented as block of memory
Big enough to hold all of the 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
a
r
i
next
0
16
24
32
struct rec {
int a[4];
size_t i;
struct rec *next;
};
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
What does size_t mean??
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.1 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.
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
# r in %rdi, idx in %rsi
leaq (%rdi,%rsi,4), %rax
ret
int *get_ap
(struct rec *r, size_t idx)
{
return &r->a[idx];
}
Generating Pointer to Structure Member
Generating Pointer to an Array Element
Offset of each structure member determined at compile time
Compute as
r + 4*idx
r+4*idx
a
r
i
next
0
16
24
32
struct rec {
int a[4];
size_t i;
struct rec *next;
};
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
loop: # loop:
movslq 16(%rdi), %rax # i = M[r+16]
movl %esi, (%rdi,%rax,4) # M[r+4*i] = val
movq 24(%rdi), %rdi # r = M[r+24]
testq %rdi, %rdi # Test r
jne loop # if !=0 goto loop
#movslq=>Fig 3.6, move sign-extended double to quad
void set_val
(struct rec *r, int val)
{
while (r) {
int i = r->i;
r->a[i] = val;
r = r->next;
}
}
Following Linked List
C Code
Register Value
%rdi r
%rsi val
struct rec {
int a[4];
int i;
struct rec *next;
};
Element i
r
i
next
0
16
24
32
a
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Structures & Alignment
Unaligned Data
Aligned Data
Primitive data type requires K bytes
Address must be multiple of K
c
i[0]
i[1]
v
3 bytes
4 bytes
p+0
p+4
p+8
p+16
p+24
Multiple of 4
Multiple of 8
Multiple of 8
Multiple of 8
c
i[0]
i[1]
v
p
p+1
p+5
p+9
p+17
struct S1 {
char c;
int i[2];
double v;
} *p;
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Alignment Principles
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)
Compiler
Inserts gaps in structure to ensure correct alignment of fields
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Specific Cases of Alignment (x86-64)
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 double (GCC on Linux)
lowest 4 bits of address must be 00002
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
struct S1 {
char c;
int i[2];
double v;
} *p;
Satisfying Alignment with Structures
Within structure:
Must satisfy each element’s alignment requirement
Overall structure placement
Each structure has alignment requirement K
K = Largest alignment of any element
Initial address & structure length must be multiples of K
Example:
K = 8, due to double element
c
i[0]
i[1]
v
3 bytes
4 bytes
p+0
p+4
p+8
p+16
p+24
Multiple of 4
Multiple of 8
Multiple of 8
Multiple of 8
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Meeting Overall Alignment Requirement
For largest alignment requirement K
Overall structure must be multiple of K
struct S2 {
double v;
int i[2];
char c;
} *p;
v i[0] i[1] c 7 bytes
p+0 p+8 p+16 p+24
Multiple of K=8
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Arrays of Structures
Overall structure length multiple of K
Satisfy alignment requirement
for every element
struct S2 {
double v;
int i[2];
char c;
} a[10];
v i[0] i[1] c 7 bytes
a+24 a+32 a+40 a+48
a[0] a[1] a[2] • • •
a+0 a+24 a+48 a+72
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Accessing Array Elements
Compute array offset 12*idx
sizeof(S3), including alignment spacers
Element j is at offset 8 within structure
Assembler gives offset a+8
Resolved during linking
struct S3 {
short i;
float v;
short j;
} a[10];
short get_j(int idx)
{
return a[idx].j;
}
# %rdi = idx
leaq (%rdi,%rdi,2),%rax # 3*idx
movzwl a+8(,%rax,4),%eax
#Fig 3.5,move zero-extended word to double
a[0] • • • a[idx] • • •
a+0 a+12 a+12*idx
i 2 bytes v j 2 bytes
a+12*idx a+12*idx+8
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Saving Space
Put large data types first
Effect (K=4)
struct S4 {
char c;
int i;
char d;
} *p;
struct S5 {
int i;
char c;
char d;
} *p;
c
i
3 bytes
d
3 bytes
c
i
d
2 bytes
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Summary
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
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
15
Understanding Pointers & Arrays #1
A1
A2
Allocated int
Unallocated pointer
Allocated pointer
Unallocated int
int A1[3]
int *A2
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Understanding Pointers & Arrays #2
A1
A2/A4
Allocated int
Unallocated pointer
Allocated pointer
Unallocated int
A3
int A1[3]
int *A2[3]
int (*A3)[3]
int (*A4[3])
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Understanding Pointers & Arrays #3
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Declaration
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
A2/A4
A5
Allocated int
Unallocated pointer
Allocated pointer
Unallocated int
Allocated pointer to unallocated int
A1
A3
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
/docProps/thumbnail.jpeg