뒤돌아보기

이 글은 책 컴퓨터 밑바닥의 비밀 chapter 5.3의 내용을 읽고 요약한 글입니다. 

5.3.1 캐시와 메모리 상호 작용의 기본 단위: 캐시 라인

캐시 라인(Cache line)이란?

• 프로그램이 어떤 데이터에 접근하면 다음에도 인접한 데이터에 접근할 가능성이 높으므로 데이터가 있는 곳의 ‘묶음’ 데이터를 캐시에 저장하는데 이 ‘묶음’을 캐시 라인이라고 함

캐시와 메모리가 상호 작용하는 기본 단위는 캐시 라인이며, 이 크기는 일반적으로 64 바이트임.

캐시가 적중하지 모샇는 경우 이 묶음 데이터가 캐시에 저장됨.

5.3.2 첫번째 성능 방해자: 캐시 튕김 문제

아래 2가지 코드가 있음

첫번째 코드

atomic<int> a;

void threadf()
{
	for(int i=0;i<500000000;i++)
	{
		++a;
	}
}

void run()
{
	thread t1 = thread(threadf);
	thread t2 = thread(threadf);
	
	t1.join();
	t2.join();
}

• 2개의 스레드를 시작하는데 각 스레드를 전역변수 a값을 1씩 5억번씩 증가

두번째 코드

atomic<int> a;

void run()
{
	for(int i=0;i<1000000000;i++)
	{
		++a;
	}
}

• 단일 스레드로 전역변수 a값을 1씩 10억번씩 증가

어떤 코드의 속도가 더 빠를까?

• 다중 코어 컴퓨터 기준 첫번째 프로그램의 실행시간이 16초, 두번째 실행시간은 8초에 불과했음
• 병렬 계산임에도 다중 스레드가 단일 스레드보다 느린 이유는?
• 리눅스의 perf 도구를 사용하여 두 코드를 분석할 수 있음
• “perf stat” 명령어는 프로그램 실행 시에 나타나는 각종 주요 정보의 통계를 보여주는데 여러 항목 중 insn per cycle 항목에서 차이를 보임

insn per cycle

• 하나의 클럭 주기에 CPU가 실행하는 프로그램에서 기계 명령어를 몇개 실행하는지 알려줌
• 다중 스레드는 0.15, 단일 스레드는 0.6으로 단일 스레드 프로그램에서 하나의 클럭 주기 동안 기계 명령어나 4배나 다 많이 실행되었음. 이유는?

캐시 일관성을 보장하기 위해 두 코어의 캐시에서 전역 변수 a처럼 동일한 변수가 사용될 때는 두 캐시에 모두 저장됨

두 스레드는 모두 해당 변수에 1을 더해야 함. 이때 첫번 째 스레드가 아래 그림과 같이 a 변수에 덧셈 연산을 실행하기 시작한다면, 다른 cpu 캐시의 a 변수를 무효화(invalidation) 해야 함 → 캐시 튕김 발생

1. 캐시와 메모리의 불일치 문제를 방지 하기 위해 메모리의 a 변수 값도 업데이트
2. 동시에 다른 cpu 캐시에 있는 a 변수 값을 무효화

1. 아래 cpu의 캐시가 무효화되어 어쩔 수 없이 메모리에서 직접 a변수 값을 읽어야 함

1. 아래 cpu도 a 변수에 1을 더하고 캐시이 일관성을 보장하기 위해 메모리에 a 변수 값을 업데이트
2. 위 cpu 캐시의 a 변수 무효화 → 또 다시 캐시 튕김이 발생

이와 같이 각 cpu의 캐시가 끊임없이 서로 상대 캐시를 무효화하면서 튕겨냄
⇒ 여러 스레드 사이에 데이터 공유를 피할 수 있다면 가능한 피해야 함을 의미

5.3.3 두번째 성능 방해자: 거짓 공유 문제

첫번째 코드

struct data
{
	int a;
	int b;
};

struct data global_data;

void add_a()
{
	for(int i=0;i<50000000;i++)
	{
		++ global_data.a;
	}
}

void add_b()
{
	for(int i=0;i<50000000;i++)
	{
		++ global_data.b;
	}
}

void run()
{
	thread t1 = thread(add_a);
	thread t2 = thread(add_b);
	
	t1.join();
	t2.join();
}

• 스레드 2개를 시작한 후 구조체의 a 변수와 b 변수를 1씩 5억번 증가시킴

두번째 프로그램

