[CSAPP] 3.8 Array allocation and access(배열의 할당과 접근)

3.8 Array allocation and access(배열의 할당과 접근)

C언어에서 배열은 숫자 데이터를 더 큰 데이터 유형으로 확장하는 한가지 방법이다.

C에서 배열은 간단히 구현해서 machine code로 번역이 간단하다.

C의 특징은 배열 내 element에 대한 포인터 만들고 그 포인터로 계산할 수 있다는 것이다.

이것은 machine code에서 주소 계산으로 번역할 수 있다.

3.8.1 basic principles(기본 원리)

배열 선언하는 방법은 아래와 같다.

데이터형 이름[N]; (N=element 개수)

이 선언에는 두가지 효과가 있다.

1. (데이터 형의 크기 = L * N) 바이트의 연속적인 메모리를 할당한다.
2. 이름은 배열의 시작을 가리키는 포인터로 사용될 수 있다.
   1. 배열의 시작 주소가 Xa라고 하면 이름의 값은 Xa인 것이다.

배열의 element들은 0~N-1의 정수 index로 접근할 수 있다.

그리고 i번째 element는 Xa+L*i 주소에 저장이 된다.

x86-64에서 메모리를 참조하는 명령어는 배열 접근을 간단하게 할 수 있게 설계 되었다.

예를 들어 E[i]를 계산하고 싶다고 해보자. 이때 E에 저장된 값은 int이다.

E의 값은 rdx에 i의 값은 rcx에 저장되어 있다고 하자.

 

그러면 mov(%rdx, %rcx, 4) , %eax

이렇게 하면 Xe+4*i 주소를 계산해서 그 주소의 메모리를 읽고 거기에 있는 값은 eax 레지스터에 복사해주는 것이다.

3.8.2 pointer arithmetic(포인터 연산)

C에서 포인터 연산이 가능하다.

포인터 p의 데이터형이 T이고 p의 값 즉 주소가 Xp이면 p+i의 값은 Xp+L*i이다.

L은 데이터형 T의 크기다. int이면 4바이트이다.

 

단하 연산자 &, *는 포인터의 생성과 참조를 허용한다.

Expr이 어떤 값이라고 하면 &Expr은 그 객체의 주소를 반환하는 포인터다.

Expr이 주소라고 하면 *Expr은 그 주소에 있는 값을 반환한다.

 

배열에서 A[i] == *(A+i)이다.

이것은 i번째 배열의 요소의 주소를 계산하고 그 메모리 위치에 접근하는 것이다.

 

아래 예시를 보자.

rdx 레지스터는 배열 E의 값 = 배열 E의 시작 주소를 가지고 있다.

rcx 레지스터는 index i의 값을 가지고 있다.

그리고 data 결과 값은 eax 레지스터에, 포인터 = 주소 결과 값은 rax 레지스터에 저장된다.

예제에서 보면 배열에 저장된 타입이 int이기 때문에 4바이트이니 4바이트 연산자 mov1과 4바이트 레지스터 eax를 사용하는 것을 알 수 있다.

그리고 포인터형은 int*이기 때문에 8바이트 연산자 leaq와 8바이트 레지스터 rax를 사용하는 것을 알 수 있다.

 

마지막 예시를 보면 동일한 데이터 구조 내에서 즉 같은 배열에서 두 포인터 차이를 계산할 수 있다.

결과를 보면 데이터 형은 long이고 값은 두 주소의 차이를 데이터 형의 크기로 나눈 값이다.

왜냐하면 E[i]의 값이 E+(int 크기)*i이기 때문이다.

 

3.8.3 Nested arrays(다중 배열)

중첩 배열에 관한 이야기다.

중첩 배열을 만들 때에도 배열 할당과 참조에 관한 기본 원리는 같다.

 

선언은 int A[5][3]; 이렇게 하면 된다.

이것은 아래와 같은 의미다.

이때 row3_t 데이터 형은 int 3개 가지고 있는 배열로 정의된 것이다. 즉 이 데이터 형 크기는 3*4=12바이트이다.

배열 A는 그런 데이터 형을 5개 가지고 있는 것이다. 그래서 전체 배열의 크기는 5*12=60 바이트다.

 

이런 중첩 배열은 2차원 배열로도 보일 수 있다. 5개 행과 3개 열로 이뤄진 이뤄진 배열이다.

 

0열 1열 2열

0행

1행

2행

3행

4행

 

2차원 배열은 메모리에 행 주요 순서로 정렬된다.

이것의 의미는 0행의 것들이 쭉 써지고 1행의 것들이 쭉 써지는 것이다.

아래 그림처럼 저장되는 것이다.

2차원 배열에 element에 접근하려면 아래와 같이한다.

이때 L은 2차원 배열의 데이터 형 크기다.

여기서 C*i는 우선 i번째로 온 것이다.

열이 C개 있으니 거기에 i를 곱해 i번째 시작으로 온 것이다.

거기에 j를 더하는 것이다.

 

실제 A[i][j]의 값을 계산하는 machine code를 보자.

