[게임서버] Temporal locality, Spatial locality

C#으로 작성된 내용입니다.

using System;

namespace ServerStudy
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] arr = new int[10000, 10000];

            {
                long start = DateTime.Now.Ticks;
                for (int y = 0; y < 10000; y++)
                    for (int x = 0; x < 10000; x++)
                        arr[y, x] = 1;
                long end = DateTime.Now.Ticks;
                Console.WriteLine($"[y,x] 걸린 시간 : {end - start}");
            }

            {
                long start = DateTime.Now.Ticks;
                for (int y = 0; y < 10000; y++)
                    for (int x = 0; x < 10000; x++)
                        arr[x, y] = 1;
                long end = DateTime.Now.Ticks;
                Console.WriteLine($"[y,x] 걸린 시간 : {end - start}");
            }
        }
    }
}

10000 × 10000 배열이 있다. for문을 돌면서 모든 자리에 1을 넣는 반복문을 2번 실행한다. 하나의 반복문은 [y, x]의 순서로 1을 넣고 하나의 반복문은 [x, y]의 순서로 1을 넣는다. 실행시간에 차이가 있나 알아보자.

약 1.8배 정도의 시간 차가 생긴다. 비슷해보이는 두 반복문에 차이가 생기는 이유는 Spatial locality 때문이다. 

Spatial locality란 한 번 접근한 영역은 다음 번 접근에서도 빠르게 접근할 수 있는 컴퓨터의 특성이다.

위의 예시에서 배열을 도는 for문을 잠깐 살펴보자. y가 1 늘어날 때마다 x는 만 번 늘어나게 된다. [y, x]의 순서로 배열을 채워넣을 경우 배열이 원래 도는 순서 그대로 따라가며 배열을 채워넣기만 하면 된다. [x, y] 순서로 배열을 채워넣을 때는 그렇지 않다. y가 1 늘어나고 x가 만 번 도는 동안 채워치는 배열의 수는 단 하나다. 다시 y가 1 늘어나고 x가 만 번 도는 동안 또 하나의 배열만을 채운다. 이런 식으로 컴퓨터는 엄청난 손해를 보며 배열을 채우고 있는 셈이 된다. [y, x]가 더 빠르게 채워지는 이유를 간단하게 이해할 수 있다.

 

비슷한 특성으로 Temporal locality가 있다. Temporal locality란 최근 접근한 데이터는 다시 읽어올 때도 빠르게 접근할 수 있는 특성을 말한다.