シンプルで高速なアロケータ

細々としたメモリを動的に確保しているせいか、今やってるアプリケーションが結構遅くなってきました。
なので、小さいメモリについてはアロケータを使って確保してやろうと思っているんだけど、そこら辺の汎用的なアロケータは、超シンプルなアロケータに比べて遅い（に違いない）ので、高速に動作する（と思われる）アロケータを自前で作ってみることにしました。

このアロケータは一定のサイズのメモリしかアロケートしないようにします。
こうすることによって複数のブロックにまたがるようなアロケートは考慮しなくて良くなり、また、メモリの断片化についても気にする必要が無くなるので、高速化・簡略化が図れます。

ブロックの管理方法ですが、これはビットが立っているか立っていないかで使用している・使用していないを判断することにします。
一定のサイズのブロックが 32768 個あれば、ビットフラグの数も 32768 個です。
また、アロケートするたびに空いているブロックを探して 32768 / 8 = 4096 バイトもの領域を全て走査していたのでは遅すぎるので、32768 個のフラグをさらに 32 個単位で分割し、32768 / 32 = 1024 個のフラグを用意し、その 1 ビットが管理している 32 個のフラグに１つでも空きがあれば 0 に、空きが１つもない場合は 1 に設定するようにします。
また、アロケートするたびに空いているブロックを探して 1024 / 8 = 128 バイトもの領域を全て走査していたのでは遅すぎるので、1024 個のフラグをさらに 32 個単位で分割し、1024 / 32 = 32 個のフラグを用意し、その 1 ビットが管理している 32 個のフラグに１つでも空きがあれば 0 に、空きが１つもない場合は 1 に設定するようにします。
また、アロケートするたびに空いているブロックを探して 32 / 8 = 4 バイトもの領域を全て走査していたのでは……十分速いですね。
int の大きさが 4 バイトなのであれば、領域が空いているかどうかは 0xffffffff との比較をするだけで済みます。
ようするにこれは 32 分木になっていて、こうすることで 32768 個のブロックがある場合は 回の比較で空いているブロックの位置を求めることが出来るようになります。

しかもどのビットが立っているかを検索するのは x86 の CPU であれば bsr, bsf 命令を使うことで、１命令で求めることが可能です。
ただし、今回の場合はビットが落ちている場所を検索するので、not 命令が必要になります（これについては最後に 1 を空き状態、0 を使用状態にすることで解決します）。

inline int FindEmptyBit(unsigned int bits)
{
    __asm
    {
        mov eax, dword ptr [bits]
        not eax
        bsr eax, eax
    };
}

ターゲットが x86 ではない場合には困ることになりますが、大抵の CPU にはそういう命令があるので大丈夫でしょう。

ということで寝る時間になってきたので次回へ持ち越し。