背景：
1.游戏引擎运行于操作系统上，操作系统又运行于特定的硬件（CUP/RAM/IO）上，因此硬件的瓶颈会限制游戏引擎的性能；
2.由于摩尔定律接近天花板，芯片上晶体管的密集程度再增加的话会严重影响功耗，于是为了继续提升性能，芯片只能不断增加核数量，于是利用多核并行编程成为行业趋势。
进程和线程：
进程：
1.一个应用程序实例；
2.拥有独立的内存空间。
线程：
抢占式多任务处理；
？最小任务单元能被系统调度（抢占？）；
必须在进程中运行
进程中的线程，用于独立的寄存器资源、栈空间和计数器，且共享内存空间
多任务处理方式：
抢占式：
1.当前执行的任务会被调度者打断一次；
2.调度者决定哪个任务先执行；
3.大多数操作系统都是抢占式。
非抢占式：
1.任务必须明确的被编码以挂起（yield）；
2.任务必须协同合作才能实现调度方案；
3.现在很多实时操作心痛RTOS也支持这种模式。
线程间切换：
1.一个需要切换的情景，当1核跑2个线程，为了保证“并行”两个线程会不断切换；
2.一个线程的状态包括寄存器、堆栈和其他操作系统数据；
3.线程间切换意味着额外的开销在“用户态-内核态”，单是一个系统中断（user to kernel ->context switch -> kernel to user）就要2000 cycles；
4.当切换到新的线程后，数据并不在各级缓冲里面（Cache invalidation），而要从内存中读取数据，时间又会增加10,000~1,000,000 cycles。
结论：线程间的切换很昂贵。
易并行计算问题（Embarrassingly Parallel）VS 不易并行计算问题（Non-Embarrassingly Parallel）
典型的Embarrassingly Parallel：蒙特卡洛积分计算
Non-Embarrassingly Parallel：大多数情况
并行编程的困难
【Data Race】
Data Race：一个进程中的不同线程同时使用共享内存中的相同数据。
例子：A线程在使用数据过程中，B线程改了数据。
Data Race解决方法：
1.Lock
通过mutex.lock()和mutex.unlock()锁定 critical section，同一时间只有一个线程处理数据。
带来的问题：
1.1线程暂停和恢复会带来性能开销；
1.2如果获得锁的线程异常退出，其余暂停的线程永远恢复不了（死锁）；
1.3高优先级任务无法从低优先级任务那里获得锁。
2.Atomic Operation - Lock Free
优点：系统底层支持的原子操作，可以有效避免了死锁。
带来的问题：原子之间的等待和依赖会带来大量空洞（时间块空白）。
【编译优化导致乱序Out-of-order】
编译型语言，编译器在保证单线程中结果正确的情况下，会对指令进行优化，可能会导致指令执行顺序错乱，导致在多线程的情况下的无序所造成的问题。
很多CPU架构为了追求性能（不被动等待指令执行，而是主动把一个函数中的所有指令都同时处理），都会进行指令优化（表现：在PC模拟器上运行没问题，放在真机上宕机；或者在debug版本正常，在release版本异常）。
游戏引擎中的并行架构
【固定数量多线程】
网络线程+渲染线程+模拟线程+逻辑线程
固定多线程的问题：
1.不同线程的工作量不同，核利用率均衡；
2.当有更多处理器的核的时候，无法增加线程数量。
【Fork-Join】
Named Thread+ Worker Thread，可以动态把一个工作量大的任务分到多个工作线程中，当工作量小的时候可以合并回来。
树形结构。
优点：工作量较为均衡，可利用多核的优势。
Fork-Join的问题：
1.对于写逻辑的程序员不友好，需要分割任务和管理线程数量；
2.当线程过多时又会带来切换时的性能开销；
3.依然会有工作量均衡问题。
【Task graph】
有向无环图结构，节点是任务，边是依赖关系。
任务图的问题：
1.图的构建对于技术开发人员不透明；
2.早期的版本任务不能完成之前插入其他任务。
Job System
【Coroutine】
在一个协程中，函数做到一半，可以通过yield“让道”给其他任务，再通过resume恢复。
Coroutine vs. Thread
Coroutine：
1.由开发者调度；
2.多个协程在一个线程中执行；
3.轻量级上下文，切换在线程中，开销很小（底层并不知道有切换）。
Thread：
1.由操作系统调度；
2.居住在进程中；
3.上下文切换需要系统中断，开销很大。
Stackful Coroutine vs. Stackless Coroutine
Stackful Coroutine：
1.带运行时独立堆栈，同时也需要更多的内存；
2.函数中的局部变量，在yield时会被记录下来，重新回来时恢复，同时协程上下文切换需要更多的时间；
3.可在嵌套协程中yield。
Stackless Coroutine：
1.不带运行时独立堆栈，没有额外的内存分配；
2.类似C++的goto，重新回到函数时，之前的状态会丢失，协程上下文切换更快；
3.不可在嵌套协程中yield。
【Fiber-based Job System】
理念：构建一个通过高速管道Fiber，任务在管道里切换开销降到最小。
Fiber：类似于协程，不同的是由调度系统来调度。一个Fiber管道对应一个工作线程。
Job System减少性能开销的核心思想：一个工作线程对应一个核，job间切换不会引起Thread间切换。
Work Thead（Fiber）如何调度jobs：
1.Job Scheduler（调度者）决定job被分配到哪个Work Thead（区别于Fork-Join，其实单线程，只是任务多了以后分成多线程）
2.调度模式：LIFO，因为在大多数情况下，job依赖更像树形结构；
3Job Dependency：当有被依赖的子jobs执行时，父job会被放入等待队列（yeild），等子jobs执行完再重新压入Work Thead执行；
4. Job Stealing：调度者会把负载过大的Work Thread中的job“偷”移到空闲Work Thread中，平衡负载。
Job System的优点和缺点：
优点：
1.很容易去执行任务调度；
2.很容易控制任务依赖；
3.job栈是独立的，不会相互干扰；
4.没有硬件中断，避免经常上下文切换。
缺点：
1.C++原生不支持Fiber，得自己实现（boost）；
2.很难在不同的操作系统中执行；
3.ABA case处理（heap空间中A被清空了，B又进来了且数据跟A相同，则检测空间时误认为还是原来的数据）
一句话解释Job System：
传统并行编程通过创建多线程的方式，弊端很明显：当核过多得时候浪费，核过少的时候线程切换导致性能开销过大；Job System通过“一核 一线程 一高速管道”的方式，解决了以上2个难题。
编程范式----------------
游戏引擎中的各种编程范式：
1.命令式编程 Imperative Paradigm：Procedural Programming， Object Oriented Programming， Structured Programming；
2.声明式编程 Declarative Paradigm：Functional Programming，Logic Programming。
面向过程的编程
面向对象的编程：更符合人对世界的描述
面向对象编程的问题：
1.二义性："Attacker.doDamageTo()" or "Victim.receiveDamage()"?
2.继承数中的方法：很难找到/明确方法是定义在哪个父类中；
3.过于繁复的基类：有大量实现各种功能的函数；
4.性能问题：
4.1内存分散：由于数据全部会分散到各个objects中，而每个object经过继承全是异构，导致alloc和dealloc都是分散进行，导致OOP系统的内存占用是非连续的（CPU读取消耗大）；
4.2虚函数指针乱跳；
5.可测试性：由于一个单位的数据集中在object中，为了测试单位的一个功能，必须先把这个单位的object的所有数据和状态创建出来。
面向数据的编程
背景：CPU的访问数据远远大于内存。
导致：通过增加各级cache来加速数据访问。
L1 cache - 1M，读取速度1ns
L2 cache - 10M，读取速度3ns
L3 cache - 64M，读取速度10ns
Memory，读取速度100ns
局部性原则：处理器越来越趋向于访问一段连续内存，以减少读取次数。
CPU加速读取原理：
1.现代CPU基本实现了SIMD，即一次性读32bit*4(16byte)数据，一次性计算vector4，4倍的加速；
2.LRU（Least Recently Used），当cache不足的时候，会优先保留最近使用的。
基于以上亮点，我们尽量把data放在一起。
cache line：从各级缓存读取固定大小的数据块，一行cache line通常为64bytes。
cache miss：读取顺序不同，效率可能差2个数量级--假设L1 cache 有4行cache lines，每行64bytes，即可读取4*16 integers的连续数据；对于一个矩阵，如果按行的方式读取，内存是连续的；但如果按列的方式读取，内存是非连续的，读取效率相差（列数*各级缓存数）倍！
面向数据的编程的核心思想：一切（代码、特效、网格...）皆数据，尽量保证在cache中在一起，减少cache miss。
效率提升：1~2个数量级。
性能敏感编程
减少顺序依赖：
1.工作会因为误判而停止。
2.变量初始化后，不要改变它的值（否则将不会并行处理）。
False Sharing in Cache Line：不要让多个线程同时读写同一个cache line（否则会有双倍数据移植消耗）。
Branch prediction：编译器会把if-else某个分支的执行代码直接放到cache中，以至于如果分支切换频繁会导致更新cache频繁，影响效率。解决方法有：1先排序，尽量减少分支切换；2不用if-else，而是分好组。
性能敏感数据组织
Array of Structure vs. Structure of Array
Array of Structure：一个对象对应一个Structure，里面有N个属性，多个Structure组成一个数组，属性与属性是分离的；
Structure of Array：所有对象的属性先组成1个数组，所有数组组成1个Structure。