GAMES104课程笔记20-Data-Oriented Programming and Job System

这个系列是GAMES104-现代游戏引擎：从入门到实践(GAMES 104: Modern Game Engine-Theory and Practice)的同步课程笔记。本课程会介绍现代游戏引擎所涉及的系统架构、技术点以及引擎系统相关的知识。本节课主要介绍面向数据编程以及任务系统在游戏引擎中的应用。

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

Basics of Parallel Programming

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

Process and Thread

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

Types of Multitasking

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

Thread Context Switch

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

Parallel Problems in Parallel Computing

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

Data Race in Parallel Programming

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

Blocking Algorithm

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

尽管使用锁可以保证程序的正确执行，但锁的存在会影响程序的并行性。更严重的是它可能会产生死锁(dead lock)的现象从而阻塞程序的运行。因此在编写并行程序时需要注意尽可能减少锁的使用。

Atomic Operation

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

Complier Reordering Optimizations

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

实际上很多的现代芯片出于种种方面的考虑都无法保证多线程情况下编译后代码的执行顺序。

Parallel Framework of Game Engine

Fixed Multi-Thread

游戏引擎在使用多线程时最经典的架构是fixed multi-thread，此时引擎中的每个系统都各自拥有一个线程。在每一帧开始时会通过线程间的通信来交换数据，然后各自执行自己的任务。

fixed multi-thread的一个缺陷在于它很难保证不同线程上负载是一致的。实际上不同线程之间负载的差异往往非常巨大，很多时候一些线程已经完成了自己的任务却必须要等待其它线程结束。这就造成了计算资源的浪费。

Thread Fork-Join

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

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

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

Task Graph

除此之外还可以使用task graph来处理多线程，task graph会根据不同任务之间的依赖性来决定具体的执行顺序以及需要进行并行的任务。

Job System

Coroutine

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

Stackful Coroutine

协程有两种实现方式。首先是使用栈来保存函数切换时的状态，当协程切换回来后根据栈上的数据来恢复之前的状态。

Stackless Coroutine

另一种实现方式是不保存函数切换时的状态，当协程切换回来后按照当前的状态继续执行程序。

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

Fiber-Based Job System

基于协程的思想可以实现fiber-based job system。在这种任务系统中job会通过fiber来进行执行，在线程进行计算时通过fiber的切换来减少线程调度的开销。

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

在执行计算时根据程序的需要生成大量的job，然后调度器根据线程负载分配到合适的线程以及线程上的fiber中。

在执行job时根据计算顺序可以分为FIFO以及LIFO两种模式，在实践工程中一般会选择LIF。

当job出现依赖时会把当前的job移动到等待区然后执行线程中的下一个job。这样的方式可以减少CPU的等待，提高程序效率。

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

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

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计算的速度。

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的机制来加速访问。以矩阵这种数据格式为例，按照行来进行存储的矩阵往往要比按照列来存储的有更高的读写效率。

Data-Oriented Programming

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

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

Performance-Sensitive Programming

Reducing Order Dependency

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

对于多线程的程序要避免两个线程同时访问同一块数据，我们希望不同的线程之间尽可能地相互独立。

Branch Prediction

对于包含分支的程序，CPU会对程序可能选择的分支进行预测并把最有可能直线的指令提前送到缓存中，如果程序选择了不常见的分支则往往需要从内存中重新读取相应的指令从而降低程序性能。

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

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

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中的数据。这样游戏中的数据可以集中到一起进行管理，从而极大地提升数据读写的效率。