第10章 容器内存管理——TArray、TMap、TSet深度剖析UE的核心容器——TArray、TMap、TSet——是日常开发中使用频率最高的数据结构也是内存分配最密集的来源之一。一个中等规模的场景中仅TArray的分配次数就可能占到Binned2总分配量的相当比例。本章深入这些容器的内存管理策略TArray的倍增算法与量化、TMap/TSet的开放寻址哈希表实现、TSparseArray的稀疏存储以及InlineAllocator等特殊分配策略。理解它们在内存层面的行为是写出高效UE代码的基础。10.1 TArray——动态数组10.1.1 内存布局templatetypenameElementType,typenameAllocatorTypeFDefaultAllocatorclassTArray{// UE的TArray没有存储Allocator实例FDefaultAllocator是空类ElementType*Data;// 8字节指向堆上的元素数组int32 ArrayNum;// 4字节当前元素数量int32 ArrayMax;// 4字节已分配的容量// 总计TArray本身16字节};堆上数组TArrayint32 本体 (16字节)Data* (8B)ArrayNum (4B)ArrayMax (4B)[0] 使用[1] 使用[2] 使用[3] 未用[4] 未用[5] 未用ArrayNum3 表示已使用 3 个元素ArrayMax6 表示已分配 6 个元素的空间剩余 3 个为空闲 Slack。TArray的16字节本体Data指针 ArrayNum ArrayMax通常作为结构体或类的成员存在于栈或宿主对象中。空的TArray不做堆分配——Data为nullptrArrayNum和ArrayMax均为0。10.1.2 增长策略当ArrayNum ArrayMax时需要扩容。UE使用几何增长接近倍增加量化int32DefaultCalculateSlackGrow(int32 NumElements,int32 NumAllocatedElements,SIZE_T BytesPerElement){int32 Retval;if(NumAllocatedElements||!NumElements){// 已有分配时增长约1.5-2倍RetvalNumElements3*NumElements/816;}else{RetvalNumElements;}// 量化——利用Binned2实际分配的大小SIZE_T SlackFMemory::QuantizeSize(Retval*BytesPerElement,DEFAULT_ALIGNMENT);Retval(int32)(Slack/BytesPerElement);returnRetval;}增长因子3/8对应1.375倍增长再加上16个元素的基底。这比标准的2倍增长更保守避免了大数组扩容时浪费太多空间。量化的意义在于和Binned2配合如果Binned2的Size Class是32KB请求30KB实际分配32KB。TArray通过QuantizeSize得知实际获得了32KB就将ArrayMax设为32768/sizeof(Element)充分利用那2KB的差额。在不支持量化的分配器上如系统malloc这一步不产生额外收益但也不会造成错误。10.1.3 Shrink与EmptyTArrayint32Arr;Arr.Reserve(1000);// 分配1000个int的空间Arr.Add(42);// ArrayNum1, ArrayMax1000// Shrink释放多余空间Arr.Shrink();// ArrayMax缩小到ArrayNum释放多余内存// Empty清除元素但保留内存Arr.Empty();// ArrayNum0, ArrayMax不变Arr.Empty(0);// ArrayNum0, ArrayMax0, 释放所有内存// Reset清除元素保留分配Arr.Reset();// ArrayNum0, ArrayMax不变, 不调用元素析构这三者的区别在析构和内存两个维度上。Empty调用析构并清零Num可选地释放内存Reset不调用元素析构适用于POD或已经手动处理过的元素只清零NumShrink保留当前元素只释放多余空间。选择哪一个取决于你是否还会重新填充Reset/Empty保留容量避免重新分配以及元素是否需要析构。10.1.4 Reserve的重要性// 不好——触发多次扩容TArrayFVectorVertices;for(int32 i0;i10000;i){Vertices.Add(FVector(i,0,0));// 约十余次扩容增长因子≈1.375倍16非2的幂序列// 每次扩容 Malloc Memcpy Free}// 好——一次分配TArrayFVectorVertices;Vertices.Reserve(10000);// 一次Mallocfor(int32 i0;i10000;i){Vertices.Add(FVector(i,0,0));// 无扩容}每次扩容时旧数组的内容要完整拷贝到新位置、旧内存要释放。对于包含堆成员的元素类型如FString、嵌套的TArray扩容还意味着逐个调用移动构造如果元素支持移动或拷贝构造。TArray在扩容时会检查元素类型的trait对于可按字节复制的类型TIsBitwiseConstructible直接使用Memcpy整块搬运对于含有非平凡移动构造的类型逐个调用移动构造器。这十余次扩容累计拷贝的元素数量约为总数的两倍——预分配一次性消除这些开销。10.1.5 MoveTemp与内存转移TArrayFStringSource;// ... 填充SourceTArrayFStringDestMoveTemp(Source);// Source的Data指针转移给Dest// Source变成空数组Datanullptr, Num0, Max0// 无元素拷贝O(1)操作TArray的移动操作仅转移三个字段Data、Num、Max不遍历元素也不涉及堆分配。但要注意移动后源数组变为空再访问它是未定义行为。对于TArray中元素本身的移动Add(MoveTemp(Element))会调用元素类型的移动构造避免深拷贝——对于FString、TArray等含有堆指针的类型差异显著。对于嵌套容器如TArrayTArrayint32移动语义的价值更突出。拷贝一个包含1000个子数组的TArray意味着1000次堆分配加内容复制移动只需转移外层TArray的三个字段所有子数组的堆指针统统原地不动。在函数返回嵌套容器时确保返回值优化RVO生效或显式使用MoveTemp能避免成本昂贵的深拷贝。Emplace进一步避免了临时对象的构造TArrayFStringNames;Names.Emplace(TEXT(Hello));// 原地构造无中间对象// vsNames.Add(FString(TEXT(Hello)));// 构造临时FString → 再移动入数组10.2 TArray的分配器变体10.2.1 FDefaultAllocator默认分配器使用FMemory::Malloc/Realloc/FreeclassFDefaultAllocator{// 空类——无实例数据voidResizeAllocation(...){DataFMemory::Realloc(Data,NewMax*ElementSize,Alignment);}};FDefaultAllocator是个空类不在TArray对象中增加额外字段。所有分配操作直接转发给FMemory最终落入Binned2或当前活跃的分配器。10.2.2 TInlineAllocatorN在TArray对象本身内部内联存储前NNN个元素避免小数组的堆分配TArrayint32,TInlineAllocator4SmallArray;// 内存布局// TArray {// Inline Storage: [0][1][2][3] ← 栈上// Data* → 指向 InlineStorage 或堆// ArrayNum, ArrayMax// }当元素超过NNN时自动切换到堆分配。内联存储区的空间始终存在于对象体中——即使已切换到堆分配后也不释放因为它是对象本体的一部分。这意味着对象永远比默认TArray多占N×sizeof(Element)N \times sizeof(Element)N×sizeof(Element)字节。选择NNN时需要在大概率避免堆分配和每个对象的固定成本之间权衡。SmallArray.Add(1);// 内联存储SmallArray.Add(2);// 内联存储SmallArray.Add(3);// 内联存储SmallArray.Add(4);// 内联存储SmallArray.Add(5);// 超出Malloc堆空间拷贝前4个到堆上Actor的Components列表通常3-10个、碰撞结果缓冲区通常不超过几个等场景是TInlineAllocator的典型用途。10.2.3 TFixedAllocatorN固定容量不会堆分配超出时断言TArrayint32,TFixedAllocator16FixedArray;FixedArray.Add(1);// OK// ... 添加16个后...FixedArray.Add(17);// 断言失败在确定知道上限的场合如固定大小的查找表、平台限定的缓冲区TFixedAllocator既避免了堆分配也避免了InlineAllocator在超出后退化到堆的行为。10.2.4 TMemStackAllocator使用FMemStack分配适合帧临时数据第4章已介绍。分配在当前线程的帧栈上完成帧结束时整个栈一起回收不需要逐个Free。适合在渲染线程或异步计算中收集临时结果。10.3 TMap——哈希映射10.3.1 实现原理UE的TMap基于开放寻址Open Addressing哈希表底层使用TSet实现templatetypenameKeyType,typenameValueType,typenameAllocator,typenameKeyFuncsclassTMap{typedefTSetTPairKeyType,ValueType,KeyFuncs,AllocatorElementSetType;ElementSetType Pairs;};10.3.2 TSet的内存布局templatetypenameElementTypeclassTSet{typedefTSparseArrayFSetElementId,AllocatorElementArray;ElementArray Elements;// 元素存储稀疏数组TArrayFSetElementIdHash;// 哈希桶数组// HashSize通常是Elements容量的2倍// 负载因子约0.5};TSparseArray 元素HashBuckets (8个槽)-12-10-11-1-1[0] KeyB, Val20HashNext1[1] KeyC, Val30HashNext-1[2] KeyA, Val10HashNext-1哈希桶数组存储的是指向Elements数组中第一个落入该桶的元素的索引。如果多个元素落入同一个桶通过Elements内部的HashNext字段形成链表。负载因子约0.5意味着桶数组的大小是元素容量的两倍——这是用空间换时间的典型权衡桶越稀疏冲突链越短查找越快。10.3.3 TSparseArray——底层存储TSparseArray是一个稀疏数组支持O(1)的插入和删除不移动其他元素templatetypenameElementTypeclassTSparseArray{TArrayFElementOrFreeListLinkData;AllocationBitArrayType AllocationFlags;// 位数组标记有效索引int32 FirstFreeIndex;// 空闲链表头int32 NumFreeIndices;};Data数组的每个槽位要么存放一个有效元素要么存放一个空闲链表节点。删除操作不移动元素——只是将该位置标记为空闲加入空闲链表。下次插入时优先复用空闲槽位。这意味着元素的索引在其生命周期内是稳定的外部可以安全地通过索引引用元素。代价是遍历时可能遇到空洞需要检查AllocationFlags来跳过无效槽位。TSet/TMap的迭代器在内部做了这个跳过调用者不需要手动处理。10.3.4 TMap内存开销分析对于NNN个键值对的TMapK,V内存 TSparseArray存储 Hash桶数组 TSparseArray: N × (sizeof(K) sizeof(V) sizeof(int32 HashNext) 对齐填充) 位数组 (N / 8 字节) Hash桶数组: ~2N × sizeof(int32) 8N 字节 大致总计: N × (sizeof(K) sizeof(V) ~12) 8N 字节例如TMapFName, int3210,000个条目元素: 10,000 × (8 4 4 padding) ≈ 200 KB 哈希: 20,000 × 4 80 KB 总计: ~280 KB10.3.5 TMap的Rehash与CompactTMap/TSet在以下情况会触发Rehash重新构建哈希桶数组当负载超过阈值时自动扩容、调用Reserve增大容量、调用Compact/Shrink时。Rehash需要遍历所有有效元素重新计算哈希并插入新桶是O(N)操作。Compact操作更进一步它将TSparseArray中的所有空洞消除把有效元素紧凑地排列在数组前部。这回收了空洞浪费的空间但代价是元素的索引发生变化——任何外部持有的旧索引都会失效。在确定没有外部引用索引的情况下如批量删除后即将遍历调用Compact可以减少内存浪费并改善缓存局部性。10.4 其他容器10.4.1 TSortedMapTSortedMapK,V基于排序的TArrayTPairK,V实现通过二分查找提供O(log N)的查找。相比TMapTSortedMap不需要哈希桶数组内存开销更低只有元素本身的连续数组且遍历时元素按键的顺序排列。在元素数量较少几百以内或需要有序遍历的场景下TSortedMap是比TMap更合适的选择。10.4.2 TChunkedArray对于超大规模的数组百万级元素单次连续分配可能造成虚拟地址空间压力或分配失败。TChunkedArray将元素分散到多个固定大小的块Chunk中每个Chunk独立分配。索引时先定位到对应Chunk再在Chunk内偏移。代价是失去了连续内存的缓存友好性和指针算术的便利。对于顺序遍历Chunk内部是连续的性能与普通TArray相当但跨Chunk边界时会有一次缓存未命中。在元素数量极端庞大或频繁扩缩的场景下分块分配避免了大块连续内存的搬迁成本。在更常见的场景中普通的TArray加Reserve已经足够。10.5 容器选择与内存影响容器查找插入内存模型适用场景TArrayO(N)末尾O(1)*连续内存有序数据、小规模查找TMapO(1)平均O(1)平均哈希表键值查找TSetO(1)平均O(1)平均哈希表去重集合TSortedMapO(log N)O(N)排序数组有序映射、小规模TSparseArrayO(1)索引O(1)稀疏连续稳定索引、频繁增删TArrayViewO(N)只读非拥有零拷贝切片TStaticArrayNO(1)索引不可增长栈/内联固定大小*TArray末尾Add是摊销O(1)一个常见的决策是TArray与TMap之间的选择。经验法则是元素数量在几十个以内时TArray的线性查找可能比TMap的哈希查找更快因为连续内存的缓存友好性且内存开销更低。超过几十个元素后TMap的O(1)查找优势开始体现。10.6 TArrayView——零拷贝视图templatetypenameElementTypeclassTArrayView{ElementType*DataPtr;// 8字节int32 ArrayNum;// 4字节// 总计12字节};TArrayView不拥有内存只是一个指针加长度的组合。它可以从TArray隐式构造也可以手动指定范围voidProcessVertices(TArrayViewconstFVectorVertices){for(constFVectorV:Vertices){// ...}}TArrayFVectorAllVertices...;// 零拷贝传递整个数组ProcessVertices(AllVertices);// 零拷贝传递子范围ProcessVertices(MakeArrayView(AllVertices.GetData()100,50));在函数接口设计中如果函数只需要读取数组内容而不需要修改或拥有它用TArrayViewconst T作为参数比const TArrayT更灵活——它能同时接受TArray、C数组、TStaticArray和手动构造的范围且调用者不需要先把数据放进TArray。10.7 容器内存最佳实践预分配是最基本的优化手段。对已知或可估计大小的容器调用Reserve将多次扩容合并为一次分配TArrayFHitResultResults;Results.Reserve(100);TMapFName,FAssetDataAssetMap;AssetMap.Reserve(10000);减少不必要的拷贝是第二个要点。大容器的传递优先使用const引用或MoveTemp。元素插入优先使用Emplace而非先构造临时对象再Add。如果函数返回TArray编译器的返回值优化RVO通常能避免拷贝但在条件分支中返回不同的局部数组时RVO可能失效——此时显式MoveTemp可以保证移动语义。及时释放不再需要的内存是第三个要点。关卡卸载后、缓存失效后对不再使用的容器调用Empty(0)释放堆内存。如果容器会被重新填充如每帧收集碰撞结果Reset保留分配避免反复分配释放的抖动。Shrink在不确定后续使用模式时提供折中——收缩到当前大小释放多余部分。TArrayFActorSpawnInfoSpawnInfos;SpawnInfos.Empty(0);// 释放所有内存SpawnInfos.Reset();// 保留内存清空元素SpawnInfos.Shrink();// 收缩到当前大小在多人协作的项目中容器的“忘记释放”是常见的内存泄漏来源。一个典型模式是某个管理器类的TMap在关卡切换时没有被Empty下一关的数据叠加在旧数据之上导致容器不断增长。LLMLow Level Memory Tracker的标签可以帮助定位这类问题如果某个Tag的内存在关卡切换后只增不减多半是某个容器没有被正确清理。10.8 容器内存的度量UE的MemReport命令会输出各子系统的内存占用摘要其中包含容器使用的内存。但由于容器分配的内存和其他堆分配混在同一个Binned2池中直接区分容器内存和其他堆内存较难。更实用的手段包括在代码中对特定容器做size计算。TArray的堆内存为GetAllocatedSize()返回ArrayMax * sizeof(Element)。TMap和TSet的GetAllocatedSize()累计了TSparseArray和Hash桶数组的内存。在MemReport的自定义回调或Stat系统中定期上报关键容器的GetAllocatedSize()可以追踪其增长趋势。SIZE_T MapMemoryMyLargeMap.GetAllocatedSize();SET_MEMORY_STAT(STAT_MyMapMemory,MapMemory);在Unreal Insights的Memory Insights视图中可以按分配标签过滤特定子系统的堆分配观察容器增长的时机是否与关卡加载、Streaming等事件对齐。如果看到某个大块分配在关卡卸载后没有对应的释放往往指向一个被遗忘的容器。另一种低成本的检测方式是在调试构建中对容器的SlackArrayMax - ArrayNum做采样。如果一个TArray长期保持50%以上的Slack说明要么预分配过于激进要么在填充完成后忘记了Shrink。10.9 小结TArray是16字节的连续动态数组增长策略为1.375倍加量化与Binned2紧密配合避免Size Class内的空间浪费。Reserve预分配是最基本也是最有效的优化手段。TMap和TSet基于开放寻址哈希表加TSparseArray存储负载因子约0.5每条目的额外开销约12字节。TSparseArray的稳定索引和O(1)增删使TMap/TSet的元素不会因增删而移动但遍历时需要跳过空洞。TSortedMap适合小规模有序映射TChunkedArray适合极端大规模的分块存储。InlineAllocator和FixedAllocator为小规模容器提供零堆分配方案代价是对象本体变大。TArrayView以12字节的零拷贝视图替代const引用传递是函数接口设计中最灵活的数组参数形式。移动语义在容器操作中的价值不可忽视——特别是嵌套容器和含有堆成员的元素类型MoveTemp和Emplace能将深拷贝的O(N)开销降为O(1)的指针转移。