메모리 정렬과 캐싱

메모리 정렬

메모리를 배수 단위로 맞추어서 선언하는 것을 말한다. 가상주소와 물리주소가 어떻게 매핑이 되어있는지는 잘 모르지만, 보통 우리의 컴퓨터는 64bit이기 때문에 8byte 씩 메모리를 읽는다.
(확실하지는 않지만 SSE,AVX 명령어에서는 16,32byte 씩 읽는 듯)

이때문에 메모리 정렬이 안되있으면 아래와 같은 문제가 일어난다. 다음과 같은 구조체가 있다고 해보자.

이는 메모리상에서 아래와 같은 가지게 된다. 우리가 이 구조체에서 b를 읽고 싶으면 바로 b에 접근하는것이 아니라 8byte를 읽어서 shift 연산등의 비트연산을 통해서 a의 값과 b 뒤에 있는 값들을 제거해주는 연산이 필요해지게 되고, 속도저하가 일어날 수 있다.

따라서 보통 우리가 구조체를 선언하면 컴파일러는 적절하게 메모리 정렬을 한다.
SIMD에서 정렬이 필요한 이유가 이 때문이다. 속도를 위해서 메모리 정렬이 필요한 명령어들은 추가적인 비트연산을 하는 과정이 생략되있고, 만약 정렬되있지 않다면 연산과정에서 오류가 난다고 생각된다.

캐시와 메모리 정렬

아래 코드를 보자. int 형의 2048x2048 크기의 배열을 생성해서 인덱싱을 하는 기본적인 코드이다. 과연 속도차이가 날까?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
	clock_t start;
	int** arr = (int**)malloc(sizeof(int*) * 2048);
	for(int j=0;j<2048;j++)
	{
		arr[j]=(int*)malloc(sizeof(int)*2048);
		for(int i=0;i<2048;i++)
			arr[j][i]=i;
	}
	// Loop 1
	start = clock();
	for(int i=0;i<2048;i++)
	{
		for(int j=0;j<2048;j++)
			arr[i][j]*=i*j;
	}
	clock_t end = clock();
	printf("index [i][j]:%.3fs\n", (float)(end - start)/CLOCKS_PER_SEC);
	// Loop 2
	start = clock();
	for(int i=0;i<2048;i++)
	{
		for(int j=0;j<2048;j++)
			arr[j][i]*=i*j;
	}
	end = clock();
	printf("index [j][i]:%.3fs\n", (float)(end - start)/CLOCKS_PER_SEC);
}

결과

거의 3배 가까운 시간의 차이가 난다! 대체 어떻게 이런 결과가 나온걸까? 이를 이해하기 위해서는 2차원배열이 메모리에서 어떻게 할당되는지와, 캐시에 대한 이해가 필요하다.

일단 먼저 2차원 배열은 동적할당을 했기 때문에 아래와 같이 할당 된다.

( 이미지 출처 : https://cxcore.tistory.com/24 )

즉 연속성이 보장되는 것은 arr[i][j++] 를 통해서 접근할 때 메모리를 순차적으로 탐색한다고 할 수 있다. 만약 i 값이 커지거나 작아지면 메모리의 연속성은 보장될 수 없다.

그리고 우리의 cpu에는 캐시메모리가 있다. 이 캐시메모리는 보통 최근에 접근한 메모리 근처에 다시 접근할 것이라고 생각을 해서 메모리에서 캐시메모리로 데이터들을 로딩한다. (자세한 과정은 공부를 안해서 잘 모른다. 일단 캐시 자체가 외부에서 보는 것이 불가능하다. 추측할 수는 있어도..) 캐시 메모리로 로딩하는 크기는 캐시라인의 크기만큼 가지고 오고, 이 크기는 cpuid 를 통해서 확인 할 수 있는데 보통 64byte이다.

for(int i=0;i<2048;i++)
{
	for(int j=0;j<2048;j++)
		arr[i][j]*=i*j;
}

따라서 위 코드에서는 처음에 캐시로 arr[0][0]~arr[0][15] 까지의 값을 가지고 와서 연산을 수행하고 arr[0][16]부터는 캐시미스(캐시에서 값을 찾지 못함)가 나서 다시 캐시로 로딩을 해주고 위의 과정을 반복한다. 캐시가 잘 이용된 예라고 할 수 있다. 그러나 2번째 for문의 경우 문제가 발생한다.

for(int i=0;i<2048;i++)
{
	for(int j=0;j<2048;j++)
		arr[j][i]*=i*j;
}

arr[0][0] 에 접근하면 캐시로 arr[0][0]~arr[0][15] 까지의 데이터를 적재할텐데, 다음에 접근은 arr[1][0]이다. 캐시미스가 나고, 따라서 다시 캐시에 로딩을 해준다. 그러나 캐시적중은 아마도 거의 없을 것이다. 따라서 적중하지도 못할 데이터를 캐시에 올리는데에서 시간이 너무 들어가는 것 때문에 차이가 이렇게 많이 난 것이다.

위와 같은 사례로 보면, 캐시라인 크기인 64byte로 메모리를 정렬해서 이용하는 것이 효율적이라고 생각된다. 메모리 정렬이 안되있는 상태에서는 캐시미스가 나기 쉽고 캐시미스가 나면 안쓰는 것만 못하기 때문이다.

메모리 거짓 공유

멀티스레드 환경에서 위 문제가 발전하면 메모리 거짓 공유라는 상황이 발생한다. 캐시는 일관성을 보장해야 하기 때문에, A라는 스레드가 있고 B라는 스레드가 있다고 가정할 때, 서로 동일한 캐시가 사용되면 A,B는 서로의 상황을 알 수 없기 때문에 캐시를 계속 업데이트 하고 이 과정에서 엄청난 리소스를 잡아먹게된다. 쉽게 말하면 캐시가 lock 걸린다고 생각하면 된다. 아래 코드에서는 인접한 배열인 arr1과 arr2가 있는데 한 스레드에서는 arr1[99] 다른 스레드에서는 arr2[0] 을 참조하고 이 두 데이터는 캐시에 올라갈 때 같이 올라가기 때문에 위의 현상이 나타난다.

#include <thread>
#include <chrono>
#include <iostream>
using namespace std;
int arr1[100];
int arr2[100];

void function1()
{
	for(size_t i=0; i<0xfffffff; i++)
		arr1[99]=10;
}

void function2()
{
	for(size_t i=0; i<0xfffffff; i++)
		arr2[0]=99;
}


int main()
{
	auto start = chrono::high_resolution_clock::now();
	thread _t1(function1);
	thread _t2(function2);
	_t1.join();
	_t2.join();
	auto end = chrono::high_resolution_clock::now();
	cout<<"multithread : "<<(end-start).count()/1000000<<endl;
	start = chrono::high_resolution_clock::now();
	function1();
	function2();
	end = chrono::high_resolution_clock::now();
	cout<<"singlethread : "<<(end-start).count()/1000000<<endl;
}

결과

멀티스레드를 이용한 것이 싱글스레드보다 더 느리게 측정되었다. 연산의 횟수가 적은 것도 아니기 때문에 멀티스레드<=싱글스레드가 정상적인 결과일 것이다. 이를 해결하는 방법은 메모리 정렬을 해서 배열 선언을 해주면 된다. 컴파일러마다 방법이 다르다. 아래는 g++에서 정렬방법이다. 보통 캐시라인의 사이즈인 64byte로 정렬을 해주었다.

alignas(64) int arr1[100];
alignas(64) int arr2[100];

결과

정상적으로 멀티스레드가 2배 정도 빠르게 나왔다.