2차원 배열 탐색과 캐시 미스 (Cache Misses in 2D Arrays)

삼성 C형 전체 링크

 

참고

- Visual Studio 실행 시간 확인 방법

 

1차원 배열은 연속된 메모리의 집합이다.

2차원 배열은 [row][col]로 접근하지만, 1차원 배열과 마찬가지로 연속된 메모리의 집합이다.

 

Cache Friendly Code

- 특정 데이터를 참조할 때, 그 데이터 주위의 데이터도 함께 캐시에 로드되는 특성. (Locality)

- 연속적인 메모리 주소에 있는 데이터는 캐시에 함께 로드될 가능성이 높음.

 

즉, 2차원 배열(arr[r][c])을 접근할 때, r이 증가하는 방향보다, c가 증가하는 방향으로 먼저 탐색하는 것이 더 빠르다.

 

임의의 2차원 배열을 만들어서 주소를 출력해보자.

#include <stdio.h>

int main()
{
	char arr[5][5];

	for (int r = 0; r < 5; r++) 
	{
		for (int c = 0; c < 5; c++)
			printf("%x ", &arr[r][c]);
		putchar('\n');
	}

	return 0;
}

 

char 타입 배열이므로, col이 커질수록 메모리의 주소가 1 단위로 증가하는 것을 알 수 있다.

row가 증가하는 방향은 메모리가 5 단위로 증가한다.

 

캐시 미스(Cache Miss)는 데이터가 캐시에 없어서 메인 메모리에서 데이터를 가져와야할 때 발생한다.

즉, 연속된 메모리는 쉽게 접근하지만, 비연속적인 메모리는 캐시 미스가 발생하여 속도가 느려진다.

 

→ Cache Friendly Code에 따라 연속된 메모리로 접근하는 코드가 더 성능이 좋다.

---

2차원 배열 탐색 속도 비교

 

2차원 배열 myMap이 있다고 가정하자.

#define MAX (10000)

char myMap[MAX][MAX];

 

그리고 2개의 함수가 있다.

search1은 row을 기준으로 column을 탐색하고, search2는 column을 기준으로 row를 탐색한다.

여기서는 단순히 배열의 값을 sum에 모두 더하기만 한다.

void search1(char map[MAX][MAX])
{
	int sum = 0;
	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			sum += map[r][c];
}

void search2(char map[MAX][MAX])
{
	int sum = 0;
	for (int c = 0; c < MAX; c++)
		for (int r = 0; r < MAX; r++)
			sum += map[r][c];
}

 

탐색 방향만 다를 뿐 두 함수의 결과는 같다.

하지만 함수의 실행속도는 search1이 훨씬 더 빠르다.

아래 코드를 실행해보자.

#include <stdio.h>
#include <time.h>

#define MAX (10000)

char myMap[MAX][MAX];

void search1(char map[MAX][MAX])
{
	int sum = 0;
	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			sum += map[r][c];
}

void search2(char map[MAX][MAX])
{
	int sum = 0;
	for (int c = 0; c < MAX; c++)
		for (int r = 0; r < MAX; r++)
			sum += map[r][c];
}

int main()
{
	int TESTCASE = 10;

	{
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			search1(myMap);
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("\nSEARCH 1 TIME : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	{
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			search2(myMap);
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("SEARCH 2 TIME : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	return 0;
}

 

search2는 비연속적인 메모리에 접근하기 때문에 연속된 메모리에 접근하는 search1보다 2배 이상 시간이 소모된다.

 

이런 경우, map을 transpose하고 함수를 사용하는 것이 효율적이다.

void transpose(char map[MAX][MAX])
{
	for (int r = 0; r < MAX; r++)
	{
		for (int c = 0; c < r; c++)
		{
			int t = map[r][c];
			map[r][c] = map[c][r];
			map[c][r] = t;
		}
	}
}

 

배열을 transpose하고 search1을 사용하면 search2의 순서대로 배열에 접근하게 된다.

transpose + search1 테스트케이스를 추가한 코드를 실행해보자.

#include <stdio.h>
#include <time.h>

#define MAX (10000)

char myMap[MAX][MAX];

void search1(char map[MAX][MAX])
{
	int sum = 0;
	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			sum += map[r][c];
}

void search2(char map[MAX][MAX])
{
	int sum = 0;
	for (int c = 0; c < MAX; c++)
		for (int r = 0; r < MAX; r++)
			sum += map[r][c];
}

void transpose(char map[MAX][MAX])
{
	for (int r = 0; r < MAX; r++)
	{
		for (int c = 0; c < r; c++)
		{
			int t = map[r][c];
			map[r][c] = map[c][r];
			map[c][r] = t;
		}
	}
}

int main()
{
	int TESTCASE = 10;

	{
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			search1(myMap);
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("\nSEARCH 1 TIME : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	{ 
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			search2(myMap);
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("SEARCH 2 TIME : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	{ // transpose + search1
		int TIME = 0;

		/* Timer on */
		clock_t start = clock();

		/* 실행 코드 */
		transpose(myMap);
		for (int tc = 1; tc <= TESTCASE; tc++)
		{
			search1(myMap);
		}

		/* Timer off */
		TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);

		printf("SEARCH Transpos + 1 TIME : %d ms\n", TIME); /* ms 단위로 출력 */
	}

	return 0;
}

 

transpose 비용이 발생하지만, 훨씬 더 효율적으로 2차원 배열을 순회하였다.

 

예시 함수는 단순히 sum에 배열의 값을 더하는 것이므로, 어떤 방향으로 탐색해도 결과가 같았다.

만약, 2차원 배열을 반드시 row 방향으로 탐색해야 한다면, transpose로 배열을 바꾸는 것이 더 효율적일 수 있다.