[D3D12]简易DescriptorHeap分配策略

标题怎么取的和大作业似的（

用语

这里写一下一些术语的对照，有些英文单词对应中文不一定准确（

描述符：Descriptor
描述符堆：Descriptor Heap
资源：Resource
分配器：Allocator
奇异模板递归模式：Curiously Recurring Template Pattern（CRTP）

问题

DX12龙书的示例代码是要多少描述符就开多大的描述符堆，如果想稍微封装一下裸API基本上不能采用这样的策略，谁知道运行时有多少资源需要创建描述符呢，甚至一个资源可以创建多个描述符（

对于shader可见的描述符堆来说，由于D3D12某些奇妙的设计或者限制，一次只能绑定两个，且只能是CBV_SRV_UAV和SAMPLER各一个。加上官方文档说，录制渲染命令时更改描述符堆开销巨大（链接），因此在查阅了许多开源RHI、开源引擎源码后发现，大家不约而同的选择了全局开两个很大的ID3D12DescriptorHeap对象，在cmd list开始录制命令时绑定，中途不更换绑定。

对于shader不可见的描述符堆，按理说是可以创建多个了，但是也不能采取，在需要时就直接创建一个新ID3D12DescriptorHeap对象这种做法，除了创建和销毁时的开销，大量对象应该也会导致内存碎片化。（其实也不是不行，只要能接受，和自己和解233）

总之为了让描述符管理看起来更优雅一些，我们需要一种或多种策略组合来管理各种描述符堆。

设计

以下设计实现未经过检验，想一出是一出

如果我们仔细观察D3D12的描述符堆的性质，会发现

许多性质、大小完全一致的描述符组成一个描述符堆
可以通过数字索引来随机访问

好像有点熟悉了，我们向操作系统申请的一块内存不也具有这些性质嘛，由一堆byte组成且可以通过数字索引随机访问（有点抽象但别在意）。

那目前已有的大量内存分配解决方案，是不是也可以套到管理描述符堆上。笔者认为完全可行。

分配器概念

因此首先我们需要约束一下“分配器”这个概念的适用范围。

template <class TAllocator, class TAllocation>
concept is_allocator = requires(TAllocator alloc, size_t size, TAllocation allocation) {
    { alloc.Allocate(size) } -> std::same_as<std::optional<TAllocation>>;
    { alloc.Destroy(allocation) } -> std::same_as<void>;
};

不难看出，分配器具有两个函数

Allocate输入一个size_t类型的长度，返回分配结果，std::optional来表达分配成功或失败（C++26就能用std::result了）,分配的结果是一个抽象类型TAllocation，可以是任意类型，非常自由。我们不需要内存对齐，因此不存在align参数。

Destroy输入之前存在的分配结果，用于回收已被使用的区域。显然，传入参数不可以是其他分配器，或者自己造的结果。

有了概念，接下来就是一系列具体算法实现了。

伙伴算法

这个算法感觉都已经被介绍烂了，CSAPP中也有对其的具体介绍，此处就偷个懒省略掉介绍。

为什么要用这个算法来分配描述符堆？

伙伴算法用来记录空闲链表的是一颗完全二叉树（如果长度是2^n那应该是满二叉树），实际实现里是个数组，节点的合并和分裂只修改数组元素值，0内存分配，理论上会非常快速。

笔者会将它用在分配shader不可见的描述符堆上，这个使用使用场景下描述符基本是一个一个分配的，如果真用链表法串起来会浪费大量内存作为链表节点，但对于伙伴算法来说分配这种大小的块不仅速度很快，大部分时候甚至0描述符浪费，少量需要一次分配多个描述符的情况也不会浪费太多空间。

空闲链表

伙伴算法是一种特殊的空闲链表法，在特殊场景下表现优异，但我们还是需要一种更通用的办法来平衡大部分使用场景。

CSAPP里详细论述了显式空闲链表，笔者还没读完，lab也没做，只大致参考了下思路。

普通内存分配器会在分配时多给些空间，在分配结果的头部藏数据，目前应用场景下就没条件用这种手段了，分配器不太好暴露太多细节出去。

