[컴퓨터구조] 2-5. Data Structure

메모리에 각각의 자료구조가 어떻게 올라가는지 알아보자.

 

배열은 항상 메모리의 연속적인 공간에 할당된다. 메모리에서 데이터를 가져오는 시간이 CPU 연산 시간보다 길기 때문에 메인 메모리에 접근하는 시간은 전체 성능에 영향을 준다. 이때, 연속 공간에 배열을 할당하면 locality가 향상되어 메모리에서 데이터를 가져오는 시간을 줄일 수 있다. locality에 대해서는 이후 캐시 메모리에서 자세하게 배울 것이다.

 

 

 

그렇다면, 한 코드에서 여러 개 배열을 선언하면 어떻게 할당될까? 일반적으로 하나의 배열을 연속적인 공간에 할당되지만 서로 다른 배열은 연속적으로 할당되지 않는다. 즉, 처음 할당된 배열 다음에 항상 두번째 할당된 배열이 놓이지 않는다는 것이다.

 

아래처럼 배열을 선언한다고 했을 때, 각각 하나의 배열은 연속적인 공간에 할당되지만 배열과 배열은 연속적으로 할당되지 않을 수도 있다. 만약에 a[5] 값을 접근한다고 하면, 아래 그림에서는 9가 출력될 것이다. 왜냐하면 아래 그림에서는 각각의 배열이 연속적으로 할당되어 있어서 a의 주소를 넘어버려도 큰 문제는 없다. 그러나 아래와 같이 할당되지 않을 확률이 높기 때문에 일반적인 경우라면 쓰레기값이 출력될 것이다.

typedef int zip_dig[5];

zip_dig a = { 1, 5, 2, 1, 3 };
zip_dig b = { 9, 8, 1, 9, 5 };
zip_dig c = { 9, 4, 7, 2, 0 };

 

 

이제 2차원 배열(multi dimensional array)도 살펴보자. 기본적으로 메모리에서 모든 요소들은 행 우선 순서(Row-Major Ordering)이기 때문에 아래 그림처럼 배치된다. 그래서 정수형 A[i][j]이 선언되어있다고 할 때, A[R][C]에 접근하고 싶다면,  A +(i*C + j)*K가 메모리 주소가 된다.

zip_dig d[4] = 
	{{9, 8, 1, 9, 5},
    	{9, 8, 1, 0, 5},
    	{9, 8, 1, 0, 3},
    	{9, 8, 1, 1, 5}};

 

 

2차원 배열과 유사하게, Multi-level Array에 대해서도 알아보자. Multi level Array는 배열이긴 하나, 각 요소에 다른 배열의 시작주소를 담고 있다. 이 경우에는 multi dimensional array와 동일하게 다차원 배열이지만, 연속된 공간을 차지 하지 않아서 메모리가 부족한 상황에서 유용하다. 즉, 꼭 메모리의 연속된 공간에 넣지 않아도 되기 때문에 편리하지만, 그만큼 메모리 접근 횟수가 늘어나 성능을 저하시킬 수 있다.