日記ちゃんがmemory pool

　メモリプールの挙動が怪しかったので、取得と解放を繰り返すだけのプログラムを書いて動かしたらメモリリークした。たかが128Byteのメモリプールをうまくコントロールできないとか涙が出る。
　ここ数週間ずっとそんなかんじ。

　たぶん解決した。
メモリ最適化のときに、空きメモリを指すポインタがおかしい値になってた。これを修正したらとりあえずリークしなくなった。

　修正したメモリプールをゲームのほうに適用したら、まだエラー出たんで、なんでよーって具合。
メモリプールはおかしくない！俺は常に正しい！俺が間違うことはない！
犯人はお前だ！　撲滅！ オーバーフロー！
って、勘でoggをデコードするプログラムを見直したら、範囲外にもりもりファイル読み込んでた。
直したらエラーでなくなった。
たたかいはおわった。

　

　以下、使用中のメモリプール。
newと比較したところ10000000回で1000ms程度の差。つまりほとんど差なし。
resizeできたら面白いかなーと思ってvectorを使用しているけど、std::allocとかのほうが速いと思う。
参考程度に。

●基本イメージ
□□□□□□□□□□□□
↓メモリ頂戴
■■■■□□□□□□□□
↓メモリ頂戴
■■■■■■■■□□□□
↓返すよ
□□□□■■■■□□□□

こんな感じ。


●メモリ最適化イメージ
■■■■□□□□■■■■□□□□
[■4][□4][■4][□4]
↓返すよ
□□□□□□□□■■■■□□□□
[□4][□4][■4][□4]
↓最適化
□□□□□□□□■■■■□□□□
[□8] [■4][□4]



●欠陥
以下のような状況が頻繁に発生する
□□□□□□□□
↓1つ頂戴
□□□□■□□□
↓5つ頂戴
□□□□■□□□空きが無いから無理


#include <limits.h>
#include <windows.h>
#include <cstdio>
#include <tchar.h>
#include <vector>
 
 
 
class Pool
{
private:
  struct PoolObject
  {
    size_t blockNum;
    bool use;
 
    // デバッグ用オーバーフローチェック
    unsigned short check;
    enum { CHECK_PARAM = 0x5353, };
  };
 
 
 
  /** プール */
  std::vector<PoolObject> m_pool;
 
  /** 使用したメモリ量 */
  size_t m_useBlockNum;
 
  /** 次に確保しようとするメモリの先頭位置 */
  PoolObject* m_head;
 
public:
 
 
  /**
   * compaction
   * 隣り合った空きメモリを結合する。
   */
  void compaction()
  {
    m_head = NULL;
    size_t space = 0;
 
    const PoolObject* lastPoint = &m_pool[0] + m_pool.size();
    PoolObject* runner = &m_pool[0];
    for (; runner<lastPoint; runner+=runner->blockNum)
    {
      // err
      if ( runner->blockNum == 0 )
      {
        OutputDebugString(TEXT("Memory Pool Error...(object size == 0)\n"));
        abort();
        break;
      }
 
      if ( runner->use && space )
      {
        (runner - space)->blockNum = space;
        space = 0;
      }
      else if ( runner->use == false )
      {
        if ( !m_head ) m_head = runner;
        space += runner->blockNum;
      }
    }
 
    if ( space )
    {
      (runner - space)->blockNum = space;
    }
 
    if ( !m_head )
    {
      m_head = &m_pool[0];
    }
  }
 
 
 
private:
  /**
   * searchSpace
   * 空きメモリを探す。
   * @param blockNum 確保したいメモリ量(ブロック単位)
   * @return 見つけた空きメモリのポインタ。確保できないようであれば NULL。
   */
  PoolObject* _searchSpace( size_t blockNum )
  {
    // search
    const PoolObject* lastPoint = &m_pool[0] + m_pool.size();
    for (PoolObject* runner=m_head; runner<lastPoint; runner += runner->blockNum)
    {
      if ( runner->use == false &&
        runner->blockNum >= blockNum )
      {
        return (m_head = runner);
      }
    }
 
    // compaction
    compaction();
 
    // search retry
    for (PoolObject* runner=m_head; runner<lastPoint; runner += runner->blockNum)
    {
      if ( runner->use == false &&
        runner->blockNum >= blockNum )
      {
        return (m_head = runner);
      }
    }
 
    // space none
    return NULL;
  }
 
 
 
