高效数据结构 - 循环队列

循环队列在游戏开发中通常叫做CircularBuffer、RingBuffer，常用来做数据缓存，生产者/消费者模型等。

在UE中有内置这样的数据结构，而Unity的.Net库中恰恰没有。

 

为什么说这样的结构高效，以双下标循环队列为例。配个图：

Tail是尾索引，Head是头部索引。当新元素加入循环队列时，Head索引+1并%取模操作

当加入队列的元素释放时(假如用于对象池)，交换元素到尾部索引位置，Tail索引+1并%取模操作

 

我们知道Unity里做对象池通常是栈实现，Unity自己的对象池是List实现。

但是这样的方式都有问题，会导致早期加入池的对象长期不会被操作，CPU侧会导致缓存丢失。

而循环队列在高频率使用时，每个元素都会频繁使用，CPU缓存利用率非常高。

 

即使不是双下标，单下标的循环队列也有缓存利用率高效的特点。双下标则可

模拟生产者/消费者模型，用于多线程Job时检查任务是否完成。

 

UE的CircularBuffer用&与运算代替%取模操作，效率还会更高一些。

 

上代码。

public class CircularBuffer<T> where T : class, new()
{public T[] items;private int _head;private int _tail;public CircularBuffer(int capacity){items = new T[capacity];_head = 0;_tail = 0;for (int i = 0; i < capacity; ++i){items[i] = new T();}}public int Get(){var item = items[_head];_head = (_head + 1) % items.Length;return _head;}public void Release(int index){if (!ReferenceEquals(items[_tail], items[index])){Swap(_tail, index);}_tail = (_tail + 1) % items.Length;}private void Swap(int indexA, int indexB){var temp = items[indexA];items[indexA] = items[indexB];items[indexB] = temp;}
}

 

测试：

• Stack 顺序测试: 845ms
• CircularBuffer 顺序测试: 798ms
• Stack 随机释放测试: 2490ms
• CircularBuffer 随机释放测试: 2325ms