MemoryPoolについて

MemoryPoolという構造体がある。これは一種のアロケータで、あるサイズ分メモリーをブロックとして確保しておき、それをためて置く。これを必要になったときそれを使用する。Effecient C++にはそんな構造体が載っている。
いくつかの不具合を修正したので、以下にそれを示す。

#ifndef MEMORY_POOL_H_
#define MEMORY_POOL_H_


/// from Efficient c++ section 6

#include <memory>


    const int MEMORY_POOL_DEFAULT_EXPAND_SIZE = 32;

    template <class T_, size_t size_ =MEMORY_POOL_DEFAULT_EXPAND_SIZE>
    class MemoeyPool {
    public:
        MemoeyPool(){
            expandTheFreeList(size_);
        }
        ~MemoeyPool() {
            MemoeyPool<T_, size_>* nextPtr = next_;
            while(nextPtr){
                MemoeyPool<T_, size_>* nowPtr = nextPtr;
                nextPtr = nextPtr->next_;
                delete [] reinterpret_cast<char*>(nowPtr);//ここちゃんとキャストしなおさなきゃダメだよ
            }           
        }

        void* alloc(size_t) {
            if (!next_)expandTheFreeList(size_);

            MemoeyPool<T_, size_>* head = next_;
            next_ = head->next_;

            return head;
        }
        void free(void* doomed) {
            MemoeyPool<T_, size_>* head = static_cast<MemoeyPool<T_, size_>*>(doomed);
            head->next_ = next_;
            next_ = head;
        }

    private:
        void expandTheFreeList(int howMany);
    private:
        MemoeyPool<T_, size_>* next_;
    };
    template <class T_, size_t size_>
    void MemoeyPool<T_, size_>::expandTheFreeList(int howMany) {
        size_t size = (sizeof(T_) > sizeof(MemoeyPool<T_, size_>*))
            ? sizeof(T_) : sizeof(MemoeyPool<T_, size_>*);

        MemoeyPool<T_, size_>* runner =
            reinterpret_cast<MemoeyPool<T_, size_>*> (new char[size]);

        next_ = runner;
        for (int i = 1; i < howMany; i++) {//ここ正確には1から！
            runner->next_ =
                reinterpret_cast<MemoeyPool<T_, size_>*> (new char[size]);
            runner = runner->next_;
        }
        runner->next_ = 0;
    }

//以下のクラス用のユーティリティ
    template <class T_, size_t size_ =MEMORY_POOL_DEFAULT_EXPAND_SIZE>
    class MemoeyPoolHolder{
    public:
        MemoeyPoolHolder():p_pool_(new MemoeyPool<T_, size_>()){}
        ~MemoeyPoolHolder(){delete p_pool_;}
        void initialize(){
            std::auto_ptr< MemoeyPool<T_, size_> > ap(new MemoeyPool<T_, size_>());
            delete p_pool_;
            p_pool_ = ap.release();
        }
        MemoeyPool<T_, size_> * operator ->( ) const throw( ){ return p_pool_;}
    private:
        MemoeyPool<T_, size_> *p_pool_;
    };

//コイツを継承することで自然にMemoryPoolが使える
    template <class T_, size_t size_ =MEMORY_POOL_DEFAULT_EXPAND_SIZE>
    class UseMemoeyPool{
    public:
        void* operator new(size_t size) { return UseMemoeyPool::get_instance()->alloc(size); }
        void operator delete(void* doomed, size_t) { UseMemoeyPool::get_instance()->free(doomed); }

        static void initialize(){UseMemoeyPool::get_instance().initialize();}
    protected:
        static MemoeyPoolHolder<T_, size_> & get_instance(){
            static MemoeyPoolHolder<T_, size_> pool_;
            return pool_;
        }
    };


#endif // ! MEMORY_POOL_H_

ところでこのMemoryPool速いのか？コレが問題だ。以下の実験はPentium 2.4GHz マシン上でVC++2003にてリリースコンパイルして行なった。
以下のようなクラスを定義してみる

