Article:MemPoolSize

From IdeA thinKING

Contents 1 MemPoolSize - 비슷한 크기의 클래스들끼리 같은 Pool을 쓰는 MemPool 1.1 서론 1.2 상세 구현 1.2.1 Singleton 사용 1.2.2 Pool들의 크기 1.2.3 MemPoolSize 구현 1.2.4 size_helper 1.2.5 다시 MemPoolSize 구현 1.3 사용 예제 1.4 마무리

MemPoolSize - 비슷한 크기의 클래스들끼리 같은 Pool을 쓰는 MemPool

서론

이제 마지막으로 가장 복잡하고 가장 범용적인 MemPool인 MemPoolSize에 대해 알아보겠습니다. 몇몇 프로젝트에서 앞에서 작성한 MemPoolClass와 MemPoolShare들을 사용하여 본 후 매우 마음에 들었다고 가정합니다. 이제 프로젝트의 모든 클래스들을 MemPool에서 상속받아 사용하려고 합니다. 하지만 이 경우 몇가지 문제가 있습니다.

먼저 MemPoolClass를 사용할 경우 각 클래스는 자신만의 pool을 가지게 됩니다. 문제는 동시에 한 두개의 instance만 필요한 클래스들도 모두 50개(default)씩의 메모리를 차지하게 된다는 것입니다. 물론 사용자가 클래스의 종류에 따라 적당한 값을 줄 수는 있지만 어떤 클래스가 몇개나 사용될지 미리 알기도 어려울 것입니다.

그리고 MemPoolShare의 경우는 모든 클래스중에 가장 큰 클래스의 크기를 기준으로 해야 하므로 메모리 낭비가 너무 심합니다.

따라서 크기별로 pool을 몇개 만들어 놓고 특정 클래스는 이 pool들 중 자신의 크기에 적당한 pool을 사용하는 MemPool을 만들어 보도록 하겠습니다. 이때 자신의 크기에 적당한 pool을 찾는 작업은 모두 컴파일 시간에 하여 runtime overhead는 전혀 없도록 작성합니다.

상세 구현

Singleton 사용

먼저 고려할 사항은 이번에 만들 MemPool은 특정 클래스에 따라 구현을 다르게 사용하는 것이 아니라 공통 구현을 모든 클래스가 사용해야 합니다. 따라서 이 공통 구현을 위해 MemPool을 다루는 Singleton 객체가 필요합니다. 여기서는 Singleton 구현을 위해 간단한 SingletonHolder 클래스를 만들어 사용합니다. Modern C++ Design 에 나왔던 것과 같은 기능이 많은 클래스를 가져와 사용할 수도 있으나 여기서 사용할 SingletonHolder는 많은 기능이 필요하지 않기 때문에 간단하게 만들었습니다.

template <class T, class LockModel>
class SingletonHolder : public LockModel
{
 public:
  static T* instance() {
    if (pthis_ == 0) {
      Lock lk; lk;
      if (pthis_ == 0) {
        pthis_ = new T;
      }
    }
 
    return pthis_;
  }
       
private:
  SingletonHolder();
  ~SingletonHolder();
  SingletonHolder(const SingletonHolder& );
  SingletonHolder& operator=(const SingletonHolder& );
 
  static T* pthis_;
};
 
template <class T, class LockModel>
T* SingletonHolder<T, LockModel>::pthis_;

코드에서 보이는 바와 같이 매우 간단한 코드입니다. LockModel을 사용하여 Double-Checked-Locking 패턴을 사용했습니다. (실제 코드에서는 [1], [2]를 참고하여 memory barrier를 같이 사용합니다.)

이 SingletonHolder를 사용하여 다음과 같이 공통으로 사용할 MemPool 구현을 만듭니다. 여기서는 구현 클래스의 이름을 ChunkAllocatorImpl이라고 하였습니다.

template <
  ...
  class LockModel
>
class ChunkAllocatorImpl : public LockModel
{

그리고 Singleton으로 사용할때는 다음과 같이 선언하여 사용합니다.

typedef SingletonHolder<ChunkAllocatorImpl, LockModel> ChunkAllocator;

Pool들의 크기

다음으로 고려할 사항은 pool들을 만들때 어떤 기준으로 크기를 잡을까 하는 것입니다. 여기서는 사용자가 pool의 최소, 최대 크기를 지정할 수 있는 다음과 같은 방법을 사용합니다.

• 사용자는 최소, 최대 크기만을 지정합니다.
• 먼저 pool의 크기가 최소값인 pool을 만듭니다.
• 앞의 크기에 2를 곱한 크기의 pool을 만듭니다.
• 위를 크기가 최대값이 될때까지 반복하여 pool을 만듭니다.

즉, 최소값이 32, 최대값이 4096일 경우 다음과 같은 크기를 가진 8개의 pool이 만들어집니다.

