前言

本篇以源码角度解析UE中标记清除算法GC的实现

https://zhuanlan.zhihu.com/p/401956734

UE 4.26

垃圾回收伪实现

标记清除算法 、 复制算法 、标记-整理算法 、分代收集算法等。我们就用标记清除算法来实现。标记-清除算法，看名字就知道有两个阶段，标记和清除：

  • 标记：遍历所有对象，根据某种规则，标记其是否需要清除
  • 清除：遍历所有对象，清除标记了的对象，回收内存

因此可知，要实现标记清除垃圾回收，在标记阶段我们需要做到以下两点：

  • 能拿到所有对象
  • 确定对象清除的规则

在自定义的 NewObject 方法内，把生成的对象指针放入全局数组 GUObjectArray ，这样我就能拿到所有对象了

以下就是垃圾回收的伪实现：

  • 启动垃圾回收，加锁（ 保持所有对象的引用关系不变 ）
  • 设置所有对象为”不可达”标记（根对象、特殊对象 除外）
  • 遍历根对象列表，根对象引用到的对象去除”不可达”标记
  • 收集所有仍然标记为”不可达”的对象，全部删除

GC过程

GC 启动

  • 手动：UWorld::ForceGarbageCollection( bool bFullPurge)会在World.tick 的下一帧强行进行GC
  • 系统会根据默认的设置（可重新配置）一定的间隔时间或者条件下，自动调用垃圾回收

GC锁

GC锁的主要用处就是为了暂停其他线程以免UObject对象的引用关系在GC过程中发生变化。

1
2
3
4
5
6
void CollectGarbage(EObjectFlags KeepFlags, bool bPerformFullPurge)
{
    AcquireGCLock(); //获取GC锁
    CollectGarbageInternal(KeepFlags, bPerformFullPurge); //垃圾回收
    ReleaseGCLock(); //释放GC锁
}
  • 发送信号，表示我想获取GC锁，GCWantsToRunCounter 自增(原子操作)
  • GC 线程 Sleep，查看 AsyncCounter 是否等于 0 判断其他线程是否有阻塞GC的操作还在执行，不等于 0 就继续等待
  • AsyncCounter = 0，通过另一个变量 GCCounter 递增(原子操作)，来标识正在执行GC，其他所有线程将被阻塞
  • 执行内存屏障
  • 将 GCWantsToRunCounter 设为 0，开始真正的 GC 操作
  • GC 操作完毕， GCCounter 自减释放 GC 锁

内存屏障的主要意思就是，在这个屏障之前的所有读和写的操作，一定会在这个屏障后面的读和写的操作之前执行。为了防范多线程读写操作时序问题导致的逻辑 bug，详细内容自行 Google

获取所有对象

NewObject的时候把生成的对象的指针放入一个全局数组。

这边GUObjectArray 不是数组，就是一个容器体，为了多线程分块扫描

1
2
3
4
5
6
7
8
9
10
11
12
13
//UObjectBase.cpp
//NewUObject方法调用后,UObject对象初始化
UObjectBase::UObjectBase(UClass* InClass..等参数)
{
   AddObject(InName, InInternalFlags); 
}

void UObjectBase::AddObject(FName InName, 
EInternalObjectFlags InSetInternalFlags)
{ 
   //加入GUObjectArray,为Object分配InternalIndex
   GUObjectArray.AllocateUObjectIndex(Object);
}

UObject对象不直接存入容器的，而是被组装成 FUObjectItem 结构：

1
2
3
4
5
6
7
8
9
//UObjectArray.h
//对象存储的结构体,GC操作的就是这个对象
struct FUObjectItem
{
   class UObjectBase* Object; //对象
   int32 Flags;               //EInternalObjectFlags标识
   int32 ClusterRootIndex;    //当前所属簇索引
   int32 SerialNumber;        //对象序列码(WeakObjectPtr实现用到它)
}

