小对象的分配技术

 

小对象分配技术是Loki提高效率的有效途径，Loki里广泛使用小对象， 如果使用系统默认分配器，因为薄记得缘故，可能代价在400%以上，所以这个是必须要解决的问题。我们首先来谈Chunks。

1.MemControlBlock结构

struct MemControlBlock 
{
    bool    available_;
    MemControlBlock*    prev_;
    MemControlBlock*    next_;
};

是的，你看到了，这里没有块大小标志，这个时候注意这点会对你理解Chunk代码很有帮助，因为MemControlBlock里没有保存块大小的字段，所以它的上层——Chunk必须每次在需要的时候传入，而且必须自己保证不会修改传递数字的大小，这是非常基础的假设，宛如二者是一个类，是一个整体，你不能进行自己给自己错误数据的方式进行测试，那肯定是极端疯狂者的做法或者有特殊原因。

明白了这点，在Chunk的代码中关于size_t的意义就非常好理解了。

2.Chunks结构

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

我希望可以在声明上花多一点时间，这有助于你理解系统，从这个角度来说代码片段是没有任何意义的。

Init初始化本Chunk，它有若干MemControlBlock组成，你要指定块数量和块大小，特别要注意的是，如我们上边讨论的，一旦调用成功，你必须保证blockSize的大小每次都一样（永远不改变）。可以预期的是，在Init函数里使用了new方法开辟大块内存，以后每次Allocate都是回传特定一块。

对，还有一点要注意，基于Chunk的内存分配的块大小是在Init中已经确定的，是的，就是我反复强调的blockSize，你无法改变它，使用Allocate分派内存也是这个大小，而且每次一块，从这个层次上来说，这里的内存分配没有任何自由度，你可以认为这是new情况下的char，这是最小的分配单元。

有了以上两点注意，Allocate和Release的功能变的非常简单，取出一块特定大小的内存或归还一块内存。

pData_是Init中new出内存的位置。关于firstAvailableBlock_和blockAvailable_两个数据，是为了高效处理内存Allocate和Deallocate而定义的，使用它们，我们可以避免遍历查找内存块，尽管查找的效率好不错，但是不要忘了我们在做底层基础块，线性复杂度是我们十分不愿意看到的。

3.Chunk实现细节

为了高效查找、分配，我们在分配的时候对各个小块标记偏移位置，未分配的内存可以存放任何数据，所以在每个小块的开始存放偏移量是没有任何问题的，firstAvailableBlock记录第一个可用块，那查找该块的策略就是pData_ + blockSize × firstAvailableBlock，这是索引访问。唯一难理解的是归还内存。

我们知道，firstAvailableBlock指向第一块可用内存（如果有的话），归还的时候，它应该指向我们刚归还的那块，这很好处理firstAvailableBlock  × blockSize = pcur - pData_ ，关键是firstAvailableBlock在归还前指向可用内存如何在以后被检索到，是的，这块内存也应该有偏移量记录，我们可以记录该可用内存的索引，也就是那一刻的firstAvailableBlock了，问题变的异常简单。

具体代码不再贴了，核心三个函数的功能已经讲明白了。

我们使用了偏移量（构造索引查询）得方法避免了检索，这是Chunk效率的核心部分，Chunk又是小对象分配技术的核心部分。

 

 

2.大小一致得分配器

Chunk可以分配固定大小的有限数量内存块，为了达到分配任意多个内存块的目的，我们需要另外一个策略满足这个需求，也就是对Chunk的进一步包装。

小对象的分配技术将固定大小内存分配做成两个层次，当然，更多时候这种划分里考虑效率问题，但是你可以用心体会这里的隔离思想。

FixedAllocator的思想异常简单，为了应对可能的数量不固定的内存块分配，它使用vector存放Chunks，这已经可以解决问题，唯一需要注意的是如何提高效率。

我们记录可用Chunk位置，当有分配请求的时候直接获取，如果可用Chunk用完，则引发一次线性查找，如果还是未找到，那引发一次分配。为了提高哪怕是一点点的归还效率，我们记录最后分配内存的Chunk的位置，在归还的时候优先查询，如果未找到（也就是该块待归还内存不在当前Chunk里），会引发一次线性查找。

是的，FixedAllocator中，查找开始变的多了起来，但是似乎不太容易找到更好的方案了。

为了进一步提高效率，可以使用高速缓冲的策略，归还的内存留待下次使用，而不是直接归还，这是个不错的想法，但是暂时我不优化这个，我更想说的是Loki的小对象分配策略，确切的说是它使用的结构和有限的技术细节。

有必要提一下FixedAllocator的结构和分配方法：

