Skip to main content

C++ of the Day #22 - MemPool 클래스 개선 (switch-case문 제거)

(까막님의 downcast overloading 글에서 아이디어를 얻어 작성하였습니다.)

이전에 MemPool 클래스를 작성할 때 마음엔 안들지만 방법을 찾지 못해 그냥 두었던 부분이 하나 있었습니다.

실제 코드를 읽기 쉽게 간단히 다시 써보았습니다. ((log_2와 power_2는 다음과 같이 간단히 구현되어 있습니다.
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 <std::size_t n>
struct power_2
{
  enum {
    value = 2 * power_2<n - 1>::value
  };
};

template <>
struct power_2<0>
{
  enum {
    value = 1
  };
};
))
struct Base
{
};

template <int n>
class Impl : public Base
{
};

template <int max_size, int min_size>
class Allocator
{
public:
  static Base* get_impl(int index) {
    const int POOL_CNT = log_2<max_size, min_size>::value + 1;

    static Base* impl_[POOL_CNT] = { 0 };

    Base* ret = impl_[index];
    if (ret == 0) {
      switch (index) {
      case 0: impl_[index] = new Impl<min_size * power_2<0>::value>; break;
      case 1: impl_[index] = new Impl<min_size * power_2<1>::value>; break;
      case 2: impl_[index] = new Impl<min_size * power_2<2>::value>; break;
      case 3: impl_[index] = new Impl<min_size * power_2<3>::value>; break;
      case 4: impl_[index] = new Impl<min_size * power_2<4>::value>; break;
      }
      ret = impl_[index];
    }

    BOOST_STATIC_ASSERT(POOL_CNT <= 5);
    assert(index < POOL_CNT);

    return ret;
  }
};
간단히 설명하자면 Allocator의 template parameter인 MIN_SIZE와 MAX_SIZE는 16, 256과 같이 2의 자승으로 된 숫자로 MemPool 클래스가 사용할 최소 크기와 최대 크기를 나타냅니다. 이 크기를 가지고 MemPool은 16, 32, 64, 128, 256의 다섯개 크기의 Impl을 사용하게 됩니다. 위의 코드의 get_impl 함수는 index를 가지고 이 크기에 해당하는 Impl 객체를 리턴하는 함수로 아직 해당 Impl 객체가 생성되지 않았다면 new 한 후 리턴해 줍니다. 여기서 문제가 되었던 것은 특정 크기의 Impl을 new하기 위한 switch-case 부분인데 여기를 MIN_SIZE와 MAX_SIZE에 맞게 자동으로 case 구문이 늘어나거나 줄어들도록 만들지 못했었습니다. 그래서 임시 방편으로 BOOST_STATIC_ASSERT로 일단 잘못되면 컴파일 에러가 발생하도록 만들어 놓았었죠. 컴파일 에러가 나면 case를 추가할 수 있도록 말이죠. ;-) 하지만 그때 생각하지 못했던 것은 recursive template을 사용하는 것이었습니다. 아이디어만 떠올랐다면 어렵지 않았을 텐데... 최근에 까막님의 downcast overloading 글을 보고 난 후에야 생각할 수 있었네요. :-| 이 방법을 사용해 수정한 get_impl 함수는 다음과 같습니다.
static Base* get_impl(int index) {
  const int POOL_CNT = log_2<max_size, min_size>::value + 1;

  static Base* impl_[POOL_CNT] = { 0 };

  Base* ret = impl_[index];
  if (ret == 0) {
    ret = impl_[index] = ImplFactory<min_size - 1, pool_cnt>::make(index);
  }

  assert(index < POOL_CNT);

  return ret;
}
그리고 사용된 ImplFactory 클래스는 다음과 같습니다.
template <int min_size, int n>
struct ImplFactory
{
  static Base* make(int index) {
    if (index == N) return new Impl<min_size * power_2<n>::value>;
    return ImplFactory<min_size - 1, n>::make(index);
  }
};

template <int min_size>
struct ImplFactory<min_size, 0> {
  static Base* make(int index) {
    return new Impl<min_size>;
  }
};
이것으로 MemPool 구현에서 가장 맘에 걸리던 부분이 해결되었네요. log_2나 power_2에서 열심히 썼던 recursive template을 사용해서 함수 호출할 생각을 못했다니... 좀 부끄럽습니다. :-(

성능상 기존 방법에 비해 함수 호출에 따른 overhead가 조금 있을 수 있겠지만 매번 호출되는 것이 아니라 각 Impl에 대해 한번씩만 호출되는 것이므로 문제는 없어보입니다. 이런 overhead에 신경쓸 사람도 많지 않겠지만요. :-)

Comments

  1. 도움이 되셨다니 다행이네요 :)
    함수호출 cost가 걱정되면 inline!!! ㅋ

    ReplyDelete
  2. minsize-1이 이 아니라 n-1일 것같네요. 많이 배우고 있습니다:)

    ReplyDelete

Post a Comment

Popular posts from this blog

1의 개수 세기 - 해답