class AA:public UseMemoryPool<int[100],1000>{//ほんとはclass AA:public UseMemoryPool<AA,1000> としたいがこれはうまくいかない・・・
public:
    AA(int a){
        dummy[99] = a;
    }
    int get()const {return dummy[99];}
private:
    int dummy[100];
};

class BB{
public:
    BB(int a){
        dummy[99] = a;
    }
    int get()const {return dummy[99];}
private:
    int dummy[100];
};

さて実験

timer t1;//内部的にはtimeGetTime()をつかったタイマークラスだと思いねえ。
const int NUMX = 10000; 

t1.start();
for(int i = 0;i<NUMX;i++){
    AA* ptr = new AA(i);
    delete ptr;
}
t1.end();
std::cout << "AA:" << t1.msec() << "ms" <<std::endl;

t1.start();
for(int i = 0;i<NUMX;i++){
    BB* ptr = new BB(i);
    delete ptr;
}
t1.end();
std::cout << "BB:" << t1.msec() << "ms" <<std::endl;

AA:3ms

BB:73ms

おお！すごい！差は歴然！

・・・・
・・・・
実は落とし穴がある。MemoryPoolは事前に確保したメモリを『貸し出す』ことでメモリのアロケートをしたように見せかけるものだ。
上記のテストコードではnewしたオブジェクトをすぐさまdeleteしてしまっている。このためMemoryPoolは実際にはまったくメモリの確保をしていないのだ。こういうケースはめったにないだろう。テンポラリが欲しいのならわざわざヒープ上に確保する必要はないのだから。
以下のように大き目の配列に確保するケースはどうだろうか？

AA* array_AA[NUMX];
BB* array_BB[NUMX];

t1.start();
for(int i = 0;i<NUMX;i++){
    array_AA[i] = new AA(i);
}
t1.end();
std::cout << "AA:" << t1.msec() << "ms" <<std::endl;

t1.start();
for(int i = 0;i<NUMX;i++){
    array_BB[i] = new BB(i);
}
t1.end();
std::cout << "BB:" << t1.msec() << "ms" <<std::endl;

結果は以下

AA:30ms

BB:28ms

ほとんど差がない。・・・つまりメモリ確保の速度での優位性はないわけだ。
ところでメモリ破棄するときはどうだろう？

t1.start();
for(int i = 0;i<NUMX;i++){
    delete array_AA[i];
}
t1.end();
std::cout << "AA:" << t1.msec() << "ms" <<std::endl;

t1.start();
for(int i = 0;i<NUMX;i++){
    delete array_BB[i];
}
t1.end();
std::cout << "BB:" << t1.msec() << "ms" <<std::endl;

結果は以下

AA:1ms

BB:171ms

すばらしい。断然じゃないか！これはMemoryPoolがメモリ破棄を実際にはせず単純に内部のリンクリストにつなぎなおして、管理対象にしなおしているだけであるためだ。

・・・・つうことでやっぱりコレにも穴がある。

MemoryPoolが確保しているメモリをいったん初期化しなおしてみよう。これをしないと、プロセスが終了するまで大量のメモリを確保したままになってしまう。

t1.start();
AA::initialize();           
t1.end();
std::cout << "AA:initialize:" << t1.msec() << "ms" <<std::endl;

結果・・・

AA:initialize:229

結果ははっきりいって遅い。まあ大量の配列をリンクリストを見ながら破棄しているのだから当然だろう。

まとめると以下のようになる。
10000個の400バイト(sizeof(int)*100)のオブジェクトを確保して破棄した時の速度

クラス名	メモリ確保	メモリ破棄	内部メモリ初期化	トータル(ms)
AA	30	1	229	260
BB	28	171	-	199

MemoryPoolは使いどころが難しい。
使いどころとしてはメモリの確保と破棄を交互に使う繰り返すような場合、または、あらかじめトータルで使うメモリ量がわかっているときなどが考えられる。
ただ多くのケースではトータルでは遅くなることの方が多いのではないかとおもう。またマルチスレッド時に用いるのにはやはり慎重にならなくてはいけないなど、少なくとも安易に使えるものでは決してない。よって内部的な仕組みの理解が使用するときの条件となるだろう。

参考：
http://shinh.skr.jp/loki/SmallObj.html