メモリプール - きままにブログ

概要

固定長メモリプールを再び作った。
簡易unique_ptr, shared_ptrを自作し、速度の向上を図った。
普通にunique_ptr, shared_ptrを使用するよりも2～3倍の実行速度が得られた。

実装について

簡易shared_ptrであるSharedPtrを使用することを前提としたメモリプールSharedPoolと、共有を前提としない、UniquePoolを用意した。それぞれは共通部分のPoolを基底としているがポリも―フィックな動作をしないのでvirtualにしていない。また、SharedPoolはその特性上、参照カウンタ及び親のポインタを保存するためのメモリを余分に確保していることに注意されたい。一方でUniquePoolはメモリ上のオーバーヘッドはないが、UniquePtrを使用するためのオーバーヘッドが幾分かある。

簡単に言うと、大きなメモリブロックをリンクリストでつないでそこから切り出し、使わなくなったメモリはstd::stackにいれて再利用をしている。ページの減少は実装していない。参照カウンタ方式はPointerクラスとしてその実態と参照カウンタを合わせてこれを単位とする。メモリの切り出し1回につき参照カウンタも一緒に生成するためコストの低減に繋がる。

使用例

mytools::SharedPool<C> pool; // (1)
using sptr = decltype(pool)::SharedPtr; // (2)

std::array<sptr, 32> list2; // (3)
for (int i = 0; i < 100; ++i) {
	auto s = pool.make_shared(i);  // (4)
	list2[(何らかの乱数)] = std::move(s); // (5)
}

まず、(1)でひとまとまりのメモリを確保する。初期値は128個であるが、テンプレート引数に入れることで可変に出来る。なお、今回の実験ではこれを変えたところであまり優位な差は得られなかった。(2)では簡易スマートポインタの型を取得している。各プールごとに型が異なるので、必要ならばこのようにする必要がある。(3)では32個のスマートポインタを保存する配列を作っている。今回はこの配列に生成したデータをランダムに入れて検証している。この例では(4)でデータを生成し、(5)でランダムに配列に突っ込む。既にある場合は参照カウントが0になって消滅し、新しいオブジェクトが入ることになる。従って高々32個のオブジェクトしか存在し得ないことになる。

ベンチマーク結果

Visual Studio 2017 RC Release (--std:C++ latest)で実験を行った。

std::shared_ptrのみ : 163[ms]
メモリプール&SharedPtr : 58[ms]

このようにメモリプールを使用すると確保の時間が低減される。大量のオブジェクトを使い回すようなプログラム、すなわち個数の上限はある程度決まっているが、寿命が異なる場合などには有用だと思われる。なお、スマートポインタを使用しないでnew-delete/メモリプールの比較、unique_ptr/メモリプール&UniquePtrの比較も行ったが、いずれも当たり前なのだがメモリプール仕様の方が2～3倍高速に動いた。

class C {
public:
	C(int n) : n { n } { }
	~C() { }
	int buffer[256];
	int n;
};
int main() {
	constexpr int n = 64;

	std::random_device rd;
	std::mt19937 mt(rd());
	std::uniform_int<> ui { 0, n - 1 };
	const int N = 1000000;
	
	auto start = std::chrono::system_clock::now();
	std::array<std::shared_ptr<C>, n> list;
	for (int i = 0; i < N; ++i) {
		auto s = std::make_unique<C>(i);
		list[ui(mt)] = std::move(s);
	}
	auto end = std::chrono::system_clock::now();
	std::cout << "1:" << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "[ms]" << std::endl;

	mytools::SharedPool<C> pool;
	using sptr = decltype(pool)::SharedPtr;

	start = std::chrono::system_clock::now();
	std::array<sptr, n> list2;

	for (int i = 0; i < N; ++i) {
		auto s = pool.make_shared(i);
		list2[ui(mt)] = std::move(s);
	}
	end = std::chrono::system_clock::now();

	std::cout << "2:" << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "[ms]" << std::endl;

	system("pause");
	return 0;
}

実装

#pragma once

#include <stack>
#include <memory>

namespace mytools {
	template <typename T, size_t SIZE = 128>
	class Pool {
	protected:
		template <typename T>
		struct Storage {
			Storage()
				: next { nullptr } {}
			T& operator[](int no) {
				return (reinterpret_cast<T*>(static_cast<void*>(buffer)))[no];
			}
			Storage* makeNext() {
				next = new Storage {};
				return next;
			}
			~Storage() {
				delete next;
			}
		private:
			char buffer[SIZE * sizeof(T)];
			Storage* next;
		};

		template <typename T>
		class StorageManager {
		public:
			StorageManager() : position { 0 } {
				last_storage = &storage;
			}

