메모리 풀 (Memory Pool)

삼성 B형 전체 링크

삼성 C형 전체 링크

 

참고 

- 메모리 풀 Memory Pool

- 메모리 풀 vs malloc 속도 비교

- 링크드 리스트 Linked List

- 링크드 리스트 Linked List Tail ver

- 더블 링크드 리스트 Double Linked List
- 더블 링크드 리스트 Double Linked List Tail ver

 

삼성 B형에서는 c++ library 사용이 불가능하지만, 유일하게 malloc은 사용이 가능하다.

 

swexpertacademy.com/main/sst/intro.do

하지만 이건 100% 함정이다.  (100% 쓸모가 없다.)

 

아직도 가끔 외부 강사들이 malloc, free, new, delete를 멋지게(?) 사용하는 방법을 알려주는 것 같지만...

애초에 사용하면 할수록 memory crash가 나타날 확률만 높아지고, 성능 또한 느리다.

 

메모리 풀(memory pool) 방법을 사용해서 malloc의 함정에서 벗어나자.

---

먼저 메모리 풀이 무엇인지 알아보자.

 

게임 엔진 Unity에서는 오브젝트 풀링(Object Pooling)이라는 개념이 있다.

모바일 게임에서 수 많은 블럭, 몬스터와 같은 게임 오브젝트를 동적으로 생성하면 

물리적인 부하가 걸릴 수밖에 없다.

 

그래서 처음 로딩을 할 때, 어느 정도 적당히 게임 오브젝트를 미리 만들어 두고,

필요할 때 마다 가져오는 방식을 이용한다.

---

메모리 풀 방식도 오브젝트 풀과 같다.

malloc이나 new로 선언하지 말고, 전역 변수로 사용할 메모리를 미리 선언해두면 된다.

 

이러면 메모리를 할당할 때, 해제할 때 비용이 거의 0이다.

실제 알고리즘 문제 B형에서는 메모리를 넉넉하게 주기 때문에, 전역으로 마음껏 선언할 수 있다.

 

실제 코드로 사용법을 알아보자. (관련 코드는 BOJ 1707 이분 그래프)

먼저 NODE 구조체가 있고 HEAD를 선언하자.

typedef struct st
{
	int node;
	struct st *next;
}NODE;

NODE HEAD[20200]; /* 1 ~ 20000 개의 head가 필요한 문제 */

 

그리고 전역 변수로 메모리를 미리 선언하고, 메모리 위치를 나타내는 index를 선언하자.

NODE POOL[202000 * 2]; /* 문제를 보면 40만개의 node가 필요해 보인다. */
int pcnt; /* = 0 */

 

이제 그래프를 만든다고 가정하자.

3번 node에 7번 node가 연결 되는 것(양방향)을 구현하고 싶다.

 

그러면

HEAD[3] - 노드(값은 7) 이 되어야 하고,

HEAD[7] - 노드(값은 3) 이 되어야 한다.

 

malloc을 사용하면 아래의 코드가 실행되어야 한다.

/* head 3에 연결하는 값이 7인 node가 필요하므로 메모리 할당 */
NODE *nd = (NODE*)malloc(sizeof(NODE)); 

/* 값을 입력 */
nd->node = 7;

/* head 3에 이미 값이 있다면, 7번 노드 다음으로 연결 */
nd->next = HEAD[p].next;

/* head 3에 7번 노드 연결 */
HEAD[3].next = nd;

malloc을 해서 비용이 많이 들었지만, 메모리를 해제하는 방법도 어려워진다.

BOJ 1707의 경우 메모리를 해제안해도, size가 작아서 메모리 초과가 나타나지 않지만,

B형에서는 숨겨진 tc의 메모리들이 매우 크기 때문에 반드시 해제를 해야한다.

 

따라서 malloc한 메모리를 적어두었다가 문제가 끝난 후, 다음 tc에 들어가기 전에 메모리를 해제해야 한다.

해제 비용에도 시간이 드니깐 이중으로 비용이 발생한다.

 

하지만 POOL 방식을 사용하면 이러한 문제를 모두 해결할 수 있다.

/* 필요한 메모리는 POOL의 배열에서 1개 가져온다. */
NODE *nd = &POOL[pcnt++]; /* pcnt는 *nd가 사용하므로 접근하지 못하게 증가시킨다 */

/* 값을 입력 */
nd->node = 7;

/* head 3에 이미 값이 있다면, 7번 노드 다음으로 연결 */
nd->next = HEAD[p].next;

/* head 3에 7번 노드 연결 */
HEAD[3].next = nd;

 

먼저 미리 선언해 둔 POOL의 배열 중 1개를 포인터 nd가 가르키게 한다. (최초는 POOL[0])

그러면 nd = POOL[0]을 가르키게 되고, POOL[0]에 값을 7로 적는다.

HEAD[3].next = nd; 를 하면 nd는 POOL[0]을 가르키고 있으므로,

최종적으로, HEAD[3]가 POOL[0] (값은 7)를 가르키게 된다.

POOL[0]은 HEAD[3]에 연결되어 사용 중이 되었으므로, 다시 접근하지 못하게 pcnt를 증가시키면 된다.

(처음에 할당할 때 증가시키면서 할당하면 편하다)

 

그러면 초기화는 어떻게 할까?

아래처럼 생각할 수 있다.

/* 사용한 POOL을 모두 0으로 초기화 */
for (int i = 0; i < pcnt; i++)
{
	POOL[i].node = 0;
	POOL[i].next = 0;
}

/* index도 초기화 */
pcnt = 0;

free보다 훨씬 간단해 보인다.

 

하지만 실제로 초기화 코드는 단 한줄이면 충분하다.

pcnt = 0; /* 메모리 풀의 초기화 init 함수에 넣어두자. */

 

POOL의 메모리가 더럽혀졌더라도, 신경 쓸 필요가 없다.

왜냐하면 head에 연결할 때, 원하는 값을 write한 다음 연결하기 때문이다.

 

즉, 더럽혀진 메모리라도, 그대로 안 쓰는 것이 보장되므로, for문을 돌면서 0으로 초기화해줄 필요가 없다.

---

이제 B형에서 유일하게 사용할 수 있는 유일한 library인 malloc이 얼마나 쓸모없는지 알 수 있게 되었다.

BOJ 그래프 문제들을 풀면서 메모리 풀 만드는 방법을 익혀두자.

 

BOJ 1707 이분 그래프의 malloc vs 메모리 풀 속도 비교는 이 링크에서 확인해 보자.