L.  / 内存管理
create

内存管理

在游戏开发时,内存的操作尤为重要。如今游戏普遍在60fps以上,而CPU/主存的带宽远低于GPU/显存的带宽,同时CPU访问内存的延迟通常在100ns左右。如果我们能规划好内存的管理,让缓存命中率提高,则能够降低这个延迟。

C++的中new和delete并不能直接对内存进行操作,而是通过操作系统进行间接操作。若我们频繁使用new和delete操作内存,势必会因系统的调用而增加操作延迟,所以我们可以使用内存的时候,直接申请一大块内存空间,并自行管理这块内存空间,从而减少操作系统的底层调用次数。

另外,自己的内存管理器能更好的Debug、对齐等等的优点。

Allocator

从零开始手敲次世代游戏引擎(十八) 中,利用block chain的技术进行内存分配。

Memory structure

struct BlockHeader {
    BlockHeader* pNext;
};

struct PageHeader {
    PageHeader*  pNext;
    BlockHeader* Blocks() { return reinterpret_cast<BlockHeader*>(this + 1); }
};
Allocator API
class Allocator {
public:
    static const uint8_t PATTERN_ALIGN = 0XFC;
    static const uint8_t PATTERN_ALLOC = 0XFD;
    static const uint8_t PATTERN_FREE  = 0XFE;

    Allocator();
    Allocator(size_t data_size, size_t page_size, size_t alignment);
    Allocator(const Allocator* clone);
    Allocator& operator=(const Allocator& rhs);
    ~Allocator();

    void Reset(size_t data_size, size_t page_size, size_t alignment);

    void* Allocate();
    void  Free(void* p);
    void  FreeAll();

private:
    BlockHeader* NextBlock(BlockHeader* pBlock);
    PageHeader*  m_pPageList;
    BlockHeader* m_pFreeList;

    size_t   m_szDataSize;
    size_t   m_szPageSize;
    size_t   m_szAlignmentSize;
    size_t   m_szBlockSize;
    uint32_t m_nBlocksPerPage;

    uint32_t m_nPages;
    uint32_t m_nBLocks;
    uint32_t m_nFreeBlocks;
};

分配器维护一个page list和free list,当程序申请内存空间时,从free list返回指针,并更新free list。

Allocator implementation
  • 构造解析函数
Allocator::Allocator()
    : m_pPageList(nullptr),
      m_pFreeList(nullptr),
      m_szDataSize(0),
      m_szPageSize(0),
      m_szAlignmentSize(0),
      m_szBlockSize(0),
      m_nBlocksPerPage(0) {}

Allocator::Allocator(size_t data_size, size_t page_size, size_t alignment)
    : m_pPageList(nullptr), m_pFreeList(nullptr) {
    Reset(data_size, page_size, alignment);
}

Allocator::~Allocator() { FreeAll(); }
  • 初始化配置函数
#ifndef ALIGN
#define ALIGN(x, a) (((x) + ((a)-1)) & ~((a)-1))
#endif

void Allocator::Reset(size_t data_size, size_t page_size, size_t alignment) {
    FreeAll();

    m_szDataSize = data_size;
    m_szPageSize = page_size;

    size_t minimal_size = (sizeof(BlockHeader) > m_szDataSize)
                              ? sizeof(BlockHeader)
                              : m_szDataSize;
#if defined(_DEBUG)
    assert(alignment > 0 && ((alignment & (alignment - 1))) == 0);
#endif

    m_szBlockSize     = ALIGN(minimal_size, alignment);
    m_szAlignmentSize = m_szBlockSize - minimal_size;
    m_nBlocksPerPage  = (m_szPageSize - sizeof(PageHeader)) / m_szBlockSize;
}

此处初始化Page和Block的大小以及对齐尺寸。首先保证alignment为2n ,然后将block size设置为k×2n ,此时补齐尺寸(m_szAlignmentSize)则为m_szBlockSize - minimal_size,再计算每页的Block数。结构示意图如下

Block chain structrue
  • Allocate
void* Allocator::Allocate() {
    if (!m_pFreeList) {
        PageHeader* pNewPage =
            reinterpret_cast<PageHeader*>(new uint8_t[m_szPageSize]);
        ++m_nPages;
        m_nBLocks += m_nBlocksPerPage;
        m_nFreeBlocks += m_nBlocksPerPage;

        // push new page
        if (m_pPageList) pNewPage->pNext = m_pPageList;
        m_pPageList = pNewPage;

        // the first block in page
        BlockHeader* pBlock = pNewPage->Blocks();
        // fill block
        for (uint32_t i = 0; i < m_nBlocksPerPage - 1; i++) {
            pBlock->pNext = NextBlock(pBlock);
            pBlock        = NextBlock(pBlock);
        }
        pBlock->pNext = nullptr;  // the last block
        // push free block
        m_pFreeList = pNewPage->Blocks();
    }

    BlockHeader* freeBlock = m_pFreeList;
    m_pFreeList            = m_pFreeList->pNext;
    --m_nFreeBlocks;

    return reinterpret_cast<void*>(freeBlock);
}

BlockHeader* Allocator::NextBlock(BlockHeader* pBlock) {
    return reinterpret_cast<BlockHeader*>(reinterpret_cast<uint8_t*>(pBlock) +
                                          m_szBlockSize);
}

从构造新页说起(if块),流程如下图。一格代表一字节(uint8_t),而size的单位都是一字节(图中一格),所以计算next blockl的位置时转换为字节计算。

Allocate
  • Free & FreeAll
void Allocator::Free(void* p) {
    BlockHeader* block = reinterpret_cast<BlockHeader*>(p);

    // push free block
    block->pNext = m_pFreeList;
    m_pFreeList  = block;
    ++m_nFreeBlocks;
}

void Allocator::FreeAll() {
    PageHeader* pPage = m_pPageList;

    while (pPage) {
        PageHeader* _p = pPage;
        pPage          = pPage->pNext;
        delete[] reinterpret_cast<uint8_t*>(_p);
    }

    m_pPageList = nullptr;
    m_pFreeList = nullptr;

    m_nPages      = 0;
    m_nBLocks     = 0;
    m_nFreeBlocks = 0;
}

此处我还未学到同步、异步、线程安全等特性,故此笔记未完...

←To Be Continued