아래 2 개의 헤더파일은 예전에 회사를 그만두고 나서 집에서 쉬면서 만들었던 코드들입니다.
게임 프로그램은 작은 오브젝트를 여러개 많이 만들 경우가 자주 생깁니다. 필요할때마다 메모리를 할당하고, stl 의 list<T> 같은 자료구조를 사용해서 관리하는 것은 어렵지 않지만, 메모리 동적할당을 많이 하게 되면 성능상의 저하와, 단편화로 인한 메모리의 불안정을 초래하게 됩니다.
그래서 효율을 중시하는 엔진에서는 메모리를 좀 더 소비하고라도 동적할당을 줄이는 방식을 선호하게 되는데 이것에 필요한 클래스 템플릿을 2가지 만들어보았습니다.
첫번째는 pool<T> 입니다. 메모리를 페이지단위 (아래에 보면 8*1024-16) 로 할당해놓고 그 안에서 오브젝트 T를 만들어서 주는 식이며, 오브젝트는 모두 같은 크기를 쓰게 되어있기 때문에 동적할당의 횟수를 크게 줄일 수 있습니다.
두번째는 fixedlist<T> 입니다. stl 의 list<T>와 비슷하지만, 각 노드가 추가될 때 (push_back 등) 노드를 동적생성하는 것이 아니라 자체적인 pool<T> 에서 가져옴으로써, 효율저하를 막도록 하였습니다. 자체적인 pool 은 각 리스트마다 갖고 있게 할 수도 있고, static 으로 선언하여, 동일한 Type 을 갖는 fixedlist 끼리는 pool 을 공유하게 할 수도 있는데, 그것은 상황에 따라 달라지리라 생각합니다. (static 으로 선언하게 되면 소스파일에 따로 선언을 해줘야 합니다)
보잘것 없지만 이 두개의 소스를 공개하는 이유는, 비슷한 것을 만들고자 했던 분들께 참고가 되기를 바람과 동시에, 이 소스에 있을지도 모르는 버그에 대한 지적과 개선점에 대한 의견을 받기 위해서입니다.
이 소스는 공개용, 상업용 프로그램을 개발하는데에 자유롭게 사용하실 수 있습니다. 다만 이 소스를 다른 웹사이트나 책, 기타수단을 이용해 인용, 게제할 때에는 원작자의 출처를 밝혀주시기 바랍니다.
이 소스는 하단의 Reference 에서 밝힌 바와 같이, The C++ Programming Language 책과, ChrisC 의 튜토리얼, VC6 STL 소스코드등을 참고하여 만들었습니다.
--------------
<pool.h>
#ifndef __POOL
#define __POOL
// pool<T>
// -------
//
// Purpose: 메모리 단편화를 줄이기 위해 커다란 영역의 메모리를 미리 할당해놓고 (as list of chunk)
// 그 메모리 안에서 오브젝트를 O(1) 로 할당, 해제하도록 한다
//
// Usage: testPool.cpp 참조
//
// Warning: 사용하려고 하는 클래스의 인스턴스의 크기가 chunk::size 보다 크면 안된다
//
// Note: 템플릿을 이용하도록 함
// 싱글턴 풀 생성과, 개체들의 자동 생성, 소멸을 위한 보조 매크로
// DECLARE_POOL 매크로를 이용해서 자동 관리를 하는 경우 컴파일러는 (C4291) 경고메시지를
// 발생한다. 이것을 막으려면 throw() 를 생성자에 붙여주면 된다. testPool.cpp line 8 참조
//
// Todo: --
//
// Reference: [1] Bjarne Stroustrup's The C++ Programming Language
// [2] Flipcode: ChrisC's object pool lite
//
// History: neolith note 에 warning 제거법 2 줄 추가
template <class T>
class pool {
public:
pool();
~pool();
void * Alloc();
void Free(void *b);
private:
struct link { link *next; };
struct chunk {
enum { size = 8*1024-16 };
char mem[size];
chunk * next;
};
const unsigned int esize;
chunk * m_chunks;
link * m_head;
pool(pool &);
void operator = (pool &);
void Grow();
};
template <class T>
inline pool<T> :: pool()
: esize(sizeof(T)<sizeof(link)?sizeof(link):sizeof(T))
{
m_head = 0;
m_chunks = 0;
}
template <class T>
inline pool<T> :: ~pool()
{
chunk * n = m_chunks;
while (n) {
chunk * p = n;
n = n->next;
delete p;
}
}
template <class T>
inline void * pool<T> :: Alloc()
{
if (m_head == 0)
Grow();
link * p = m_head;
m_head = p->next;
return p;
}
template <class T>
inline void pool<T> :: Free(void *b)
{
link * p = static_cast<link *>(b);
p->next = m_head;
m_head = p;
}
template <class T>
inline void pool<T> :: Grow()
{
chunk * n = new chunk;
n->next = m_chunks;
m_chunks = n;
const int nelem = chunk::size/esize;
char * start = n->mem;
char * last = &start[(nelem-1)*esize];
for (char *p = start; p<last; p+=esize)
reinterpret_cast<link *>(p)->next = reinterpret_cast<link *>(p+esize);
reinterpret_cast<link *>(last)->next = 0;
m_head = reinterpret_cast<link *>(start);
}
// 간단하게 풀 컨테이너 (singleton) 를 선언하고
// 모든 오브젝트의 생성, 소멸을 풀에서 관리하도록 해주는 매크로
// [2] 참조
#define DECLARE_POOL(classname)
public:
void* operator new(size_t size) { return g_pool.Alloc(); }
void operator delete(void* ptr, size_t size) { g_pool.Free(ptr); }
static pool<classname> g_pool;
#define DEFINE_POOL(classname)
pool<classname> classname::g_pool;
#endif
-------------
<fixedlist.h>
#ifndef __FIXEDLIST
#define __FIXEDLIST
// fixedlist<T>
// ------------
//
// Purpose: list 와 pool_allocator 의 결합된 형태.
// 양방향 iterator 를 지원. 메모리 단편화를 유발하지 않는 빠른 할당, 해제, 순차탐색이 특징
//
// Usage: 주로 객체 관리자용으로 사용된다. testFixedlist.cpp 참조
//
// Warning: stl style 로 씌여졌으나 pooling 을 하는 자체 allocator 를 사용한다
// for_each 말고는 알고리즘을 쓸 일이 별로 없을 듯 (주로 포인터를 담기 위한 용도이므로)
//
// Note: 원래는 stl list 와 pool_alloc 을 조합해 사용하려 하였으나, list 에서 node 를 alloc 하는 부분 때문에
// 정확한 pool_alloc 의 구현이 불가능함 (VC6, SGI 공통으로 node 를 할당하는 allocate 와 item을 할당하는
// allocate 가 혼재되어 있음)
// 내부적인 pooling 은 pool<T> 를 사용
//
// Todo: 좀 더 상세한 테스트를 만들어야 함
//
// Reference: visual C++ 기본 STL 의 list 파일을 참고하여 만듬
//
// History: neolith 작성함
// placement new 를 할때 #include <new> 를 해야 한다는 사실을 알았음
#include <new>
#include "pool.h"
template <class T>
class fixedlist {
private:
struct node;
typedef node * nodePtr;
struct node {
nodePtr prev,next;
T value;
};
static pool<node> m_pool;
nodePtr m_head;
size_t m_size;
public:
class iterator;
fixedlist() : m_head(AllocNode()), m_size(0) {}
fixedlist(iterator f, iterator l) : m_head(AllocNode()), m_size(0) { insert(begin(), f, l); }
fixedlist(const fixedlist<T> &x) : m_head(new node), m_size(0) { insert(begin(), x.begin(), x.end()); }
fixedlist<T> & operator=(const fixedlist<T> &x) { if (this != &x) {/* copy from x */ } }
~fixedlist() { erase(begin(), end()); FreeNode(m_head); m_head = 0; m_size = 0; }
class iterator {
public:
iterator() {}
iterator(nodePtr p) : m_ptr(p) {}
iterator(iterator &x) : m_ptr(x.m_ptr) {}
T & operator *() const {return (*m_ptr).value;}
iterator & operator++() {
m_ptr = m_ptr->next;
return *this;
}
iterator operator++(int) {
iterator tmp = *this;
++*this;
return tmp;
}
iterator & operator--() {
m_ptr = m_ptr->prev;
return *this;
}
iterator operator--(int) {
iterator tmp = *this;
--*this;
return tmp;
}
bool operator==(const iterator &x) const { return m_ptr == x.m_ptr; }
bool operator!=(const iterator &x) const { return !(*this == x); }
nodePtr GetNode() const { return m_ptr; }
private:
nodePtr m_ptr;
};
iterator begin() const { return iterator(m_head->next); }
iterator end() const { return iterator(m_head); }
size_t size() const { return m_size; }
bool empty() const { return (size() == 0); }
iterator insert(iterator p, const T&x = T()) {
nodePtr s = p.GetNode();
s->prev = AllocNode(s, s->prev);
s = s->prev;
s->prev->next = s;
Construct(&s->value, x);
++m_size;
return s;
}
void insert(iterator p, size_t m, const T&x) {
for(; 0<m; --m)
insert(p, x);
}
void insert(iterator p, const T *f, const T *l) {
for(; f!=l; ++f)
insert(p, *f);
}
void insert(iterator p, iterator f, iterator l) {
for(; f!=l; ++f)
insert(p, *f);
}
iterator erase(iterator p) {
nodePtr s = (p++).GetNode();
s->prev->next = s->next;
s->next->prev = s->prev;
Destroy(&s->value);
FreeNode(s);
--m_size;
return p;
}
iterator erase(iterator f, iterator l) {
while (f != l)
erase(f++);
return f;
}
void resize(size_t n, T x = T()) {
if (size() < n)
insert(end(), n-size(), x);
else
while(n<size())
pop_back();
}
void clear() { erase(begin(), end()); }
void push_front(const T& x) { insert(begin(), x); }
void pop_front() { erase(begin()); }
void push_back(const T& x) { insert(end(), x); }
void pop_back() { erase(--end()); }
void assign(iterator f, iterator l) { clear(); insert(begin(), f, l); }
void assign(size_t n, const T &x = T()) { clear(); insert(begin(), n, x); }
private:
nodePtr AllocNode(nodePtr nextarg = 0, nodePtr prevarg = 0) {
nodePtr s = (nodePtr)m_pool.Alloc();
s->next = (nextarg != 0) ? nextarg : s;
s->prev = (prevarg != 0) ? prevarg : s;
return s;
}
void FreeNode(nodePtr s) {
m_pool.Free(s);
}
void Construct(T *p, const T&val) { new (p) T(val); }
void Destroy(T *p) { p->~T(); }
};
#endif
----
<testPool.cpp>
#include "pool.h"
#include <list>
using namespace std;
struct foo {
public:
foo() throw() { puts("foo::ctor"); }
~foo() { puts("foo::dtor"); }
private:
DECLARE_POOL(foo)
int a;
int b[100];
};
DEFINE_POOL(foo)
void TestPool()
{
typedef list<foo *> fooList;
fooList l;
for (int i=0; i<10; i++)
l.push_back(new foo);
fooList :: iterator it = l.begin();
while (it!=l.end()) {
(*it)->a = 0;
it++;
}
it = l.begin();
while (it!=l.end()) {
delete *it;
it++;
}
l.clear();
}
----
<testFixedlist.cpp>
#include "fixedlist.h"
#include <stdio.h>
typedef fixedlist <int> intlist;
pool<intlist::node> intlist::m_pool;
void printlist(const intlist &a)
{
intlist :: iterator it = a.begin();
while (it != a.end()) {
printf("%d ", *it);
++it;
}
printf("n");
}
void TestFixedlist()
{
// basic test
intlist a;
printf("now size of a is %dn", a.size());
puts("adding 10 members");
for (int i=0; i<10; i++)
a.push_back(i);
printf("now size of a is %dn", a.size());
puts("printing");
printlist(a);
puts("erasing");
a.erase(a.begin());
a.erase(a.begin());
a.erase(a.begin());
printlist(a);
printf("now size of a is %dn", a.size());
// insert test
intlist :: iterator it = a.begin();
a.insert(it, 999);
it++;
it++;
it++;
a.insert(it, 999);
it = a.end();
a.insert(it, 999);
printlist(a);
puts("clearing");
a.clear();
printf("now size of a is %dn", a.size());
}
잘 쓸게요. 그리고 혹시나 버그나 오류를 발견하면 알려드릴께요.