与CSAPP lab的要求不同，笔者希望使用双向链表将所有块，无论空闲还是占用，全都串起来，以便debug时追踪分配状态。

为了快速索引所有块，使用基于hash表的unordered_map，顺便块的生命周期也由它持有，避免链表的递归释放。增删性能不一定高，但应该会比遍历链表快一些（当然也更占空间）（内存分配器分配时会分配更多内存，听起来有点怪）

接着为了索引适合大小的块，使用multimap记录所有空闲块，key表示剩余大小，multimap应该是红黑树实现也不会慢。

定义链表节点。链表节点在64位下要占40字节，有没有办法压缩到32字节呢

enum class NodeState {
    Free,
    Used
};

class LinkNode {
public:
    LinkNode(size_t start, size_t length) noexcept;

    size_t _start;
    size_t _length;
    FreeListAllocator::LinkNode* _prev;
    FreeListAllocator::LinkNode* _next;
    NodeState _state;
};

定义空闲链表分配器的基本结构

class FreeListAllocator {
public:
    explicit FreeListAllocator(size_t capacity) noexcept;

    std::optional<size_t> Allocate(size_t size) noexcept;

    void Destroy(size_t offset) noexcept;

private:
    // 所有节点的索引兼容器
    radray::unordered_map<size_t, radray::unique_ptr<FreeListAllocator::LinkNode>> _nodes;
    // 快速索引适合的剩余空间的节点
    radray::multimap<size_t, FreeListAllocator::LinkNode*> _sizeQuery;
    size_t _capacity;
};

分配时非常简单，只需要找到适合大小的空闲节点，将节点分裂并标记正在使用就行了。如果没有合适的空闲节点则分配失败。

std::optional<size_t> FreeListAllocator::Allocate(size_t size) noexcept {
    if (size == 0 || size > _capacity) {
        return std::nullopt;
    }
    // 遍历适合大小的节点
    for (auto iter = _sizeQuery.lower_bound(size); iter != _sizeQuery.end(); iter++) {
        FreeListAllocator::LinkNode* node = iter->second;
        if (node->_length == size) { // 如果正巧节点大小和所需一致, 只需要标记被使用
            _sizeQuery.erase(iter); // 别忘了从索引中去除
            node->_state = FreeListAllocator::NodeState::Used;
            return std::make_optional(node->_start);
        } else {
            RADRAY_ASSERT(node->_length > size);
            // 分裂后新节点起始和长度
            size_t newStart = node->_start + size;
            size_t newLength = node->_length - size;
            // 分配新节点
            auto [newIter, isInsert] = _nodes.emplace(
                newStart,
                radray::make_unique<FreeListAllocator::LinkNode>(newStart, newLength));
            RADRAY_ASSERT(isInsert);
            FreeListAllocator::LinkNode* newNode = newIter->second.get();
            node->_state = FreeListAllocator::NodeState::Used;
            node->_length = size;
            newNode->_state = FreeListAllocator::NodeState::Free;
            // 连接链表
            newNode->_prev = node;
            newNode->_next = node->_next;
            node->_next = newNode;
            if (newNode->_next != nullptr) {
                newNode->_next->_prev = newNode;
            }
            _sizeQuery.erase(iter); // 别忘记更新节点索引
            _sizeQuery.emplace(newNode->_length, newNode);
            return std::make_optional(node->_start);
        }
    }
    return std::nullopt;
}

回收内存要考虑的就多一些了，要合并邻近空闲的节点以便下次分配时使用，减少碎片率

