Chapter 8 : Machine-Level Programming 4 (Data)

Array Allocation

T A[L] 이라고 하면 T는 데이터 type이고 L은 배열의 길이입니다.

메모리에 L * sizeof(T) byte를 연속적으로 할당함으로써 구현됩니다.

배열의 index의 접근은 배열의 첫번째 요소를 가리키는 포인터인 A의 특정 index 값을 더한 주소에 접근하는

방식으로 구현됩니다. A는 배열의 첫번째 요소를 가리키는 자료형이 T*인 포인터입니다.

 

Array Access

 

EX)

Allocate (할당)

다음 예시는 배열들이 연속적인 20 byte 씩 할당 받았습니다.

 

Access (접근)

z[digit]의 값을 얻는 함수입니다.

레지스터 %rdi에는 배열의 시작 주소가 들어갑니다.

레지스터 %rsi에는 배열의 index가 들어갑니다.

우리가 원하는 주소값은 %rdi + 4 * %rsi 입니다.

 

Loop

i값은 %rax(=%eax)에 들어갑니다.

 

Multidimensional (Nested) Arrays (다차원 배열)

T A[R][C] 

자료형 T의 크기를 K라고 하면 위의 2차원 배열의 총 크기는 R * C * K가 됩니다.

2차원 배열은 R개의 행과 C개의 열로 이루어져 있습니다. 그러나 실제로은 가로방향으로 연속적으로

할당되어 있습니다. 이러한 할당 방식을 "Row Major Ordering"이라고 합니다.

ex)

zig_dig pgh[4] = int pgh[4][5] 입니다.

pgh 자체는 4개의 요소로 이루어진 배열이며, 각 요소는 다시 5개의 int형 요소로 이루어진 배열입니다.

 

1) Nested Array Row Access (행 접근)

int A[R][C];

A[i]의 시작 주소는 다음과 같이 나타낼 수 있습니다.

A + i * (C * sizeof(Data type))

pgh[index]는 index * 5의 공간이 필요합니다.

pgh[index]의 시작주소는 pgh + 20 * index 입니다.

 

2) Nested Array Element Access (요소 접근)

int A[R][C];

A[i][j]의 주소는 다음과 같이 나타낼 수 있습니다. 

A + i * (C * sizeof(Data type)) + j * sizeof(Data type) = A + sizeof(Data type) * (i * C + j)

먼저 pgh[index]의 공간을 할당 합니다. (5 * index)

pgh[index][dig]의 주소는 pgh + 20 * index + 4 * dig = pgh + 4 *(5 * index + dig)

 

Multi-Level Array

Multi-Level Array는 각 요소가 특정 배열을 가리키는 포인터인 배열을 의미합니다.

다차원 배열과의 차이점은 각 요소에 해당하는 배열들이 메모리 상에서 순차적으로 할당된다는 보장이 없습니다.

변수 univ는 3개의 요소를 가리킵니다.

각 요소는 8 byte인 포인터입니다. 

각 포인터는 int형 배열을 가리킵니다.

또 다차원 배열과 차이점은 univ[i][j]에 접근할 때 메모리 접근이 두 번 필요하다는 것입니다. 

먼저 univ[i]에 저장되어 있는 포인터를 읽고 나서, 그것에 인덱스 값을 더하여 얻은 주소로 다시 접근해

값을 가져와야 하기 때문입니다. 

Mem[Mem[univ + 8 * index] + 4 * digit]

 

Array Element Accesses (다차원 배열 vs multi-level 배열)

위의 그림은 다차원 배열과 multi-level 배열에서 요소에 접근하기 위한 코드를 각각 보여줍니다.

그림에서 볼 수 있듯이 할당 구조가 서로 다르기 때문에 요소에 접근하기 위한 machine code 또한 

달라질 수 밖에 없습니다.

다차원 배열 : Mem[pgh + 20 * index + 4 * digit]

muti-level : Mem[Mem[univ + 8 * index] + 4 * digit]

 

N X N Matrix Code

n x n 행렬(square matrix)을 구현하는 방법을 정리하면 다음과 같이 3가지 입니다.

1) Fixed Dimensions (고정 차원)

2) Variable dimensions, explicit Indexting (가변차원, 명시적 인덱싱)

3) Variable dimensions, implicit Indexing (가변차원, 암묵적 인덱싱)

 

ex) 16 x 16 matrix access

1) Fixed Dimension

int A[R][C] = A[16][16]

A[i][j]의 주소값 = A + i * (C * K) + j * K

행렬의 가로 세로 길이에 해당하는 N을 compile time에 알고 있는 경우 입니다. 행렬의 다차원 배열로 구현된

경우 요소의 접근은 A + i * (C * K) + j * K 방식으로 구현되는데, 이 때 C에 해당하는 N을 이미 알고 있기 때문에

컴파일러가 올바르게 번역을 수행할 수 있습니다.

2) Variable Dimension

N을 compile time에 알 수 없는(= 실제로 실행을 해봐야 알 수 있는) 행렬을 동적 배열로 구현하는 방식입니다. 

그중 명시적 인덱싱은 현대에서는 거의 사용하지 않는 방식입니다. 

반면에 암묵적 인덱싱은 최근에 gcc에 의해 채택되어 사용되는 현대적인 방식입니다.

마찬가지로 행렬이 다차원 배열로 구현된 경우 요소의 접근은  A + i * (C * K) + j * K 방식으로 구현됩니다.

이 때 인자로 전달받은 N의 값을 C자리에 넣어주는 방식을 통해 컴파일러가 올바르게 번역을 수행할 수 있습니다.

즉, Vriable demension 방식으로 구현하려면 N의 값을 반드시 인자로 전달해줘야 합니다.