ゲーム開発におけるメモリアロケーションの実装について

はじめに

• 今回は、メモリアロケーションに関して、Java・C#などプログラミング言語やUnity・UDKなどのゲームエンジンにおいてはメモリの事なんて全然気にしなくていい時代になっている(!?)中、ゲーム開発におけるメモリアロケーションについて、えーでるわいすで現在使われているゲームエンジンでの実装も踏まえて一回まとめてみようかと。。。
  
  発端は、@aizen76さんの「カスタムメモリマネージャと高速なメモリアロケータについて」というスライドを偶然見つけたのがきっかけで、自分は今まで深く理解せず何となくでやってきてしまっていた気がしたのでちょっとまとめて見ようと思い立った感じです。

対象

• C++初級者~中級者ぐらい
  
  ※ ガベコレだのスマートポインタだのmallocの実装によるマルチスレッド環境下での速度がどうとかその辺の話は止まらなくなるので我慢します( ´∀｀)

メモリアロケーションって何なの？(念のため軽く基礎から。。。)

メモリアロケーションとは?

プログラムが起動する際に、そのプログラムが動作するために必要となるメモリー領域を、OSがCPUのメモリー上に確保することである。(IT用語辞典)

メモリアロケーションのパターンはおおまかに2つ

(ウィキペディア)

静的アロケーション → コンパイル時にメモリ領域を確定

• メリット

  • アロケーションに処理を必要としないため速度面で有利。メモリリークも存在しない！みんな幸せ＼(^o^)／

• デメリット

  • どの場面でもメモリサイズが固定になってしまうため、必要の無い場面でもメモリを多く消費してしまう。
    (例:1面では敵が2体しか出ないけど、2面は20体出るので、予め20体分配列を用意しないといけない)
    

動的アロケーション → プログラム実行時に、並行してメモリ領域の確保と解放

• メリット

  • 場面に応じて柔軟に必要なメモリ使用量を変化させることができる。

• デメリット

  • それなりに処理を食われる。 → 空いてるメモリを探したり登録・解除に処理を食う。
  • メモリ解放忘れ(メモリリーク) 通称お漏らし を起こす可能性がある。
  • リークや断片化でメモリがなくなると最悪クラッシュ／(^o^)＼
    ※STLとか使ってると、断片化や処理負荷の問題が顕著にあらわれてくる。知らず知らずのうちにリークすることも(・∀・)

あれ？ゲームなら敵の数とか出るエフェクト数大体決まってるし静的確保でいいんじゃね？w


しかしながら、えーでるわいすのエンジン・エフェクトシステム・キャラクタ処理などでは、何故か動的アロケーションが多用されています／(^o^)＼

なぜ動的アロケーションを使うのか？

• 出るものが多すぎて正確な最大メモリ使用量が読めない。メモリの最大使用量とかいちいち気にするのめんどい。
• STLとか便利だしいっぱい使いたい！

ただそれだけ！(ひどい)


だがしかし、動的アロケーションは処理を食う
大した事してないのにゲームが重いとか目も当てられない！！

でなんでいちいちアロケータをカスタムするの？

• Windows標準のメモリアロケーションの仕組みは細かいメモリアロケーションに向いてなくて速度的にいまいち(らしい) 　→ (2014/04/27追記)デバッガを繋げてると、性能が極端に落ちるらしい → 詳細
• Windowsのメモリリーク・メモリ破壊チェックはいまいち使いづくて激重なので自分好みにしたい。

ただそれだけ！(更にひどい！)

えーでるわいすにおける動的メモリアロケーションの実装につい

概要

• new/deleteを乗っ取ってdlmalloc(メモリ管理ライブラリ)に渡す処理を実装。
  　→ dlmallocがいかに素晴らしいか？についてはぐぐってくださいｗ
• メモリの管理領域は、STL用/エンジン用/ゲーム用 に分割。
  　→空き領域検索処理を少しでも軽くするため。
• メモリリーク/破壊チェックのために、メモリ確保情報をリストで管理

• メモリリークはゲーム終了時や、ステージ切替時にチェックが走ってログに出力。 VSで決められてる書式でログを出してるので、ログ出力ウィンドウのソースファイル名のところをクリック するとソースが開く！便利＼(^o^)／
  
