C# 다차원 배열 순회 행 우선 순회와 열 우선 순회의 성능 차이

C# 다차원 배열 순회 행 우선 순회와 열 우선 순회의 성능 차이

예제 코드 소개

먼저, 예제 코드를 살펴보겠습니다. 이 코드는 10,000 x 10,000 크기의 2차원 배열을 두 가지 순서로 설정하면서 걸리는 시간을 측정합니다.

class Program
    {

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

            {
                long now = 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 - now}");
            }

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

결과 분석

위 코드를 실행하면 (y, x) 순서로 배열을 설정하는 것이 (x, y) 순서로 설정하는 것보다 더 빠르게 실행된다는 것을 알 수 있습니다. 그 이유를 이론적으로 살펴보겠습니다.

메모리 접근 패턴과 캐시의 역할

컴퓨터의 메모리는 계층적으로 구성되어 있습니다. CPU는 메모리 접근 시간을 줄이기 위해 캐시 메모리를 사용합니다. 캐시 메모리는 속도가 빠르지만, 용량이 제한적입니다. 프로그램이 메모리에 접근할 때, 캐시의 적중률(cache hit rate)이 높을수록 성능이 향상됩니다.

1. 행 우선 순회 (Row-major order)

C#에서 다차원 배열은 행 우선 순서로 메모리에 저장됩니다. 즉, 배열의 요소는 메모리에 행 단위로 연속적으로 저장됩니다. 예를 들어, int[,] arr = new int[3, 3]; 배열은 메모리에 다음과 같이 저장됩니다:

arr[0,0], arr[0,1], arr[0,2], arr[1,0], arr[1,1], arr[1,2], arr[2,0], arr[2,1], arr[2,2]

따라서, for (int y = 0; y < 10000; y++) for (int x = 0; x < 10000; x++) arr[y, x] = 1; 코드에서 메모리에 접근할 때, 인접한 메모리 주소에 순차적으로 접근하게 됩니다. 이는 캐시 적중률을 높여 성능을 향상시킵니다.

2. 열 우선 순회 (Column-major order)

반면, for (int y = 0; y < 10000; y++) for (int x = 0; x < 10000; x++) arr[x, y] = 0; 코드에서는 메모리에 접근할 때, 비연속적인 메모리 주소에 접근하게 됩니다. 이는 캐시 적중률을 낮추어 성능 저하를 초래합니다.

캐시 메모리 동작 이해

캐시는 메모리의 특정 부분을 블록 단위로 저장합니다. 행 우선 순회는 이 블록 단위 접근을 최대한 활용합니다. 예를 들어, 2차원 배열 arr의 첫 번째 행이 캐시로 로드되면, 행의 모든 요소를 캐시에서 빠르게 읽을 수 있습니다.

반면, 열 우선 순회는 각 열의 요소가 다른 메모리 블록에 분산되어 있어 캐시 미스(cache miss)가 자주 발생합니다. 이는 메모리 접근 시간이 길어지고 성능이 저하되는 원인이 됩니다.

지역성(Locality) 이론 적용

지역성(Locality)은 컴퓨터 프로그램이 메모리에 접근할 때, 일정한 패턴을 가진다는 개념입니다. 지역성은 크게 두 가지로 나뉩니다: 시간적 지역성(Temporal Locality)과 공간적 지역성(Spatial Locality).

시간적 지역성 (Temporal Locality)

시간적 지역성은 최근에 접근한 데이터에 곧 다시 접근할 가능성이 높다는 것을 의미합니다. 예를 들어, 루프 안에서 반복적으로 같은 변수를 사용하는 경우가 해당됩니다.

공간적 지역성 (Spatial Locality)

공간적 지역성은 근처에 있는 데이터가 함께 접근될 가능성이 높다는 것을 의미합니다. 예를 들어, 배열의 연속된 요소에 접근하는 경우가 해당됩니다.

지역성과 배열 순회

for (int y = 0; y < 10000; y++) for (int x = 0; x < 10000; x++) arr[y, x] = 1; 코드에서는 공간적 지역성을 최대한 활용합니다. 행 우선 순회는 배열의 요소들이 메모리에 연속적으로 저장되어 있어, 캐시 메모리에 한 번 로드되면 이후 연속된 접근이 빠르게 이루어집니다.

반면, for (int y = 0; y < 10000; y++) for (int x = 0; x < 10000; x++) arr[x, y] = 0; 코드에서는 공간적 지역성이 떨어집니다. 열 우선 순회는 배열의 요소들이 비연속적으로 저장되어 있어, 매번 새로운 메모리 블록을 로드해야 하므로 캐시 미스가 자주 발생합니다.

 

결론

이번 포스트에서는 C#에서 다차원 배열을 순회할 때, 행 우선 순회와 열 우선 순회의 성능 차이에 대해 알아보았습니다. 행 우선 순회는 캐시 메모리의 적중률을 높여 성능을 향상시킵니다. 반면, 열 우선 순회는 비연속적인 메모리 접근으로 인해 성능 저하를 초래할 수 있습니다. 이 이론을 바탕으로, 다차원 배열을 순회할 때는 행 우선 순회를 사용하는 것이 더 효율적이라는 결론을 내릴 수 있습니다.

추가적인 질문이나 궁금한 점이 있다면 언제든지 댓글로 남겨주세요!