void run()
{
	for(int i=0;i<50000000;i++)
	{
		++global_data.a;
	}
	
	for(int i=0;i<50000000;i++)
	{
		++global_data.b;
	}
}

• 단일 스레드로 동일하게 a 변수와 b 변수를 1씩 5억 번 증가시킴
• 첫번째 코드가 두 변수를 공유하지 않고 다중 쓰레드 프로그램이니 더 빠르게 실행될 것이라고 예상할 수 있음 → 사실을 그렇지 않음
• 사실 두 스레드는 어떤 변수도 공유하지 않지만 이 두 변수는 동일한 캐시 라인(cache line)에 있을 가능성이 매우 높아 캐시 튕김 문제가 발생할 수 있음 ⇒ 거짓 공유(false sharing)이라고 함

개선하는 방법으로 두 변수가 같은 캐시라인에 있지 않도록 하는 것인데 아래처럼 구조체를 구성하면 가능

struct data
{
	int a;
	int arr[16];
	int b;
}

• 다중 코어 컴퓨터에서 캐시 라인 크기가 64바이트이며, arr[16]을 통해 int 형식의 배열을 채우면 a 변수와 b변수는 다른 캐시라인에 있게 됨.

이 글은 책 컴퓨터 밑바닥의 비밀 chapter 5.2의 내용을 읽고 요약한 글입니다. 

5.2.1 프로그램 지역성의 원칙

프로그램 지역성의 원칙(locality of reference or principle of locality)

• 본질은 매우 규칙적으로 메모리에 접근한다는 것으로 크게 2가지 종류가 있음

(1) 시간적 지역성 (temporal locality)

• 프로그램이 메모리 조각에 접근하고 나서 이 조각을 여러번 참조하는 경우를 이야기 함
• 캐시 친화성이 매우 높은데, 데이터가 캐시에 있는한 메모리에 접근하지 않아도 반복적으로 캐시의 적중이 가능하다는 단순한 이유

(2) 공간적 지역성(spatial locality)

• 캐시가 적중하지 않으면 메모리의 데이터를 캐시에 적재해야 함
• 일반적으로 요청한 메모리의 인접 데이터도 함께 캐시에 저장되므로 프로그램이 인접 데이터에 접근할 때 캐시가 적중하게 됨

5.2.2 메모리 풀 사용

• 메모리를 동적으로 할당받을 때 일반적으로 malloc을 이용
• 메모리 조각 N개를 할당받을 때 malloc을 사용하면 N개 조각이 힙 영역의 이곳 저곳에 흩어져 공간적 지역성에 좋지 않음
• 메모리 풀 기술은 커다란 메모리 조각(연속적인 메모리 공간)을 미리 할당받으며 메모리 요청/해제 할 때 더 이상 malloc을 거치지 않아 캐시 친화적

5.2.3 struct 구조체 재배치

Linked list에 특정 조건을 만족하는 노드가 있는지 판단하려고 할 때, 구조체는 다음과 같이 정의

#define SIZE 100000

struct List
{
	List* next;
	int arr[SIZE];
	int value;
}

Linked list의 노드에는 필요한 값 value와 다음 노드를 가리키는 next 포인터 외에도 배열 arr이 포함되어있음

bool find(struct List* list, int target)
{
	while(list)
	{
		if(list->value == target)
			return true;
		
		list = list->next;
	}
	
	return false;
}

• 위 코드에서 빈번하게 사용되는 항목은 next 포인터와 value값이며, 배열 arr은 전혀 사용되지 않음
• 하지만 next 포인터와 value 값이 배열 arr에 의해 멀리 떨어져 있기 때문에 공간적 지역성이 나빠질 수 있어 아래 처럼 함께 배치 → 캐시 적중률 상승시킬 수 있음. 

#define SIZE 100000

struct List
{
	List* next;
	int value; // next 아래에 value
	int arr[SIZE];
}

5.2.4 핫 데이터와 콜드 데이터의 분리

• 핫데이터 (hot data): 더 빈번하게 사용되는 데이터
• 콜드 데이터(cold data): 덜 빈번하게 사용되는 데이터

위 코드에서 next, value는 핫데이터, arr는 콜드 데이터라고 할 수 있음

일반적으로 Linked list에 노드가 하나뿐인 경우는 거의 없으며, 노드가 비교적 많을 때에는 캐시해야 할 노드가 비교적 많아짐 → 캐시 용량은 제한적!

Linked list 자체가 차지하는 저장 공간이 클수록 캐시에 저장할 수 있는 노드는 줄어듬. 아래와 같이 배열 arr을 다른 구조체에 넣고 List 구조체 안에 이 구조체를 가리키는 포인터를 추가할 수 있음

