[4기 강북 이동욱] 게임을 만들기 전에 #3 - 게임에서의 배열

안녕하세요. 강북 멤버십 21기 이동욱 입니다.

  오늘은 앞의 이야기에 이어서 게임을 만들기 전에 알고 있으면 좋은 몇가지 부분에 대해서 이야기를 해보도록 하겠습니다.

  이 포스팅에 앞서서 게임을 개발할 때 많이 신경 쓰게 되는 부분이 메모리와 속도라고 앞에서 언급한 적이 있을텐데요. 그 중에서 자료구조를 사용하면서 알고 있으면 성능 향상에 약간이나마 도움이 될법한 부분에 대해서 이야기를 해보도록 하겠습니다. 

  배열은 가장 기본적이면서 가장 많이 사용되는 자료구조 입니다.  특히 배열을 사용함에 있어서, 이론적인 속도에 대한 부분에 대해서 알아두면 좋은 내용에 대하여 이야기 해보도록 하겠습니다.

 

우선 간단하게 배열에 대해서 살펴보고 갈까요?

가장 기본적인 자료구조이다 보니 배열을 모르시는 분은 없으시리라고 생각합니다. 그 정도로 기본적이면서도 가장 많이 사용하는 자료구조가 배열이기 때문입니다.

---

배열

  배열은 가장 일반적인 이며, 가장 기본적인 자료구조입니다.

  배열은 여러개의 상자가 일렬로 나열되어 있는 형태로 구성되어 있습니다.

---

  배열을 많이 사용하는 이유는 여러 이유가 있지만 몇가지 꼽아보자면 관리하기가 쉽고, 접근이 빠르며 필요할 때에 쉽게 생성하고 제거할 수 있기 때문입니다. 배열은 이러한 장점으로 인하여 많이 사용 되며 배열을 사용하지 않는 프로그램이 없을 정도라고 생각해도 무리가 없을 정도 입니다. 그러나 배열이 많이 사용된다고 해서 모든 곳에 사용되는 자료구조는 아닙니다. 그것은 배열이 가지고 있는 몇가지 단점때문 이라고 볼 수 있습니다.(이러한 단점은 다른 자료구조를 사용하여 해결 할 수 있습니다.)

항목의 삽입, 제거

  배열의 단점 중 하나는 배열 항목들의 순서를 유지하면서 항목을 삽입하거나 제거하는 것이 어렵다는 점입니다. 순서를 유지할 필요가 없다면, 크게 문제가 되지 않겠지만, 특정 순서를 유지하면서 삽입이나 제거를 수행하기 위해서는 배열에 들어 있는 모든 요소들을 순서대로 이동시켜야 하는데 이러한 알고리즘 복잡도는 O(n)이므로 배열의 크기가 크면 클수록 수행 시간이 늘어나게 됩니다.

배열의 크기 변경

  또 다른 문제점 중 하나는  배열의 크기가 유연하지 않다는 점입니다. 예를들어 크기가 100인 배열이 있다고 가정하겠습니다. 그런데 이 배열의 100칸이 전부 사용되어 더 큰 크기의 배열이 필요하게 되면 현재 배열인 100의 배열은 유지한 채로 추가적으로 200의 크기를 가지는 배열을 생성 한후 각 요소의 정보를 옮겨 담게 됩니다.

  결국 자료가 많으면 많을수록 배열의 크기를 변경하는데 필요한 메모리의 소비도 추가적으로 발생하며 그 만큼의 시간 소비가 일어나게 됩니다. 또한 이론상으로는 배열의 크기 변경은 O(n)의 알고리즘 복잡도를 가지지만, 이론적인 알고리즘 복잡도에서 무시하는 부분(상수 영역)인 메모리의 할당과 메모리의 해제의 시간 또한 무시할 수 없는 부분 이기 때문에, 메모리 확보와 제거를 자주 하게 되면, 게임의 속도에 상당히 부정적인 요인으로 작용하게 됩니다.

캐시 와 메모리 계층

  보통 배열의 장점(특히 Linked list와 비교했을 때)중 하나는 배열의 요소에 임의 접근 할 수 있다는 것입니다. 대부분의 경우에 배열은 임의 접근이 가능하다는 것을 장점으로 알고 있지만, 실제로 컴퓨터가 수행하는 동작은 우리가 생각하는 것처럼 완벽한 임의 접근 이라고 할 수는 없습니다. 그것은 컴퓨터의 동작 방식 때문이라고 할 수 있습니다. 컴퓨터의 연산은 CPU에 의해 처리되고 실제로 연산이 이루어지기 위해서는 레지스터(register)라는 곳에 값이 들어가야 합니다.

  레지스터는 컴퓨터에서 가장 빠른 메모리 입니다. 그런데 이 레지스터 라는 것이 가격상의 문제와 기억계층 상의 이유로 많이 존재하지 않습니다. (x86 아키텍처에 있는 레지스터는 총 16개 입니다) 그러니 결국 CPU가 직접 처리할 수 있는 자료의 양은 제한 적이라고 할 수 있습니다. 

  

  그런데 여러분, 여러분이 만약 게임상에서 아주 강력한 아이템을 구입했다고 가정해 보겠습니다. 비싼만큼 아주 강력하거나 혹은 아주 멋있는 이 아이템을 사용하지 않고 창고에 박아두시는 분은 없으리라 생각합니다. 비싼 아이템을 구매한 후 사용하지 않는 것은 매우 아까운 일이니까요.

  이와 마찬가지로 컴퓨터도 비싸지만 강력한 성능을 가진 레지스터를 사용하지 않는 것은 매우 아까운 상황이기 때문에 사용성을 극으로 올리기 위해서 레지스터보다 용량이 좀더 크면서 속도도 상당히 빠른 메모리 영역을 추가적으로 가지고 있습니다. 그런 메모리를 레벨1 캐시(L1 캐시) 라고 부릅니다.  

