Chunk allocator

# はじめに
良く知られる名称があるのかも知らないのですが, 小さなサイズのメモリを大量に確保・解放を繰り返すパターンに用いられるメモリ管理戦略です. 欠点はコンパクションのコストが高いことです.

割り当て時に, 大きなメモリブロックから切り出して小さなメモリを確保し, 解放時にテーブルにキャッシュし次回割り当て時に再利用します. 基本はプログラム終了まで解放しません. 次の図では8Bの倍数でメモリブロックを分類していますが, 2のべき乗などの様々なやり方があります.
メモリ確保のパターンによって, 様々なやり方があるため~~コードを書きません~~. 私も5個ぐらいはワンオフで書いていると思います.　dlmalloc, jemalloc, tcmalloc, mimallocなど小サイズのメモリ割り当てはこれなので参考にするとよいです.

![chunk00.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/27065/986955ca-6f33-2471-10a9-e2b055e3f71c.jpeg)

# 実装

固定サイズのアロケータです. 管理情報はChunk構造体で, 固定サイズの配列に入れています. サイズは1バイトから2の冪乗で16バイトまでです. 用途の都合で管理情報を別にしていますが, 汎用のメモリアロケータの場合, 要求サイズより大きくメモリを確保し, 余分な領域に管理情報を埋め込む実装が一般的です.

<details><summary>Chunk Allocator</summary><div>

```cpp
class ChunkAllocator
{
public:
    typedef ChunkAllocator this_type;

    static constexpr u8 Invalid = 0xFFU;
    static constexpr u8 NumChunks = 5;
    static constexpr u8 MaxSize = 16;
    static constexpr u8 PageSize = 254;

    ChunkAllocator();
    ~ChunkAllocator();

    void* allocate(u8 size);
    void deallocate(u8 size, void* ptr);

private:
    ChunkAllocator(const ChunkAllocator&) = delete;
    ChunkAllocator& operator=(const ChunkAllocator&) = delete;

    void exp2(u8& p, u8& s, u8 size)
    {
        p = 0;
        s = 1;
        while(s<size){
            s <<= 1;
            ++p;
        }
    }

    struct Chunk
    {
        u8 next_;
        u8 size_;
    };

    void* heap_;
    u8 size_;
    u8 chunkTable_[NumChunks];
    Chunk chunks_[PageSize];
};

ChunkAllocator::ChunkAllocator()
    : heap_(nullptr)
    , size_(PageSize)
    , chunks_{}
{
    heap_ = malloc(PageSize);
    for(u8 i=0; i<NumChunks; ++i){
        chunkTable_[i] = Invalid;
    }
}

ChunkAllocator::~ChunkAllocator()
{
    free(heap_);
}

void* ChunkAllocator::allocate(u8 size)
{
    assert(0 < size && size <= MaxSize);

    u8 index, alignedSize;
    exp2(index, alignedSize, size);

    u8 offset;
    if(Invalid != chunkTable_[index]) {
        offset = chunkTable_[index];
        assert(size <= chunks_[offset].size_);

        chunkTable_[index] = chunks_[offset].next_;

    } else if(size <= size_) {
        offset = PageSize - size_;
        size_ -= alignedSize;
        chunks_[offset].size_ = alignedSize;

    } else {
        return nullptr;
    }
    chunks_[offset].next_ = Invalid;
    return reinterpret_cast<u8*>(heap_)+offset;
}

void ChunkAllocator::deallocate(u8 size, void* ptr)
{
    assert(0 < size && size <= MaxSize);
    if(nullptr == ptr){
        return;
    }

    u8 offset = static_cast<u8>(std::distance(
        reinterpret_cast<u8*>(heap_),
        reinterpret_cast<u8*>(ptr)));

    assert(size <= chunks_[offset].size_);

    u8 index, alignedSize;
    exp2(index, alignedSize, size);

    chunks_[offset].next_ = chunkTable_[index];
    chunkTable_[index] = offset;
}
```
</div></details>

管理領域を可変にしたバージョンです. このように用途によって最適な実装を求めると, 少しずつ違う実装を作ることになります.

<details><summary>Dynamic Chunk Allocator</summary><div>

```cpp
class DynamicChunkAllocator
{
public:
    typedef DynamicChunkAllocator this_type;
    static constexpr u32 MaxSize = 32;
    static constexpr u32 NumChunks = 32;
    static constexpr u32 PageSize = MaxSize*32;
    static constexpr u32 Invalid = 0xFFFFFFFFU;

    DynamicChunkAllocator();
    ~DynamicChunkAllocator();

    void* allocate(u32 size);
    void deallocate(u32 size, void* ptr);
private:
    DynamicChunkAllocator(const DynamicChunkAllocator&) = delete;
    DynamicChunkAllocator& operator=(const DynamicChunkAllocator&) = delete;

    struct Chunk
    {
        u32 next_;
        u32 offset_;
    };

    void* heap_;
    u32 remain_;
    u32 chunkTable_[NumChunks];
    u32 empty_;
    std::vector<Chunk> chunks_;
};

DynamicChunkAllocator::DynamicChunkAllocator()
    : heap_(nullptr)
    , remain_(PageSize)
    , empty_(Invalid)
{
    heap_ = malloc(PageSize);
    chunks_.reserve(16);
    for(u32 i=0; i<NumChunks; ++i){
        chunkTable_[i] = Invalid;
    }
}

DynamicChunkAllocator::~DynamicChunkAllocator()
{
    free(heap_);
}

void* DynamicChunkAllocator::allocate(u32 size)
{
    assert(0<size && size<=MaxSize);
    u32 index = size-1;
    u32 offset;
    if(Invalid != chunkTable_[index]){
        u32 next = chunkTable_[index];
        chunkTable_[index] = chunks_[next].next_;
        chunks_[next].next_ = empty_;
        empty_ = next;

        offset = chunks_[next].offset_;

    }else if(size<=remain_){
        offset = PageSize - remain_;
        remain_ -= size;

    }else{
        return nullptr;
    }
    return reinterpret_cast<u8*>(heap_) + offset;
}

void DynamicChunkAllocator::deallocate(u32 size, void* ptr)
{
    assert(0 < size && size <= MaxSize);

    if(nullptr == ptr){
        return;
    }

    u8 offset = static_cast<u8>(std::distance(
        reinterpret_cast<u8*>(heap_),
        reinterpret_cast<u8*>(ptr)));

    u32 index = size-1;
    u32 chunk;
    if(Invalid != empty_){
        chunk = empty_;
        empty_ = chunks_[chunk].next_;
    }else{
        chunk = static_cast<u32>(chunks_.size());
        chunks_.resize(chunks_.size()+1);
    }

    chunks_[chunk].offset_ = offset;
    chunks_[chunk].next_ = chunkTable_[index];
    chunkTable_[index] = chunk;
}
```
</div></details>

# まとめ
何に使うの？というのは後日書くかもしれません.