벌써 어제 말한 내일이 되었는데 답을 주신 분이 아무도 없어서 좀 뻘쭘하네요. :-P 그리고 어제 문제에 O(1)이라고 적었는데 엄밀히 얘기하자면 O(log 10 n)이라고 적었어야 했네요. 죄송합니다. ... 문제를 잠시 생각해보면 1~n까지의 수들 중 1의 개수를 얻기 위해서는 해당 숫자 n의 각 자리의 1의 개수가 모두 몇개나 될지를 구해서 더하면 된다는 사실을 알 수 있습니다. 예를 들어 13이라는 수를 생각해 보면 1~13까지의 수에서 1의 자리에는 1이 모두 몇개나 되는지와 10의 자리에는 모두 몇개나 되는지를 구해 이 값을 더하면 됩니다. 먼저 1의 자리를 생각해 보면 1, 11의 두 개가 있으며 10의 자리의 경우, 10, 11, 12, 13의 네 개가 있습니다. 따라서 2+4=6이라는 값을 구할 수 있습니다. 이번엔 234라는 수에서 10의 자리를 예로 들어 살펴 보겠습니다. 1~234라는 수들 중 10의 자리에 1이 들어가는 수는 10, 11, ..., 19, 110, 111, ... 119, 210, 211, ..., 219들로 모두 30개가 있음을 알 수 있습니다. 이 규칙들을 보면 해당 자리수의 1의 개수를 구하는 공식을 만들 수 있습니다. 234의 10의 자리에 해당하는 1의 개수는 ((234/100)+1)*10이 됩니다. 여기서 +1은 해당 자리수의 수가 0이 아닌 경우에만 더해집니다. 예를 들어 204라면 ((204/100)+0)*10으로 30개가 아닌 20개가 됩니다. 이런 방식으로 234의 각 자리수의 1의 개수를 구하면 1의 자리에 해당하는 1의 개수는 ((234/10)+1)*1=24개가 되고 100의 자리에 해당하는 개수는 ((234/1000)+1)*100=100이 됩니다. 이들 세 수를 모두 합하면 24+30+100=154개가 됩니다. 한가지 추가로 생각해야 할 점은 제일 큰 자리의 수가 1인 경우 위의 공식이 아닌 다른 공식이 필요하다는 점입니다. 예를 들어 123에서 100의 자리에 해당하는 1의 개수는 ((123/1...

CodeHighlighter plugin test page.

This post is for testing CodeHighlighter plugin which uses GeSHi as a fontifier engine. ((Those code blocks are acquired from Google Code Search .)) ((For more supported languages, go CodeHighlighter plugin or GeSHi homepage.)) C++ (<pre lang="cpp" lineno="1">) class nsScannerBufferList { public: /** * Buffer objects are directly followed by a data segment. The start * of the data segment is determined by increment the |this| pointer * by 1 unit. */ class Buffer : public PRCList { public: Buffer() { ++index_; } PHP (<pre lang="php" lineno="4">) for ($i = 0; $i $value = ord( $utf8_string[ $i ] ); if ( $value < 128 ) { // ASCII $unicode .= chr($value); } else { if ( count( $values ) == 0 ) { $num_octets = ( $value } $values[] = $value; Lisp (<pre lang="lisp">) ;;; Assignment (define-caller-pattern setq ((:star var fo...

C++ of the Day #43 - SQLite3 C++ wrapper #1

The Definitive Guide to SQLite 를 읽다가 공부 겸 해서 C++ wrapper를 만들어 보았습니다. 최대한 C++ 냄새(?)가 나도록 만들어 보았습니다. :-) ((SQLite는 복잡한 관리가 필요없이 사용가능한, 파일이나 메모리 기반의, 라이브러리로 제공되는, 약 250kb 용량의, 대부분의 SQL92문을 지원하는, open source RDB입니다.)) 이 wrapper를 사용하기 위해서는 (당연하게도!) sqlite3 와 (당연하게도?) boost 라이브러리가 필요합니다. 사용 예들을 살펴보는 것으로 설명을 대신합니다. 이번 글에서는 다음과 같은 contacts 테이블이 test.db에 존재한다고 가정합니다. CREATE TABLE contacts ( id INTEGER PRIMARY KEY, name TEXT NOT NULL, phone TEXT NOT NULL, UNIQUE(name, phone) ); Command 먼저 test.db 파일을 사용하기 위해 다음과 같이 파일 이름을 주어 connection 객체를 생성합니다. 생성과 동시에 test.db와 연결이 이루어집니다. ((생성자외에 open() 함수를 사용할 수도 있습니다.)) sqlite3pp::connection conn("test.db"); 다음은 contacts 테이블에 정보를 추가하는 가장 간단한 방법입니다. connection 클래스에서 제공하는 execute 함수를 사용합니다. ((executef 함수를 사용하면 printf와 같은 문법을 사용하여 query문을 작성할 수 있습니다.)) conn.execute("INSERT INTO contacts (name, phone) VALUES ('user', '1234')"); 위와 동일한 작업을 parameterized query를 사용하여 할 수도 있습니다. ((step()함수가 실제 query문을 수행하는 함수입니다. ...