FT_Newton: 메모리 풀 구현 - (12)

이번 글에서는 메모리 풀 구현에 대해 알아보자.

 

 우선, 왜 메모리 풀을 써야 할까에 대한 의문이 먼저 생길 수 있다.

 

 C에서는 malloc, C++에서는 new 연산자를 통해 메모리를 할당받아 사용한다. 물론 명시적으로 malloc이나 new를 호출해 메모리를 할당할 수도 있지만, vector와 같은 동적 자료구조를 사용할 경우 내부적으로 메모리 할당이 수시로 일어나게 된다. 즉, new와 malloc을 통해 쉽게 메모리를 할당받을 수 있다는 장점이 있지만, 자주 사용하게 되면 다음과 같은 단점들이 발생한다.

1. 시스템 콜 오버헤드
   • malloc과 new는 메모리를 할당하기 위해 내부적으로 시스템 콜을 사용하는데,
     시스템 콜은 사용자 모드에서 커널 모드로 전환되는 비용이 크므로 자주 호출하면 성능이 저하된다.
2. 복잡한 내부 자료구조
   • malloc과 new는 내부적으로 복잡한 자료구조를 사용하여 메모리 블록을 검색하고,
     적절한 크기의 공간을 찾아 할당하기 때문에 처리 시간이 오래 걸릴 수 있다.

 따라서, malloc과 new 대신 메모리 풀을 구현하면, 1번 단점은 한 번에 큰 메모리를 할당받아 시스템 콜 호출 횟수를 줄임으로써, 2번 단점은 우리가 원하는 방식으로 간단한 구조의 메모리 풀을 구현해 해결할 수 있다.

 

 그러면 이제 실제로 구현한 두 가지 종류의 메모리 풀에 대해 살펴보자.

---

1. 스택 메모리 풀

 스택 메모리 풀은 실제 스택 메모리처럼 동작하는 메모리 풀이다. 하나의 큰 메모리 블록을 확보한 후, 스택 포인터를 통해 앞에서부터 메모리를 할당해 준다. 메모리를 해제할 때는 할당한 순서대로 해제가 이루어지며, 스택 포인터도 그에 맞게 이동한다.

 개념이 굉장히 단순하므로 코드를 보면서 이해해보자.

#pragma once

#include <cstdint>

namespace ale
{
const int32_t STACK_SIZE = 10 * 1024 * 1024; // 100k
const int32_t MAX_STACK_ENTRY_SIZE = 32;

struct StackEntry
{
	char *data;
	int32_t size;
};

class StackAllocator
{
  public:
	StackAllocator();
	~StackAllocator();

	void *allocateStack(int32_t size);
	void freeStack();

  private:
	char m_data[STACK_SIZE];
	int32_t m_index;

	StackEntry m_entries[MAX_STACK_ENTRY_SIZE];
	int32_t m_entryCount;
};
} // namespace ale

 

• m_data: 스택 메모리
• m_index: 스택 포인터
• m_entries: 할당한 메모리 정보를 저장하는 배열
• m_entryCount: 할당한 메모리의 개수
• StackEntry: 개별 할당 정보를 담은 구조체

 

메모리 할당

void *StackAllocator::allocateStack(int32_t size)
{
	if (m_entryCount == MAX_STACK_ENTRY_SIZE)
	{
		return nullptr;
	}

	StackEntry *entry = m_entries + m_entryCount;
	entry->size = size;
	if (m_index + size > STACK_SIZE)
	{
		AL_CORE_ERROR("Requested size: {0}", size);
		throw std::runtime_error("stack over size");
	}
	else
	{
		entry->data = m_data + m_index;
		m_index += size;
	}

	++m_entryCount;

	return entry->data;
}

• m_data에서 스택 포인터인 m_index만큼 이동한 위치의 메모리를 요청한 size만큼 반환한다.
• 이와 함께 해당 정보를 StackEntry에 저장하여 배열에 보관한다.

메모리 해제

void StackAllocator::freeStack()
{
	if (m_entryCount == 0)
	{
		return;
	}

	StackEntry *entry = m_entries + m_entryCount - 1;

	m_index -= entry->size;

	--m_entryCount;
}

• m_entries 배열에서 가장 마지막에 저장된 entry를 가져와, 그 entry가 사용한 만큼 스택 포인터(m_index)를 뒤로 이동시키며 메모리를 반환한다.

---