  /** sizeToBlockNum */
  static inline size_t sizeToBlockNum( const size_t size )
  {
    // ヘッダ用とデータ用で2は必ずいる
    return size / sizeof(PoolObject) + 2;
  }
 
 
 
  /** blockNumToSize */
  static inline size_t blockNumToSize( const size_t blockNum )
  {
    return blockNum * sizeof(PoolObject);
  }
 
 
 
public:
 
 
  /**
   * constructor
   * @param 作成するプールサイズ
   */
  explicit Pool( size_t size )
    : m_pool( sizeToBlockNum(size) + 8 )
    , m_useBlockNum( 0 )
    , m_head( NULL )
  {
    if ( size > 0 )
    {
      PoolObject* po = &m_pool[0];
      po->blockNum = m_pool.size();
      po->use = false;
      m_head = po;
    }
  }
 
 
 
  /**
   * destructor
   */
  ~Pool()
  {
#ifdef _DEBUG
    if ( m_useBlockNum )
    {
      Debug::outputDebugString( TEXT("[Pool]memory reak!: %dbyte, poolSize: %d\n"), getUseSize(), getPoolSize() );
    }
#endif
  }
 
 
 
  /**
   * alloc
   * プールからメモリを取得する。
   * @param size 取得したいメモリ量
   * @return 使用可能なアドレス。取得に失敗すればNULLが戻る。
   */
  void* alloc( size_t size )
  {
    // はなから空きがないのでお帰りください
    const size_t newBlockNum = sizeToBlockNum( size );
    if ( m_pool.size() - m_useBlockNum < newBlockNum )
    {
      return NULL;
    }
 
    PoolObject* po = _searchSpace( newBlockNum );
    if ( !po )
    {
      Debug::outputDebugString( TEXT("noneSpaceError: %d\n"), size );
      return NULL;
    }
 
 
    // もしも空きサイズが取得したいサイズよりも大きければ、空きサイズを減少させる
    if ( po->blockNum > newBlockNum )
    {
      PoolObject* next = po + newBlockNum;
      next->use = false;
      next->blockNum = po->blockNum - newBlockNum;
 
      // ここにこなかった場合ぴったりサイズなので設定しなおさなくていい
      po->blockNum = newBlockNum;
    }
 
#ifdef _DEBUG
    po->check = PoolObject::CHECK_PARAM;
#endif
    po->use = true;
    
    m_useBlockNum += newBlockNum;
    m_head = po + newBlockNum;
 
    // PoolObject一つ分だけずらしたアドレスを戻す
    return (po + 1);
  }
 
 
 
  /**
   * free
   * @param 返却するメモリのアドレス。
   */
  void free( void* obj )
  {
    if ( obj )
    {
      PoolObject* po = static_cast<PoolObject*>( obj ) - 1;
#ifdef _DEBUG
      if ( po->use == false )
      {
        Debug::outputDebugString( TEXT("2重解放? - [%p]size: %d\n"), obj, blockNumToSize(po->blockNum) );
      }
      else if ( po->blockNum == 0 || po->check != PoolObject::CHECK_PARAM )
      {
        Debug::outputDebugString(TEXT("オーバーフローの疑い: %p\n"), obj);
      }
      else
#endif
      {
        po->use = false;
        m_useBlockNum -= po->blockNum;
      }
    }
  }
 
 
 
  /** プールのサイズ取得 */
  size_t getPoolSize() const { return blockNumToSize( m_pool.size() ); }
  /** プールのメモリ使用量を取得 */
  size_t getUseSize() const { return blockNumToSize(m_useBlockNum); }
};



　空きメモリをリストにして、要求があればリストから渡すようにすれば高速化できそう。
ただメモリ最適化のときに、空きメモリリストもいじらないといけなくなるので処理時間が気になる。メモリ要求回数が圧倒的に多いから、全体的には速くなると思うが。