#define SIZE 100000

struct List
{
	List* next;
	int value; // next 아래에 value
	strcut Arr* arr;
};

struct Arr
{
	int arr[SIZE];
};

• 콜드 데이터와 핫 데이터를 분리하면 더 나은 지역성을 얻을 수 있는데 이런 방법을 사용하려면 각 항목하다 접근 빈도를 알고 있어야 함

5.2.5 캐시 친화적인 데이터 구조

• 지역성 원칙 관점에서 배열이 linked list보다 나음
  • C++, std::vector 컨테이너가 std::list 컨테이너 사용보다 나음
• 실제로 사용할 때는 캐시 친화적 여부를 포함하여 구체적인 상황에 맞추어 선택해야 함
• 예를 들어, 배열의 공간적 지역성은 linked list보다 낫지만, 노드의 추가/삭제가 빈번하게 발생하는 경우에는 linked list가 배열에 비해 우수함
  • Linked list의 노드 추가/삭제에 대한 시간 복잡도 O(1)
• 노드의 추가/삭제가 쉬운 장점을 유지하면서 캐시 친화적이고 싶은 linked list를 사용하려면? → 직접 정의한 메모리 풀에서 메모리를 요청하면 됨

이런 최적화를 진행할 때 반드시 분석 도구를 사용하여 캐시의 적중률이 시스템 성능에 병목이 되는지 판단해야 함. 병목이 되지 않으면 굳이 이런 최적화를 할 필요가 없음

5.2.6 다차원 배열 순회

• 배열을 row, column 순서로 순회하면서 값을 모두 더하는데 C언어 역시 row 우선 방식(row major)으로 배열을 저장
  • row major: 메모리에 저장할 때 첫번째 행이 첫번째 열부터 마지막 열까지 저장되고, 이어서 두번째 행이 첫번째 열부터 마지막 열까지 저장되는 것을 반복하는 구조

int matrix_summer(int A[M][N])
{
    int i, j, sum = 0;
	
    for(i=0; i< M;i++)
    {
        for(j=0;j<N;j++)
        {
            sum += A[i][j];
        }
    }
	
    return sum;
}

• 배열에 행 4개와 열 8개가 있다고 가정 (M이 4, N이 8)
• 캐시가 최대 4개의 int 형식 데이터를 저장할 수 있다고 가정

• 순회가 시작되면 캐시에 아직 배열에 대한 데이터가 없기 때문에 캐시는 비어있어 배열 A의 첫번째 요소인 A0에 접근하는 시점에 캐시가 적중할 수 없음 → A0를 포함한 요소 4개가 캐시에 저장됨

• 캐시 준비가 완료되어 A1부터 A3에 접근할 때는 모두 캐시가 적중하기 때문에 메모리에 접근할 필요가 없음

• A4에 접근할 때는 캐시 용량의 제한으로 캐시가 적중할 수 없는데 다시 A4개를 포함한 요소 4개가 캐시에 저장되어 이전 데이터와 교체됨

• 각 행마다 8개 요소들 중 2개를 miss하기 때문에 75% 의 캐시 적중률을 보여줌

이번에는 열 우선 방식으로 접근 (column major)

int matrix_summer(int A[M][N])
{
	int i, j, sum = 0;
	
	for(j=0; j< N;j++)
	{
		for(i=0;i<M;i++)
		{
			sum += A[i][j];
		}
	}
	
	return sum;
}

첫번째 요소인 A0에 접근하면 아직 캐시가 적중할 수 없기 때문에 아래와 같이 A0부터 A3까지 캐시에 저장됨

그러나 우리 코드에서 다음에 접근할 요소는 A8이며 이 데이터는 여전히 캐시가 적중할 수 없고 캐시에 A8부터 A11을 저장. 이전 캐시는 사용되지 못함

• 위와 같이 열 우선 방식으로 배열을 순회하면 캐시는 매번 적중에 실패하여 적중률은 0

이 글은 책 컴퓨터 밑바닥의 비밀 chapter 5.1의 내용을 읽고 요약한 글입니다. 

5.1.1 CPU와 메모리의 속도 차이

• CPU 속도는 1년에 52%씩 성능이 증가한 반면, 메모리 속도는 1년에 7%씩 증가
• CPU는 명령어를 실행할 때 어쩔 수 없이 메모리의 처리를 기다려야 함
  • 일반적인 시스템에서 메모리의 속도는 CPU의 100분의 1

5.1.2 도서관, 책상, 캐시