2. 블록 메모리 풀

 블록 메모리 풀은 먼저 청크(Chunk)라는 큰 메모리 블록들을 미리 생성해 둔다. 메모리 할당 요청이 들어오면, 해당 요청 크기에 맞게 청크를 여러 개의 작은 블록으로 분할하여 그 중 하나의 블록을 반환한다. 분할된 블록들은 모두 연결리스트로 관리되며, 동일한 크기의 할당 요청이 들어오면 미리 분할해 놓은 블록 중 하나를 즉시 제공한다.

 

 다음 코드들을 보며 자세히 이해해보자.

#pragma once

#include <cstdint>

namespace ale
{
const int32_t CHUNK_SIZE = 1024 * 1024;
const int32_t MAX_BLOCK_SIZE = 4096;
const int32_t BLOCK_SIZE_COUNT = 16;
const int32_t CHUNK_ARRAY_INCREMENT = 256;

struct Block
{
	Block *next;
};

// 특정 size의 블록 리스트가 보관된 공간
struct Chunk
{
	Block *blocks;
	int32_t blockSize;
};

class BlockAllocator
{
  public:
	BlockAllocator();
	~BlockAllocator();

	void *allocateBlock(int32_t size);
	void freeBlock(void *pointer, int32_t size);

  private:
	Chunk *m_chunks;	  // 전체 청크 메모리
	int32_t m_chunkCount; // 사용 중인 청크 수
	int32_t m_chunkSpace; // 전체 청크 공간

	Block *m_availableBlocks[BLOCK_SIZE_COUNT];

	static int32_t s_blockSizes[BLOCK_SIZE_COUNT];
	static uint8_t s_blockSizeLookup[MAX_BLOCK_SIZE + 1];
	static bool s_blockSizeLookupInitialized;
};
} // namespace ale

 

 

• Chunk: 미리 할당해 놓은 큰 메모리(나중에 블록으로 분할됨)
• Block: 청크를 특정 크기로 나누어 만든 메모리 블록. 동일 크기의 블록끼리 연결리스트로 관리된다.
• m_chunks: 청크들이 모여 있는 배열
• m_chunkCount: 현재 사용 중인 청크 개수
• m_chunkSpace: 전체 청크 배열 공간
• s_blockSizes: 메모리 블록 크기 목록(예, {16, 32, …})
• s_blockSizeLookup: 할당 요청 크기에 따라 어떤 크기의 블록을 할당할지 결정하는 테이블
• s_blockSizeLookupInitialized: s_blockSizeLookup 배열 초기화 여부
• m_availableBlocks: 크기별로 분류된 메모리 블록을 보관하는 배열
  • 예를 들어, s_blockSizes가 {16, 32}라면,
    m_availableBlocks[0]에는 16바이트 블록,
    m_availableBlocks[1]에는 32바이트 블록이 저장된다.
  • 해당 크기의 블록이 없으면 nullptr이 들어간다.

 

 

 블록 메모리 풀이 어렵다면, 쉽게 m_chunks가 창고, m_availableBlocks가 판매대라고 생각하면 편하다. 

 m_availableBlocks 판매대에 원하는 크기의 블록이 있다면 바로 가져가고, 원하는 크기의 블록이 떨어져서 없다면 m_chunks의 Chunk 메모리 1개를 썰어서 블록들을 생성한 후 m_availableBlocks 판매대에 다시 전시해 놓는 방법으로 운영된다고 생각할 수 있다.

 

블록 메모리 풀 초기화

int32_t BlockAllocator::s_blockSizes[BLOCK_SIZE_COUNT] = {
	16,	  // 0
	32,	  // 1
	64,	  // 2
	96,	  // 3
	128,  // 4
	160,  // 5
	192,  // 6
	224,  // 7
	256,  // 8
	320,  // 9
	384,  // 10
	448,  // 11
	512,  // 12
	1024, // 13
	2048, // 14
	4096, // 15
};

BlockAllocator::BlockAllocator()
{
	m_chunkSpace = CHUNK_ARRAY_INCREMENT;
	m_chunkCount = 0;
	m_chunks = (Chunk *)malloc(m_chunkSpace * sizeof(Chunk));

	memset(m_chunks, 0, m_chunkSpace * sizeof(Chunk));
	memset(m_availableBlocks, 0, sizeof(m_availableBlocks));

	// 블록 크기 조회 배열 초기화
	if (s_blockSizeLookupInitialized == false)
	{
		int8_t j = 0;
		for (int32_t i = 1; i <= MAX_BLOCK_SIZE; ++i)
		{
			if (j >= BLOCK_SIZE_COUNT)
			{
				throw std::runtime_error("failed to initialize blockSizeLookup");
			}

			if (i <= s_blockSizes[j])
			{
				s_blockSizeLookup[i] = static_cast<uint8_t>(j);
			}
			else
			{
				++j;
				s_blockSizeLookup[i] = static_cast<uint8_t>(j);
			}
		}

		s_blockSizeLookupInitialized = true;
	}
}