 32, 64, 128, 256, 512, 1024, 2048, 4096

이 방법을 사용하기 위해 최대값은 최소값의 2의 자승으로 표현되는 숫자여야 합니다. (4096 = 32 * 2⁷)

그럼 사용자로부터 최소값, 최대값을 받았을 때 몇개의 pool이 필요한지를 컴파일 시간에 알려면 어떻게 해야 할까요? 간단하게 4096을 계속 2로 나누어 32가 되려면 몇 번이나 나누어야 되는지를 계산한 후 1을 더하면 됩니다.

이를 수식으로 표현하면 다음과 같습니다.

 log2(4096) / log2(32) + 1 = log2(4096 / 32) + 1

위 식을 컴파일 시간에 계산하기 위해 다음과 같이 log₂를 계산해 주는 template meta function을 만듭니다.

template <int N>
struct log_2
{
  BOOST_STATIC_ASSERT(N % 2 == 0); 
 
  enum {
    value = 1 + log_2<N / 2>::value
  };
}; 
 
template <>
struct log_2<2>
{
  enum {
    value = 1
  };
};

두번째 template specialization은 loop를 멈추기 위해 필요합니다. 만약 위의 함수에서 N이 홀수라면 2의 자승으로 표현되지 않는 숫자임을 나타내므로 컴파일 에러를 발생시키기 위해 BOOST_STATIC_ASSERT를 사용합니다.

이 함수를 사용하여 다음과 같이 POOL_COUNT를 정의하고 이 값을 이용하여 값들의 배열을 선언합니다.

template <
  int MIN_SIZE,
  int MAX_SIZE,
  int OBJS_IN_A_BLOCK,
  class LockModel
>
class ChunkAllocatorImpl : public LockModel
{
public:
  enum {
    POOL_COUNT = log_2<MAX_SIZE / MIN_SIZE>::value + 1
  };
 
  ChunkAllocatorImpl();
 
  void* allocate(size_t real_size, size_t size, int index);
  void deallocate(void* p, size_t real_size, size_t size, int index);
 
  size_t capacity(int index) const;
  size_t size(int index) const;
  void reserve(int index, size_t size);
 
private:
  void allocate_block(size_t size, int index);
 
  unsigned char* free__[POOL_COUNT];
  size_t capacity__[POOL_COUNT];
  size_t size__[POOL_COUNT];
};

이 ChunkAllocatorImpl 클래스는 기존의 MemPoolClass나 MemPoolShare를 구현할때 사용했던 방법을 그대로 사용합니다. capacity, size, reserve 함수들은 이전과 동일한 구현을 사용하나 어떤 index에 있는 pool을 사용할지를 알려주는 인자를 추가로 가지고 있습니다.

그리고 allocate나 deallocate는 기존 MemPool의 new, delete에 해당하는 것으로 real_size 인자는 실제 클래스의 크기를 나타내고 index는 지금 이 함수에서 사용해야 할 pool의 index를, 그리고 size는 이 index에서 쓰이고 있는 크기를 나타냅니다.

예를 들어 100바이트짜리 클래스가 생성되고 있다면 다음과 같은 인자를 가지고 allocate가 불리게 됩니다.

allocate(100, 128, 2);

생성자에서는 각 멤버 변수들을 초기화해줍니다. 클래스의 static 멤버 변수와는 달리 일반 멤버 변수는 초기화가 자동으로 되지 않기 때문에 생성자에서 반드시 해주어야 합니다.

나머지 세부적인 구현은 기존과 동일하기 때문에 설명은 생략하겠습니다.

마지막으로 ChunkAllocatorImpl을 Singleton 객체로 사용하는 ChunkAllocator 클래스를 다음과 같이 구현합니다. 이 클래스는 나중에 MemPoolSize의 template parameter로 사용됩니다.

template <
  int MIN_SIZE,
  int MAX_SIZE,
  int OBJS_IN_A_BLOCK,
  class LockModel
>
class ChunkAllocator
{
public:
  typedef ChunkAllocatorImpl<
    MIN_SIZE,
    MAX_SIZE,
    OBJS_IN_A_BLOCK,
    LockModel
  > ImplType;
 
  typedef SingletonHolder<
    ImplType,
    LockModel
  > Allocator;
 