• 도서관에서 책상은 캐시에 비유할 수 있고, 서가는 메모리에 비유 가능
• CPU와 메모리 사이에 캐시 계층이 추가되어, 최근에 메모리에서 얻는 데이터가 저장됨
• 캐시가 적중하면 메모리에 접근할 필요가 없어 CPU가 명령어 실행하는 속도를 크게 끌어올릴 수 있음
  • 캐시 적중: CPU가 요청한 데이터가 캐시에 이미 저장되어있어 캐시가 해당 요청을 이행할 수 있을 때 발생

• 일반적으로 x86 CPU와 메모리 사이에는 세 단계의 캐시가 추가 되어 있음
  • L1, L2, L3
• L1 캐시 접근 속도: 레지스터 접근 속도에 비해 약간 느리지만 대동 소이하기 때문에 대략 4클럭 주기가 소요됨
• L2캐시 접근 속도: 대략 10클럭 주기 소요
• L3캐시 접근 속도 : 대략 50클럭 주기 소요
• 캐시 단계에 따라 접근 속도는 낮아지지만 용량을 증가

• L1, L2, L3 캐시, CPU 코어는 레지스터 칩 내에 묶여 패키징되어 있음
• CPU가 메모리 내에 데이터가 필요하다고 판단하면 우선 L1 캐시에서 데이터를 검색
• 없다면 L2, L3 를 순차적으로 검색 후 모두 없으면 메모리에 직접 접근하여 캐시에 데이터를 갱신

5.1.3 공짜 점심은 없다: 캐시 갱신

불일치 문제

• 캐시의 데이터는 갱신되었지만 메모리의 데이터는 아직 예전 것이 남아 있어 캐시와 메모리 사이에 불일치가 발생할 수 있음

해결 방법

1. 연속 기입(write-through)

• 캐시를 갱신할 때 메모리도 함께 갱신하는 방법
• 캐시를 업데이트하면 어쩔 수 없이 메모리에 접근해야 함 → CPU는 메모리가 갱신될 때까지 대기하고 있어야 함 → 동기식 설계 방법
• 이 상황을 최적화하는 방법은 동기를 비동기로 바꾸는 것

2. 후기입(write-back)

• 캐시 용량에 한계가 있어 용량이 부족하면 자주 사용되지 않는 데이터를 제거해야 함
• 캐시에서 제거된 데이터가 수정된 적이 있다면 이를 메모리에 갱신해야 함
• 캐시의 갱신과 메모리의 갱신이 분리되므로 비동기임
• 연속 기입보다 훨씬 복잡하지만 성능은 분명 더 나음

자주 사용할만한 데이터를 캐싱하는데, 삭제할 때만 메모리에 갱신하는 방식이 후기입

5.1.4 세상에 공짜 저녁은 없다: 다중 코어 캐시의 일관성

• 단일 CPU 성능 향상이 어려워 숫자를 늘리게 됨 → 다중 코어 시대 진입
• CPU가 코어를 여러개 가지면 다른 문제가 발생하는데 두 코어에서는 다른 스레드 2개가 실행됨

Step 1

• 두 스레드 모두 메모리 내 X변수에 접근해야하고 변수의 초기값이 2라고 가정
• 코어 2개는 모두 X 변수를 사용해야 한다

캐시 동작 원리에 따르면,

• 처음으로 X 변수를 읽으면 캐시에 적중할 수 없으므로 X 변수를 메모리에서 읽어야 함
• 이어서 대응하는 캐시에 갱신되므로, 이제 cpu1 캐시와 cpu2 캐시는 모두 X 변수를 가지고 있고 그 값은 2

Step2

1. C1은 X 변수에 2를 더해야 하는데 캐시 동작 원리에 따라 C1은 캐시에서 X 변수 값을 가져온 후 2를 더해서 다시 캐시에 갱신
2. 이 시스템이 연속 기입(write-through) 방식이라고 가정하면 메모리도 동기 방식으로 동시에 갱신되고 메모리에 있는 X 변수 값은 4

Step3

1. cpu2 도 X 변수에 덧세 연산을 수행하는데 4를 더한다고 가정
   1. 캐시 동작 원리에 따라 cpu2는 캐시에서 X 변수 값을 가져온 후 4를 더해서 다시 캐시를 갱신
   2. 캐시 값은 6으로 바뀌는데 연속 기입 방식에 따라 메모리를 갱신하면 메모리에 저장된 값도 6이 됨 ⇒ 문제 바생

• 초기 값이 2인 변수에 2 와 4를 각각 더한 후 결과는 8이 되어야 하지만 X 변수 값은 6이 됨