[警告 #023](04:18:31) メモリリークしてまっせ。[sys]
..\src\Core\TGLMemory.cpp(675)
..\src\sAppMain.cpp(78) : {80} [area:5 adress:0x06230fb0 size: 0.00Kbyte]
dump<
[ﾍﾍﾍﾍ]
cd cd cd cd


• メモリ破壊は、確保領域の後ろのアドレスにチェック用の値を忍ばせて、確保・開放時にチェック。→ メモリを0xCDCDCDCDで塗りつぶして、値が書き換わってたら壊れたとみなす。

そんな感じ。特に何も難しいことはしてない(・∀・)

※配布時はデバッグ処理は重いので省かれてます。

実装

new/delete乗っ取り

• new/deleteを直接使わずに独自のdefineで置き換え。
• デバッグ用にソース名とライン数を引数で渡してます。(ゲームを配布する際にデバッグ処理は省かれます)
• ゲームなので、メモリが確保出来なかったりした時の例外処理は無効にしてある。(例外処理は重いし面倒なので)
• 詳細は、operator new オーバーライド　でぐぐると出てきます。
• 念のため、Windows標準のアロケータに簡単に戻せるようにしてあります。
• メモリマネージャーの初期化よりも先にアロケーションが来ることがあるのでゴニョゴニョする必要がある。(後述)

TGLTypes.h

#if defined(_TGL_DEBUG) || defined(_TGL_RELEASE)

#define SYS_NEW new(TGL::Memory::AREA_TYPE_SYS,__FILE__, __LINE__)
#define APP_NEW new(TGL::Memory::AREA_TYPE_APP,__FILE__, __LINE__)

#else

#define SYS_NEW new(TGL::Memory::AREA_TYPE_SYS)
#define APP_NEW new(TGL::Memory::AREA_TYPE_APP)

#endif

TGLMemory.h

inline void* operator new( std::size_t size, TGL::Memory::AREA_TYPE newFlag,const char* pszFile,s32 nLine ) throw()
{
    void* ptr = TGL::Memory::Allocater::Malloc( size ,newFlag,pszFile,nLine);

#if 0
#ifdef _USE_EXCEPTION   // 例外処理を許可しているときのみコンパイル
    if ( NULL == ptr )
    {
        throw std::bad_alloc();
    }
#endif
#endif

    return ptr;
}

inline void* operator new[]( std::size_t size, TGL::Memory::AREA_TYPE newFlag,const char* pszFile,s32 nLine  ) throw()
{
    return ::operator new( size ,newFlag,pszFile,nLine);
}



inline void* operator new( std::size_t size, TGL::Memory::AREA_TYPE newFlag) throw()
{
    void* ptr = TGL::Memory::Allocater::Malloc( size ,newFlag);

#if 0
#ifdef _USE_EXCEPTION   // 例外処理を許可しているときのみコンパイル
    if ( NULL == ptr )
    {
        throw std::bad_alloc();
    }
#endif
#endif

    return ptr;
}

inline void* operator new[]( std::size_t size, TGL::Memory::AREA_TYPE newFlag ) throw()
{
    return ::operator new( size ,newFlag);
}



inline void operator delete( void* ptr, TGL::Memory::AREA_TYPE newFlag) throw()
{
    TGL::Memory::Allocater::Free( ptr ,newFlag);
}

inline void operator delete[]( void* ptr, TGL::Memory::AREA_TYPE newFlag) throw()
{
    ::operator delete( ptr ,newFlag);
}

STLのアロケータを置き換え

• STLのアロケータは、デバッグ用とゲーム用で分けた。
• " STL カスタムアロケータ "で検索すると詳細が出てきます。

TGLSTL.h

    //! STLのカスタムアロケータ
    template <class T, s32 N = 1,TGL::Memory::AREA_TYPE AREA = TGL::Memory::AREA_TYPE_STL>
    class Allocator {
    public:
        // 型定義
        typedef T value_type;
        typedef T *pointer;
        typedef const T *const_pointer;
        typedef T &reference;
        typedef const T &const_reference;
        typedef size_t size_type;
        typedef ptrdiff_t difference_type;

        // アロケータをU型にバインドする
        template <class U>
        struct rebind {
            typedef Allocator<U, N> other;
        };


        // コンストラクタ
        Allocator() throw(){}
        Allocator(const Allocator&) throw(){}
        template <class U> Allocator(const Allocator<U>&) throw(){}
        // デストラクタ
        ~Allocator() throw(){}

        // メモリを割り当てる
        pointer allocate(size_type num, void *hint = 0)
        {
            hint;
            //return (pointer)( ::operator new( num * sizeof(T) ) );
            return (pointer)(TGL::Memory::Allocater::Malloc(num * sizeof(T),AREA));
        }
        // 割当て済みの領域を初期化する
        void construct(pointer p, const T& value)
        {
            // コンストラクタを無理やりコール
            new( (void*)p ) T(value);
        }

        // メモリを解放する
        void deallocate(pointer p, size_type num)
        {
            num;

            //::operator delete( (void*)p );
            TGL::Memory::Allocater::Free((void*)p,AREA);
        }
        // 初期化済みの領域を削除する
        void destroy(pointer p)
        {
            p;
            p->~T();
        }

        // アドレスを返す
        pointer address(reference value) const { return &value; }
        const_pointer address(const_reference value) const { return &value; }

        // 割当てることができる最大の要素数を返す
        size_type max_size() const throw()
        {
            return std::numeric_limits<size_t>::max() / sizeof(T);
        }
    };

    // システム向け
    namespace sys
    {


        template <class T, s32 N = 1>
        class SystemAllocator : public stl::Allocator<T,N,TGL::Memory::AREA_TYPE_STL>
        {
        public:
            // アロケータをU型にバインドする
            template <class U>
            struct rebind {
                typedef SystemAllocator<U, N> other;
            };

            // コンストラクタ
            SystemAllocator() throw(){}
            SystemAllocator(const SystemAllocator&) throw(){}
            template <class U> SystemAllocator(const SystemAllocator<U>&) throw(){}
            // デストラクタ
            ~SystemAllocator() throw(){}
        };

        // カスタムアロケータを指定したSTL
        typedef std::basic_string<char, std::char_traits<char>, SystemAllocator<char> > string;
        typedef std::basic_string<wchar_t , std::char_traits<wchar_t>, SystemAllocator<wchar_t> > wstring;

        template<typename T>
        class vector : public std::vector<T, SystemAllocator<T> > {};

// その他必要に応じて各コンテナに対して定義を書いていく。//

メモリマネージャー(主要なコードを抜粋)

• dlmallocについて　ぽこつん研究所

TGLMemory.cpp

#include <malloc.h>     // dlmalloc

    //==========================
    //! メモリエリア管理ラッパー
    //==========================
    class MemoryArea
    {
    public:

        MemoryArea(){}
        ~MemoryArea(){}

        //! メモリスペースの作成
        bool CreateMspace(const char* pszAreaName,size_t size=DEFAULT_ALLOC_SIZE)
        {
            m_size = size;
            strcpy(m_AreaName,pszAreaName);
            msp = create_mspace(size , 0 );

            ASSERTMSG(msp,"メモリスペースの作成に失敗しました。[%s]",pszAreaName);

            return (msp != null);
        }

        //! メモリスペース削除
        void DeleteMspace()
        {
            destroy_mspace( msp );
        }

        //! Malloc
        void* Malloc(size_t size)
        {
            return mspace_memalign( msp, DEFAULT_ALIGNMENT_SIZE , size );
        }

        //! ReAlloc
        void* ReAlloc(void *p,size_t size)
        {
            return mspace_realloc( msp, p , size );
        }

        //! 開放
        void Free(void *p)
        {
            mspace_free( msp, p );
        }

        //! 情報取得
        stl::dbg::string Info()
        {
            stl::dbg::string str;
            mallinfo info = mspace_mallinfo(msp);
            str = stl::FormatString<stl::dbg::string>("%12s size %sbyte / free %sbyte / use %sbyte",
                        m_AreaName,
                        stl::GetFormatUnitString<stl::sys::string>(m_size).c_str(),
                        stl::GetFormatUnitString<stl::sys::string>(info.fordblks).c_str(),
                        stl::GetFormatUnitString<stl::sys::string>(info.uordblks).c_str());
            return str;
        }

    private:
        char m_AreaName[64];
        mspace msp;
        size_t m_size;
    };
    MemoryArea s_MemorySpaceArray[TGL::Memory::AREA_TYPE_MAX];

//----------------------------
// 初期化
//----------------------------
void Allocater::Initialize()
{
#ifndef ENABLE_CRT_DEBUG

s_MemorySpaceArray[AREA_TYPE_DEBUG].CreateMspace("AREA_TYPE_DBG",DBG_ALLOC_SIZE);
    s_MemorySpaceArray[AREA_TYPE_STL].CreateMspace("AREA_TYPE_STL",STL_ALLOC_SIZE);
    s_MemorySpaceArray[AREA_TYPE_SYS].CreateMspace("AREA_TYPE_SYS",SYS_ALLOC_SIZE);

s_MemorySpaceArray[AREA_TYPE_APP].CreateMspace("AREA_TYPE_APP",APP_ALLOC_SIZE);

#else // Windows標準のアロケータの場合

    // Get current flag
    int tmpFlag = _CrtSetDbgFlag( _CRTDBG_REPORT_FLAG );

    // Turn on leak-checking bit
    tmpFlag |= _CRTDBG_LEAK_CHECK_DF;
    tmpFlag |= _CRTDBG_ALLOC_MEM_DF;
    //tmpFlag |= _CRTDBG_CHECK_EVERY_128_DF; // _CRTDBG_CHECK_EVERY_16_DF とすれば16回に一回 デフォは1024回に一回


    // Turn off CRT block checking bit
    //tmpFlag &= ~_CRTDBG_CHECK_CRT_DF;

    // Set flag to the new value
    _CrtSetDbgFlag( tmpFlag );
#endif

}

//------------------------
// 終了処理
//------------------------
void Allocater::Terminate()
{
#ifndef ENABLE_CRT_DEBUG
    for(s32 i = 0;i<AREA_TYPE_MAX;++i)
    {
        s_MemorySpaceArray[i].DeleteMspace();
    }
#endif
    s_bInit = false;

    OutputDebugString("Memory Allocater Terminate\n");
}

//------------------------
// デバッグ機能付きmalloc
//------------------------
void* Allocater::Malloc(size_t size,TGL::Memory::AREA_TYPE areaType,const char* pszFile,s32 nLine)
{   
    ASSERT(s_bInit&&"メモリマネージャーが初期化されてない");

#ifdef ENABLE_CRT_DEBUG

    void* adress = Malloc(size);

#else

    size_t alloc_size = size;
#ifdef CHECK_MEMORY_BREAK
    // メモリ破壊検地用領域
    alloc_size += MEMORY_TRAP_SIZE;
#endif

    void* adress = Malloc(alloc_size,areaType);

#ifdef CHECK_MEMORY_LEAK

    // デバッグ情報
    if( adress )
    {
        TGL::Thread::ScopedLock lock(s_pLock_dbg);

        // ブレーク
        if( s_BreakAllocCount == s_AllocCount ){BP();}

        DebugMemoryInfo info;
        info.pAdress = adress;
        info.size   = size;
        info.filename = stl::FormatString<stl::dbg::string>("%s(%u)",pszFile,nLine);
        info.count = s_AllocCount;
        info.areaType = areaType;
        if( !m_checkPointName.empty() )
        {
            info.checkName = (*m_checkPointName.begin());
        }

        info.Fill();

        m_MemoryInfo[info.Adress()] = info;
        s_AllocCount++;
    }
#endif

#endif // ENABLE_CRT_DEBUG

    return adress;
}

//!Malloc
void* Allocater::Malloc(size_t size,TGL::Memory::AREA_TYPE areaType)
{
    if( !s_bInit){
        T_WARNING("メモリマネージャーが初期化されてない");
        //T_CONSOLE("メモリマネージャーが初期化されてない\n");
#ifndef _TGL_FINAL
        BP();
#endif
        void *p = (int *)malloc( size );
        return p;
    }

#ifdef ENABLE_CRT_DEBUG

    void *p = (int *)malloc( size );

#else

    TGL::Thread::ScopedLock lock(s_pLock);

    //void *p = mspace_memalign( s_mspArray[areaType], DEFAULT_ALIGNMENT_SIZE , size );
    void* p = s_MemorySpaceArray[areaType].Malloc(size);


#endif

    ASSERTMSG(p,"メモリ領域の確保に失敗[%s]",stl::GetFormatUnitString<stl::sys::string>(size).c_str());
    return p;
}

//------------------------
// 開放
//------------------------
void Allocater::Free(void *p,TGL::Memory::AREA_TYPE areaType)
{
    if( !s_bInit){
        T_WARNING("メモリマネージャーが初期化されてない");
        //T_CONSOLE("メモリマネージャーが初期化されてない\n");
#ifndef _TGL_FINAL
        BP();
#endif
        free(p);
        return;
    }

#ifdef ENABLE_CRT_DEBUG

    free(p);
#else

#ifdef CHECK_MEMORY_LEAK

    // デバッグ情報削除
    if( p && !m_MemoryInfo.empty())
    {
        TGL::Thread::ScopedLock lock(s_pLock_dbg);

        u32 add = reinterpret_cast<u32>(p);
        MEMORY_INFO::iterator it = m_MemoryInfo.find(add);
        if( it != m_MemoryInfo.end() )
        {
            m_MemoryInfo.erase(it);
        }
    }
#endif
    {
        TGL::Thread::ScopedLock lock(s_pLock);

        //mspace_free( s_mspArray[areaType], p );
        s_MemorySpaceArray[areaType].Free(p);
    }
#endif

}

//! リークのダンプ
void Allocater::DumpMemoryLeak(const char* pszName)
{
#ifndef ENABLE_CRT_DEBUG


#ifdef CHECK_MEMORY_LEAK
    if( m_MemoryInfo.empty() )
        return;

    typedef stl::sys::vector<DebugMemoryInfo> LEAK_ARRAY;
    LEAK_ARRAY leakArray;

    if( !pszName ) pszName ="";

    foreach(MEMORY_INFO,m_MemoryInfo,it)
    {
        DebugMemoryInfo info = (*it).second;

        if( info.checkName == pszName )
        {
            leakArray.push_back(info);
        }
    }

    if( !leakArray.empty() )
    {
        PRINT("--------------------------\n");
        T_WARNING("メモリリークしてまっせ。[%s]",pszName);

        s32 num = 0;
        foreach(LEAK_ARRAY,leakArray,it)
        {
            DebugMemoryInfo info = (*it);
            stl::sys::string str = stl::FormatString<stl::sys::string>("%s : {%d} [area:%d adress:0x%08x size:%sbyte]\n",
                                info.filename.c_str(),
                                info.count,
                                info.areaType,
                                info.Adress(),
                                stl::GetFormatUnitString<stl::sys::string>(info.size).c_str());
            PRINT(str.c_str());
            info.Dump();

            if( ++num>10 ){
                PRINT("リークし過ぎなのでとりあえず終わる");           
                break;
            }

        }

        PRINT("--------------------------\n");
    }

    stl::clear(leakArray);

    if( m_checkPointName.size() > 0 ) m_checkPointName.pop_front();
#endif

#endif // ENABLE_CRT_DEBUG

自前のメモリマネージャーの初期化が一番最初に来るようにゴニョゴニョする

sTGLMain.cpp

    //------------------------
    //! 初期化オブジェクト
    //------------------------
    class Initialize
    {
    public:
        Initialize() {
            //! メモリ管理初期化
            Memory::Allocater::Initialize();
        }

        ~Initialize() {
            //! メモリ管理終了
            Memory::Allocater::Terminate();
        }
    };
    //! 初期化順制御
    #pragma warning(disable: 4074)
    #if defined(__cplusplus) && defined(__GNUC__)
        Initialize init __attribute__((init_priority( 111 )));
    #elif defined (_MSC_VER)
        #pragma init_seg(compiler)
        Initialize init;
    #else
        #error not supported.
    #endif
    //------------------------

なんかそんな感じ。若かりし頃に書いたコードでしょぼいのであまりお見せできませんorz
近々大改装予定！

まとめ

• ゲームではなるべく動的アロケーションは使わない方が吉ですよ！どれ位必要かぐらいはプログラマなんだからちゃんと把握しておきましょう＼(^o^)／
• どうしても動的アロケーションが必要な場合コストを十分に理解して使ってね！簡単に沼にハマるよ！
• STLは初心者が内部実装理解せず気軽に使うものではないよ！ EffectiveSTL とかちゃんと読んで内部実装理解してからね！(できれば、自前で簡易的なSTLを実装できるようになるまでは。。。)
• ゲーム向けに最適化&使いやすくなったSTLをEAが作ったりしてるので見てみると良いかも。EASTL@Github

その他、動的アロケーションのコストを下げる方法など

• ゲーム開始時やステージ開始時にまとめてアロケーションして置いてその中から使う。
  →メモリプールという仕組みを使う手もある。自前でも簡単に作れるけど、もっと高機能な、Boost.Poolってのがあるらしいよ！僕、boostよく知らないけど！
  
• STLの場合、予め領域を確保しておける
  → std::vector::reserve()など。

その他STL関連おまけ

• 生固定配列だと、サイズオーバでメモリ破壊とか怖いなという時は、生配列より安全だけど、生配列と同じ処理コストで使える(メモリ使用量は生配列と同じで、デバッグ処理を無効にすれば処理コストもゼロ)std::arrayとかもあったりします。

アロケーションは用法・容量に注意して正しく使いましょう＼(^o^)／

終わり。