Small-Object Allocation, Ch4, Modern C++ Design

這章算是開始介紹 library 的設計，為後面其他工具鋪路，要設計一個有效率的 allocator。個人對於 memory 的配置不特別感興趣，因為這是 C++ 很基本的功能，也有很多 library 針對不同需求實作這個東西，直接找來用是很簡單的。但是除了 memory，其他地方也是有類似的資源分配需求，這章有些技巧可以學。



上面的圖表示了四層的設計。SmallObject 是對外的界面，只要繼承他就可以快速 new-delete。SmallObjAllocator 則是負責 allocate 不同大小的 memory。FixedAllocator 只負責處理固定大小的 allocation。Chunk 則是把小塊 memory 拼成大塊，轉交給底層 ::operator new 一次處理一大塊。

Chunks

這是 Chunk 的定義，用 Init() 來真的呼叫 ::operator new 取得一塊大塊 memory，用 pData_ 記下來。書裡沒列出的 Deinit() 應該要呼叫 ::operator delete。

struct Chunk
{
    void Init(std::size_t blockSize, unsigned char blocks);
    void Deinit();
    void* Allocate(std::size_t blockSize);
    void Deallocate(void* p, std::size_t blockSize);
    unsigned char* pData_;
    unsigned char firstAvailableBlock_;
    unsigned char blocksAvailable_;
};

Allocate() 和 Deallocate() 是用來分配使用 pData_ 指到的 memory 空間 (memory chunk)，參數 blockSize 是要 allocate 的大小，對同一個 Chunk 永遠是固定的，為了節省空間所以存在上層。Memory chunk 分成多個相同 blockSize 的 block，每個 block 的第一個 byte 紀錄下個 available block 的 index，形成一個 linked list 來紀錄可用的 block。這是 memory management 常見的作法。因為只用一個 byte，所以一個 Chunk 最多有 256 個 block。

在 Chunk 裡面，Allocate() 和 Deallocate() 都只要處理 linked list 的頭，速度很快。額外用的空間也佔很少比例。但是要注意，因為用 linked list 紀錄 available block，所以 Deallocate() 沒辦法檢查 double free，double free 會造成 linked list 壞掉。如果要解決這個問題，就要每個 block 多用一個 bit 紀錄是否 available。

The Fixed-Size Allocator

針對同一個大小的 allocation，使用同一個 FixedAllocator 來分配，就是這一層要處理的。因為他要控制多個 Chunk，可能需要 linear search 會降低效率，所以加了幾個技巧。

1. 使用最簡單的 cache 機制，紀錄最後一個 allocated chunk, deallocated chunk。先找最後一個。
2. 如果最後一個 allocated chunk 沒有空間，那就從頭開始 linear search。
3. 如果最後一個 deallocated chunk 不是，那就從這個指標同時往上下找。這是為了改進兩種 memory 使用模式，一種是 delete 順序跟 new 相同，另一種 delete 順序跟 new 相反。
4. 等到 Deallocate 有兩個空的 Chunk，才真的刪掉一個。這是為了避免 new & delete 反覆跨過邊界條件浪費時間。

The SmallObjAllocator Class

這個 class 處理任意大小的 memory 分配。如果太大，直接用 ::operator new/delete。如果夠小，就呼叫適當的 FixedAllocator 來處理。所以他有一個 vector<FixedAllocator> pool_，並且按照allocation 大小排序。

跟 FixedAllocator 類似，SmallObjAllocator 也 cache 紀錄了最後一個用來 allocate & deallocate 的 FixedAllocator，為了讓連續相同大小的物件使用更有效率。

SmallObject

實作 static operator new & delete 來給其他 class 繼承。他的定義很簡單，但是他的 delete 有第二個參數 size，是比較特別的。一般 operator delete 只有一個參數，但是 C++ 也支援兩個參數的版本，對實作 SmallObjAllocator 比較有效率，可以省下很多搜尋的時間。而 compiler 實作的時候，可以透過 virtual destructor 或者 v-table 得到指標執行時候真正的 size，再把 size 傳給 operator delete。

class SmallObject
{
public:
    static void* operator new(std::size_t size);
    static void operator delete(void* p, std::size_t size);
    virtual ~SmallObject() {}
};

其實這個部份我有疑惑，因為繼承 SmallObject 都會一併繼承 virtual desctructor，很多 compiler 會需要多存一個 vptr，這多使用的空間，和整個 allocation 的設計目的違背。而且，如果這邊沒有 virtual destructor，還是能夠繼承使用相同的功能，因此這邊不必 virtual，如果繼承以後有需要再加就可以了。為了避免直接 delete (SmallObject*)pFoo 沒呼叫到實際的 destructor，要把 ~SmallObject() 改成 protected。實際用 gcc 測試，struct Foo{ int a; }; 本身只要 4 bytes，多一個 virtual 會變成 16 bytes。改成 non-virtual protected destructor 就沒有問題。

Singleton and Multithreading Issues

設計基礎的 memory 分配的時候，整個系統都呼叫同一個 operator new，所以只能有一個 SmallObjAllocator 實體，同時也只能有一個 thread 使用。這邊很優雅的用 policy template 處理 multi-thread mutex lock 的實作，加上適當的 default 就完全不影響原本的設計，是很精彩的設計範例。