Arrays
Array Allocation
자료형이 T인 요소 L개로 이루어진 배열 A가 있다면, 해당 요소들의 전체 크기 L * sizeof(T) 바이트가 연속된 구간으로 메모리에 할당된다.
Array Access
배열의 이름 A를 배열의 첫 번째 요소를 가리키는 포인터처럼 사용할 수 있다. 단, A의 값을 변경하는 것은 불가능하다.
1
| int A[5] = { 1, 5, 2, 1, 3 };
|
| Reference | Type | Value |
|---|
A[4] | int | 3 |
A | int * | x |
A + 1 | int * | x + 4 |
&A[2] | int * | x + 8 |
A[5] | int | ? |
*(A + 1) | int | 5 |
A + i | int * | x + 4*i |
Array Accessing Example
1
2
3
4
5
6
7
| #define ZLEN 5
typedef int zip_dig[ZLEN];
int get_digit(zip_dig z, int digit) {
return z[digit];
}
|
1
| movl (%rdi,%rsi,4), %eax ; Mem[z + digit*4]
|
상수에 의미 있는 이름을 부여하고, typedef를 이용하여 자료형을 간결하게 표현함으로써 코드의 가독성과 유지 보수성을 향상시킬 수 있다.
Array Loop Example
1
2
3
4
| void zincr(zip_dig z) {
for (size_t i = 0; i < ZLEN; i++)
z[i]++;
}
|
1
2
3
4
5
6
7
8
9
10
| zincr:
movl $0, %eax
jmp .L3
.L4:
addl $1, (%rdi,%rax,4) ; Mem[z + i*4] += 1
addq $1, %rax
.L3:
cmpq $4, %rax
jbe .L4
rep; ret
|
Understanding Pointers & Arrays
sizeof() | An | *An | **An |
|---|
int A1[3] | 12 | 4 | - |
int *A2[3] | 24 | 8 | 4 |
int (*A3)[3] | 8 | 12 | 4 |
*A1은 int 타입이므로 역참조(**A1)가 불가능하다.A2는 포인터의 배열이다. *A2가 null 포인터일 가능성이 있으므로, 이를 역참조하는 것(**A2)은 안전하지 않다.A3는 배열을 가리키는 포인터이며, null 포인터일 가능성이 있으므로 이를 역참조하는 것(*A3, **A3)은 안전하지 않다.
Nested Arrays
2차원 배열은 1차원 배열을 요소로 가지는 배열이며, 수학적으로 표현하면 행렬과 같다.
| | Column | | |
|---|
| Row | A[0][0] | ⋯ | A[0][C - 1] |
| | ⋮ | | ⋮ |
| | A[0][0] | ⋯ | A[0][C - 1] |
2차원 배열 T A[R][C]는 R * C * sizeof(T) 바이트의 연속된 공간을 차지한다.
Nested Array Example
1
2
3
4
5
6
7
8
9
10
11
12
| #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 }
};
int *get_pgh_zip(int index) {
return pgh[index];
}
|
1
2
| leaq (%rdi,%rdi,4), %rax ; index*5
leaq pgh(,%rax,4), %rax ; pgh + index*5*4
|
1
2
3
| int get_pgh_digit(int index, int digit) {
return pgh[index][digit];
}
|
1
2
3
| leaq (%rdi,%rdi,4), %rax ; index*5
addl %rax, %rsi ; index*5 + digit
movl pgh(,%rsi,4), %eax ; Mem[pgh + (index*5 + digit)*4]
|
Muiti-Level Array Example
1
2
3
4
5
6
7
8
9
10
11
| #define UCOUNT 3
zip_dig cmu = { 1, 5, 2, 1, 3 };
zip_dig mit = { 0, 2, 1, 3, 9 };
zip_dig ucb = { 9, 4, 7, 2, 0 };
int *univ[UCOUNT] = { mit, cmu, ucb };
int get_univ_digit(size_t index, size_t digit) {
return univ[index][digit];
}
|
1
2
3
4
| salq $2, %rsi ; digit*4
addq univ(,%rdi,8), %rsi ; Mem[univ + index*8] + digit*4
movl (%rsi), %eax ; Mem[Mem[univ + index*8] + digit*4]
ret
|
Structures
Structure Representation
1
2
3
4
5
| struct rec {
int a[4];
size_t i;
struct rec *next;
};
|
구조체는 다양한 타입의 필드를 가질 수 있으며, 할당 및 접근 방식이 배열과 유사하다.
Following Linked List
1
2
3
4
5
6
7
| void set_val(struct rec *r, int val) {
while (r) {
int i = r->i;
r->a[i] = val;
r = r->next;
}
}
|
1
2
3
4
5
6
| .L3:
movslq 16(%rdi), %rax ; i = Mem[r + 16]
movl %esi, (%rdi,%rax,4) ; Mem[r + i*4] = val
movq 24(%rdi), %rdi ; r = Mem[r + 24]
testq %rdi, %rdi
jne .L3
|
Structures & Alignment
프로세서는 워드 단위로 메모리에 접근하기 때문에, 효율적인 작업 수행을 위해 컴파일러는 원시 자료형(primitive data type)의 크기가 K 바이트일 때 그 시작 주소가 K의 배수가 되도록 정렬(Alignment)하는 것을 선호한다.
구조체에서는 K 값이 더 큰 필드가 존재하면, 그에 맞추어 패딩(Padding) 바이트를 삽입하여 정렬한다.
1
2
3
4
5
| struct S1 {
char c;
int i[2];
double v;
} *p;
|
| Offset | 0 | 1 | 4 | 8 | 12 | 16 | 24 |
|---|
| Data | c | 3바이트 패딩 | i[0] | i[1] | 4바이트 패딩 | v | 끝 |
Saving Space
일반적으로 원시 자료형의 크기는 2의 거듭제곱으로 서로 배수 관계에 있다. 따라서 자료형의 크기가 작아지는 순서로 필드를 배치하여 패딩을 최소화할 수 있다.
1
2
3
4
5
| struct S2 {
char c;
int i;
char d;
} *p;
|
| Offset | 0 | 1 | 4 | 8 | 9 | 12 |
|---|
| Data | c | 3바이트 패딩 | i | d | 3바이트 패딩 | 끝 |
1
2
3
4
5
| struct S3 {
int i;
char c;
char d;
} *p;
|
| Offset | 0 | 4 | 5 | 6 | 8 |
|---|
| Data | i | c | d | 2바이트 패딩 | 끝 |
Floating Point
Streaming SIMD Extensions 3
그래픽 처리와 같은 무거운 연산을 수행하기 위해, 하나의 명령어로 여러 개의 데이터를 병렬적으로 처리하는 SIMD(Single Insturciton, Multiple Data) 기법이 등장했다. SSE(Streaming SIMD Extensions)는 x86의 SIMD 확장 명령어 집합으로, SSE3는 SSE의 3번째 버전이다.
XMM Registers
%xmm0부터 %xmm15까지 총 16개의 128비트 레지스터가 존재하며, 각 레지스터에는 여러 개의 데이터를 저장할 수 있다.
- 8비트 정수 16개
- 16비트 정수 8개
- 32비트 정수 4개
- 64비트 정수 2개
- 32비트 부동 소수점 수 4개
- 64비트 부동 소수점 수 2개
FP Basics
- 인자들은
%xmm0에서부터 순서대로 저장된다. - 반환값은
%xmm0에 저장된다. - 모두 caller-saved 레지스터이다.
1
2
3
| double dadd(double x, double y) {
return x + y;
}
|
1
2
| addsd %xmm1, %xmm0 ; x += y
ret
|
FP Memory Referencing
정수, 포인터, 부동 소수점 수가 혼합되어 있는 경우, 정수 및 포인터는 범용 레지스터(General-Purpose Register, GPR)에, 부동 소수점 수는 XMM 레지스터에 저장된다.
1
2
3
4
5
| double dincr(double *p, double v) {
double x = *p;
*p = x + v;
return x;
}
|
1
2
3
4
5
| movapd %xmm0, %xmm1 ; temp = v
movsd (%rdi), %xmm0 ; x = *p
addsd %xmm0, %xmm1 ; temp += x
movsd %xmm1, (%rdi) ; *p = temp
ret
|
각 명령어에 대한 설명은 여기 참고
References