Organisasi Sistem Komputer
Bagian 8 Struktur Data
Sekolah Teknik Elektro dan Informatika ITB 2009 1
Pembahasan pe data dasa Tipe dasar Array : alokasi, pengaksesan Loop array Nested array Array multi multi-level level
2
Tipe Data Dasar Integer disimpan dan beroperasi pada register umum signed atau unsigned tergantung dari instruksi yang dipakai Intel byte word double word
GAS b w l
Byte 1 2 4
C [unsigned] char [unsigned] short [unsigned] int
Floating Point disimpan dan beroperasi pada register khusus floating point Intel Single Double Extended
GAS s l t
Byte 4 8 10/12
C float double long double
3
Alokasi Array Prinsip dasar : T A[L]; Array dengan tipe data T dan panjang L Area yang dialokasikan secara berurutan : L * sizeof(T) byte char nama[12]; x
x + 12
int val[5]; x
x+4
x+8
x + 12
x + 16
x + 20
double nilai[4];
x
x+8
x + 16
x + 24
x + 32
char *p[3]; p[3]; x
x+4
x+8 4
Mengakses Array Prinsip dasar : T A[L];
Array dengan tipe data T dan panjang L Identifier A dapat digunakan sebagai pointer ke elemen array 0 val[0]
int val[5];
val[1]
1 x
5 x+4
val[2]
val[3]
2
1
3
x + 12
x + 16
x+8
Referensi
Tipe
Nilai
val[4] val val+1 &val[2] val[5] ( a ) *(val+1) val + i
int int int int int int t int
3 * * *
*
val[4]
x + 20
x x+4 x+8
?? 5 x+4i 5
Contoh Array
typedef yp int kode_p pos[5]; kode_pos itb = { 4, 0, 1, 3, 2 }; kode_pos mit = { 0, 2, 1, 3, 9 }; kode pos cmu = { 1 kode_pos 1, 5 5, 2 2, 1 1, 3 };
kode_pos itb;
4 16
kode_pos mit;
0 20
0 36
kode_pos cmu;
24 2
40 1
56
1 28 1 44
5 60
3 32 3 48
2 64
2
9 52
1 68
36
56 3
72
76
Catatan : Deklarasi “kode_pos itb” ekivalen dengan “int itb[5]” Setiap array dialokasikan berurutan dengan panjang setiap blok 20 byte. Tetapi hal h l ini tidak d k selalu l l terjadi d pada d program sesungguhnya h 6
Contoh Mengakses Array Perhitungan : Register %edx berisi alamat awal array Register %eax berisi indeks array Di Digit it yang dii diinginkan i k berada b d pada d 4*%eax + %edx
int get_digit (kode pos z, (kode_pos z int dig) { return z[dig]; }
Menggunakan referensi memori (% d % (%edx,%eax,4) 4) Memory Reference Code # %edx = z # %eax = dig movl (%edx,%eax,4),%eax # z[dig]
7
Contoh Melakukan Referensi kode_pos itb;
4 16
20
kode_pos mit;
0 36
mit[3] mit[5] mit[-1] itb[15]
2
1 56
+ + + +
4* 3 4* 4 5 4*-1 4*15
1
5 60
48 56 32 76
3
2 64
36 9
52 1
68
3 1 2 ??
2 32
48
Nilai = = = =
3 28
44
Alamat 36 36 36 16
1 24
40
kode_pos cmu;
Referensi
0
56 3
72
76
Jaminan Valid? Ya Tidak Tidak
=cmu[0]? =itb[4]?
Tidak
Kode tidak melakukan pengecekan kebenaran Tidak ada jaminan lokasi relatif untuk array yang berbeda
8
Loop Array Kode asal
Versi hasil transformasi dihasilkan oleh GCC Mengeliminasi loop variabel i Konversi kode array menjadi kode pointer Diekspresikan dalam bentuk do-while Tidak perlu tes ketika masuk loop
int kode2int(kode kode2int(kode_pos pos z) { int i; int zi = 0; for (i = 0; 0 i < 5; i++) { zi = 10 * zi + z[i]; } return zi; ; } int kode2int(kode_pos z) { int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi; ; } 9
Loop Array Register :
%ecx
z
%eax % b %ebx
zi zend d
Perhitungan : 10*zi + *z diimplementasikan menjadi *z 2*(zi+4*zi) j di * + 2*( i 4* i) z++ bertambah 4
int kode2int(kode_pos zd2int(zip_dig z) z) { int zi = 0; int *zend = z + 4; do { zi i = 10 * zi i + * *z; z++; } while(z <= zend); return zi; ; }
# %ecx = z xorl l %eax,%eax % % leal 16(%ecx),%ebx .L59: leal (%eax,%eax,4),%edx movl (%ecx),%eax addl $4,%ecx leal (%eax,%edx,2),%eax cmpl %ebx %ebx,%ecx %ecx jle .L59
# zi i = 0 # zend = z+4 # # # # # #
5*zi *z z++ zi = *z + 2*(5*zi) z : zend if <= goto loop 10
Nested Array
kode_pos _ pgh[4];
typedef int kode_pos[5]; kode pos pgh[4] = kode_pos {{1, 5, 2, 0, 6}, {1, 5, 2, 1, 3 }, {1, 5, 2, 1, 7 }, {1, 5, 2, 2, 1 }};
1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1 76
96
116
136
156
Deklarasi “kode_pos pgh[4]” ekivalen dengan “int pgh[4][5]” Variabel pgh merupakan array dengan 4 elemen dialokasikan secara seca a berurutan be tan Masing-masing elemen merupakan array dengan 5 int dialokasikan secara berurutan Seluruh elemen dijamin berurutan secara “Row-Major” 11
Alokasi Nested Array Deklarasi T A[R][C];
A[0][0]
• • •
A[0][C-1]
Array dari tipe data T • • • • R baris, C kolom • • Elemen type T memerlukan K byte A[R-1][0] • • • A[R-1][C-1] Ukuran Array b t R * C * K bytes Pengaturan Row-Major Ordering int A[R][C]; A A A A [0] • • • [0] [1] • • • [1] [0] [ ] [ [C-1] ][ [0] ] [ [C-1] ]
•
•
•
A A [R-1] • • • [R-1] [0] [ ] [ [C-1] ]
4*R*C Bytes 12
Mengakses Baris Nested Array Vektor baris A[i] adalah arrayy dengan g C elemen Masing-masing elemen bertipe T Dimulai dari alamat A + i * C * K int A[R][C]; A[0] A [0] [0] A
•••
A[i] A [0] • • • [C-1]
A [i] [0]
•••
A+i*C*4
A[R 1] A[R-1] A A [i] • • • [R-1] [C-1] [0]
•••
A [R-1] [C-1]
A+(R-1)*C*4
13
Kode Mengakses Baris
Vektor baris
int *get_pgh_zip(int index) { return pgh[index]; }
pgh[index] adalah array dengan 5 int Dimulai dari alamat pgh+20*index
Kode Menghitung dan mengembalikan alamat Perhitungan : pgh + 4*(index+4*index) # %eax = index (%eax,%eax,4),%eax , , ), # 5 * index leal ( leal pgh(,%eax,4),%eax # pgh + (20 * index) 14
Mengakses Elemen Array Elemen array A[i][j] adalah elemen dengan tipe T Alamat A + (i * C + j) * K
A [i] [j]
[ ][ ]; int A[R][C]; A[0] A [0] [0] A
•••
A[i] A [0] • • • [C-1]
•••
A [i] [j]
A[R-1]
•••
A+i*C*4
A • • • [R-1] [0]
•••
A [R-1] [C-1]
A+(R-1)*C*4
A+(i*C+j)*4
15
Kode Akses Elemen Array Elemen array pgh[index][dig] adalah int Alamat : pgh + 20*index + 4*dig Kode Perhitungan alamat pgh + 4*dig + 4*(index+4*index) movl melakukan referensi memori # %ecx = dig # %eax = index leal 0(,%ecx,4),%edx leal (%eax,%eax,4),%eax movl pgh(%edx pgh(%edx,%eax,4),%eax %eax 4) %eax
int get_pgh_digit (i t i (int index, d i int t di dig) ) { return pgh[index][dig]; }
# 4*dig # 5*index # *(pgh (pgh + 4*dig 4 dig + 20*index) 20 index) 16
Contoh Referensi Unik kode_pos pgh[4]; pg [ ];
1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1 76
Referensi pgh[3][3] pgh[2][5] pgh[2][-1] pgh[4][-1] pgh[0][19] pgh[0][-1]
96
Alamat 76+20*3+4*3 = 148 76+20*2+4*5 = 136 76+20*2+4*-1 = 112 76+20*4+4*-1 = 152 76+20*0+4*19 = 152 76+20*0+4*-1 = 72
116
Nilai 2 1 3 1 1 ??
Kode tidak melakukan pengecekan kebenaran Elemen array dijamin berurutan
136
156
Jaminan ? Ya Ya Ya Ya Ya Tidak
17
Contoh Array Multi Level Variabel univ adalah array dengan 3 elemen Masing-masing elemen merupakan pointer 4 byte y Masing-masing pointer menunjuk ke array int
typedef int kode_pos[5]; kode pos itb = { 4 kode_pos 4, 0 0, 1 1, 3 3, 2 }; kode_pos mit = { 0, 2, 1, 3, 9 }; kode_pos cmu = { 1, 5, 2, 1, 3 }; int *univ[3] = {mit, {mit itb, itb cmu};
itb 4
0
1
3
2
univ 160
36
164
16
168
56
mit
16
20 0
cmu 36
2 40
1 56
24 1 44 5
60
28 3 48 2
64
32 9 52 1
68
36
56 3
72
76 18
Akses Elemen Array Multi Level int get_univ_digit (int index, int dig) { return univ[index][dig]; }
Perhitungan Akses elemen Mem[Mem[univ+4*index]+4*dig]
Melakukan dua kali pembacaan memori Pertama, ambil pointer ke baris array Kemudian, mengakses elemen pada array # %ecx = index # %eax = dig % di leal 0(,%ecx,4),%edx # 4*index movl univ(%edx),%edx # Mem[univ+4*index] movl (%edx,%eax,4),%eax , , , # Mem[...+4*dig] g
19
Mengakses Elemen Array Referensi C Nested Array
Perhitungan alama berbeda Multi-Level Array
int get_pgh_digit (int index, int dig) { return pgh[index][dig]; }
int get_univ_digit (int index, int dig) { return univ[index][dig]; }
Elemen pada Mem[pgh+20*index+4*dig]
Elemen pada Mem[Mem[univ+4*index]+4*d ig] cmu 1
5
2
1
3
univ 160
1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1 76
96
116
136
156
36
164
16
168
56
mit
16
20 0
ucb 36
40 9
56
24 2 44 4
60
28 1 48 7
64
32 3 52 2
68
36 9 56 0
72
76
20
Contoh Referensi Unik itb 4
0
1
3
2
univ 160
36
164
16
168
56
mit
16 0
cmu 36
Alamat a at 56+4*3 16+4*5 56+4*-1 ?? 16+4*12
= 68 = 36 = 52 = 64
24 2
40 1
56 Referensi ee e s univ[2][3] univ[1][5] univ[2][-1] [ ][ ] univ[3][-1] univ[1][12]
20
28 1
44 5
60 Nilai a 1 0 9 ?? 2
3 52 1 68
36 9
48 2
64
32
56 3
72 Jaminan Ja a ?
76
Ya Tidak Tidak Tidak Tidak
Kode tidak melakukan pengecekan kebenaran Tidak ada jaminan urutan elemen pada array yang berbeda
21
Menggunakan Nested Array Kelebihan Compiler l C menangani array secara double Menghasilkan kode sangat efisien f Menghindari perhitungan indeks ganda
Keterbatasan K t b t Hanya bekerja jika ukuran array tetap (*,k) (i,*) B i Baris
A
B
#define N 16 t typedef d f i int t fi fix_matrix[N][N]; t i [N][N] /* Compute element i,k of fixed matrix product */ / int fix_prod_ele (fix_matrix a, fix_matrix b, int i, , int k) ) { int j; int result = 0; for (j = 0; f 0 j < N; N j++) result += a[i][j]*b[j][k]; return result; }
Kolom 22
Nested Array Dinamik Kelebihan Dapat membuat matriks dengan urutan tertentu Pemrograman Perhitungan P hit iindeks d k harus h secara eksplisit Kinerja Biaya mengakses satu elemen cukup besar Harus melakukan perkalian movl 12(%ebp),%eax movl 8(%ebp),%edx imull 20(%ebp),%eax addl 16(%ebp),%eax 16 movl (%edx,%eax,4),%eax
int * new_var_matrix(int n) { return (int *) calloc(sizeof(int), n*n); } int var_ele (int *a, int i, int j, int n) { return a[i*n+j]; } # # # # #
i a n*i n*i+j Mem[a+4*(i*n+j)] 23
Perkalian Array Dinamik Tanpa optimisasi P Perkalian k li 2 untuk subscript 1 data data Penjumlahan 4 untuk indeks array 1 untuk indeks loop 1 untuk data (*,k)
/* Compute element i,k of variable matrix product */ int var var_prod_ele prod ele (int *a, int *b, int i, int k, int n) { int j; int result = 0; for (j = 0; j < n; j++) result += + a[i*n+j] * b[j*n+k]; return result; }
(i,*) Baris
A
B Kolom 24
Optimisasi Perkalian Array Dinamik {
Optimisasi
int j; int result = 0; for (j = 0; j < n; j++) result += a[i*n+j] * b[j*n+k]; return result;
Terjadi j jika j level optimisasi p diset -O2
Pergerakan kode Ekspresi i*n dapat dihitung di luar loop
Reduksi kekuatan
} { int j; i t result int lt = 0 0; int iTn = i*n; int jTnPk = k; for (j j = 0; j < n; j j++) { result += a[iTn+j] * b[jTnPk]; jTnPk += n; } return result;
Increment j berpengaruh pada increment j*n+k sebanyak n
Kinerja Compiler dapat mengoptimisasi pola pola-pola pola akses regular }
25
