Introduction to Computer Systems 15-213/18-243, spring 2009
CSE 2421
Array and Structure Storage and Access: Part 2
‹#›
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
Multidimensional (Nested) Arrays
Declaration
T A[R][C];
2D array of data type T
R rows, C columns
Type T element requires K bytes
Array Size
R * C * K bytes
Arrangement
Row-Major Ordering
A[0][0]
A[0][C-1]
A[R-1][0]
• • •
• • •
A[R-1][C-1]
•
•
•
•
•
•
int A[R][C];
• • •
A
[0]
[0]
A
[0]
[C-1]
• • •
A
[1]
[0]
A
[1]
[C-1]
• • •
A
[R-1]
[0]
A
[R-1]
[C-1]
• • •
4*R*C Bytes
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Board: show 3D example: a[2][3][2] to illustrate the idea of row major as enumerating indices from right to left
Nested Array Example
zip_dig pgh[4] equivalent to int pgh[4][5]
Variable pgh: array of 4 elements, allocated contiguously
Each element is an array of 5 int’s, allocated contiguously
“Row-Major” ordering of all elements in memory
#define PCOUNT 4
zip_dig pgh[PCOUNT] =
{{1, 5, 2, 0, 6},
{1, 5, 2, 1, 3 },
{1, 5, 2, 1, 7 },
{1, 5, 2, 2, 1 }};
zip_dig pgh[4];
76
96
116
136
156
1
5
2
0
6
1
5
2
1
3
1
5
2
1
7
1
5
2
2
1
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
• • •
Nested Array Row Access
Row Vectors
A[i] is array of C elements
Each element of type T requires K bytes
Starting address A + i * (C * K)
• • •
A
[i]
[0]
A
[i]
[C-1]
A[i]
• • •
A
[R-1]
[0]
A
[R-1]
[C-1]
A[R-1]
• • •
A
• • •
A
[0]
[0]
A
[0]
[C-1]
A[0]
A+(i*C*4)
A+((R-1)*C*4)
int A[R][C];
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Nested Array Row Access Code
Row Vector
pgh[index] is array of 5 int’s
Starting address pgh+20*index
Machine Code
Computes and returns address
Compute as pgh + 4*(index+4*index)
int *get_pgh_zip(int index)
{
return pgh[index];
}
# %rdi = index
leaq (%rdi,%rdi,4),%rax # 5 * index
leaq pgh(,%rax,4),%rax # pgh + (20 * index)
pgh
1
5
2
0
6
1
5
2
1
3
1
5
2
1
7
1
5
2
2
1
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
• • •
Nested Array Element Access
Array Elements
A[i][j] is element of type T, which requires K bytes
Address A + i * (C * K) + j * K = A + (i * C + j)* K
• • • • • •
A
[i]
[j]
A[i]
• • •
A
[R-1]
[0]
A
[R-1]
[C-1]
A[R-1]
• • •
A
• • •
A
[0]
[0]
A
[0]
[C-1]
A[0]
A+(i*C*4)
A+((R-1)*C*4)
int A[R][C];
A+(i*C*4)+(j*4)
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Nested Array Element Access Code
Array Elements
pgh[index][dig] is int
Address: pgh + 20*index + 4*dig
= pgh + 4*(5*index + dig)
int get_pgh_digit
(int index, int dig)
{
return pgh[index][dig];
}
leaq (%rdi,%rdi,4), %rax # 5*index
# %rsi => 2nd parameter
addq %rax, %rsi # 5*index+dig
movl pgh(,%rsi,4), %eax # M[pgh + 4*(5*index+dig)]
pgh
1
5
2
0
6
1
5
2
1
3
1
5
2
1
7
1
5
2
2
1
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Multi-Level Array Example
Variable univ denotes array of 3 elements
Each element is a pointer
8 bytes
Each pointer points to array of int’s
zip_dig cmu = { 1, 5, 2, 1, 3 };
zip_dig mit = { 0, 2, 1, 3, 9 };
zip_dig ucb = { 9, 4, 7, 2, 0 };
#define UCOUNT 3
int *univ[UCOUNT] = {mit, cmu, ucb};
36
160
16
56
168
176
univ
cmu
mit
ucb
1
5
2
1
3
16
20
24
28
32
36
0
2
1
3
9
36
40
44
48
52
56
9
4
7
2
0
56
60
64
68
72
76
Note int *
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Element Access in Multi-Level Array
Computation
Element access Mem[Mem[univ+8*index]+4*digit]
Must do two memory reads
First get pointer to row array
Then access element within array
salq $2, %rsi # 4*digit (2nd parameter)
addq univ(,%rdi,8), %rsi # p = univ[index] + 4*digit
movl (%rsi), %eax # return *p
ret
int get_univ_digit
(size_t index, size_t digit)
{
return univ[index][digit];
}
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Array Element Accesses
int get_pgh_digit
(size_t index, size_t digit)
{
return pgh[index][digit];
}
int get_univ_digit
(size_t index, size_t digit)
{
return univ[index][digit];
}
Nested array
Multi-level array
Accesses looks similar in C, but address computations very different:
Mem[pgh+20*index+4*digit]
Mem[Mem[univ+8*index]+4*digit]
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
N X N Matrix Code
Fixed dimensions
Know value of N at compile time
Variable dimensions, explicit indexing
Traditional way to implement dynamic arrays
Variable dimensions, implicit indexing
Now supported by gcc (non-ANSI C)
#define N 16
typedef int fix_matrix[N][N];
/* Get element a[i][j] */
int fix_ele(fix_matrix a,
size_t i, size_t j)
{
return a[i][j];
}
#define IDX(n, i, j) ((i)*(n)+(j))
/* Get element a[i][j] */
int vec_ele(size_t n, int *a,
size_t i, size_t j)
{
return a[IDX(n,i,j)];
}
/* Get element a[i][j] */
int var_ele(size_t n, int a[n][n],
size_t i, size_t j) {
return a[i][j];
}
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
16 X 16 Matrix Access
/* Get element a[i][j] */
int fix_ele(fix_matrix a, size_t i, size_t j) {
return a[i][j];
}
# a in %rdi, i in %rsi, j in %rdx
salq $6, %rsi # 64*i
#calculate address of needed row
addq %rsi, %rdi # a + 64*i
#now get to specific row element
movl (%rdi,%rdx,4), %eax # M[a + 64*i + 4*j]
ret
Array Elements (A[16][16]
Address A + i * (C * K) + j * K
C = 16, K = 4, therefore, each row = 16*4 = 64 bytes
Total Size of Array: 16*16*4 = 1024 bytes
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
n X n Matrix Access
/* Get element a[i][j] */
int var_ele(size_t n, int a[n][n], size_t i, size_t j) {
return a[i][j];
}
# n in %rdi, a in %rsi, i in %rdx, j in %rcx
imulq %rdx, %rdi # n*i
leaq (%rsi,%rdi,4), %rax # a + 4*n*i
movl (%rax,%rcx,4), %eax # a + 4*n*i + 4*j
ret
Array Elements
Address A + i * (C * K) + j * K
C = n, K = 4
Must perform integer multiplication
‹#›
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
/docProps/thumbnail.jpeg