对与上面的Flags的标识 有:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//ObjectMacros.h
enum class EInternalObjectFlags : int32
{
   None = 0,
   ReachableInCluster = 1 << 23, ///< 簇中可达
   ClusterRoot = 1 << 24, //cluster root 不会被GC回收,簇根节点
   Native = 1 << 25, // C++类对象
   Async = 1 << 26, //异步对象
   AsyncLoading = 1 << 27, //异步加载中
   Unreachable = 1 << 28, // 不可达对象，会被GC删除
   PendingKill = 1 << 29, // 等待析构，会被GC删除
   RootSet = 1 << 30, // 根节点

    //拥有这三种标记之一的对象在GC检测时会被跳过
   GarbageCollectionKeepFlags = Native | Async | AsyncLoading,
};

标记不可达

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//GarbageCollection.cpp
   void PerformReachabilityAnalysis(EObjectFlags KeepFlags......等参数)
   {
      //从系统提供的数组池中获取数组（为了支持多线程）
      auto ArrayStruct = FGCArrayPool::Get().GetArrayStructFromPool();
      auto ObjectsToSerialize = ArrayStruct->ObjectsToSerialize;

      // 继承了FGCObject的非Uobject对象，放入ObjectsToSerialize
      ObjectsToSerialize.Add(FGCObject::GGCObjectReferencer);

      //将对象标记为不可达,并且将根节点以及不可删除对象放入ObjectsToSerialize
      MarkObjectsAsUnreachable(ObjectsToSerialize, KeepFlags);
      
      //分析ObjectsToSerialize数组内的对象,它能达到的对象,去掉不可达标签
      PerformReachabilityAnalysisOnObjectsInternal(ArrayStruct)
   }

所以 非UObject 对象的 FMyStruct 类继承与FGCObject 可以变成可GC

1
2
3
4
5
6
7
8
9
class FMyStruct: public FGCObject
{
    UObject* NoGCObj;

    void AddReferencedObjects(FReferenceCollector& Collector) override
    {
        Collector.AddReferencedObject(NoGCObj);
    }
}

引用关系分析

MarkObjectsAsUnreachable() 方法消耗不大，因为是多线程操作，且这些 FUObjectItem 结构体对象是内存块连续的数据，对CPU很友好。

怎么去处理对象的引用依赖关系呢？

遍历：通过UObject对象的实例化地址就可以将相应的属性遍历出来，进行读写，等于就是遍历了一整个引用树，这样效率过低。

所以在反射生成阶段就已经用ReferenceTokenStream收集到Token数组中了。

在 https://zhuanlan.zhihu.com/p/58868952有提到这个结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct FGCReferenceInfo
{
    union
    {
        struct
        {
            uint32 ReturnCount  : 8; //引用对象的嵌套深度
            uint32 Type         : 5; //引用对象的类型( EGCRefenceType )
            uint32 Offset       : 19; //当前引用的对象的变量在 Obj 对象内的内存偏移值
        };
        //ReturnCount + Type  + Offset
        //00000000    + 00000 + 0000000000000000000
        uint32 Value; 
    };
};

img

PerformReachabilityAnalysisOnObjectsInternal 代码内最后调用的分析代码是 ProcessObjectArray

代码看原文

HandleTokenStreamObjectReference 会调用 HandleObjectReference，它会去除它的”不可达”标记，并将它加入NewObjectsToSerialize，开辟新的 task 线程去处理，而不是在当前线程递归

清理

遍历 GObjectArray内的数组仍然被标记为不可达的对象放入 GUnreachableObjects ，随后就是执行清除

清理有分俩个逻辑

  • UnhashUnreachableObjects：调用不可达对象的ConditionalBeginDestroy()方法，最终会调用 BeginDestroy()
    • 通知UObject对象，告知这个对象即将被销毁，销毁之前需要做什么事情这是最后的机会
  • IncrementalDestroyGarbage：调用不可达对象的ConditionalFinishDestroy()方法，最终会调用 FinishDestroy()
    • 内部其实也没有真正销毁对象，因为没有调用对象的析构函数
  • TickDestroyGameThreadObjects 调用析构方法的地方
    • 根据GC的设置在下一帧或者规则的时间内执行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//标记RF_BeginDestroyed