문제는 메모리의 X 변수에 cpu1, cpu2의 캐시에 복사본 2개를 가지고 있기 때무네 발생하고 C1 캐시가 갱신될 때 C2 캐시는 동기적으로 수정되지 않아 다중 코어에서 캐시 데이터의 불일치 문제가 발생함

⇒ 해결책: 캐시 한개에 갱신된 변수가 다른 CPU 코어의 캐시에도 존재한다면 함께 갱신되어야 함

• 최신 CPU에는 고전적인 MESI 규칙(MESI protocol)같은 다중 코어 캐시의 일관성을 유지하는 규칙이 있음

5.1.5 메모리를 디스크의 캐시로 활용하기

• 디스크는 탐색(seek) 을 위해 10ms 가량의 시간이 소요됨 (메모리 접근 속도가 10만배 가량 빠름)
  • 물론 모든 디스크 접근에 탐색이 필요하지는 않음

메모리와 디스크의 속도 차이를 해결하기 위해 둘 사이에 직접 캐시를 추가하면 어떨까?

먼저 레지스터가 메모리의 캐시가 될 수 없는 이유는 레지스터 크기가 한정되어있기 때문. 메모리 용량은 사실 꽤 큰편이라(GB 단위) 어려움

• 최신 운영체제는 분명히 메모리를 디스크의 캐시로 사용
• 일반적으로 메모리 사용률은 100%에 도달하지 않으며 이 여유 공간을 낭비시키지 않도록 디스크의 캐시로 활용하여 디스크에서 데이터 읽어 오는 일을 최소화 함 → 페이지 캐시의 기본원리

결국 CPU의 내부 케시가 메모리 데이터를 저장하고, 메모리가 디스크 데이터를 저장

• 최근 서버에서는 메모리가 디스크를 대체하는 것이 대세 → 메모리 가격이 엄청 저렴해졌기 때문
• AWS에서는 2TB 용량의 메모리를 탑재한 인스턴스도 제공
• Presto, Flink, Spark 같은 메모리 기반 시스템이 디스크 기반의 경쟁자들을 빠르게 대체하고 있음

5.1.6 가상 메모리와 디스크

• 앞서 모든 프로세스가 표준 크기의 자체적인 주소 공간을 가지고 있다고 여러번 이야기 함
  • 물리 메모리와는 관련이 없어 물리 메모리의 크기를 초과활 수 있음

Q. 시스템에 프로세스 N개가 실제 물리 메모리를 모두 사용하고 있을 때 새로운 프로세스가 생성되어 N+1번째 프로세스도 메모리를 요청한다면 시스템이 어떻게 처리할까?

A. 디스크는 메모리의 창고 역할을 할 수 있어 자주 사용하지 않은 메모리 데이터를 디스크에 기록하고 데이터가 차지하던 물리 메모리 공간을 해제할 수 있음. 그러면 N+1 번째 프로세스가 다시 메모리를 요청할 수 있음

5.1.7 CPU는 어떻게 메모리를 읽을까?

• CPU가 볼 수 있는 것은 모두 가상 메모리 주소로 실제 물리 메모리 주소로 변환되어야 함
• 변환이 완료되면 캐시를 검색하기 시작하고 캐시에서 찾을 수 없을 때는 메모리에 접근
• 프로세스의 데이터는 디스크에 임시로 보관되어 있을 수 있는데 이때 메모리에서 데이터를 찾을 수 없을 가능성이 있으며 디스크의 프로세스 데이터를 다시 메모리에 적재한 후 메모리를 읽어야 함
• 빅 데이터의 시대가 도래해 단일 장치의 디스크만으로 더이상 데이터를 완전히 저장할 수 없다면 대안은?

5.1.8 분산 저장 지원

• 분산 파일 시스템(distributed file system)을 직접 장착(mount)할 수도 있고, 로컬 디스크는 원격의 분산 파일 시스템에서 전송된 파일을 저장 → 로컬 디스크를 원격의 분산 파일 시스템의 캐시로 간주할 수 있음
• 물론 응답 속도를 높이기 위해 원격 분산 파일 시스템의 데이터를 데이터 흐름(data stream) 형태로 직접 로컬 컴퓨터 시스템의 메모리로 끌어올 수도 있음 (apache kafka)
• 이 경우 대용량 메시지는 원격 분산 파일 시스템에 저장되어 있지만 실시간으로 해당 데이터는 소비자에게 전달되고 이때 메모리를 원격 분산 파일 시스템의 캐시로 간주