class FixedAllocator
{
private:
    std::size_t        blockSize_;
    unsigned char    numBlocks_;
    typedef    std::vector<Chunk>    Chunks;
    Chunks            chunks_;
    Chunks*            allocChunk_;
    Chunks*            deallocChunk_;
};

void*    FixedAllocator::Allocate()
{
    if(allocChunk_ == 0 || allocChunk_->blockAvailable_ == 0)
    {
        Chunks::iterator    i = chunks_.begin();
        for (;;++i)
        {
            if (i == chunks_.end())
            {
                chunks_.push_back(Chunk());
                Chunk&    newChunk    = chunks_.back();
                newChunk.Init(blockSize_,numBlocks_);
                allocChunk_    = &newChunk;
                deallocChunk_    = &chunks_.front();
                break;
            }
            if (i->blocksAvailable_ > 0)
            {
                allocChunk_    = &*i;
                break;
            }
        }
    }
    assert(allocChunk_ != 0);
    assert(allocChunk_->blocksAvailable_ > 0);
    return    allocChunk_->Allocate(blockSize_);
}

 

 

3.SmallObjAllocator

如果第一次看到小型对象的分配细节，看完Chunk和FixedAllocator之后你一定很迷茫，在内存分配的起初两层，我们总是在研究固定大小的内存块，这似乎没有一点用处，大小一旦确定，你无法分配比blockSize大的内存块，即使是 blockSize得整数倍，因为一次只得到了一块内存，连续两次得到的内存块未必是连续的，你也不适合分配比blockSize小的内存块，这要浪费内存，而且很别扭。其实这都是因为Loki小对象分配器把Chunk和FixedAllocator做为原组使用了，真正分配任意大小内存的是SmallObjAllocator，看一下代码你就肯定明白了：

class SmallObjAllocator
{
public:
    SmallObjAllocator(std::size_t    chunkSize,std::size_t    maxObjectSize);
    void*    Allocate(std::size_t    numBytes);
    void    Deallocate(void*    p,std::size_t    size);
private:
    std::vector<FixedAllocator>    pool_;
};

我们在构造函数里确定最大可分配的内存块大小，但是这并不意味着你只能分配不比maxObjectSize大的内存块，只是对于这样的内存块SmallObjAllocator转发给了系统的new。

我们已经知道，FixedAllocator只能分配固定大小的内存块，是的，到这里你明白了，pool_里有所有大小的Chunk，如此任意大小的块分配都可以转给合适的Chunk。在Deallocate里我们要求提供一个内存块大小的参数，避免pool_级别的遍历。

为了避免可能的内存浪费，pool_里的FixedAllocator并不是从1到maxObjectSize全部一次性分配的，一般情况下，一次性分配对内存的浪费是惊人的，相反，我们采用首次使用分配的策略。在首次使用的时候分配，依FixedAllocator里使用到的策略，我们对最后使用到的FixedAllocator记录以优化查询，最差情况下，SmallObjAllocator进行二分查找。

class SmallObjAllocator
{
public:
    ...
private:
    std::vector<FixedAllocator>        pool_;
    FixedAllocator*                    pLastAlloc_;
    FixedAllocator*                    pLastDealloc_;
};

 

4.SmallObject

小对象分配策略在SmallObjAllocator层已经柳暗花明，可以猜测SmallObject是个顶级包装，使得使用更方便，确实是这样的，“SmallObject的定义 非常简单，只不过情节有点复杂”。

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

需要注意的一点是delete的类级别重载：

class Base
{
public:
    static void    operator delete(void* p,std::size_t    size)
    {
        cout<<"you call my delete"<<endl;
        ::operator delete(p);
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    Base*    haha    = new Base;
    delete    haha;
    return 0;
}

如你所见，delete haha得时候，我们定义的delete得到了调用，也就是编译器提供给了我们额外的一个参数size，这也是Andrei要讨论编译期获取size的策略的原因，编译器给我们传了额外参数，我们有必要了解一下编译器开发者怎么做的。但注意，只是了解，我觉得在这里明白类operator delete以及定义类类虚析构函数的重要性就可以了。

对于整个程序里的SmallObject而言，我们只需要一个SmallObjAllocator，这就是Singleton模式了，可以抢先欣赏一下Loki得SingletonHolder：

typedef    SingletonHolder<SmallObjAllocator>    MyAlloc;
void*    SmallObject::operator new(std::size_t    size)
{
    return    MyAlloc::Instance().Allocate(size);
}
void    SmallObject::operator delete(void* p,std::size_t size)
{
    MyAlloc::Instance().Deallocate(p,size);
}