UE4/UE5的TaskGraph
UE4/UE5的TaskGraph
简介
TaskGraph是虚幻引擎做多线程开发时，一个非常方便好用的任务框架。这套框架具体做了什么呢？简单说就是创建或绑定了多个线程，根据业务需要把任务调度到不同的线程上来执行。从原理和实现上比较近似于苹果objc的GCD，Java的ThreadPoolExecutor，Unity的JobSystem等多线程任务框架。
这些多线程任务框架，可能只是作为组件的一部分来让业务使用，而UE的TaskGraph与这些框架还是有一些不同的地方。内部管理的线程除了普通的工作线程外，还包括游戏的主线程GameThread，渲染线程RenderThread，RHI等。封装的更激进也更彻底一些，整个TaskGraph贯穿了引擎所有重要的模块。
整个框架非常的复杂，想要理解清楚也非常有挑战性。因此本文主要介绍在业务中怎样使用TaskGraph，以及梳理内部的实现原理，UE5和UE4的TaskGraph对比和改进点，当然也会介绍一些TaskGraph多线程优化的内容。
基础知识
先简单科普一些UE中多线程的基础知识，非常简单，如果已经了解了可以自行跳过。
首先是上一篇中的基础知识在这里也同样需要了解，这块就不反复提了：
还有一些UE的多线程的基本对象或API
阻塞
UE的源码里叫做Stall，源码很多地方都会出现这个单词，可能其他支持多线程的语言或代码会叫做Blocking(Java)。本质是程序主动让出CPU的执行权，让CPU可以有机会去执行别的线程或者休息。UE中的锁，事件，Sleep函数等都会产生阻塞。
上面一篇中我们知道，LockFree操作一般都是写在一个循环中，最后CAS根据结果来决定是否回滚，全程是没有让出CPU的，如果并发量大，严重的数据竞争会导致CPU使用率暴涨，尤其是移动平台很容易出现发热降频等问题。和LockFree的失败回滚机制不同的是，阻塞发生后当前线程就不占用CPU了，反而CPU可以得到休息或者去执行别的线程，这里是需要注意的一点。
写UE业务代码时也有个大致的原则：GameThread要尽量避免写有阻塞的代码防止掉帧，而其他异步执行的工作线程要多考虑用阻塞的方式，尽量避免写有循环并通过CAS回滚的代码，防止机器发热降频。
锁
锁主要是操作系统提供的一种机制，可以让在锁的作用范围内的代码，在同一时间只能有一个线程执行，其他线程会阻塞等待，直到正在访问的线程离开作用域才可以继续执行。UE提供的锁，主要有FScopeLock，FScopeUnlock，FScopeTryLock，FWriteLock，FReadLock，FRWLock等，前面3个是互斥锁，后面3个是读写锁。这些都是以C++的class方式提供的，利用了C++的RAII机制保证在生命期内加锁或解锁成对出现（构造函数加锁，析构函数解锁）。
加锁和解锁，是通过对象构造和析构自动调用
锁在windows上是临界区
- 互斥锁：在Windows上是通过临界区实现的，而在其他平台是通过pthread提供的mutex实现的。临界区本身细节这里不细说，本质是操作系统提供的一对API（EnterCriticalSection/LeaveCriticalSection），保证这对API之间的代码同一时刻只有一个线程能访问。另外临界区本身不是系统的内核对象，从性能上对比，比系统的内核对象mutex要好很多。当然也有封装系统内核对象级别的互斥锁，UE封装成了FSystemWideCriticalSection。这里比较重要的一点是，UE提供的锁是同一线程可重入的，也就是说，递归加同一个锁是不会出现死锁的，会在最外层的锁释放时，锁才会真正释放。
- 读写锁：和互斥锁差不多，互斥锁的问题是无论是否修改数据，都只能有一个线程访问，但假如只读数据，不改数据，即使多线程访问也不会有问题，如果用互斥锁性能就会很差，为了提升一些加锁并行度就有了读写锁。具体就是这样的规则：
- 允许多个线程同时占有读锁，只允许一个线程占有写锁
- 一个线程占有写锁的时候，其他线程不能占有读锁
- 一个线程占有读锁的时候，其他线程不能占有写锁
- 写锁释放后，写期间更新的数据对所有线程生效
事件
事件也是操作系统提供的机制，和锁做的事情是差不多的，都是阻塞唤醒线程，区别在于不同的控制方法。锁是一个线程访问到了加锁区域后，其他线程如果也进入这一区域就会被阻塞，当这个线程离开加锁区域其他线程会被唤醒继续执行。而事件是让业务程序可以主动的阻塞当前线程，或者主动的去唤醒其他线程，而不用考虑是否进入了某段区域。UE封装成了FEvent对象，对象上有两个函数，Wait函数会阻塞，Trigger会唤醒。
当然Wait也有几个重载版本，可以指定需要阻塞多长时间自动唤醒，不指定时间会无限阻塞，直到手动调用Trigger才会唤醒。
在Windows上封装的Event内核对象，Wait实际是调用WaitForSingleObject来阻塞，而Trigger是调用SetEvent来唤醒的。在其他平台是通过pthread库提供的mutex和cond组合模拟出来的，直接用mutex阻塞，通过broadcast/signal来唤醒，效果和windows上的基本一致，这里不过多介绍细节了，有需要可以自行搜索。
信号量
如果学过操作系统，肯定知道线程同步还有个更高级的信号量，但是UE基本没用到，只有在渲染底层DX12或vulkan涉及到多线程的代码里有局部使用。（DX12: Handle -> CreateSemaphore，Vulkan: FSemaphore -> vkCreateSemaphore）。本质上信号量和事件没区别，都是主动阻塞唤醒，唯一不同的点是信号量内部额外维护了一个计数器，可以知道阻塞了多少次，这样可以在唤醒时去检测这个计数来知道有多少个地方还在阻塞等，能更精细的控制线程调度，信号量本身细节这里不过多说了，如果有兴趣可以自行了解，
可见性
在写代码时如果用到了锁，本身感觉好像只是保证了锁的区域内数据在出了多线程范围，就会同步给其他线程，但实际情况是周围的一些没被锁保护起来的变量，虽然值只在本地有改写，但也有可能被同步到了所有线程。如下图所示
线程A加锁前的代码块执行的结果，对线程B不可见，数据可能还在寄存器上。线程A加锁结束的时候，线程B可以看到代码块内加锁前的结果（不一定是这样，如果没发生编译器或CPU的代码重排，或者数据在同一个缓存行上肯定就会一起同步过来）。
UE也有提供对应的API：FPlatformMisc::MemoryBarrier()让程序可以利用这一个机制，防止CPU或编译器做指令重排。一定保证在屏障之前的代码都执行完，再执行屏障之后的代码。会把屏障代码之前计算的结果同步到内存。这个API本身性能要比锁好很多，源码中很多地方都能看到使用。
原子变量
UE4的原子变量TAtomic，本身也支持更细粒度的控制数据同步。这里只简单说一下Relaxed就是程序完全不关心内存是否同步，而SequentiallyConsistent会严格保证顺序
而UE5直接废弃掉了原子变量TAtomic，直接使用std::atomic，提供有6种控制方法：
对比下来UE4提供的TAtomic只有releaxed和seq_cst这两种模式，还不如标准库，所以直接废弃掉也是合理的。因为这个不是重点，每种模式的区别具体不细说了，可以参考：std::memory_order - cppreference.com这里讲的很详细，包括示例等。进一步理解可以参考上一节讲的缓存相关部分，再结合这个大佬的回答：如何理解 C++11 的六种 memory order？ - 知乎 (zhihu.com)
TaskGraph
异步Task
要执行异步Task，最简单的就是使用Async这个全局函数:
可以看到，其实这个函数就是一个通用的执行异步逻辑的函数，异步的Task就是一个lambda，而第一个参数分为这样几种：
- Thread，通过创建独立的线程执行Task，也可以直接使用AsyncThread函数
- TaskGraph，通过TaskGraph来执行Task，也可以使用AsyncTask函数
- TaskGraphMainThread，也是TaskGraph来执行Task，但是会在主线程上执行
- ThreadPool，通过线程池来执行Task，也可以使用AsyncPool函数
- LargeThreadPool，通过编辑器专用的线程池来执行Task
其实这就是一个大入口，当然更便捷的还有3个函数AsyncThread，AsyncTask，AsyncPool。本质上就是自动填好了第一个参数的Async。当我们传不同参数的时候，这个Task就会在不同线程上执行，假如这个task记录了stat，那么对应的stat信息就要到如下图所示的线程中去寻找
当然还有别的入口，这里只是说最简单的情况。上图也看到了，其实UE的多线程，也就是由这些线程组成的，大致分为3类：
其中TaskGraph中分为NamedThread和WorkerThread，我们平常说的游戏线程，渲染线程，RHI线程，就都是NamedThread，而除此外还有一大堆工作线程。
除了TaskGraph外，UE还提供了线程池，这些线程池都是以全局变量的方式被定义，分为GThreadPool，GIOThreadPool等，和TaskGraph功能差不多但没有TaskGraph这么复杂，看名字也能知道，是根据功能不同划分的，其中GIOThreadPool就是专门执行IO任务的。对于直接定义线程，或者线程池来执行Task，本身实现比较简单这里就不多说了。
线程
UE的线程接口是FRunnable，而对应实现是FRunnableThread。
但他们不是继承关系而是组合关系。具体关系如下：
在Windows上创建的是FRunnableThreadWin，而手机安卓/iOS或linux/Mac上是FRunnableThreadPThread，也就是pthread库提供的线程，而FakeThread是给单线程提供的假线程对象，可以模拟多线程。上面说的无论是NamedThread或者WorkerThread，以及线程池中的线程，或者自定义的线程，最终创建的都是FRunnableThread实例。
这里没什么需要特殊说的，如果是开发手机游戏，有一个小优化可以注意一下，就是在创建线程时，StackSize建议改小一些，或者少创建一些线程，可以显著降低游戏的内存占用（但不能小于PTHREAD_STACK_MIN否则会失败），因为这部分内存是启动就会分配的。
上面关系图中可以看到还有个ThreadManager
看名字都可以知道，他其实是线程的管理器，全局单例，可遍历或通过id获取所有运行的FRunnableThread对象。线程创建和销毁时，会主动调用AddThread和RemoveThread到内部注册，业务如果需要，可以用这个单例来找到对应的线程对象。
TaskGraphInterface
UE的TaskGraph其实是由两部分组成，一部分是Graph，另一部分是TaskGraphInterface。Graph部分是处理Task之间的依赖关系的，在这里的Task其实还没有进入TaskGraph，会根据Graph的执行情况，来选择性把Task丢给TaskGraphInterface来执行。而TaskGraphInterface这部分，本质上是一个任务调度执行器，外部传进来的Task，按照指定参数派发到不同线程的队列上。其实这部分是不管依赖关系的，就是按照进入队列的顺序执行。下面就是具体怎样执行Task的流程
可以看到，分为了两部分，一部分就是NamedThread，另一部分就是WorkerThread。这里要注意的是，对于NamedThread，每个线程都有一个独有的Task队列，这个队列就是上一篇讲的FStallingTaskQueue。而对于WorkerThread，是多个线程共享同一个Task队列。当一个Task进来时，如果指定了线程就直接丢入对应线程的消息队列，命名线程会在一个大循环中持续取Task来执行。如果没指定具体线程而是AnyThread，FStallingTaskQueue会根据标记位找到一个空闲的线程，通过事件FEvent唤醒并将这个Task派发给这个线程来执行，每个工作线程其实也是一个大循环从队列中取任务执行，唯一不同的是在取不到任务时就会进入阻塞状态，交出CPU资源。
上面说的这个大循环两种模式，其实就是下面这两个函数：
ProcessTasksUntilIdle 持续执行Task，如果没Task了就Stall 必须主动Trigger才会唤醒继续执行 AnyThread的模式 ProcessTasksUntilQuit 持续执行Task，如果没Task了也继续循环取，根据参数决定是否Stall（渲染线程会Stall） 必须主动调用RequestQuit才会退出循环 NamedThread的模式
对于WorkerThread的Task，也会按照优先级会丢到不同的线程上，分为NP，HP，BP3种级别，其实就是这3个的缩写
这里的优先级，在业务上其实没区别，并不是说高优先级的就一定会先执行，这里只是为了人为的错开不同的线程，让不同的Task可以在不同的线程上执行。可以这样理解，大部分情况都是普通Task，那么都在NP线程上执行，这时需要优先执行某个Task，如果还是提交到NP线程上可能就会等很久，要等前面的Task都执行完。但如果丢到HP线程上，如果HP线程上没任务，这时候就会立即执行这个Task，从而表现出优先级更高的情况。当然这些不同优先级的线程也不是完全一样的，创建线程时会设一个优先级的参数传给操作系统，高优先级的线程系统会优先唤醒，低优先级的线程系统不会优先唤醒，如下图所示。
然后再来具体说说 FStallingTaskQueue，前面一篇也说了只能最多管理26个线程，如果是在DS上执行，需要魔改下面这个值，且额外定义一个结构支持更大的值，当然代价是ABA更容易冲突。
UE5提供了Scheduler这样的新机制，而且默认使用新机制，可以不限数量，支持处理器组（操作系统规定处理器组最多64个线程，超过了就会分组），完美满足超过64核的机器使用。
具体就是通过TaskGraphInterface不同的实现类做到的，UE4是通过FTaskGraphImplementation实现。UE5默认是FTaskGraphCompatibilityImplementation，可通过关掉GUseNewTaskBackend控制台指令切回旧版实现
处理器组是什么，这里不细说，可以参考Processor Groups - Win32 apps | Microsoft Docs
前面这部分很简单，其实就是根据队列顺序依次消费Task来执行，而TaskGraph最强大的地方在于不同的Task之间可以设置先决条件，下面就来说说具体怎样做到这一点的
TaskGraph
先来说下怎样使用TaskGraph，让有依赖关系的Task可以按照既定的方式执行
假设有8个Task，按照上面这个有向无环图执行，这个情况就非常复杂了。其实用TaskGraph来描述这样的行为，代码很好写，如下图所示
可以看到，我在每个Task中都打了Log输出当前Task名，结束的时候输出 Finish。运行，结果如下图：
我这里没打印线程id，但其实是在多个工作线程上执行的。简单这样几行代码，具体怎么做到依赖的呢？我们先看这里面的几个关键的东西，FGraphEvent，CreateAndDispatchWhenReady的参数Task。这里我直接把内部结构画了图：
上面的lambda其实就是对应的TTask，进入CreateAndDispatchWhenReady函数后，其实是通过模板把TTask核TGraphTask这两个类绑定到了一起，他们是组合关系，通过模板可以生成任意子类。而真正处理依赖关系是在基类FBaseGraphTask上。
我们先来说TTask，预定义的有下面这几种
FReturnGraphTask 会返回到调用ProcessThreadUntilRequestReturn的线程 FNullGraphTask 什么都不做，只用TGraphTask的功能，可以把多个依赖转为1个 FTriggerEventGraphTask 封装FEvent，执行时主动Trigger FDelegateGraphTask/FSimpleDelegateGraphTask Simple版的Delegate无参数，普通版有带DoTask的两个参数 TFunctionGraphTaskImpl 封装lambda的Task 当然也可以自己定义，UE提供了模板，不过是写在了注释里，这个看看就好：
这里有个关键的函数，模板上没写，但需要指定一个返回值：
在Task执行时，会根据这个值来决定是否派发后续的Task。
前面说了处理依赖主要是靠着FGraphEvent，这里要说清楚机制，要从内部成员变量说起
第一个成员变量，SubsequentList存着后续要执行的任务列表。每个Task在创建的时候，会把自己Add到其他自己依赖的SubsequentList里。自己执行完，会对自己的SubsequentList挨个执行ConditionalQueueTask。而每个FBaseGraphTask内部有个计数NumberOfPrequistitesPOutstanding，当计数为0的时候就会进入TaskGraphInterface。
还是用前面这个图的一部分来说吧：
这里代码是这样写的，这个数组是多少，创建Task后，内部的计数就是多少。因此Task 8内部的计数为2，当Task6执行完后，会执行到ConditionalQueueTask，把Task 8的计数减1，而Task 8计数为1，这时什么都不做。当Task 7执行完的时候，也会执行到ConditionalQueueTask，这时Task 8的计数为0，那么就会调用QueueTask，把Task 8丢入TaskGraph中执行。这样就实现了依赖。
而对于一开始不想马上执行的Task，UE也提供了一个Hold函数，其实本质就是让计数设为1，当主动调用Unlock时，才会把Task解锁继续执行。本质上和加了一个前置任务是一样的，只是这个前置任务需要手动触发。如上图所示。
第二个变量，EventsToWaitFor，这个是专门给DontCompleteUntil函数使用的等待列表，上面第一个参数可以说是自己执行完，需要接着执行的Task，而这个参数表示的是这里Wait的Task执行完，才会有可能执行自己。
内部本质其实是在自己执行完之后，准备派发后续Task的时候，如果有WaitFor就先不要让后续任务开始，而是创建一个新的NullTask，把自己的后续任务都转交给这个新的NullTask，而WaitFor的任务会作为新的NullTask的依赖，这样就相当于自己的Task做完了也不结束，等到WaitFor的做完才结束，就达到了DontCompleteUntil的目的。
这里可能说的有些绕，可以简单这样认为：第一个参数是自己完成之后准备要做的Task，第二个参数是自己做完之前要先完成的Task。创建一个新NullTask是因为自己已经做完了，没法等待了，而新的NullTask是还没有开始的状态，已经做完的任务没法再依赖别的任务了这时不派发后续就再也没有机会派发了，而新的Task可以依赖别的任务做完再派发，这样就可以让TaskGraph在中途插入新的等待任务了。
第三个变量，ReferenceCount，这个计数其实是提供了类似于TSharedPointer的机制，只是侵入式，内部自定义的，当计数为0的时候就会销毁。为什么要设计成这样，因为FGraphEventRef不仅是内部会持有，外部也会持有（前面示例创建的Task 8类型就是FGraphEventRef），所以必须有一个很明确的方式管理好对象生命周期，智能指针的机制正好就能很好满足这个要求。创建Task的时候，Task之间如果有依赖就会持有对方引用，同时外部业务也可以拿着FGraphEventRef这样的引用，无论是内部还是外部，最后一个被释放掉时，这个对象就会真正销毁。反过来说，只要还有一个地方在持有就不会销毁，内部Task的内存会一直被保留着，这也是业务在使用时要注意的地方，执行完或加完依赖的Task，就不要继续拿着FGraphEventRef对象了。
前面那张图上，还有一个要注意的部分，就是左上角这里。这部分是UE5特有的，为了支持任意多个线程新加的机制。这里简单看看成员
这里没什么需要特别说的，但其中有个比较黑科技的地方需要提一下：TaskBase中PackedData的DebugName，这里实际传进来的是TChar*指针，但是这里只占用了57位。为什么这样不会有问题呢？看这里有具体解答，为什么64位机指针只用48个位？ - 知乎 (zhihu.com)
为什么要专门提这一点，其实想说的是，不仅仅是TaskGraph，很多地方都可以通过这样的机制来实现一些意想不到但又性能很好的功能，甚至之前见过有些垃圾回收器都是利用指针末几位来记录额外信息的，这里不展开说了。
TaskGraph的问题和改进
TaskGraph在实际使用中其实也是有一些不太好用的地方，比如上面的执行到Task2时，临时决定不想执行后续节点了，这时该怎么做呢？这种情况真实情况是比较常见的，比如在实现类似蜘蛛侠那种加载task，一开始很可能建立了一个很长的Task链，然后执行到中间某个节点时，地图已经都离远了没加载完的Task也可以不用继续做了，这时就需要取消掉剩余Task。
TaskGraph并没有提供取消这样的接口，一般情况，可能业务就要在自己的每个Task中主动监听某个外部变量来实现功能，但这样对于TaskGraph来说，后续的所有任务，都抛到了对应的线程上执行了一遍，只是内部没有做事情而已，这个过程本身也产生了空耗。那么从TaskGraph内部入手，前面在说FGraphEvent派发的时候，如果调用了DontCompleteUntil，会把派发列表转交给NullTask，那么我们可以在这里改造一下，不要转交了，而是给Task加一个标记，直接递归把派发列表丢掉即可达到目的。
另外一个不好用的地方是，Task没法反复执行，或像协程一样可以中断，恢复执行。在上层包成多个Task本质上也是没有问题的，但是也可以通过修改TaskGraph来做到这一个功能。我们可以在ExecuteTask函数中给TTask加一些参数，由业务设置参数来指定协程阶段或标记，在DispatchSubsequents中根据这个标记来决定是否派发后续Task：如果没有结束，就把自己重新QueueTask不派发后续Task，如果协程彻底结束就派发后续Task。