void FreeListAllocator::Destroy(size_t offset) noexcept {
    auto iter = _nodes.find(offset);
    if (iter == _nodes.end()) {
        RADRAY_ABORT("FreeListAllocator::Destroy invalid offset {}", offset);
        return;
    }
    FreeListAllocator::LinkNode* node = iter->second.get();
    if (node->_state == FreeListAllocator::NodeState::Free) {
        RADRAY_ABORT("FreeListAllocator::Destroy invalid offset {}", offset);
        return;
    }
    // 标记节点空闲
    node->_state = FreeListAllocator::NodeState::Free;
    // 向前找临近的空闲节点
    FreeListAllocator::LinkNode* startFreePtr = node;
    while (startFreePtr->_prev != nullptr && startFreePtr->_prev->_state == FreeListAllocator::NodeState::Free) {
        startFreePtr = startFreePtr->_prev;
    }
    // 向后找临近的空闲节点
    FreeListAllocator::LinkNode* endFreePtr = node;
    while (endFreePtr->_next != nullptr && endFreePtr->_next->_state == FreeListAllocator::NodeState::Free) {
        endFreePtr = endFreePtr->_next;
    }
    if (startFreePtr == endFreePtr) { // 前后没有空闲节点, 更新一下索引就可以了
        _sizeQuery.emplace(node->_length, node);
        return;
    }
    FreeListAllocator::LinkNode* endFreeNext = endFreePtr->_next;
    size_t newSize = 0;
    // 遍历所有临近空闲节点
    for (FreeListAllocator::LinkNode* i = startFreePtr; i != endFreeNext;) {
        newSize += i->_length;
        // 移除老空闲节点索引
        for (auto j = _sizeQuery.begin(); j != _sizeQuery.end(); j++) {
            if (j->second == i) {
                _sizeQuery.erase(j);
                break;
            }
        }
        if (i == startFreePtr) { // 留下第一个空闲节点, 作为合并后的节点
            i = i->_next;
        } else {
            // 释放其他空闲节点
            auto key = i->_start;
            i = i->_next;
            _nodes.erase(key);
        }
    }
    // 更新合并后节点
    startFreePtr->_length = newSize;
    startFreePtr->_next = endFreeNext;
    if (endFreeNext != nullptr) {
        endFreeNext->_prev = startFreePtr;
    }
    // 别忘了索引
    _sizeQuery.emplace(startFreePtr->_length, startFreePtr);
}

动态块

尽管上面我们已经实现了两种分配算法，但它们都建立在一块长度固定的块上，分配过多空间就会Out of Memory，简直是恶魔的低语。

shader不可见的描述符堆是可以创建多个的，我们可以创建多个描述符堆串起来，避免空间不足导致的分配失败。很类似内存池的概念。

因此需要一种全新的分配器，它能创建一个一个的块，每个块内拥有一个独立分配器（套娃）。它能按需创建和卸载抽象的内存。

具体实现与空闲链表类似，依然使用unordered_map+multimap的组合来快速索引可能可以分配空间的块，且为了让分配器能够释放掉多余不需要的内存，我们再引入一个阈值，表示最多存在多少个完全没有被使用过的块。

根据需求，我们可以借助模板实现分配器套娃

template <class THeap>
struct BlockAllocation {
    THeap* Heap;
    size_t Start;
    size_t Length;
};

template <class TSubAlloc, class THeap, class TDerived>
requires is_allocator<TSubAlloc, size_t>
class BlockAllocator {
public:
    BlockAllocator(
        size_t basicSize,
        size_t destroyThreshold) noexcept
        : _basicSize(basicSize),
          _destroyThreshold(destroyThreshold) {}

    virtual ~BlockAllocator() noexcept = default;

private:
    class Block {
    public:
        Block(
            radray::unique_ptr<THeap> heap,
            TSubAlloc&& allocator,
            size_t heapSize) noexcept
            : _freeSize(heapSize),
              _initSize(heapSize),
              _heap(std::move(heap)),
              _allocator(std::move(std::forward<TSubAlloc>(allocator))) {}

        size_t _freeSize;
        size_t _initSize;
        radray::unique_ptr<THeap> _heap;
        TSubAlloc _allocator;
    };

    radray::unordered_map<THeap*, radray::unique_ptr<BlockAllocator::Block>> _blocks;
    radray::multimap<size_t, BlockAllocator::Block*> _sizeQuery;
    radray::unordered_set<BlockAllocator::Block*> _unused;
    size_t _basicSize;
    size_t _destroyThreshold;
};

BlockAllocation<T>表示分配结果，里面存了分配的内存块所在的抽象内存
TSubAlloc表示套娃的分配器类型，使用之前定义的概念约束类型
THeap无约束，表示块持有的抽象内存
TDerived用于奇异模板递归模式获取子类

有了这么多辅助结构，分配过程应该是水到渠成。

