面向数据编程与任务系统

June 25, 2023About 22 min

面向数据编程与任务系统

现代游戏引擎对于性能的需求非常高，为了保证游戏的实时性需要使用大量的高性能编程技术。

Basics of Parallel Programming

随着硬件技术的发展，芯片中晶体管的大小(2nm)已经接近了物理极限。
因此在现代计算机中会使用多核(multi-core)处理器来进一步提升计算性能。

Process and Thread

**进程(process)和线程(thread)**是并行编程会涉及到的基本概念。
简单来说一个程序就是一个进程，它拥有自己的内存空间；
而一个进程可以拥有很多线程，它们会共享进程指向的同一片内存数据。

对于多核的计算机我们希望能够充分利用不同的计算核心来提升程序的性能。
根据处理器管理任务的不同可以把进程调度分为两种：抢占式(preemptive multitasking)和非抢占式(non-preemptive multitasking)式。
preemptive multitasking是由调度器来控制任务的切换，而non-preemptive multitasking则是由任务自身来进行控制。

Thread Context Switch

线程在进行切换时会产生额外的开销，因此在游戏引擎中我们希望尽可能减少线程的上下文切换。

线程被打断的话会调用中断，开销至少是2000个CPU Cycles, 最快的指令只需要一个Cycle.
线程切换后还需要从内存中获取数据，需要更大的CPU Cycle开销，如图右上.

Parallel Problems in Parallel Computing

在并行程序中我们希望不同的任务之间互不打扰，只需要在程序最后把所有的计算结果进行汇总就好。
这样的程序往往有着非常高的运行效率，比如说蒙托卡罗积分就是典型的例子。
不过现实中的程序往往不会这样理想，很多任务之间存在各种相互依赖，这会降低程序的运行效率。

Data Race in Parallel Programming

data race是编写并行程序中最常见的问题，当不同的线程想要访问并修改同一块内存时就会产生data race。
由于线程的调度是不可预料的，data race会导致程序的计算结果出现各种各样的问题。

Blocking Algorithm

处理data race最简单的方式是给程序上锁(lock)，这样可以保证同一时间只能有一个线程对指定的内存区域进行访问。
锁之间的程序片断称为critical section，当某个线程执行critical section时其它需要访问同一内存的线程会被强制等待。
Critical section 本质就是一种阻断式编程。

尽管使用锁可以保证程序的正确执行，但锁的存在会影响程序的并行性。
更严重的是它可能会产生死锁(dead lock)的现象从而阻塞程序的运行。
因此在编写并行程序时需要注意尽可能减少锁的使用。
不能保证Task成功，Task的Crash会导致整个系统死锁。
高优先级很难打断。

Atomic Operation

处理data race的另一种常用方法是使用原子操作(atomic operation)。
原子操作是硬件层面实现的最基本操作，它无法同时被多个CPU一起执行。
利用原子操作可以实现无锁的程序并行，从而极大地提升运行效率。

Lock Free的空白区是CPU在等待，要高效利用CPU，需要降低等待时间

Complier Reordering Optimizations

另一方面需要注意的是现代编译器对于高级语言是可以进行自动优化的。
通过调整代码的执行顺序可以提升单线程程序的运行效率，但对于多线程的情况这种调整则可能会导致一些问题。

实际上很多的现代芯片出于种种方面的考虑都无法保证多线程情况下编译后代码的执行顺序。
乱序带来的错误例子 -- 在PC端执行正常的程序在移动端可能会出现问题。

Parallel Framework of Game Engine

Fixed Multi-Thread

游戏引擎在使用多线程时最经典的架构是fixed multi-thread，此时引擎中的每个系统都各自拥有一个线程。
在每一帧开始时会通过线程间的通信来交换数据，然后各自执行自己的任务。
经典架构适用于2~4核的CPU, 因为是固定的，所以在更高核的情况下是有浪费的。

fixed multi-thread的一个缺陷在于它很难保证不同线程上负载是一致的。
实际上不同线程之间负载的差异往往非常巨大，很多时候一些线程已经完成了自己的任务却必须要等待其它线程结束。这就造成了计算资源的浪费。
游戏中不同场景的thread复杂不同，有的环境下渲染满，有的时候因为Gameobject多，逻辑忙不过来。

Thread Fork-Join

另一种并行处理的方式是fork-join。
对于某些负载比较高的系统我们可以实现申请一系列线程(比如动画)，
当需要执行计算时通过fork操作把不同的计算任务分配到各个线程(work thread) 中并最后汇总到一起。

fork-join的缺陷在于有很多的任务是无法事先预测具体的负载的。

在虚幻引擎中设计了named thread和worker thread两种类型的线程。
其中named thread对应引擎中的不同系统，而worker thread则是系统中具体计算任务的线程。