			template <typename ...Args>
			T* make(Args&& ...args) {
				T* ret;

				if (free_list.empty()) {
					ret = &(*last_storage)[position];

					++position;

					if (position >= SIZE) {
						last_storage = storage.makeNext();
						position = 0;
					}

					new(ret)T { std::forward<Args>(args)... };
				}
				else {
					ret = free_list.top();
					new(ret)T { std::forward<Args>(args)... };
					free_list.pop();
				}

				return ret;
			}
			void free(T* it) {
				it->~T();
				free_list.push(it);
			}

		private:
			Storage<T> storage;
			Storage<T>* last_storage;
			std::stack<T*> free_list;
			size_t position;
		};
	};

	template <typename T, size_t SIZE = 128>
	class SharedPool : Pool<T, SIZE> {
	public:
		class Pointer;

	private:
		class Reference {
		public:
			Reference(SharedPool* pool)
				: counter { 1 }, pool { pool } { }

			void increment() {
				++counter;
			}
			void decrement() {
				--counter;
			}
			void release(Pointer* pointer) {
				if (counter == 0) {
					pool->free(pointer);
				}
			}
		private:
			size_t counter;
			SharedPool* pool;
		};
	public:
		class Pointer {
		public:
			template <typename... Args>
			Pointer(SharedPool* pool, Args&& ...args)
				: t { std::forward<Args>(args)... },
				reference { pool } {}

			T& operator*() {
				return t;
			}
			T const& operator*() const {
				return t;
			}
			T* operator->() {
				return &t;
			}
			T const* operator->() const {
				return &t;
			}

			T t;
			Reference reference;
		};

		class SharedPtr {
		public:
			SharedPtr(Pointer* pointer) : pointer { pointer } { }
			SharedPtr() : SharedPtr { nullptr } {}

			SharedPtr(SharedPtr const& it)
				: pointer { it.pointer } {
				it.~SharedPtr();
				pointer->reference.increment();
			}

			SharedPtr(SharedPtr&& it)
				: SharedPtr { it } {
				it.~SharedPtr();
				it.pointer = nullptr;
			}

			SharedPtr& operator=(SharedPtr const& it) {
				return *new(this) SharedPtr { it };
			}

			SharedPtr& operator=(SharedPtr&& it) {
				return *new(this) SharedPtr { std::forward<SharedPtr>(it) };
			}

			~SharedPtr() {
				if (pointer != nullptr) {
					pointer->reference.decrement();
					pointer->reference.release(pointer);
				}
			}

			T& operator*() {
				return pointer->t;
			}
			T const& operator*() const {
				return pointer->t;
			}

			T* operator->() {
				return &pointer->t;
			}
			T const* operator->() const {
				return &pointer->t;
			}

			T* data() {
				return &pointer->t;
			}

			T const* data() const {
				return &pointer->t;
			}
		private:
			Pointer* pointer;
		};
		template <typename ...Args>
		auto make_shared(Args&& ...args) {
			Pointer* pointer = make(std::forward<Args>(args)...);
			return SharedPtr { pointer };
		}

		template <typename ...Args>
		Pointer* make(Args&& ...args) {
			return storage_manager.make(this, std::forward<Args>(args)...);
		}

		void free(Pointer* it) {
			storage_manager.free(it);
		}
	private:
		StorageManager<Pointer> storage_manager;
	};

	template <typename T, size_t SIZE = 128>
	class UniquePool : Pool<T, SIZE> {
		class UniquePtr {
		public:
			UniquePtr(T* pointer, Pool* pool)
				: pointer { pointer }, pool { pool } { }
			UniquePtr() : UniquePtr { nullptr, nullptr } {}

			UniquePtr(UniquePtr const& it) = delete;

			UniquePtr(UniquePtr&& it) : pointer { it.pointer }, pool { it.pool } {
				it.~UniquePtr();
				it.pointer = nullptr;
			}

			UniquePtr& operator=(UniquePtr const& it) = delete;

			UniquePtr& operator=(UniquePtr&& it) {
				return *new(this) UniquePtr { std::forward<UniquePtr>(it) };
			}

			~UniquePtr() {
				if (pointer != nullptr) {
					pool->free(pointer);
				}
			}

			T& operator*() {
				return *pointer;
			}
			T const& operator*() const {
				return *pointer;
			}

			T* operator->() {
				return pointer;
			}
			T const* operator->() const {
				return pointer;
			}

			T* data() {
				return pointer;
			}

			T const* data() const {
				return pointer;
			}

		private:
			T* pointer;
			Pool* pool;
		};

		template <typename ...Args>
		auto make_unique(Args&& ...args) {
			return UniquePtr { make(std::forward<Args>(args)...), this };
		}

		template <typename ...Args>
		T* make(Args&& ...args) {
			return storage_manager.make(std::forward<Args>(args)...);
		}

		void free(T* it) {
			storage_manager.free(it);
		}

	private:
		StorageManager<T> storage_manager;
	};
}