A의 시작주소 Xa는 rdi, i는 rsi, j는 rdx 레지스터에 저장되어 있다.

 

우선 1번 줄은 i+i*2를 해서 3i를 계산하는 것이다.

A[5][3]이니 i의 위치를 구하기 위해서 3i한 것이다.

그리고 이 값을 rax 레지스터에 저장한다.

 

2번 줄은 Xa+3i*4해서 Xa+12i를 구한다.

이것은 i의 위치로 이동한 것이다.

배열의 처음 위치 Xa에서 int이니 4를 곱하고 이동하는 것이다.

 

3번 줄은 Xa+12i+j*4해서 Xa+12i+4j를 구하는 것이다.

이것을 묶어보면 Xa+4(3i+j)이므로 위에서 본 아래의 식처럼 A[i][j]의 값을 구할 수 있는 것이다.

3.8.4 fixed-size arrays(고정크기의 배열)

C 컴파일러는 고정 크기 다차원 배열에서 작동하는 코드를 위해 많은 최적화가 있다.

아래에서 fix_matrix라는 타입을 16*16짜리 배열로 설정한 것이다.

고정 크기 배열을 선언할 때 위처럼 #define으로 해서 하는 것이 좋다고 한다. 변경할 때 상수 값만 바꿔주면 되기 때문이다.

위와 같은 코드를 구하는데 컴파일러가 아래와 같은 코드로 바꿔서 실행해준다.

A의 i행의 모든 값과 B의 k열의 모든 값을 다 더하는 코드이다.

여기에는 많은 최적화가 들어가 있다.

보면 index j를 다 없애고 모든 배열 참조를 포인터 역참조로 바꿨다.

 

여기서 3개의 포인터가 있는게 Aptr은 i행의 연속적인 element들을 가리키는 것이다.

Bptr은 k열의 연속적인 element들을 가리키는 것이다.

Bend는 루프가 종료될 때 Bptr과 같은 값을 가지는 포인터다.

 

루프에서는 각 포인터가 가리키는 값들을 더해서 result에 넣고 각 포인터가 다음 요소를 가리키게 하는 것이다.

 

아래는 이것의 assembly code이다.

eax 레지스터는 result를 저장하는 것이고 rdi는 Aptr, rcx는 Bptr, rsi는 Bend 값을 저장한다.

3.8.5 variable-size arrays(가변크기의 배열)

C는 다차원 배열의 크기가 컴파일 할 때 결졍되는 것을 지원한다. 1차원 배열은 제외다.

C에서 variable size array는 배열을 지역 변수나 함수의 argument로도 선언할 수 있게한다.

이때 배열이 int A[expr1][expr2]라고 하면 차원 수는 expr1, expr2 이 두 식이 선언되었을 때 결정한다.

 

아래 예시는 배열을 함수의 argument로 사용한 경우다.

보면 인자 n은 인자 A[n][n]보다 반드시 앞서야 한다.

그래야 함수가 argument에서 배열을 발견했을 때 차수를 계산할 수 있다.

 

이런 코드를 GCC는 아래와 같은 코드로 만든다.

여기서 보면 A[i][j]의 주소 계산을 Xa+4(ni)+4j = Xa+4(ni+j) 이렇게 계산한다.

이런 계산 방식은 fixed size array와 비슷하다.

하지만 차이점이 있다.

1. 매개변수 n을 위해 레지스터 사용이 조금 달라진다.
2. 3i를 계산하기 위해 leaq 명령어가 아니라 ni를 계산하기 위해 imulq 명령어 사용한다.

그래서 variable size array는 i를 n으로 계산하기 위해서 shift나 add 명령어가 아니라 곱셈 명령어가 필요하다.

어떤 processor에서는 곱셈은 성능적으로 penalty가 있는데 이 경우에서는 피할 수 없다.

 

variable size array가 loop에서 참조될 때 컴파일러는 index 계산을 최적화 할 수 있다.

아래 예제는 이전과 비슷한 예제이다.

최적화한 코드를 보면 fixed size array일 때 와 조금 다른 최적화 한 것을 알 수 있다.

하지만 이것은 기본적인 요구사항 때문에 달라진 것이기 보다는 컴파일러에 의해 만들어진 선택적인 것이다.

여기서는 변수 j를 남겨 놓는다.

왜냐하면 loop가 언제 끝나는지 감지하기 위함과 A의 i행 element들 indexing하기 위함이다.

 

아래는 최적화한 함수의 assembly code이다.

보면 Bptr을 증가시키기 위해서 계산된 4n (r9 레지스터에 저장)과 n(rdi 레지스터에 저장) 이 2개 값을 사용해서 loop를체크하는 것을 볼 수 있다.

 

GCC는 최적화가 사용되었을 때 패턴을 인식한다.

이 패턴은 프로그램이 다차원 배열 요소를 사용할 때 발생하는 것이다.

그 다음 곱셈을 방지하는 코드를 생성할 수 있다.

어쨌든 이렇게 최적화된 코드를 생성하면 이것은 프로그램 성능을 크게 향상 시킨다.