bool UnhashUnreachableObjects(bool bUseTimeLimit, float TimeLimit)
{
   while (GUnrechableObjectIndex < GUnreachableObjects.Num())
   {
      ObjectItem = GUnreachableObjects[GUnrechableObjectIndex++];
      UObject* Object = static_cast<UObject*>(ObjectItem->Object);
      Object->ConditionalBeginDestroy();//调用BeginDestroy();
      ++GUnrechableObjectIndex;
   }
   return bTimeLimitReached;
}

//标记RF_FinishDestroyed
bool IncrementalDestroyGarbage(bool bUseTimeLimit, float TimeLimit)
{
         GObjCurrentPurgeObjectIndex = 0;
   while (GObjCurrentPurgeObjectIndex < GUnreachableObjects.Num())
   {
      FUObjectItem* ObjectItem = GUnreachableObjects[GObjCurrentPurgeObjectIndex];
      UObject* Object = static_cast<UObject*>(ObjectItem->Object);
      Object->ConditionalFinishDestroy();//调用FinishDestroy();
      ++GObjCurrentPurgeObjectIndex;
   }
   //真正调用析构函数释放内存的地方
   TickDestroyGameThreadObjects(bUseTimeLimit, TimeLimit, StartTime);
   return bCompleted;
}

因此，GC以后可能会出现的情况是：isVaild(Obj) 仍为 true, 实际上这个对象已经被标记为 PendingKill，只是还未置空。因此可使用 isVaildLowLevel(Obj) 来判断更准确

整个分析过程中，我省略了GC锁操作，多线程分析引用等，是为了更专注分析垃圾回收的流程；其实省略的最大一个块就是：Cluster。为什么需要Cluster ? 因为在游戏过程中很多对象的生命周期一致，是命运共同体。比如：粒子内的一堆东西其实就可以当成一个”对象”来处理，能加快分析速度。

总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void CollectGarbageInternal(EObjectFlags KeepFlags, bool bPerformFullPurge)
{
   FCoreUObjectDelegates::GetPreGarbageCollectDelegate().Broadcast();
   {
      FGCScopeLock GCLock;
      //可达性分析
      {
         PerformReachabilityAnalysis(...);
      }
      //解散簇
      if (GUObjectClusters.ClustersNeedDissolving())
      {
         GUObjectClusters.DissolveClusters();
      }      
      //收集不可达对象释放
      {
         GatherUnreachableObjects(bForceSingleThreadedGC);
         if (bPerformFullPurge || !GIncrementalBeginDestroyEnabled)
         {
            UnhashUnreachableObjects(false);//BeginDestory
         }
      }
      //全量回收
      //执行FinishDestory 必须IsReadyForFinishDestroy(异步对象清理完毕) 
      IncrementalPurgeGarbage(false);     
   }
   FCoreUObjectDelegates::GetPostGarbageCollect().Broadcast();
}

GC问答

了解了GC的流程，你觉得应该怎么优化GC？

  1. 打开簇，将Character，Weapon等生命周期一致的 Actor 对象勾选 Cluster
  2. 最好的优化还是减少UObject对象数量（包括：少用蓝图宏，Level内的Actor数量控制）
  3. 优化GC调用时机，原则上能不调用就不调用，可在关键点调用
  4. 采用对象池，不要频繁清理和生成大的对象
  5. 优化源代码，将可达性分析这块看看能不能改成无锁的方式，加快速度

源码阅读

UE5.2

