[C++] Memory Pool

메모리 풀 구현

32/64/128/... 바이트 단위로 메모리를 미리 할당하여, 실제 할당할 때 해당 메모리를 사용함.

장점
메모리 단편화 문제를 완화 가능. 특히 사이즈가 큰 메모리를 할당할 때 적절한 위치의 페이지를 찾는 것이 시간이 소요될 수 있다.

단점
사용하지 않는 메모리를 미리 할당하여 사용하게 되는 낭비.
메모리 풀과 같이 특정 할당자(Allocator)를 사용한 경우, 메모리를 반납하여 재사용할 수 있도록 할당자를 통한 해제를 해야한다.

std::shared_ptr의 생성자에는 해제자 deleter에 대한 인스턴스를 받아 해제를 제어할 수 있다.

std::unique_ptr는 타입으로 선언하여 사용한다. 커스텀 deleter를 사용하는 경우 타입 이름이 지저분해질 수 있다.

MemoryHeader

#pragma pack(push, 1)
struct DECLSPEC_ALIGN(MEMORY_ALLOCATION_ALIGNMENT) MemoryHeader {
	SLIST_ENTRY* next;
	struct Info {
		size_t id : 16;
		size_t size : 16;
		size_t tag : 32;
	} info;
	static constexpr size_t kSize = sizeof(SLIST_ENTRY*) + sizeof(Info);
};
#pragma pack(pop)

 

각 메모리의 헤더 부분으로 기본 16바이트를 차지하게 된다.
SLIST_ENTRY* next 부분은 windows의 InterlocekdSList를 사용하기 위한 필드.

*InterlockedSList는 lock-free FIFO 자료구조 API를 제공한다.
Interlockedapi.h header - Win32 apps | Microsoft Learn

Interlockedapi.h header - Win32 apps

StaticMemoryPool
필요한 페이지를 미리 할당하여 Memory 사이즈 단위로 미리 잘라서 쓰는 방식

class StaticMemoryPool {
public:
	struct BlockAlloc {
		size_t size;
		size_t count;
	};

	static constexpr size_t kMaxBlockSize = 0x4000;
    //...

	StaticMemoryPool(size_t block_size, size_t target_block_num)
		:
		_block_size(block_size) {
		_address_begin = MemoryManager::Get().request(nullptr, _block_size, target_block_num, _alloc_size);
		_address_end = reinterpret_cast<char*>(_address_begin) + _alloc_size;
		_alloc_count = _alloc_size / _block_size;
		for (size_t i = 0; i < _alloc_count; ++i) {
			auto* header = reinterpret_cast<MemoryHeader*>(reinterpret_cast<char*>(_address_begin) + i * _block_size);
			header->next = nullptr;
			header->info.tag = kFreeTag;
			header->info.id = 0;
			header->info.size = 0;
			_free_list.push(header);
		}
	}

   //...
};

예를 들면, 32바이트 단위의 메모리를 연속된 주소로 1024개를 할당하여 미리 가지고 있는다.
각 32바이트의 첫 16바이트는 메모리 헤더로 사용하고 초기화시 SList 인스턴스인 _free_list에 넣어둔다.

allocate 및 dellocate

	void* allocate(size_t size) noexcept {
		auto header = _free_list.pop();
		if (header == nullptr) {
			return ::malloc(size);
		}
#ifdef _DEBUG
		assert(header->info.tag == kFreeTag);
		header->info.tag = kAllocTag;
		header->info.id = _id_counter.fetch_add(1, std::memory_order_relaxed);
		header->info.size = size;
#endif // !_DEBUG
		return reinterpret_cast<char*>(header) + MemoryHeader::kSize;
	}

	void  deallocate(void* ptr, size_t size) noexcept {
		if (contains(ptr) == false) {
			::free(ptr);
			return;
		}
		auto* header = reinterpret_cast<MemoryHeader*>(reinterpret_cast<char*>(ptr) - MemoryHeader::kSize);
#ifdef _DEBUG
		assert(header->info.tag == kAllocTag);
		header->info.tag = kFreeTag;
#endif // !_DEBUG
		_free_list.push(header);
	}

size 만큼 할당 요청에 대하여 _free_list로 부터 여분의 메모리가 있으면 해당 메모리를 반환한다.
여분이 없다면 malloc을 사용하여 기본 내장 할당 함수를 사용한다.