先去找所有适合大小的块能不能分配，没有适合的大小或者全都无法分配，则只能创建新块。

std::optional<BlockAllocation<THeap>> Allocate(size_t size) noexcept {
    if (size == 0) {
        return std::nullopt;
    }
    // 去所有可能空闲的块里找还能分配的块
    for (auto iter = _sizeQuery.lower_bound(size); iter != _sizeQuery.end(); iter++) {
        BlockAllocator::Block* block = iter->second;
        std::optional<size_t> start = block->_allocator.Allocate(size);
        if (start.has_value()) { // 分配成功
            _sizeQuery.erase(iter);
            block->_freeSize -= size;
            CheckBlockState(block);
            return std::make_optional(BlockAllocation<THeap>{block->_heap.get(), start.value(), size});
        }
    }
    {
        // 没有能分配的块了，只能创建新块
        size_t needSize = std::max(size, _basicSize);
        radray::unique_ptr<BlockAllocator::Block> newBlock = radray::make_unique<BlockAllocator::Block>(
            static_cast<TDerived*>(this)->CreateHeap(needSize),
            static_cast<TDerived*>(this)->CreateSubAllocator(needSize),
            needSize);
        BlockAllocator::Block* blockPtr = newBlock.get();
        auto [newIter, isInsert] = _blocks.emplace(blockPtr->_heap.get(), std::move(newBlock));
        RADRAY_ASSERT(isInsert);
        size_t newStart = blockPtr->_allocator.Allocate(size).value(); // 理论上一定分配成功，直接unwrap
        blockPtr->_freeSize -= size;
        CheckBlockState(blockPtr);
        return std::make_optional(BlockAllocation<THeap>{blockPtr->_heap.get(), newStart, size});
    }
}

// 检查块的状态, 是不是应该销毁
void CheckBlockState(BlockAllocator::Block* block) noexcept {
    bool isBlockDestroyed = false;
    if (block->_freeSize == block->_initSize) { // 这个块没有分配任何空间出去
        _unused.emplace(block);
        while (_unused.size() > _destroyThreshold) { // 没有分配任何空间的块超过阈值
            auto selectIter = _unused.begin(); // 取哪个都一样, 就取第一个了
            BlockAllocator::Block* selectBlock = *selectIter;
            if (selectBlock == block) {
                isBlockDestroyed = true;
            }
            _unused.erase(selectIter);
            // 别忘了删除空闲大小的索引
            auto [qBegin, qEnd] = _sizeQuery.equal_range(selectBlock->_freeSize);
            for (auto it = qBegin; it != qEnd; it++) {
                if (it->second == selectBlock) {
                    _sizeQuery.erase(it);
                    break;
                }
            }
            // 销毁
            _blocks.erase(selectBlock->_heap.get());
        }
    } else {
        _unused.erase(block);
    }
    if (block->_freeSize > 0 && !isBlockDestroyed) {
        _sizeQuery.emplace(block->_freeSize, block);
    }
}

这里用到了奇异模板递归模式，从子类中调用CreateHeap和CreateSubAllocator来创建新内存、分配器。这两个函数签名必须是

1
2
3

radray::unique_ptr<THeap> CreateHeap(size_t size) noexcept;

TSubAlloc CreateSubAllocator(size_t size) noexcept;

删除时只需要修改下块的索引，没什么难度

void Destroy(BlockAllocation<THeap> allocation) noexcept {
    auto iter = _blocks.find(allocation.Heap);
    RADRAY_ASSERT(iter != _blocks.end());
    // 根据分配结果拿到对应块
    BlockAllocator::Block* block = iter->second.get();
    block->_allocator.Destroy(allocation.Start);
    // 重建索引
    auto [qBegin, qEnd] = _sizeQuery.equal_range(block->_freeSize);
    for (auto it = qBegin; it != qEnd; it++) {
        if (it->second == block) {
            _sizeQuery.erase(it);
            break;
        }
    }
    block->_freeSize += allocation.Length;
    CheckBlockState(block);
}

ID3D12DescriptorHeap 分配器

有了这三种分配器，再来看描述符堆的分配就简单多了，将分配工作全都代理出去就完事了。