메모리 계층

  캐시가 있는 이유는 여러가지가 있지만, 그 중에서 우리가 주의깊게 보아야 하는 점은 위에서 언급한 것처럼 속도의 성능을 위로 끌어 올리기 위해 존재한다는 점입니다.

  컴퓨터의 연산은 결국에는 메모리 값의 변화라고 볼 수 있습니다. 어떠한 연산을 하기위해 정보를 디스크에서 꺼내어 메모리에 올린 후 어떠한 연산 작용을 거쳐 값이 변화했다면 그 값을 디스크에 다시 저장하는 것입니다. 

  그런데 위에서 보이는 것처럼 디스크로 갈수록 속도가 매우 느리고 위로 올라갈수록 속도가 매우 빠릅니다. 그래서 결국에 CPU의 연산 능력은 매우 강력하지만 디스크의 속도 때문에, 전체적인 속도가 저하되게 됩니다. 연산은 다 끝났는데, 디스크에서 정보를 불러오거나 저장하는데 너무 많은 시간을 할애하게 되기 때문입니다.

  그래서 메모리는 컴퓨터에서 매우 중요한 역할을 맡고 있는데, 그 역할이란 레지스터와 디스크의 연산속도의 차이를 줄여 성능을 끌어 올리면서도 컴퓨터의 전체적인 가격을 내리는 절충적인 역할을 맡고 있는 것입니다.

  

  그런데 이런 특징이 배열과 어떤 관련이 있을까요?

  메모리는 한 수준에서 다른 수준으로 이동될 때 (L1에서 레지스터로 이동하는 것은 예외) 항상 큰 덩어리 단위로 이동을 합니다. 그 이유는 큰 단위로 이동하는 것이 훨씬 효율적이기 때문입니다.

  그렇다면 배열의 요소 접근, 그러니까 우리가 알고 있는 배열의 장점인 임의접근을 하게 되는 경우에는 어떻게 동작하게 될까요?

  만약 우리가 배열의 한 요소에 접근(순차 접근이 아닌 임의접근) 을 하게 될 경우 우리가 접근하고자 하는 그 요소 뿐만 아니라 그 항목을 포함하고 있는 주변의 많은 값들이 큰 덩어리로 L1 캐시에 올라가게 됩니다.

예를 들어보겠습니다.

  인덱스가 5개인 캐시를 가진 시스템에서 인덱스값이 10개인 배열에 접근한다고 가정합니다. 배열의 첫번째 요소에 접근을 하게 되면 캐시의 크기는 5이므로 첫번째 요소만 캐시에 올라가는 것이 아니라  0~4의 값이 캐시에 올라가게 됩니다. 이 상황에서 0~4의 요소 접근은 매우 빠르게 이루어지게 됩니다. 

  그런데 만약 이 때, 배열의 마지막 요소에 접근을 하게 된다고 가정하겠습니다. 마지막 요소의 값은 캐시에 올라와 있지 않으므로 캐시로 불러와야 합니다. 그런데 이미 캐시에는 0~4의 값이 들어 있기 때문에 이 정보들을 메모리로 다시 옮긴 뒤, 다시 배열의 뒤쪽 5~9값을 캐시로 읽어오게 됩니다.

1. 첫번째 요소에 접근 하는 경우

  첫번째 요소에 접근하게 되면, 캐시에 앞 배열의 0~4의 값이 올라가게 됩니다. 이부분은 캐시에 올라가 있기 때문에, 빠른 접근이 가능하게 됩니다.

2. 마지막 요소에 접근 하는 경우

  만약 위의 1번 상황에 바로 이어서 배열의 장점으로 꼽히는 임의접근을 가장 마지막 요소에 시도하는 경우 입니다. 이 경우에 캐시에 들어있는 값들을 저장한 후에 다시 배열 뒤쪽의 값을 캐시에 올리게 됩니다. 실제로는 배열의 요소 하나 하나에 접근을 시도한 것이지만, 이 한 동작으로 인하여 상당히 많은 일련의 과정을 거치게 됩니다. 이는 배열의 "임의 접근" 이라는 이론적인 장점 에 비한다면 매우 느린 과정입니다.

  배열을 사용하다가 임의 접근을 해야 하는 경우에 위와 같은 상황의 간단한 몇 부분의 임의 접근이 실제로는 메모리의 대부분을 이리저리 이동시켜야만 하는 상당히 부하가 걸리는 작업이라는 것을 기억해 두시면 많은 도움이 되시리라고 생각 합니다.

---

References and Notes

1. Ron Penton “DATA STRUCTURES FOR GAME PROGRAMMERS” (2004)

2. 김민장 “프로그래머가 몰랐던 멀티코어 CPU 이야기” (2010)