UE4/UE5的LockFreeList
UE4/UE5的LockFreeList
LockFreeList是UE提供的一系列LockFree容器，其实主要就是实现了多线程lockfree的栈和队列这两种容器，其他的几个容器都基于这两种扩展出来。这些容器的代码本身经过了高度优化和打磨，性能表现非常优秀，UE自己的TaskGraph中Task管理以及多线程调度都是基于这个容器来实现的。这篇文章主要就是来从细节触发，讲清楚这个LockFree容器到底是怎样实现的，代码里很多诡异的写法的用意是什么，UE引擎的多线程性能非常好，跑得这么快，到底快在了哪里？
基础知识
在开始之前，先来说说UE提供的另一个队列TQueue，为什么UE要另搞一套LockFree容器来作为TaskGraph的底层容器而不是直接使用TQueue。前面有写过TQueue源码解读：
这里先简单说说TQueue的问题：
图1
图2
图3
- 节点本身的内存不是通过池来分配和释放的(图1)，而是直接new和delete申请释放(图2)，这样会导致在超高并发量时，有很重的性能负担以及会造成大量内存碎片。TaskGraph是贯穿整个引擎的多线程框架，到处都在用，并发量肯定不会低，因此这样的行为显然不能接受。
- 模板本身需要明确指定是单生产者单消费者或者多生产者单消费者，不支持多生产者，多消费者(图1)，这对于TaskGraph这种框架来说是不可接受的，可以想一下在多线程下，所有被管理的线程都应该可以作为生产者创建Task，所有被管理的线程都可以作为消费者执行Task，那么这样的队列显然是不能支持的。
- TQueue中，Head和Tail在结构体中是依次排列的（图3），这会造成伪共享问题。对于高并发的场景来说，也是不可接受的。
基于这样的原因，那么UE就很有必要单独为TaskGraph量身定制一套容器，并彻底解决上面这些问题，LockFreeList就是这样的容器。
先看一下LockFreeList的框架图：
可以看到，本身有定义节点的结构，节点回收池，内存分配也有专用的Allocator避免内存碎片，而且还实现了栈和队列，以及为TaskGraph专门定制的FStallingTaskQueue，以及TClosableLockFreePointerListUnorderedSingleConsumer这样的容器。虽然复杂，但关于TQueue内存和节点复用这块的问题，就已经让人感到有保障。
LockFreeList中涉及到的多线程基础知识
下面就来具体分解实现。为了讲清楚下面的细节，前面还是先简单介绍一下用到的多线程知识。可以根据情况自行跳过这一节。
1 CPU的缓存、缓存行和伪共享问题：
先来看cpu-z图里的每一级缓存这里的内容。缓存，简单说就是CPU的一个硬件优化。为了高效率快速执行代码，可以将内存或磁盘，以及其他数据提前加载到CPU内部的高速存储器里，从而进行快速读写，而不是直接在原数据上读写。我们写代码肯定也用过这样的手段，如果文件很大读写很慢，我们可以把文件的一部分缓存到内存里，虽然小但是能够显著提高访问速度。而这里的多级缓存就是为了提升CPU处理数据的速度在硬件上做的多级快速存储器。缓存级数越低，容量越小，但读写速度越快，高级别的缓存甚至内存，虽然容量大，但读写速度就慢了好几个数量级了。这里用我笔记本的CPU来举例，可以看到有很多级缓存，其中L1，L2的“大小”部分，后面都有x6，我的CPU是6核的，说明L1和L2的缓存是每个核独占的，而L3后面没有x6，说明是6个核心共享的。
网上找了张CPU的芯片图，Shared L3 Cache连着4个Core，也证实了这点。当然也不是绝对L3就都共享，比如下面这个CPU，连L3都分成了4个。
我们可以看到上面CPU的L1的大小是32K，其实目前大部分CPU的L1大小都是16K以上的。你可能也注意到了，UE里面很多代码，包括LockFreeList的Allocator在预分配Block时，都会指定16384这样的大小，乘以整数倍正好就是L1的大小，这就是因为CPU访问一块内存时，很大概率也会访问周围连续的内存，对于连续内存的访问CPU是有做特殊优化的，可以显著降低cache miss的概率，那么从代码上直接来营造这样的环境，就可以显著提升程序的性能，包括Unity的ECS以性能著称，内部的Architype分配Block时就是16K这样的大小。
然后看CPU-Z截图，每一级缓存框里后面的“描述”部分，有一个64-byte line size。这个代表缓存行，也就是CPU读写一次存储数据的最小单位。大部分CPU都是64字节。UE也提供了函数可以查询这个大小(Windows)
甚至可以直接用Prefetch函数让系统预加载指定的缓存行(默认只有Windows)
也可以自己补__builtin_prefetch，让Arm CPU（手机游戏）得到支持。
前面的n-way set associative代表当前这一缓存和下一级缓存或内存的映射方式，分为直接映射和全映射以及组映射，因为每级缓存大小不同，肯定会出现映射和淘汰的问题，这里的组映射就是兼顾了cache miss和访问性能的映射方式，而直接映射和全映射就是两个极端的方式，这里就不具体细说了（可以自行参考CPU cache - Wikipedia，这里还有定义CPU缓存淘汰是写穿还是写回的手段，cachemiss问题等，内容比较全） 因为上面CPU的缓存行是64字节，假如我定义的一个结构体，内部有两个成员变量int x, int y，这两个变量的内存是连续的，大小显然小于64字节，那么CPU在读写的时候，这两个变量就很容易处在同一个缓存行上。这时进行多线程访问，线程1访问x，线程2访问y，CPU会像下面这样来做：
在写代码时，我们可能会觉得，x和y是两个线程各处理各的并没有多线程问题，但是因为他们内存连续，处在了同一个cache line上，Core1读写x的时候会把y一起带上，Core2读写y的时候也会把x一起带上，CPU为了保证数据正确和安全性，会发生大量的写回L3甚至写回内存(比如上面AMD的CPU有4个L3)的操作，造成了性能低下，就好像是加了锁一样，这就是伪共享问题。那么要怎么避免伪共享呢？可以通过填充大量的Padding，隔离开两个变量，人为的让变量内存不连续。如下图，LockFreeList中的容器就都是这样做的，每个变量前后和之间填充64字节无效数据。
2 CAS和ABA问题：
CAS是Compare And Swap的缩写，是系统提供的原子操作API。UE主要是封装在PlatformAtomics.h这样的头文件中，比如Windows如下图所示：
看着多，有些如类型或者操作不同等细微差别，但其实基本规则都是一致的。具体规则如下：
一般是三个参数：
- 修改数据的地址P
- 预期中旧的原始值A
- 要修改成的目标值B
逻辑：判断P的值是A，如果是没被改就交换A和B ，否则不交换。这个操作是原子操作，也就是线程安全的。
因为有了这样的基本操作，业务在用CAS实现LockFree复杂的操作时，一般原则都是先获取预期的值，本地进行操作，最后再进行CAS修改原值，如果失败，就将整个操作回滚重来。比如LockFreeList中某个Push函数的LockFree实现，如下图
可以看到，是一个while的死循环，首先把Head值Read到局部变量LocalHead上，之后对LocalHead做一系列操作得到新的值NewHead，最后再比较LocalHead和原来的Head是否一样，因为中间打马赛克这过程肯定不是原子操作，所以Head在这期间还是有概率被别的线程修改的，假如别的线程在这期间没有改过Head的值，那么在最后执行CAS时肯定还是一样的，那么就会把Head改为NewHead从而break退出循环，但是如果Head被别的线程改过，那么CAS就会失败，就会从头开始回滚重做之前这个过程。
我们可以看到这个过程全程都没有加锁，而是以一种乐观的心态来进行操作，也就是假设别的线程大概率不会改Head值，如果真是这样，那么这样的事情一次就做完了，这肯定要比加锁性能好多了，但是如果被改掉了Head，大不了就是从头再来而已。这个操作虽然没加锁，但达到的效果和加锁是差不多的，因此这样的操作也叫做乐观锁。相对的，正常的加锁就叫悲观锁了，因为不管其他线程是否会修改，都是把锁加上再说，这当然就是一种悲观的心态。
因为这样的操作是LockFree的，全程没有加锁，对于链表这样的结构，只要Head不变，就能代表着别的线程没有操作过吗？其实不一定，因为Head有可能被别的线程操作多次，先改成一个新的值，再改回来成原来的Head，那么CAS最终也一定会成功，而Head已经不是原来那个Head了。举个不恰当的例子：这就像是XXX挪用公款去炒股，然后赚了一波，再把钱还回去，这样的行为虽然前后公款都没变，但能说XXX这样就合法吗？显然这是犯法的。在CAS操作这里，这样行为当然也是不合法的，这个问题叫做ABA问题。看下面这个例子
链表原始为1->2->3。
线程1：想将链表改为1->4->2->3
线程2：想将链表改为1->3
经过上面这样的流程后，链表反而变成了1->4->2，导致3被脱离链表，这显然都破坏掉了整个链表，出现了BUG。
因为CAS本身避免不了ABA问题，而为了解决ABA这样的问题，就需要人为的让经过修改之后的A不能是原来的A了，只要永远不改为以前的历史值，就肯定不会出问题了。那么怎么才能做到这一点呢？自然的想到，可以对A额外记录一些信息，比如在A的内存中额外拿出一部分当作一个计数器来用，每次操作就加1，那么只要修改这个A，即使把A的值改为原值，但计数器一直在递增，就永远不会和历史值一样，那么自然不会出现ABA问题了。
举个具体点的例子：操作一个int32值，假如把这个int32扩展到int64，低32位还是原来的值，高32位作为计数器，每次操作计数器都加1。可以看出，即使数值部分和原来一样，只要经过操作计数器肯定不会和原来一样，对这样的int64做CAS操作，一定就能判断出来别的线程在自己线程操作期间是否有修改这个值。
UE的LockFree链表的指针FIndexedPointer，也就是基于这一点来特殊实现的：
其中前面有26位的真正指针位，后面38位根据情况用于Counter和State。这个Counter就是计数器，每次操作链表后都会+1，而State不一定有，会根据模板实际需要来定。如果非默认TABAInc，会有TABAInc-1位表示State，Counter每次修改+TABAInc，本质还是+1，相当于跳过State占用的位。这里需要自行对照着FIndexedPointer类的代码看，我就截个简短的部分，不贴完整代码了。
3 TLS
TLS是ThreadLocalStorage的缩写，和CAS一样，也是系统提供的多线程API和结构。我们知道普通内存是进程内的，每个线程都能共享，而TLS就是系统提供的一个机制，可以做到TLS内的数据线程独有。可以把TLS简单理解为，系统提供了一个以线程ID作为key的TMap容器，而且这个容器本身是线程安全的，由系统保证。
用法：需要手动AllocTlsSlot和FreeTlsSlot。一个SlotID等于一个map。用SetTlsValue和GetTlsValue这两个函数进行读写，key=线程id，value=void*数据。每个线程只会取到自己线程独有的数据。
LockFreeList的实现
前面已经说了基本的内容，下面就接着来说LockFreeList具体怎么实现的。还是从这个图开始
先看上面黄色部分，FIndexedPointer前面说了，其中26位是指针部分。这里你可能会想，64位的程序，指针都是8字节64位的，只用26位保存指针，能够用吗？
UE就用了一种取巧的做法，前面也说了UE的LockFreeList容器，提供了对象池，而对象池本身的节点，是TLockFreeAllocOnceIndexedAllocator里分配的。这里需要提前说一下这个的内部实现，本质上他就是一个无锁版本的TChunkedArray，每次申请会分配一个大的Block，然后把Block拆成小的Item来给外部使用，当Block用完就再申请新的。这个管理Item的方式和数组很像，因为在Block内，内存都是连续的，因此即使不告诉外部实际的指针，只需要返回数组的Index，只要内部记录每个Block的首地址，最终一样是可以获取到实际的指针和数据。那么对于FIndexedPointer来说，26位保存Index，就最多可以有2的26次方也就是67,108,864个节点，对于链表来说肯定足够用了。可以看下这个类简单的实现，如下图：
注意，这个节点分配器 并不是节点回收池，是只出不进的，节点也是只增不减，所以分配出去的节点一定是连续的。
再来看下链表节点的实际结构
这里的两个变量命名中的Double和Single，代表着大小一个是双精度64位，一个是单精度32位，而不是“两个”“单个”这样的含义，这里需要注意。32位和64位的意义是一样的，都保存着前面说的26位指针，只是32位的没有CounterAndState这部分。Payload就是链表实际的数据，因为是个通用容器，为了支持任意类型用void*肯定是没问题的。这样再看，就跟我们自己手写的下面这种链表差不多。
struct LinkNode
{
void* Data;
LinkNode* Next;
};再来看前面的结构图，红色部分中间
这个Policy就是定义一些基本结构，以及刚才说的节点分配器。可以看到，分配器指定Block大小时，指定了16384，也就是16K。前面CPU的地方说了，只要分配的内存，乘以整数倍正好就是L1的大小，就大概率能保证是整块被加载进缓存的，而且访问节点时，虽然是链表但其实处在同一块缓存上，这样就不容易发生cache miss，可以显著提升运行的效率。
这个LockFreeLickAllocator_TLSCache就是节点的回收池，本身定义了一个全局变量。容器在需要使用节点的时候，就会从这个全局变量上申请，而用完节点后会归还给这个回收池。回收池内部在开始的时候，本身也没有节点，就会向前面提到的TLockFreeAllocOnceIndexedAllocator去申请，这个Allocator前面也说了是一次分配一个Block，只增不减，而且内存连续的，所以效率很高。可能你也从回收池名字上看到了TLSCache，内部实现确实是使用TLS来管理节点的，每个线程在申请和归还节点时，都是从自己线程独有的节点包里取。内部向Allocator也是一次申请64个，这样同一线程内分配的节点，就有很大概率是连续的内存，在业务使用LockFreeList时，性能肯定也会很好。而且因为本身是TLS的，每个线程独占，所以在分配一块节点Cache时，也不用考虑多线程问题，不需要使用CAS以及回滚操作的写法。
最后，还可以看到，回收池内本身保存节点的功能，是通过FLockFreePointerListLIFORoot这个类实现的。
这个类就是一个LockFree栈的基类。因为本身LockFreeList也要实现一个栈，回收池也是一个栈，UE为了复用代码，把公共部分抽到了FLockFreePointerListLIFORoot中。这个栈，本身就是先进后出，具体怎么实现的LockFree就不细说了，可以看下面，每个函数都还是前面提到的固定套路：取值，操作，CAS检测，失败就回滚。当然这也是实现lockfree容器的标准套路：先实现一个单线程的普通容器，写好每个函数，再加上原子取值，CAS和回滚的while循环，改造一遍即可。
这是FLockFreePointerListLIFORoot的全貌
可以看到成员变量前后都有Pad，这个前面也说过，就是为了解决缓存行造成的伪共享问题。
和回收池一样，组合FLockFreePointerListLIFORoot，就有了FLockFreePointerListLIFOBase
可以看实现，没有什么特别的，从回收池申请一个节点，并且填充上内容，再调用Root的Push保存到栈上。
Pop也是一样的做法，只是调用Root的Pop后，取出数据再把节点再还回给回收池。
因为节点来源于回收池，这正好就解决了TQueue里面每个节点都是new出来，删除时直接delete的问题，在高并发环境下造成内存碎片的问题。节点是一直在复用的。既然节点是复用的，这就一定存在前面说的ABA问题，因为从回收池里取出的节点，很有可能是之前回收的节点。而因为这个容器的链表指针自带计数器，每次进出计数器都会加1，所以也完美的解决了这个ABA问题。
既然有栈，UE用同样的方式，也可以搞一个队列出来，下面这个FLockFreePointerFIFOBase就是。因为队列是先进先出，所以名字叫做FIFOList。可以对比下TQueue，可以看到实现基本一致，但是TQueue前面提到的所有问题，这个容器都彻底解决了。本身也支持多生产者多消费者，无需明确指定。
上面也可以看到Head和Tail前后以及之间，都有Pad隔离，来避免缓存行造成的伪共享问题。
后面的容器就基本上都是上面基本容器，对参数做了一些指定，没有什么特殊的地方了
- TLockFreePointerListLIFOPad：带Pad的栈(private继承栈Base，屏蔽了基类的几个函数)
- TLockFreePointerListLIFO：无Pad的栈(public继承栈Base)
- TLockFreePointerListUnordered：带Pad的栈(public继承栈Base)
- TLockFreePointerListFIFO：带Pad的队列(private继承队列Base，屏蔽了基类的几个函数)
- TClosableLockFreePointerListUnorderedSingleConsumer：带一个Close状态的栈(private继承栈Base，屏蔽了基类的几个函数)
其中有一个容器TClosableLockFreePointerListUnorderedSingleConsumer
这个容器，就是把CounterAndState的其中一位拿来做Close这样的State，具体实现也没有特别的地方。这里就简单介绍一下，这个容器是管理TaskGraph的FGraphEvent中的依赖列表用的，因为拿到一个Event，在加先决条件时，有可能前面的Task已经都结束了，所以需要有一个标记位来标记结束这件事。这里就不详细说了。
最后再来说说FStallingTaskQueue这个容器
可以看到内部组合了前面的LockFree队列的数组，同时额外维护了一个MasterState。数组和MasterState之间没有强行加Pad，因为LockFree队列已经在内部成员的前后都加过了Pad，所以本质上还是每个成员变量都处于不同的cacheline。这个容器是专门为TaskGraph实现的，用来管理TaskGraph的Task。MasterState本身也是一个TDoublePtr类型，也就是前面说的FIndexedPointer，因此26位是实际的指针，而后面38位是计数器。
这里有一个这样的操作，把某一位置为1或者置为0，以及判断指针的某一位是否为1。后面还有一个FindThreadToWake，内部代码实际是找一个是1的位，并把这个位置返回。
这里其实就是用指针的每一位来分别表示不同的线程，前面也说了，FIndexedPointer指针只有26位是有效的，因此这个结构最多只能管理26个线程。当某个线程的Task都处理完了，没有事情可以做了，就会把这一位置为1，这样外部就可以拿着这个线程号去Stall这个线程，将CPU让出来，当有新Task来的时候，会找一个被阻塞的线程来唤醒，并让这个线程做事情。可以具体看Push和Pop代码，就不细说了。当然上面这个FindThreadToWake函数不太效率，本质目的是获取第一个设1的位置，可以换成下面这个更高效的数学函数。
数第一个为1的位置，也相当于是看前面有几个0，这样的操作在不同平台上都有硬件实现，UE也做了封装，在PlatformMath中，所以按需要魔改成这样的函数效率会更高。另外这里因为受限于FIndexedPointer的结构，可以自己另外定义一个结构，把指针部分的大小调大，我自己魔改的版本是调到了32位，这样能管理32个线程。知乎上也有个大佬改到了48并且在很多核的DS上压测过完全没问题，这里如果有需要也可以自行修改。另外UE5的TaskGraphInterface内部管理Task换成了一套新的Scheduler，本身也没有这个26个线程的限制，所以UE5不用做这个修改，当然如果特殊需要可以把控制台变量GUseNewTaskBackend改为0，这样可以切回UE4的TaskGraphInterface版本。