https://www.bilibili.com/video/BV1qu4y1J7Uj?spm_id_from=333.788.videopod.sections&vd_source=d19e47552f1614194f0d0b0662850083

  • UObjectBasse::ProcessNewlyLoadedUObjects() 中会调用Class->AssembleReferenceTokenStream();
    • 引用关系分析开始
    • 为GC做准备
    • 遍历类型中所有FProperty->EmitReferenceInfo(..);
      • 会设置类型 偏移量->加入Tokens中
  • 入口
  • TryCollectGarbage（）
    • 和CollectGarbage（） 差别就是能不能获取GC锁
    • Try有上限 Try10次的话都获取失败的话就会强制 Force GC
  • CollectGarbage（）
    • CollectGarbageInternal（） 上文有提到
    • CollectGarbageImpl<>()
      • !IsLoading return
      • 执行Flush等待所有异步加载结束
      • 可达性分析 PerformReachabilityAnalysis()
        • 找出根节点 MarkObjectsFunctions（）
          • 找到Root节点以及flag对象 放入函数指针数组 获取所有对象
          • 将root对象放入 LocalObjectsToSerialize[] 中
          • 其他对象组织簇 Cluster objects
          • 分析不需要GC的Flags对象 这些对象会标记不可达 并加一个Flag
          • 可达对象加入 LocalObjectsToSerialize[] 中
          • 每个线程的 LocalObjectsToSerialize[] 会加到 总数组 ObjectsToSerializeArrays[] 中
        • 遍历每个Root节点 PerformReachabilityAnalysisOnObjects（）
          • 多线程与普通的遍历 Root[] 调用ProcessObjectArray（）
            • 取出与遍历TokenStream[]（第一步反射时写入内存的）
            • 最后调用到把对象设置为可达对象
        • 把不可达对象放到一个数组中GUnreachableObjects[]
      • 清理
        • UnhashUnreachableObjects
          • UnhashUnreachableObjects -> 调用BeginDestory（）
          • IncrementalPurgeGarbage -> IncrementalDestroyGarbage（）
            • 对每个不可达对象调用ConditionalFinishDestroy（）->调用FinishDestroy（）
            • 会进行俩次while 因为可能多线程会某些obj依旧在加载中第二次while会等待渲染线程完成
          • TickPurge
            • TickDestroyGameThreadObjects（）调用 obj析构函数
            • 这里会清理内存碎片 省略

Cluster 簇优化

https://zhuanlan.zhihu.com/p/133293284

GC Cluster：UE4垃圾回收优化技术解析

GC Cluster是UE4垃圾回收机制中的一项重要优化技术，旨在减少标记阶段的对象遍历开销，从而降低GC导致的游戏卡顿。

一、GC Cluster的基本概念

GC Cluster是一组UObject的集合，这些对象类型可以不同，但有一个作为Cluster根的对象（ClusterRootObject）。在垃圾回收时，Cluster被作为一个整体处理，其中的所有UObject与ClusterRootObject具有相同的被引用状态。这样做的核心目的是减少标记阶段需要遍历的节点数量，特别是对于复合性逻辑物体（如UClass及其内部的UProperty、UFunction），避免对内部引用关系进行冗余分析。

二、Cluster的创建和管理机制

  1. 配置参数

• gc.CreateGCClusters：是否开启Cluster功能

• gc.ActorClusteringEnabled：是否允许ULevel创建Actor的Cluster

• gc.BlueprintClusteringEnabled：是否允许BlueprintGeneratedClass创建Cluster

• gc.MinGCClusterSize：Cluster中对象的最小数量（默认为5，包括ClusterRoot）

  1. 数据结构

• FUObjectCluster：Cluster在程序中的表示，包含RootIndex、Objects数组、ReferencedClusters等属性

• GUObjectClusters：全局管理的Cluster容器

• FUObjectItem：UObjectArray中的元素类型，通过ClusterRootIndex属性标识对象是否属于Cluster

  1. 创建时机

• 打包版才会创建Cluster，Editor默认不创建

• Package同步加载完成时（EndLoad）

• 异步加载线程加载Package后的后期处理

• Level streaming时更新Components

三、对象加入Cluster的条件

  1. CanBeInCluster()

决定对象是否可以处于Cluster的Objects数组中。默认情况下UObjectBaseUtility可以加入Cluster，但以下特殊情况返回false：
• AActor默认不可加入（bCanBeCluster属性为false），但AStaticMeshActor是特例

