[TIL] 크래프톤 정글 3주차 CS:app 6(배열의 할당과 접근)

3.8 배열의 할당과 접근

사실 이 단원은 C언어를 배우고 써본 경험이 있는 사람에게는 이해하기 어렵지 않다고 생각한다.

 

하지만 C언어보다 하위 레벨인 어셈블리어를 이용해서 어떤 식으로 작동하는지 살펴보는 것은 C언어 경험자에게도 좋은 경험이라고 생각한다.

 

3.8.1 기본 원리

자료형 T와 정수형 상수 N에 대해 T  A[N]; 과 같이 선언했다고 생각해보자.

 

이 배열의 시작하는 위치를 xa 라고 하자.

 

이 배열 선언으로 인해 L * N 바이트의 연속적인 공간을 메모리에 할당하며, L(바이트 단위)은 자료형 T의 크기를 나타낸다.

 

또 A를 이 배열이 시작하는 위치를 가리키는 포인터로 사용할 수 있다. 이 값은 위의 xa와 같다.

 

배열의 i 번째 원소의 주소는 xa + L * i 이다.

포인터 변수의 크기는 가리키는 자료형에 관계없이 8byte이다.

 

예를 들어 정수형 배열 E를 선언하고 E[i]를 계산하려 한다고 하자.

 

여기서 E의 주소는 레지스터 %rdx에, i 값은 %rcx에 저장되어 있다고 하면 다음 instruction은 주소 계산 xe + 4 * i 를 수행하고 메모리 위치를 읽어 그 결과를 레지스터 %rax에 저장한다.

3.8.2 포인터 연산

위에서 진행한 예제(E)를 확장한 예제를 보도록 하자.

 

(E의 시작주소는 %rdx에, i 값은 %rcx에 저장되어 있음)

마지막 줄의 Value는 4i가 맞는 것 같음

 

배열 값들을 리턴하는 연산들은 자료형 int를 가지므로 4 byte 연산(movl)과 레지스터(%eax)와 연관되어 있는 것을 볼 수 있다.

 

포인터를 리턴하는 경우에는 자료형 int *를 가지므로 8 byte 연산(leaq)와 레지스터들(%rax)과 연관되어 있다.

 

마지막 예제의 경우에는 결과 값을 자료형 long으로 갖게 되는데 같은 자료구조 내에서 두 포인터의 차를 계산할 수 있음을 보여준다.(결과 값 value 가 (주소 값의 차 / 자료형의 크기) 와 같은 것을 볼 수 있다)

3.8.3 다중 배열

위와 같은 주소값 계산들은 다차원 배열을 선언할 때에도 적용된다.

 

다음과 같이 선언된 배열이 있다고 하자.

이 배열의 원소 D[i][j]의 메모리 주소는 다음과 같다.

L은 자료형 T의 바이트 크기

 

다차원 배열의 원소를 접근하기 위해서 컴파일러는 원하는 원소의 오프셋을 계산하는 코드를 생성하고, 배열의 시작을 기본 주소로, 오프셋을 인덱스(바이트 크기로 배율이 적용될 수도 있음)로 하는 MOV instruction을 사용한다.

이 예제에서 xa, i, j가 각각 레지스터 %rdi, %rsi, %rdx에 위치한다고 하자.

 

그럼 배열 안의 원소 A[i][j]는 다음과 같은 코드에 의해 복사될 수 있다.

주소 연산의 덧셈과 배율을 사용해서 xa + 12i + 4j = xa + 4(3i + j) 형태로 계산한 것을 볼 수 있다.

 

3.8.4 고정 크기의 배열

C 컴파일러는 고정 크기의 다차원 배열을 위한 커드에 의해 다양한 최적화를 수행할 수 있다.

 

이 장에서는 최적화 수준이 -01로 설정되었을 때 GCC가 수행하는 몇 가지 최적화를 설명한다.

 

다음과 같이 자료형 fix_matrix를 16 * 16 정수의 배열로 선언했다고 하자.

 

 

그림 3.37(a) 코드는 배열 A의 i 행과 배열 B의 k 열의 내적을 계산한다.

 

GCC는 그림 3.37(b)에서 함수 fix_prod_ele_opt로 나타낸 것처럼 C로 작성한 코드를 생성한다.

 

이 코드는 인덱스 j를 제거하고 모든 배열 참조를 포인터 역참조로 변환하는 등, 여러 최적화를 진행했다.

(1) A의 행 i의 연속된 원소들을 가리키는 Aptr로 이름붙인 포인터를 생성하고(초기값 : A의 행 i의 첫 번째 원소의 주소),

(2) B의 열 k의 연속된 원소들을 가리키는 Bptr로 이름붙인 포인터를 생성하고(초기값 : B의 열 k의 첫 번째 원소의 주소),

(3) 루프를 종료하는 조건으로 Bptr과 비교할 때 사용할 Bend 포인터를 생성한다.(Bend : B의 열 j의 n+1번째 원소가 되는 인덱스)

 

다음은 3.37(a)의 함수 fix_prod_ele에 대해서 GCC가 생성한 실제 어셈블리 코드이다. %eax는 result, %rdi는 Aptr, %rcx는 Bptr, %rsi는 Bend를 저장하는 것을 볼 수 있다.

 

3.8.5 가변 크기 배열

C언어에서는 가변 크기 배열을 다음과 같이

지역 변수나 함수의 인자로 선언할 수 있으며, 배열의 차원은 선언 부분을 만날 때 수식 expr1, expr2를 계산해서 결정된다.

 

예를 들어, n * n 배열의 i, j 원소에 접근하는 함수를 다음과 같이 작성할 수 있다.

매개 변수 n은 매개 변수 A[n][n]보다 반드시 먼저 나와야 한다.(C언어는 절차지향 언어이기 때문에 먼저 나오지 않으면 배열 선언을 만났을 때 배열의 차원이 계산이 안됨)

 

GCC는 이 역참조 함수에 대한 코드를 다음과 같이 생성한다.

 

이 주소 계산에서 주목해 볼만 한 것은

(1) 추가된 인자 n으로 인해 레지스터 사용이 바뀌었다는 것과

(2) n * i를 계산하기 위해 곱셈 instruction imulq가 사용됐다는 점이다.(leaq가 사용되지 않았다)

 

일부 프로세서에서는 곱셈이 상당한 성능 저하를 가져오지만, 이 경우에는 어쩔 수 없이 쉬프트와 더하기 대신 곱셈을 사용했다.

 

 

위의 그림 3.38(a)는 두 개의 n * n 배열 A, B의 곱에서 i, k 원소를 계산하는 코드를 보여준다.

 

GCC는 그림 3.38(b)와 같이 C로 재구성한 어셈블리 코드를 생성한다.

 

앞서 그림 3.37과 다르게 3.38(b)에서는 루프 변수 j를 유지하는데, 이 j는 언제 루프가 종료하는지를 감지하고, 행 i의 원소들로 구성되는 배열을 인덱싱하기 위해 사용된다.

 

다음은 var_prod_ele 루프에 대한 어셈블리 코드이다.

 

이 코드에서는 int의 크기만큼 커진 4n(레지스터 %r9에 담겨있음)을 Bptr을 증가시키는 데 사용하며, n의 값(레지스터 %rdi)은 루프의 경계를 체크하기 위해 사용된다.

 

C언어에서는 배율을 따로 표현하지 않아도 되기 때문에 4n과 n이 따로 존재하지 않는다.