[CSAPP] x86-64 - Data

1. C 언어 배열

1-1. 배열 할당 및 접근 (Array Allocation and Access)

T A[L];

자료형이 T인 데이터 L개로 이뤄진 배열 A를 선언하는 문장이다. 배열의 할당은 어셈블리어 수준에서 메모리에 L x sizeof(T) 바이트를 연속적으로 할당함으로써 구현된다. 그리고 배열 요소의 접근은 어셈블리어 수준에서 배열의 첫 번째 요소를 가리키는 포인터인 A에 특정 인덱스 값을 더한 주소에 접근하는 방식으로 구현된다. A는 배열의 첫 번째 요소를 가리키는 자료형이 T*인 포인터이다.

---

1-2. 예시 (Example)

다음 예시를 참고하여 배열의 할당, 요소의 접근이 어셈블리어 수준에서 어떻게 구현되는지 이해해 보자.

 

---

1-3. 다차원 배열 (Multi-dimensional (Nested) Array)

T A[R][C];

자료형이 T인 데이터 R*C개로 이뤄진 2차원 배열 A를 선언하는 문장이다. 자료형이 T인 데이터의 크기를 K라고 할 때, 2차원 배열의 총크기는 R*C*K 바이트가 된다. 2차원 배열의 논리적 구조는 다음 그림에서 보이듯이 R개의 행과 C개의 열로 이뤄져 있다. 그러나 실제로는 메모리 상에는 각 요소가 가로 방향으로 연속적으로 할당되어 있다. 이러한 할당 방식을 "Row Major Ordering"이라고 한다. 

 

 

다음 예를 살펴보자. 참고로 여기서 "zip_dig pgh[4]"는 "int pgh[4][5]"와 동일한 의미이다. pgh 자체는 4개의 요소로 이뤄진 배열이며, 각 요소는 다시 5개의 int 형 요소로 이뤄진 배열에 해당한다.

 

 

① 행 접근 : A + i * (C * K) → i번째 행에 해당하는 배열의 첫 번째 요소를 가리키는 포인터

 

② 요소 접근 : A + i * (C * K) + j * K = A + K * (i * C + j) → A[i][j] 요소를 가리키는 포인터

---

1-4. 멀티-레벨 배열 (Multi-level Array)

멀티-레벨 배열(Multi-level Array)은 각 요소가 특정 배열을 가리키는 포인터인 배열을 의미한다. 다차원 배열과의 차이점은 크게 두 가지이다. 첫 번째 차이점은 각 요소에 해당하는 배열들이 메모리 상에서 순차적으로 할당된다는 보장이 없다는 것이다. 다음 예를 참고하자.

 

 

그리고 두 번째 차이점은 univ[i][j]에 접근할 때 메모리 접근이 두 번 필요하다는 것이다. 먼저 univ[i]에 저장되어 있는 포인터를 읽고 나서, 그것에 인덱스 값을 더하여 얻은 주소로 다시 접근해서 값을 가져와야 하기 때문이다. 다음 그림을 참고하자.

 

---

1-5. 다차원 배열 vs 멀티-레벨 배열

다음은 다차원 배열과 멀티-레벨 배열에서 요소에 접근하기 위한 코드를 각각 보여준다. 다차원 배열과 멀티-레벨은 그다음 그림에서 보여주듯이 근본적으로 그 할당 구조가 다르기 때문에 요소에 접근하기 위한 기계어 코드도 달라질 수밖에 없다는 것을 기억하자.

 

---

1-6. N X N 행렬 구현 방식

위에서 설명한 내용을 기반으로, 수학에서 다루는 N X N 정방 행렬(Square Matrix)을 구현하는 방법을 정리하면 다음과 같이 크게 세 가지이다. 첫 번째는 고정 차원(Fixed Dimension), 두 번째는 가변 차원 및 명시적 인덱싱(Variable Dimension and Explicit Indexing), 마지막 세 번째는 가변 차원 및 암묵적 인덱싱(Variable Dimension and Implicit Indexing)이다.

 

 

1-6-1. 고정 차원 (Fixed Dimension)

행렬의 가로 세로 길이에 해당하는 N을 컴파일 타임에 알고 있는 경우이다. 행렬이 다차원 배열로 구현된 경우 요소의 접근은 "A + i * (C * K) + j * K" 방식으로 구현되는데, 이때 C에 해당하는 N을 이미 알고 있기 때문에 컴파일러가 올바르게 번역을 수행할 수 있다. 다음 그림에서 요소 접근이 어셈블리어 수준에서 어떻게 구현되는지 살펴보자.

 

 

1-6-2. 가변 차원 (Variable Dimension)

N을 컴파일 타임에 알 수 없는(= 실제로 실행을 해봐야 알 수 있는) 행렬을 동적 배열로 구현하는 방식이다. 그중 명시적 인덱싱은 현대에는 거의 사용되지 않는 전통적인 방식이다. 반면에 암묵적 인덱싱은 최근 gcc에 의해 채택되어 사용되는 다소 현대적인 방식이다. 이 경우에도 마찬가지로 행렬이 다차원 배열로 구현된 경우 요소의 접근은 "A + i * (C * K) + j * K" 방식으로 구현되는데, 이때 인자로 전달받은 N의 값을 C 자리에 넣어주는 방식을 통해 컴파일러가 올바르게 번역을 수행할 수 있다. 즉, 가변 차원 방식으로 구현하려면 N의 값을 반드시 인자로 전달해줘야 한다. (참고로 이러한 가변 크기 배열은 C99부터 지원된다.)

 

 