Task Graph

除此之外还可以使用task graph来处理多线程，task graph会根据不同任务之间的依赖性来决定具体的执行顺序以及需要进行并行的任务。
task graph在动态不断增加节点时复杂度很高，需要额外的系统来控制任务中断跳转这些情况。

Job System

Coroutine

协程(coroutine)是一种轻量的线程上下文切换机制，它允许函数在执行过程中临时切换(yield)到协程上然后再切换回来。
和线程相比，协程无需硬件层面上的数据切换，可以由程序自己进行定义，也不需要进入系统内核执行interruption。
因此协程要比线程切换高效的多。

就是在做任务的中途可以绕道出来然后还能回来。
例子：线程是公事公办，整个学校系统报备，携程就是私下解决，比如和同桌互换作为，不需要向学校报备。

协程有两种实现方式stackful和stackless.

Stackful Coroutine

首先是使用栈来保存函数切换时的状态，当协程切换回来后根据栈上的数据来恢复之前的状态。
比如去填写报名资料，打印结束后我们本地是保留了自己的信息的，才能方便继续填写。

Stackless Coroutine

另一种实现方式是不保存函数切换时的状态，当协程切换回来后按照当前的状态继续执行程序。
实现简单，切换成本低，需要严格测试。
另外对Coroutine的开发者要求很高，很难推广。

在实践中一般推荐使用基于栈来实现的协程。
尽管它在进行切换时的开销要稍微多一些，但可以避免状态改变导致的各种问题。

Fiber-Based Job System

基于协程的思想可以实现fiber-based job system。
Fiber可以理解为一个非常高速的线程管道，可以放很多Task, 很方便进行携程的切换。
在这种任务系统中job会通过fiber来进行执行，在线程进行计算时通过fiber的切换来减少线程调度的开销。

核心思想是对于多核的情况我们希望尽可能保证一个线程对应一个核(包括逻辑核)，这样可以进一步减少线程切换带来的额外开销。

在执行计算时根据程序的需要生成大量的job，然后调度器(schedule)根据线程负载分配到合适的线程以及线程上的fiber中。
job之前存在优先级和dependence.

在执行job时根据计算顺序可以分为FIFO以及LIFO两种模式，在实践工程中一般会选择LIF。
在游戏运行过程中很多job的产生都是前一个job做到一半，突然发现有新的依赖job需要先执行。

当job出现依赖时会把当前的job移动到等待区然后执行线程中的下一个job。
这样的方式可以减少CPU的等待，提高程序效率。
--- 如上图所示被移动到等待区的job有两个依赖的job需要先执行，等执行完毕后会将它又移动回work thread.

如果出现了线程闲置的情况，调度器会把其他线程中的job移动到闲置线程中进行计算。

和上面介绍过的多线程方法相比，任务系统可以更好地利用多核并且避免线程切换从而提升计算性能。
不过目前原生C++暂不支持协程，而且在不同的操作系统中任务系统的实现往往是不同的。

Info

Job system底层实现后，job对上层的Coroutine业务逻辑开发者是透明，不可见的.
Job system需要确保鲁棒性和稳定性，在实现时要对多线程硬件的底层开发非常了解，否则会出现各种奇怪问题。
需要参考很多的资料来避免踩坑，并要多做一些形式化推导来证明这个系统是安全的。

问题例子：
在多个线程对内存的使用过程中，导致某段内存不是按预期的操作进行(比如未释放又继续使用)，从而产生了逻辑的业务偏差，最终导致程序崩溃。
这种BUG往往运行很久才发现，也很难追踪。

Programming Paradigms

除了硬件之外，编程范式(programming paradigms)对于程序的性能也会有一定的影响。
在游戏引擎中我们会使用各种类型的编程范式来实现各种各样的功能。

Procedural-Oriented Programming

早期的游戏一般是使用面向过程编程(procedural-oriented programming, POP)来实现的。 –-- 游戏简单

Object-Oriented Programming

随着游戏系统变得不断复杂，面向对象编程(object-oriented programming, OOP)的思想在现代游戏引擎中起着越来越重要的作用。

Problems of OOP

然而在大量的实践中人们发现OOP也不是完美的，一个最常见的问题是OOP存在二义性：
角色的攻击行为既可以写在角色身上，也可以写在被攻击者身上。

同时OOP中存在大量的继承关系，有时很难去查询对象的方法具体是在那个类中实现的。

另外OOP中的基类往往需要提供非常多的功能，对于很多派生子类来说这样的基类实在过于臃肿了。

OOP最大的问题在于它的性能可能是很低的。
尽管OOP很符合人的认识，但对象的数据往往分布在不同的内存区域上。
这就导致程序运行时会浪费大量的时间来读取数据。