해제 시 해당 메모리 주소를 기준으로 자신이 관리하는 메모리 주소 영역을 판단하여 다시 반납하거나 아니라면 free 함수를 통해 직접 해제한다.

std::allocator_traits

std 컨테이너를 정의할 때 흔히 원소에 대한 첫 타입 외 Allocator 타입을 받을 수 있는데
커스텀 할당자를 정의하여 컨테이너 원소를 할당할 때 사용할 수 있다.

이 때 커스텀 할당자는 std::allocator_traits 제약을 만족해야한다.
- 참고
https://en.cppreference.com/w/cpp/memory/allocator_traits

https://learn.microsoft.com/ko-kr/cpp/standard-library/allocator-traits-class?view=msvc-170

 

- 예시
MemoryPool을 사용하는 StaticAllocator

template<typename T>
class StaticAllocator {
public:
	using allocator_type = StaticAllocator<T>;
	using value_type = T;
	using size_type = size_t;
	using difference_type = ptrdiff_t;
	using pointer = T*;
	using const_pointer = const T*;
	using reference = T&;
	using const_reference = const T&;

	StaticAllocator() = default;
	~StaticAllocator() = default;

	StaticAllocator(const StaticAllocator&) noexcept {};
	StaticAllocator& operator=(const StaticAllocator&) noexcept { return *this; }

	template<typename U>
	StaticAllocator(const StaticAllocator<U>&) noexcept {}
	template<typename U>
	StaticAllocator& operator=(const StaticAllocator<U>&) noexcept { return *this; }

	constexpr pointer address(reference x) const noexcept { return &x; }
	constexpr const_pointer address(const_reference x) const noexcept { return &x; }

	pointer allocate(size_type n, const void* = 0) {
		size_t alloc_size = n * sizeof(T);
		if (alloc_size > StaticMemoryPool::kMaxAllocSize) {
			return static_cast<pointer>(::malloc(alloc_size));
		}
		return static_cast<pointer>(StaticMemoryPool::g_memory_mapper.Get(alloc_size).allocate(alloc_size));
	}

	void deallocate(pointer p, size_type n) {
		size_t alloc_size = n * sizeof(T);
		if (alloc_size > StaticMemoryPool::kMaxAllocSize) {
			return ::free(p);
		}
		StaticMemoryPool::g_memory_mapper.Get(alloc_size).deallocate(p, alloc_size);
	}

	template<typename ...Args>
	void construct(pointer p, Args&&... args) {
		new (p) T(std::forward<Args>(args)...);
	}

	void destroy(pointer p) {
		p->~T();
	}
};

- allocate(size_type, const void* hint)
n 개의 초기화 되지 않은 메모리를 할당한다. 이전 할당 주소 등을 가리켜 hint는 할당하고자하는 메모리 주소에 대한 힌트를 제공한다.

배열과 같이 한 번에 여러 개를 요청할 때만 n > 1이다.

- deallocate(pointer p, size_type n)
 p 주소에 대한 메모리를 해제한다.

- construct
new 연산자와 같이 할당된 메모리에 대한 주소에 초기화 작업을 수행한다.

- destroy
개체 파괴를 진행하여 메모리를 해제하기 전에 소멸자와 같이 정리 작업을 수행한다.

위 allocator 타입을 사용하여 shared_ptr 인스턴스를 생성하는 예시

struct SharedPtrFactory {
	template<typename T, template <typename...> typename Allocator = std::allocator, typename ...Args>
	static inline std::shared_ptr<T> Execute(Args&&... args) {
		Allocator<T> allocator;
		return std::allocate_shared<T>(allocator, std::forward<Args>(args)...);
	}
};

테스트
std::allocator, std::pmr::polymorphic_allocator, StaticAllocator, DynamicAllocator (요청할 때 메모리를 할당하여 재사용)
백만번의 컨테이너 요소 삽입과 삭제에서 더 빠른 성능을 보인다.
특정 사이즈의 메모리를 많이 사용할 것을 미리 알 수 있다면, 더 많은 메모리를 미리 할당하여 사용할 때 유리하다.

테스트 코드

Allocator.zip

0.01MB