2. C 언어 구조체

2-1. 구조체 (Structure)

구조체(Structure)도 배열과 마찬가지로 요소들이 메모리 공간에 연속적으로 할당되며(다만 정렬 원칙을 따르기 위해 요소들 사이에 빈 공간이 삽입될 수는 있음), 할당이 되는 순서는 구조체 내에서 선언되는 순서를 그대로 따른다. 컴파일러는 해당 구조체의 전체 크기와 내부 요소들 각각의 위치 정보(오프셋)를 파악한 뒤 이를 바탕으로 구조체를 할당하고 접근하는 기계어 코드를 만들어 낸다. 따라서 기계어 수준의 프로그램은 구조체라는 것의 존재를 특별히 알지 못한다. 그저 메모리 상에 데이터들을 연속적으로 할당하고 그것에 접근할 뿐이다.

 

---

2-2. 구조체 접근 (Structure Access)

결국, 구조체도 배열과 마찬가지로 구조체의 시작 주소에 해당 요소의 오프셋을 더함으로써 접근하고자 하는 요소의 주소를 계산한다. 앞서 말했듯 구조체 요소의 접근을 위한 오프셋 정보들은 컴파일러 타임에 컴파일러에 의해 파악(결정)된다. 다음은 위에서 예시로 보여줬던 구조체 내에 선언된 배열 a에 대하여 a[idx] 요소의 주소를 반환하는 함수의 코드를 나타낸다.

 

 

다음은 구조체로 이뤄진 연결 리스트가 있을 때, 각 구조체 내에 존재하는 배열 a와 정수 i에 대하여 a[i]의 값을 val의 값으로 바꾸는 코드를 나타낸다.. 참고로 movslq는 4바이트의 데이터를 Sign Extension 한 뒤 8바이트 공간에 이동시키는 명령어이다. 앞서 살펴본 movzbl와 유사한 성격의 명령어이다. 다음 코드를 통해 구조체 접근이 어떻게 구현되는지 확실하게 이해하고 넘어가도록 하자.

 

---

2-3. 정렬 원칙 (Alignment Principle)

앞서 잠깐 언급했지만, 사실 구조체 내 요소들은 완전히 연속적으로 할당되지는 않고 그 사이사이에 빈 공간이 존재한다. 왜 그럴까? 이는 성능 향상을 위한 정렬 원칙(Alignment Principle)을 준수하기 위해서이다. 정렬이 무엇인가를 이해하기 위해 간단한 예시를 살펴보자. 다음의 첫 번째 그림은 요소들이 정렬되지 않은 구조체, 두 번째 그림은 요소들이 정렬된 구조체이다.

 

 

2-3-1. 구조체 내 각 요소들의 정렬 원칙

K 바이트 크기의 자료형이라면 시작 주소도 K 바이트여야 한다. 예를 들어, x86-64 기준으로 double, long 데이터 혹은 포인터는 8바이트 데이터이므로 그 데이터의 시작 주소도 8의 배수여야 한다. 참고로 2^n의 배수임을 판별하는 방법은 하위 비트에 0이 n개 있는지 확인하는 것이다.

 

2-3-2. 구초제 전체의 정렬 원칙

구조체 내 요소 중 가장 큰 데이터의 크기가 K 바이트라 할 때, 해당 구조체의 시작 주소와 길이는 K의 배수여야 한다.

 

그러면 이와 같은 정렬은 왜 필요한 것일까? 메모리에 접근할 때 실제로 가져오는 것은 메모리 상에 연속적으로 할당되어 있는 4바이트 혹은 8바이트 단위의 청크인데, 하나의 데이터가 여러 청크에 걸쳐 있으면 메모리 접근의 효율이 상당히 떨어진다. 또한 가상 메모리 기술에서도 하나의 데이터가 여러 페이지(Page)에 걸쳐 있으면 성능이 저하된다. 이러한 이유로 특정 시스템에서는 구조체의 정렬 원칙을 권장하고 있다. 물론 그렇지 않은 시스템의 경우에는 정렬 원칙을 지킬 필요가 없다. 참고로 x86-64의 경우 구조체의 정렬 원칙을 지킬 것을 권장하고 있다. 구조체의 정렬 원칙이 권장되는 시스템에서는 컴파일러의 기본 옵션으로 구조체 정렬이 설정되어 있다. 이러한 경우 컴파일러는 구조체 내 요소들과 구조체 전체의 정렬을 보장하기 위해서 구조체 내 요소들 사이사이에 적절히 갭을 삽입하게 된다.

 

다음 그림들을 보며 구조체 정렬이 어떻게 이뤄지는지 직접 한 번 살펴보자.

 

 

다음은 조금 더 심화된 예시로, S3 구조체로 이뤄진 배열 a에 대하여 a[idx]의 멤버 j에 접근하는 코드를 나타낸다. 참고로 빨간색으로 표시된 a+8은 컴파일 타임에 결정할 수 없는 값에 해당하며, 나중에 링커에 의해 링킹이 진행될 때 올바른 값으로 채워진다.

 

 

지금까지 이야기한 구조체의 정렬 원칙에 따르면, 구조체 내 요소들을 크기가 큰 것부터 선언해야 공간을 가장 효율적으로 쓸 수 있다는 결론에 도달한다. 다음 그림을 보며 이 점을 이해해 보기 바란다.