UE4的队列TQueue
UE4的队列TQueue
TQueue是UE4提供的队列容器，完全满足队列的先进先出性质，这里主要用于多线程同步数据。如果比较了解多线程编程的话，那你肯定知道多线程中最常用的一个容器就是消息队列，解决的就是生产者-消费者问题。
如果自己简单的去写一个消息队列，我想大部分人肯定就直接在进队列和出队列的地方加锁，避免两个线程同时访问，但是假如消息通信非常频繁，大量的加锁就会造成当前线程有大量时间在阻塞等待，这个容器的性能就会非常差，一个消息队列的性能好坏会直接影响到了两个或多个线程的性能。
如果经常写C++的话，肯定会想到STL中的队列std::queue，std的队列底层其实是用std::deque这个容器来实现的，内部存储是通过链表+数组的形式，把不同的块链在一起，我们知道std::vector和UE4的TArray一样都是单向扩容的，而std::deque通过链表+数组这种方式，就可以支持的前后双向扩容。其实std::queue这样的容器底层内存管理方式在UE4中也有一个容器TChunkedArray和他非常像，但UE4并不是把他当作队列来用的，如果看过Unity的ECS实现你就会觉得这个结构很眼熟，跟Architype的底板容器一模一样，UE4也是用他来做和ECS管理组件内存差不多的事情，ECS的多线程处理多个组件之间的关系有多复杂就不多说了。显而易见，用链表+数组这种复杂的数据结构来实现队列，要保证线程安全是非常困难的，强行加锁的话性能会变得很差。游戏引擎肯定要优先保证性能，所以这就是为什么UE4没有选择std::deque或TChunkedArray类似数据结构来实现队列的原因。
那UE4的队列是怎样做的？从最上面注释可以看到，TQueue选择了简单的单链表这样的结构，从链表的结构上就能很好的解决这个问题。UE4还通过巧妙的实现保证了无锁（lock-free），用于两个线程的单生产者-单消费者（只有一个线程的情况最后会说）或多个线程的多生产者-单消费者的这两种模式，虽然没有覆盖到多生产者-多消费者这种模式，但已经能满足绝大部分的开发需求了。引擎内部有很多地方都在使用这个容器或类似的思想，下面就来说说这个容器的具体实现
TQueue的成员变量
先看成员变量，两个指针Head和Tail，其中Head加了volatile关键字，同时用宏告诉编译器必须16字节对齐，之前分享的TripleBuffer也提到了成员变量Flag是这样声明的，上次写的时候没有说具体的原因，下面就专门解释下UE4为什么要这样写
TTripleBuffer的成员变量
先看Align(16)，16字节对齐这个很好理解，C++的字节对齐上限std::max_align_t就是16。因为TQueue不知道外面代码会用在哪里，成员变量依赖于外面的内存空间，不声明16字节，外面就有可能把内存对到一个诡异的位置上。比如用一个uint8数组来装TQueue，先用掉一个字节，从第二字节开始装TQueue，我们知道指针在64位机器是8字节，那么这个Head就有7字节在前面，一个字节在后面，那么Head指针肯定不是16的倍数，在做一些事情时，如果不接受这样的指针就很可能报错，即使不报错也不那么效率。
再看volatile，在C++中volatile关键字，是为了告诉编译器，这个变量会经常修改，让编译器不要生成带优化的汇编代码，而是生成每次访问都是从内存读取和写入的汇编代码。因为编译器在优化时不会考虑一段作用域内，不考虑多线程之间，如果发现这个值在一个作用域内的代码中从来没改过，或者改过之后再也没有使用过，就很可能把这个变量存成一个常量，赋值后就再也不改了。这样就会导致即使另一个线程改了这个值，但在这个线程就完全感知不到。加了volatile，两个线程在同时访问这块内存时，比如原始值是1，第一个线程写了2，编译器不去优化了，就会生成把2写入内存的汇编指令，第二个线程在读取的时候生成的是读取内存的汇编指令，这样就能感知到这个值为2。那么可以看到这样就保证了这个变量基本是线程安全的。
为什么这里加了一个基本？因为还要考虑读取内存和写入内存这两个操作不一定能一次做完，因为这两个操作有可能是多条汇编指令，也可能单条指令不是原子指令，如果再能保证操作也是原子的，就能保证了线程安全。怎样保证操作是原子的，这里后面来说
构造和析构函数：
默认就会new一个空节点，作为头和尾，虽然浪费一个节点内存，但这样就不用判断空指针的情况。
这个TNode是个子结构体，也很简单，就是一个普通的链表，一个Item和一个NextNode，注意NextNode也加了volatile。这里没有加align(16)的原因是，TNode外部不能使用，唯一内存来源就是TQueue内部new，new操作来源于UE4的内存池FMemory（文末有截图），内存池已经保证了是对齐的，所以不用强行加align(16)。
进队列Enqueue:
代码里的TSAN系列宏可以先无视，是查高并发时数据竞争的BUG用的，有兴趣可以看这篇怎么用。ThreadSanitizer——跟data race说再见 - 知乎 (zhihu.com)，里面写的很专业，但我目前也没怎么看懂。
前面也说了，因为要支持两种模式，单生产者-单消费者，多生产者-单消费者，进队列相当于是处理生产者，那么就可能出现1和多的情况，所以这里在进入队列的时候区分开，因为多生产者可能同时操作到这个Head变量，虽然加了volatile但不能保证原子性，所以这里使用InterlockedExchangePtr来强制保证原子性。考虑了下这里还是彻底说清楚吧，这个函数在Windows上其实调用的是下面这个函数：
查了MSDN，可以看到
注意下面的说明
在clang下用的是__sync_lock_test_and_set
所以看到，通过这个函数操作，就能保证多生产者即使同时操作这个变量，就是安全的。做的事情其实就是把Exchange的值给Dest，返回老的Dest，这是一次做完的。
所以这里就是一次性把Head指向NewNode，OldHead变为原来的Head，然后一次性把OldHead的NextNode指向了NewNode。相当于是通过两个原子操作。这里可以想象一下，假如有两个线程（多生产者）同时Enqueue，第二个线程就正好在第一个线程这两个原子操作中间Enqueue，那么可以看到第一个线程的Head被改成了新的，OldHead是局部变量不会变
对于单生产者来说，即使不是线程安全的，但是因为只有一个生产者，不会出现多线程同时修改Head这样的操作，所以也是没有问题的。我们看这里实际是三行代码，其中倒数第二行有个MemoryBarrier，这个函数的作用是，可以保证调用这个函数之后的所有代码，一定在调用这个函数之前的代码之后执行。这个听起来很怪，可能你会觉得正常代码不都是这样执行的吗？但实际上在Shipping编译时，C++编译器很可能为了性能会做优化，在作用域内保证逻辑正确的前提下让指令乱序执行，所以这里的目的就是告诉编译器不要这样搞，一定要按顺序做事情。这样就保证了OldHead->NextNode一定是在Head先指向NewNode后才会指向NewNode，假设这个步骤反过来先让OldHead->Next指向NewNode，那如果当Tail也指向的是OldHead，在还没来及让Head指向NewNode时，出队列操作就会把OldHead从链表上移除，这时再让OldHead->Next指向NewNode就变成了让一个没在链表上的节点的Next指向NewNode，这显然是有问题的。另外因为这里放弃了编译器的乱序优化，肯定在一定程度上会比不加这个内存屏障要慢，但也比加锁要快非常多。
比如有个空TQueue<int32>，调用Enqueue进队列，这个队列的变化过程就是这样的：
出队列Dequeue:
因为出队列本身只有单消费者，不存在多个线程同时访问的情况，所以这里只要处理好和Enqueue的关系，保证操作是安全的就好。具体流程是让Tail指向自己的Next，并把旧数据用默认构造的对象覆盖掉，再删掉更老的无效节点，就完成任务了。可以看到这里的代码连MemoryBarrier都没有加。至于为什么不加，是因为Head只会往Next方向去移动，不会往回移动指向前一个结点，Tail永远不会超过Head，即使追上Head又因为Tail始终指向的无效节点，真正的数据是Tail->NextNode，这样就相当于根本不存在多线程访问Tail的情况，即使编译器做了乱序优化，也能保证操作结果的正确。整个出队列的流程，用图画出来就是下面这样的：
其他函数
除了基本的进出队列的这两个基本函数外，还有清空Empty，判空IsEmpty，查询队尾但不出队的Peek，出队但不取值的Pop函数，这些都和出队列一样都是在跟Tail打交道，所以也相当于是没有涉及到多线程访问，完全不需要任何措施来保障线程安全。可以自行了解对应功能，就不再细说了。
tradeoff:
整个队列在进出时没有加任何的锁，进入队列在多生产者模式下只有两个原子操作，单生产模式只有一个MemoryBarrier，而出队列和其他函数完全没有原子操作和MemoryBarrier，性能几乎跟单线程的队列性能一样，这也正体现出来TQueue这个容器为什么是Lock-Free的队列了，性能肯定特别好，但是免费的东西就没一点代价吗？
如果再细心一些可能会注意到，这里无论是进队列还是出队列，节点都是new出来的，用完都是delete掉的，进队列时外部的对象还要拷贝到new出来的节点上，这样当队列进出非常频繁时，就产生了大量的内存碎片，如果学过C++肯定都知道new和delete虽然较快，但还是比在栈上分配要慢很多，因为分配堆内存最终会走到操作系统的API来分配，这样不会有性能问题吗？
这里确实是这个容器的唯一缺点了，但是UE4本身在全局重载了new和delete，内存的分配和释放其实是来源于内存池，只有在内存池的内存不够用时UE4才会向系统要新的内存，这个频率是远远低于代码中调用new和delete的频率的。因为UE4的内存池默认用的是Binned2或3，为了防止分配内存的全局锁，内部小内存都是在TLS (Thread Local Storage)内存块上申请的，每个线程独占，这里的队列是一个线程new另一个线程delete，肯定delete后这块内存在短期内是还不回原来的那个线程的内存块的，虽然长期来看不会有问题，但短期大量使用一定会使内存峰值撑大。但为了高性能的同步，即使有这么一点点的副作用，我觉得还是可以承受的。
UE4全局重载了new和delete，实际调用的是FMemory上的Malloc和Free函数
可以在TQueue的注释上看到下面这句，说明UE4的开发同学确实意识到了这个问题，可以搞个节点池化，但可能还没来及做或没考虑好怎样实现最优吧，所以默默的写了个todo蒙混过关。虽然已经很多个版本一直都是这样了，但还是希望哪天能看到这里该怎么来实现。
可能有人还会想到，如果是在单线程下使用队列，也属于单生产者，单消费者的情况，这里因为有个MemoryBarrier性能肯定还是比没有的情况要差，而且同一个线程可以完全不需要MemoryBarrier，事实也确实如此。强行用其实也没有任何问题，但是我觉得既然都保证了单线程访问，为什么不直接去用TArray或TSparseArray其他性能更好的容器呢？