我们可以简单封一个描述符堆的类

class DescriptorHeap {
public:
    DescriptorHeap(
        ID3D12Device* device,
        D3D12_DESCRIPTOR_HEAP_DESC desc) noexcept;

    D3D12_GPU_DESCRIPTOR_HANDLE HandleGpu(UINT index) const noexcept;
    D3D12_CPU_DESCRIPTOR_HANDLE HandleCpu(UINT index) const noexcept;

private:
    ID3D12Device* _device;
    ComPtr<ID3D12DescriptorHeap> _heap;
    D3D12_DESCRIPTOR_HEAP_DESC _desc;
    D3D12_CPU_DESCRIPTOR_HANDLE _cpuStart;
    D3D12_GPU_DESCRIPTOR_HANDLE _gpuStart;
    UINT _incrementSize;
};

struct DescriptorHeapView {
    DescriptorHeap* Heap;
    UINT Start;
    UINT Length;
};

然后根据描述符堆是否对shader可见，分成两种分配器

class CpuDescriptorAllocatorImpl final : public BlockAllocator<BuddyAllocator, DescriptorHeap, CpuDescriptorAllocatorImpl> {
public:
    CpuDescriptorAllocatorImpl(
        ID3D12Device* device,
        D3D12_DESCRIPTOR_HEAP_TYPE type,
        UINT basicSize) noexcept;
    ~CpuDescriptorAllocatorImpl() noexcept override = default;

    radray::unique_ptr<DescriptorHeap> CreateHeap(size_t size) noexcept;
    BuddyAllocator CreateSubAllocator(size_t size) noexcept;

private:
    ID3D12Device* _device;
    D3D12_DESCRIPTOR_HEAP_TYPE _type;
};

class CpuDescriptorAllocator {
public:
    CpuDescriptorAllocator(
        ID3D12Device* device,
        D3D12_DESCRIPTOR_HEAP_TYPE type,
        UINT basicSize) noexcept;

    std::optional<DescriptorHeapView> Allocate(UINT count) noexcept;

    void Destroy(DescriptorHeapView view) noexcept;

private:
    CpuDescriptorAllocatorImpl _impl;
};

shader不可见分配器这里稍微套娃了一下，把实现代理出去将BlockAllocator分配结果的size_t强制转成UINT

class GpuDescriptorAllocator {
public:
    GpuDescriptorAllocator(
        ID3D12Device* device,
        D3D12_DESCRIPTOR_HEAP_TYPE type,
        UINT size) noexcept;

    std::optional<DescriptorHeapView> Allocate(UINT count) noexcept;

    void Destroy(DescriptorHeapView view) noexcept;

private:
    ID3D12Device* _device;
    radray::unique_ptr<DescriptorHeap> _heap;
    FreeListAllocator _allocator;
};

shader可见分配器就没啥好说的了，非常标准

这样实现完了以后会发现，欸，这两个Allocator甚至也完全符合分配器的概念

1
2

static_assert(is_allocator<CpuDescriptorAllocator, DescriptorHeapView>, "CpuDescriptorAllocator is not an allocator");
static_assert(is_allocator<GpuDescriptorAllocator, DescriptorHeapView>, "GpuDescriptorAllocator is not an allocator");

这两条断言是可以通过的！精彩.jpg

尾声

至此，我们将分配描述符堆的脏活累活全都封起来，并建立了一套抽象，以后如果想替换实现也非常容易。

不得不说，业余时间研究一些奇奇怪怪的东西，越深入越会发觉基础的重要性。

翻阅CSAPP后才发现它真是大宝库，也后悔为什么以前没有深入学习它以及相关书籍…如果早先时候认真打基础，现在的处境会不会好一些。

但是世上容不得假设，路只能一步步踏踏实实的走

以上所有代码都开源在github

allocator.h

allocator.cpp

参考书籍文章就不一一列出来了，时间跨度太大没有记录过

笔记

#C++ #D3D12

[D3D12]简易DescriptorHeap分配策略

https://ksgfk.github.io/2025/03/25/D3D12-简易DescriptorHeap分配策略/

作者

ksgfk

发布于

2025年3月25日

许可协议

[C++]观察者模式下一篇