• UMaterialParameterCollection、USoundBase、USoundCue、USoundNode、UMediaPlayer、UMediaPlaylist等特殊对象

  1. CanBeClusterRoot()

决定对象是否可作为ClusterRoot创建Cluster。默认返回false，以下类可以成为ClusterRoot：
• UMaterial

• UParticleSystem

• UBlueprintGeneratedClass（需开启项目设置）

• ULevelActorContainer（特殊处理，虽然CanBeClusterRoot()返回false）

四、Cluster在GC过程中的处理流程

  1. 标记阶段（MarkObjectsAsUnreachable）

• 检查位于RootSet的对象，如果是ClusterRoot或位于Cluster中，加入KeepClusterRefsList

• 如果ClusterRoot已被标记PendingKill，则加入ClustersToDissolveList准备销毁

  1. 可达性分析

• 如果索引到Unreachable的ClusterRoot，说明该Cluster可被引用到，会去掉Unreachable标记并通过MarkReferencedClustersAsReachable将整个Cluster变为可达

• 如果索引到Cluster中非ClusterRoot对象，设置ReachableInCluster标记，如果ClusterRoot不可达，则整个Cluster变为可达

  1. Cluster销毁处理

• Dissolve操作：对于ClustersToDissolveList中的Cluster，执行DissolveClusterAndMarkObjectsAsUnreachable，将Cluster包含的对象对应ClusterRootIndex设为0并标记为Unreachable，然后删除Cluster

• 撤销操作：更温和的处理方式，先把Cluster中对象加入ObjectsToSerialize数组，以单个对象方式处理，主要目的是将指向PendingKill对象的指针置为NULL

五、GC Cluster的优化效果

GC Cluster的最大收益来自于BlueprintGeneratedClass，因为其内部包含大量子对象（属性、函数等）。将这些对象作为一个整体进行标记，可以避免大量的引用分析工作，显著减少标记阶段的耗时，从而提升游戏运行时的流畅度。

这种优化特别适合复合性逻辑物体，这些物体内部的对象生命周期通常与父物体一致，但按照传统的标记清扫规则，仍然需要对每个对象间的引用关系进行分析。GC Cluster通过将相关对象”捆绑”处理，在保证正确性的前提下提高了GC效率。

img

如果这个Object本身就是另一个Cluster的ClusterRoot或者位于另一个Cluster中，就不会添加这个Object，取而代之的是把后者Cluster加入到前者Cluster的ReferencedClusters数组中，并把后者Cluster的ReferencedClusters和MutableObjects数据都加入到前者Cluster的对应数组中，使搜寻更便捷。

img

总结

UE GC 是采用标记-清除算法：

收集所有对象→标记根对象→递归标记可达对象→清理不可达对象

  1. 根集（Root Set）：作为GC起点的对象集合，包括全局对象（如GameInstance、World）、当前活跃的Actor/组件，以及通过AddToRoot()显式标记的对象
  2. 标记阶段：从根集出发，递归遍历所有被引用的UObject，标记为“活跃”（可达）
  3. 清除阶段：销毁所有未被标记（不可达）的对象，释放其内存

触发时机：GC会定期自动触发（切换场景强制GC 到达gc时间间隔，内存压力触发），也可通过调用CollectGarbage()手动触发

对象存活条件： 无法被任何“根集”直接或间接引用: 若要在跨帧中保持对UObject的引用，必须在成员变量前添加UPROPERTY()，否则GC会认为该对象无引用而将其回收

对象销毁流程：调用Destroy()仅将Actor标记为“待销毁”，实际内存释放要等到GC运行时执行BeginDestroy()标记PendingKill → 检查引用IsReadyForFinishDestroy() ->FinishDestroy()

收集所有Object GUObjectArray

包装的结构:FUObjectItem

**调用 Destroy()**：对 Actor 或 Component 调用此方法，会将其标记为待销毁，通常在下一帧被GC回收