• 생성자에서는 먼저 청크 배열(m_chunks)을 할당하고,
  s_blockSizeLookup 테이블을 초기화하는 과정을 볼 수 있다.
• s_blockSizes 배열에는 사용할 블록의 크기가 정의되어 있다.

메모리 할당

void *BlockAllocator::allocateBlock(int32_t size)
{
	if (size <= 0)
	{
		return nullptr;
	}

	if (size > MAX_BLOCK_SIZE)
	{
		AL_CORE_ERROR("Requested block size: {0}", size);
		throw std::runtime_error("try too large memory allocated");
	}

	int32_t index = s_blockSizeLookup[size];

	if (m_availableBlocks[index] != nullptr)
	{
		// 청크 내부에 할당된 블록이 존재하는 경우 해당 블록 return
		Block *block = m_availableBlocks[index];
		m_availableBlocks[index] = block->next;
		return block;
	}
	else
	{
		// 할당된 블록이 없는 경우 블록 새로 할당
		if (m_chunkCount == m_chunkSpace)
		{
			// 청크가 꽉찬 경우 크기 증가
			Chunk *oldChunks = m_chunks;
			m_chunkSpace += CHUNK_ARRAY_INCREMENT;
			m_chunks = (Chunk *)malloc(m_chunkSpace * sizeof(Chunk));
			memcpy(m_chunks, oldChunks, m_chunkCount * sizeof(Chunk));
			free(oldChunks);
		}

		// 새로운 청크 생성
		Chunk *chunk = m_chunks + m_chunkCount;
		chunk->blocks = (Block *)malloc(CHUNK_SIZE);

		// 청크 내부 블록들 생성
		int32_t blockSize = s_blockSizes[index];
		chunk->blockSize = blockSize;
		int32_t blockCount = CHUNK_SIZE / blockSize;

		Block *block = chunk->blocks;
		for (int32_t i = 1; i < blockCount; ++i)
		{
			Block *next = (Block *)((int8_t *)chunk->blocks + blockSize * i);
			block->next = next;
			block = next;
		}
		block->next = nullptr;

		m_availableBlocks[index] = chunk->blocks->next;
		++m_chunkCount;

		return chunk->blocks;
	}
}

 

할당은 다음 세 가지 흐름으로 진행된다.

1. 판매대(m_availableBlocks) 확인
   • m_availableBlocks에 원하는 크기의 블록이 존재하면, 즉시 해당 블록을 반환한다.
2. 창고(m_chunks)에서 블록 생성
   • 판매대에 원하는 블록이 없다면,  m_chunks에서 청크 하나를 가져와 블록으로 분할한 후
     판매대에 전시하고 블록을 반환한다.
3. 청크 추가 할당
   • 만약 현재 청크 공간이 부족하다면, 새로운 청크 공간을 할당받은 후 위 과정을 진행한다.

메모리 해제

void BlockAllocator::freeBlock(void *pointer, int32_t size)
{
	if (size <= 0)
	{
		return;
	}

	if (size > MAX_BLOCK_SIZE)
	{
		return;
	}
    
	int32_t index = s_blockSizeLookup[size];

	// free한 pointer를 다시 avilableBlock에 편입
	Block *block = (Block *)pointer;
	block->next = m_availableBlocks[index];
	m_availableBlocks[index] = block;
}

 

해제 시에는 해당 블록을 다시 판매대(m_availableBlocks)에 넣어 재사용할 수 있도록 한다.

 

---

지금까지 스택 메모리 풀과 블록 메모리 풀에 대해 살펴보았다.

• 스택 메모리 풀은 정적 배열이나 특정 범위(scope) 내에서만 잠깐 사용할 메모리를 할당할 때 적합하고,
• 블록 메모리 풀은 동적으로 할당해야 하거나 생성 및 소멸 주기가 정해지지 않은 메모리를 관리할 때 유용하다.

이처럼 상황에 맞는 메모리 풀을 잘 활용하면, 이전 글에서 언급한 것처럼 프로그램 성능을 크게 향상시킬 수 있다.

 

(위 메모리 풀은 Box2D를 참고하여 만들었다)