  static void* allocate(size_t real_size, size_t size, int index) {
    return Allocator::instance()->allocate(real_size,
                                           size,
                                           index);
  }
  static void deallocate(void* p, size_t real_size, size_t size, int index) {
    Allocator::instance()->deallocate(p,
                                      real_size,
                                      size,
                                      index);
  }
};

단순히 함수가 불리면 ChunkAllocatorImpl로 작업을 넘기는 클래스임을 알 수 있습니다.

MemPoolSize 구현

다음으로 실제 클래스들이 상속받아 사용할 MemPoolSize의 구현을 살펴보겠습니다. 여기서 ChunkAllocator 인자는 위에서 구현한 ChunkAllocator 클래스를 나타내며 default값으로 최소값 32, 최대값 4096을 사용하고 있습니다.

template <
  class T,
  class ChunkAllocator = ChunkAllocator<32, 4096, 50, NoLock>
>
class MemPoolSize
{
 public:
  static void* operator new (size_t size);
  static void operator delete (void* p, size_t size);
protected:
  ~MemPoolSize() {}
};

만약 이때 상속받은 클래스의 크기가 최대값인 4096바이트를 넘는 경우에는 어떻게 해야 할까요? 여기서는 이런 경우 default new, delete를 사용하도록 구현합니다. 이를 위해 다음과 같은 DefaultAllocator 클래스를 구현합니다.

class DefaultAllocator
{
public:
  static void* allocate(size_t real_size, size_t , int ) {
    return ::operator new(real_size);
  }
  static void deallocate(void* p, size_t , size_t , int ) {
    ::operator delete(p);
  }
};

위에서 만든 ChunkAllocator와 같은 문법을 사용하는 allocator, deallocator 함수를 가지고 있으며 하는 일은 단순히 ::operator new와 ::operator delete를 호출해주는 것입니다.

그럼 어떻게 컴파일 시간에 DefaultAllocator를 부를지 ChunkAllocator를 부를지 결정할 수 있을까요?

size_helper

여기서 잠시, 위에서 알아본 내용들을 구현하려면 사용자로부터 입력받은 최소값과 최대값을 가지고 특정 크기가 최대값을 넘는지, 또는 최대값을 넘지 않는다면 몇번 index의 pool을 사용해야 하는지, 그리고 그 pool의 크기는 얼마인지등을 컴파일 시간에 알 수 있는 방법이 필요합니다.

즉, 최소값 32, 최대값 4096을 사용한다면 다음과 같이 입력값에 대한 출력이 나오는 방법이 필요합니다.

입력값	over_size	index	size
100	false	2	128
300	false	4	512
5000	true	x	x

이 값들을 컴파일 시간에 구하기 위해 아래와 같은 template meta function을 구현합니다.

template <int SIZE, int N, int MAX_SIZE>
struct size_helper_impl
{
  enum
  {
    size      = (SIZE < N ? N : size_helper_impl<SIZE, 2 * N, MAX_SIZE>::size),
    index     = (SIZE < N ? 0 : 1 + size_helper_impl<SIZE, 2 * N, MAX_SIZE>::index),
    over_size = (SIZE > MAX_SIZE ? 1 : 0)
  };
};
 
template <int SIZE, int MAX_SIZE>
struct size_helper_impl<SIZE, MAX_SIZE, MAX_SIZE>
{
  enum
  {
    size      = MAX_SIZE,
    index     = 0,
    over_size = 1
  };
};

위의 코드에서 N은 최초 입력시엔 MIN_SIZE가 입력되며 이 값이 MAX_SIZE가 될때까지 2를 곱합니다. 두번째 template specialization은 N이 MAX_SIZE가 되면 loop를 멈추기 위해 필요합니다. 이런 방법은 처음 보기엔 조금 복잡해 보이지만 하나씩 손으로 따라가다 보면 쉽게 이해됩니다.

여기서 사용자에 의해 입력된 MIN_SIZE와 MAX_SIZE는 ChunkAllocator에서 알 수 있으므로 ChunkAllocator에 다음과 같이 size_helper를 size_helper_impl을 사용하여 정의합니다.

template <
  int MIN_SIZE,
  int MAX_SIZE,
  int OBJS_IN_A_BLOCK,
  class LockModel
>
class ChunkAllocator
{
public:
  ...
  template <int SIZE>
  struct size_helper
  {
    typedef detail::size_helper_impl<SIZE, MIN_SIZE, MAX_SIZE> type;
  };
  ...

다시 MemPoolSize 구현

그럼 위에서 만든 size_helper를 사용하여 MemPoolSize를 구현해보도록 하겠습니다. 먼저 size_helper의 over_size가 true인 경우, 즉 사용할 클래스의 크기가 MAX_SIZE보다 클 경우에는 DefaultAllocator, 작을 경우에는 ChunkAllocator를 사용해야 하므로 다음과 같은 type_selector가 필요합니다.

template <bool flag, class T1, class T2>
struct type_selector
{
  typedef T1 type;
};
 
template <class T1, class T2>
struct type_selector<false, T1, T2>
{
  typedef T2 type;
};

위와 같이 type_selector를 만들어서 사용해도 그리 어렵지는 않으나 위와 똑같은 작업을 하는 타입이 이미 boost::mpl에 if_c라는 이름으로 정의되어 있습니다 따라서 여기서는 boost::mpl::if_c 를 사용합니다.

static void* operator new (size_t size) {
 typedef typename ChunkAllocator::size_helper<sizeof(T)>::type size_helper;
 typedef typename boost::mpl::if_c<
   size_helper::over_size,
   detail::DefaultAllocator,
   ChunkAllocator
 >::type Allocator;
 
 return Allocator::allocate(size,
                            size_helper::size,
                            size_helper::index);
}
 
static void operator delete (void* p, size_t size) {
  if (p == 0) return;
 
  typedef typename ChunkAllocator::size_helper<sizeof(T)>::type size_helper;
  typedef typename boost::mpl::if_c<
    size_helper::over_size,
    detail::DefaultAllocator,
    ChunkAllocator
  >::type Allocator;
 
  Allocator::deallocate(p,
                        size,
                        size_helper::size,
                        size_helper::index);
}

사용 예제

간단한 사용 예제들을 살펴 보겠습니다. 아래와 같이 네개의 클래스를 정의합니다.

struct A : MemPoolSize<A>
{
  char buf[10];
};
 
struct B : MemPoolSize< B>
{
  char buf[30];
};
 
struct C : MemPoolSize<C>
{
  char buf[200];
};
 
struct D : MemPoolSize<D>
{
  char buf[5000];
};
 
new A;
new B;
new C;
new D;
 
A::get_impl()->print();

그리고 위의 코드를 실행시키면 다음과 같은 결과를 얻을 수 있습니다.

ChunkSize	ObjSize	PoolSize
32	2	50
64	0	0
128	0	0
256	1	50
512	0	0
1024	0	0
2048	0	0
4096	0	0

물론 A, B는 0번째 index에 C는 3번째 index에 그리고 D는 ChunkAllocator가 아닌 DefaultAllcator로 생성되어 위의 결과에 포함되지 않았음을 알 수 있습니다. 여기서 get_impl() 함수는 디버깅을 쉽게 하기 위해 MemPoolSize에서 제공하는 함수입니다. 내부적으로 그 클래스가 사용하고 있는 ChunkAllocatorImpl 포인터를 리턴합니다. 따라서 A::get_impl()이나 B::get_impl(), C::get_impl()은 모두 같은 포인터를 리턴합니다.

물론 DefaultAllocator에는 get_impl()이 정의되어 있지 않으므로 D::get_impl() 함수를 호출하면 컴파일 에러가 발생합니다.

마무리

이번에 만들어 본 MemPoolSize는 Modern C++ Design의 SmallObj와 그 구조는 유사하나 구현 방향은 많이 다릅니다. 가장 다른 점은 SmallObj는 사용자의 편이성을 위해 runtime overhead를 감수하였고 MemPoolSize는 사용의 편이성을 조금 낮춰 runtime overhead를 완전히 제거했다는 점입니다.

여기서 편이성을 낮췄다는 의미는 MemPoolSize 클래스는 항상 leaf 클래스에서 사용되어야 한다는 것입니다. SmallObj는 제일 상위의 base 클래스에서 상속받아 놓으면 그 이하의 클래스에서는 신경쓰지 않아도 되지만 MemPoolSize는 항상 leaf 클래스에서 상속을 받아 사용해야 합니다. 만약 그렇지 않은 경우 allocate에서 assertion 에러를 발생하게 됩니다. (실제 클래스의 크기가 pool의 크기보다 큰 경우입니다.)

마지막으로 현재 구현된 MemPoolSize는 사용하고자 하는 환경에 따라 다양한 개선 사항이 있을 수 있습니다. 예를 들어 현재 2의 자승으로 생성되는 pool 들을 2의 곱으로 생성한다던가 하는 식입니다. (즉, 32, 64, 128, ... 이런 식으로 생성되는 것이 아니라 32, 64, 96, 128, ... 으로 생성.) 연습삼아 해보시면 좋을 것 같습니다.

그럼 이것으로 MemPool 강좌를 마치겠습니다. 끝까지 읽어주셔서 감사합니다.