最后，OOP的可测试性非常差。
当我们想要去测试对象的某个方法是否按照我们的期望运作时，
往往需要创建出整个对象的运行环境，这与单元测试的思想是相违背的。

Data-Oriented Programming

面向数据编程(data-oriented programming, DOP)是现代游戏引擎中越来越流行的一种编程范式。
现代计算机的发展趋势是CPU运行速度越来越快，但是相对地内存访问的速度却跟不上CPU计算的速度。

瓶颈在IO

Cache

为了解决的问题人们设计了缓存(cache)这样的机制来加快内存的访问。
一般来说现代计算机都有多级缓存系统，越底层的缓存容量越小但访问速度越快。
通过缓存机制我们可以把内存中的数据先放到缓存中来加快CPU的访问速度。

Principle of Locality

利用缓存机制进行编程时就需要考虑数据的局部性(locality)。

Single Instruction Multiple Data

SIMD是利用缓存机制实现高性能编程的经典案例。
现代CPU基本都实现了SIMD机制，这样可以在一个指令中同时处理4个操作。
因此我们可以把数据尽可能组织成SIMD的格式来对程序进行加速。

Least Recently Used

LRU同样是高性能编程中的常用的技巧。
当缓存满了后系统会把最不常用的数据置换出去，只留下近期用过的数据从而提升缓存的利用率。
在实践中也会采用随机丢弃数据的策略，可以证明这样的策略拥有更好的性能。
数据中谁最久没使用到，就有最大概率被丢弃。

Cache Line

当缓存中的数据进行读写时，不是对单个数据进行操作而是直接读写一条cache line上的全部数据(一般是64 byte)。
实际上CPU的读写操作都是以cache line作为单位来执行的，因此需要操作系统来保证CPU读写缓存以及内存数据时的顺序和一致性。

因此我们在设计数据的存储形式时就可以利用cache line的机制来加速访问。
以矩阵这种数据格式为例，按照行来进行存储的矩阵往往要比按照列来存储的有更高的读写效率。

访问数据时的order非常重要。

Data-Oriented Programming

DOP的核心思想在于把游戏世界(包括代码)认为是数据的集合，
在编写程序时要尽可能利用缓存同时避免cache miss。

因此在DOP中我们会把数据和代码看做一个整体，同时使它们在缓存中的分布尽可能地集中。

Performance-Sensitive Programming

Reducing Order Dependency

那么如何基于DOP的思想来设计高性能的程序呢？首先我们需要避免程序对于代码执行顺序的依赖。

对于多线程的程序要避免两个线程同时访问同一块数据，我们希望不同的线程之间尽可能地相互独立。
即确保线程访问的数据不在一个cache line, 这样内存swap的开销很大。

Branch Prediction

对于包含分支的程序，CPU会对程序可能选择的分支进行预测并把最有可能直线的指令提前送到缓存中，
如果程序选择了不常见的分支则往往需要从内存中重新读取相应的指令从而降低程序性能。
DOP的核心概念就是优化的不仅仅是数据还有代码。

因此在设计程序时要尽可能保证具有相同分支的程序在一起执行，
比如说可以通过对数据进行排序的方式来避免频繁分支切换。

更通用的方法是按照业务逻辑对数据进行分组，每一组中只使用相同的函数进行处理。
这样可以完全避免分支判断从而极大地提升程序性能。

Performance-Sensitive Data Arrangements

当然数据的组织方式对于程序性能也有巨大的影响。

一个经典的案例是AOS和SOA。
根据OOP的思想，我们可以把数据封装到不同对象中然后使用一个数组作为这些对象的容器，这种组织方式称为AOS(array of structure)；
或者直接对数据进行封装把所有数据放到一个巨大的对象中，称为SOA(structure of array)。
当程序需要对所有数据进行访问时AOS往往会产生大量的cache miss，因此在高性能编程中更推荐使用SOA的组织方式。

Entity Component System

本节课最后介绍了现代游戏引擎中的ECS架构(entity component system)。
回忆在前面的课程中我们介绍过基于OOP来对组件进行编程，然后通过继承的方式来实现具体的GO。
就像前面介绍过的那样，这种编程范式是相对低效的。

而在ECS架构中则使用了entity的概念将不同的组件组织起来。
entity实际上只是一个ID，用来指向一组component。
而ECS架构中的component则只包括各种类型的数据，不包含任何具体的业务逻辑。
当需要执行具体的计算和逻辑时则需要调用system来修改component中的数据。
这样游戏中的数据可以集中到一起进行管理，从而极大地提升数据读写的效率。
要注意的是，ESC是一个理论模型，system很多时候会同时处理好几个Component数据。