Post

[컴퓨터 시스템] 배열의 할당과 접근

Posted
By sihyun 7 min read

컴퓨터 시스템 책 3장 프로그램의 기계수준 표현에서 3.8 배열의 할당과 접근 에 대해 정리한 글입니다.

3.8 배열의 할당과 접근

C 언어에서는 배열 원소들에 대한 포인터를 만들 수 있으며, 이 포인터들 간에 연산도 가능합니다
이러한 연산은 결국 기계어 수준에서는 주소 계산으로 변환됩니다

최적화 컴파일러는 배열 인덱스를 사용할 때 필요한 주소계산을 단순화하는 데 특히 우수한 성능을 보입니다
그 이유는 반복되는 주소 계산을 미리 해둬서 더 빠르게 돌게 하기 때문입니다

예를 들어 다음과 같은 배열 선언이 있다고 가정해보자.

int arr[5] = {10, 20, 30, 40, 50};
배열은 메모리에 아래와 같이 연속적으로 저장이 된다
int형은 4byte이므로, 각 요소는 4byte 간격으로 저장이 된다

주소0x1000x1040x1080x10C0x110
값1020304050

C에서 배열에 접근하는 것은 사실상 주소를 계산하는 것과 같다
예를 들어 int x = arr[2];는 아래와 같이 포인터 연산으로도 표현할 수 있다
x = *(arr+2);
배열의 시작 주소(arr)에서 두번째 요소만큼 이동한 위치의 값을 가져오는 것이다
이러한 연산은 컴파일 시 어셈블리 코드로 변환된다

movl 8(%rdi), %eax

  • 8(%rdi) : rdi 레지스터가 가리키는 주소에서 8byte 떨어진 위치의 값을 의미
  • %eax : 목적지 레지스터, 여기에 값을 저장함

즉 8(%rdi)는 8byte 떨어진 3번째 요소를 뜻한다
결과적으로 x에는 30이 저장된다

3.8.1 기본 원리

배열 선언의 형태와 의미

1
2
3
4

char    A[12];
char   *B[8];
int     C[6];
double *D[5];
ArrayElement sizeTotal size
A112
B864
C424
D840

배열 B, D는 모두 포인터의 배열로, 배열의 원소는 각각 8byte 크기를 갖는다

배열 접근

Q. x86-64에서 배열 접근은 어떻게 처리가 될까요?
x86-64의 메모리 참조 인스트럭션은 배열 접근을 간단하고 빠르게 수행할 수 있도록 설계되었다

1

int E[10];

예를들어, E[i]에 접근하려면 실제로 배열의 시작 주소에 i * 4 byte를 더한 위치를 참조해야한다
int타입이 4byte이기 때문이다

[어셈블리 코드에서 E[i]에 접근하는 과정]

  1. E 배열의 시작 주소가 %rdx에 저장되어있고
  2. i가 %rcx에 저장되어있다면,

아래와 같은 어셈블리 인스트럭션을 사용할 수 있다
movl ($rdx, $rcx, 4), %eax

이 인스트럭션은 주소 계산을 수행하게 된다
주소 = E + i * 4
해당 주소에 저장된 값을 %eax 레지스터에 저장한다

3.8.2 포인터 연산

C는 포인터 간에 연산을 허용하며, 계산된 값은 포인터가 참조하게 되는 자료형의 크기에 따라 그 값이 확대된다.

단항연산자 &와 *는 포인터의 생성과 역참조를 수행한다

1
2

int x= 10;
int *p = &x;

p는 x의 주소를 저장하는 포인터다
*p는 p가 가리키는 값 10을 준다

포인터에 숫자 더하기

그냥 숫자처럼 더하는 게 아니라, 자료형의 크기를 기준으로 이동한다

1
2

int arr[5] = {10, 20, 30, 40, 50};
int *p = arr;
  • p : arr[0]의 주소
  • p + 1 : arr[1]의 주소
  • p + 2 : arr[2]의 주소
  • *(p+2) : arr[2]의 값 → 30

포인터 뺄셈

두 원소 사이의 거리를 구하는 것이다
아래의 경우는 4칸 차이가 나므로, 4이 출력된다

1
2
3
4

int arr[5] = {10, 20, 30, 40, 50};
int *a = &arr[4];
int *b = &arr[0];
int minus = a - b; // 4

3.8.3 다중 배열

C에서 2차원 배열은 1차원 배열의 배열이다
배열의 원소들은 메모리에 행 우선(row major)으로 쌓인다
따라서 배열에 순서대로 접근 할 때, 행 우선 순서로 접근하는 것이 좋다
arr[i][j]의 주소는 &arr[i][j] = arr + (i * 열의 개수 + j)로 계산된다

예를 들어보자

1

int A[5][3];

위와 같이 배열을 선언하면, A는 5개의 행과 3개의 열을 가지는 2차원 배열이다
각 원소는 int타입이고, 각 int는 4byte 이니까 총 크기는 4byte * 5행 * 3열 = 60byte이다

또한 &A[2][1]의 주소를 계산해보면 A + (2 * 3 + 1) = A + 7로 계산된다
즉 A[2][1]은 배열의 7번째 요소에 해당한다

  • typedef를 이용한 표현 방식
1
2

typedef int row3_t[3];
row3_t A[5];

row3_t는 3개의 정수로 이루어진 배열
A는 이런 배열을 5개 가지는 배열이다

  • 메모리엔 행 우선 저장 방식을 사용해 저장된다
1
2
3
4
5

A[0][0], A[0][1], A[0][2],
A[1][0], A[1][1], A[1][2],
A[2][0], A[2][1], A[2][2],
A[3][0], A[3][1], A[3][2],
A[4][0], A[4][1], A[4][2]

한 행의 모든 열이 먼저 저장되고, 그 다음 행으로 넘어가는 방식이다

KraftonJungle
jungle

© sihyun. Some rights reserved.