首页 > 编程学习 > 面向对象编程

面向对象编程

发布时间:2022/9/7 18:33:36

背景:
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。

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号