C++ 主要是按需付费生态系统。
任何常规队列都会让you选择存储语义(按值或按引用)。
然而,这次您订购了一些特别的东西:您订购了一个无锁队列。
为了实现无锁,它必须能够将所有可观察的修改操作作为原子操作执行。这自然限制了这些操作中可以直接使用的类型。
您可能会怀疑是否有可能拥有超出系统本机寄存器大小的值类型(例如,int64_t
).
好问题。
输入环形缓冲区
事实上,任何基于节点的容器只需要所有修改操作的指针交换,这在所有现代架构上都是原子的。
但做任何涉及copying多个不同的内存区域,以非原子顺序,真的构成了一个无法解决的问题吗?
No. Imagine a flat array of POD data items. Now, if you treat the array as a circular buffer, one would just have to maintain the index of the buffer front and end positions atomically. The container could, at leisure update in internal 'dirty front index' while it copies ahead of the external front. (The copy can use relaxed memory ordering). Only as soon as the whole copy is known to have completed, the external front index is updated. This update needs to be in acq_rel/cst memory order[1].
只要容器能够保护以下不变量front
永远不会完全环绕并到达back
,这是一笔甜蜜的交易。我认为这个想法在 Disruptor Library(以 LMAX 闻名)中得到了普及。你得到机械共振 from
- 读/写时的线性内存访问模式
- 如果您可以使记录大小与(多个)物理缓存行对齐,那就更好了
- 所有数据都是本地的,除非 POD 包含该记录之外的原始引用
如何提升spsc_queue
实际上这样做吗?
-
是的,spqc_queue 将原始元素值存储在连续对齐的内存块中:(例如,来自compile_time_sized_ringbuffer
这是其基础spsc_queue
具有静态供电的最大容量:)
typedef typename boost::aligned_storage<max_size * sizeof(T),
boost::alignment_of<T>::value
>::type storage_type;
storage_type storage_;
T * data()
{
return static_cast<T*>(storage_.address());
}
(元素类型T
甚至不需要是 POD,但它需要既可默认构造又可复制)。
-
是的,读写指针是原子整数值。请注意,Boost 开发人员已注意应用足够的填充以避免虚假分享在读/写索引的缓存行上:(来自ringbuffer_base
):
static const int padding_size = BOOST_LOCKFREE_CACHELINE_BYTES - sizeof(size_t);
atomic<size_t> write_index_;
char padding1[padding_size]; /* force read_index and write_index to different cache lines */
atomic<size_t> read_index_;
事实上,正如您所看到的,读端或写端都只有“内部”索引。这是可能的,因为只有一个写入线程,也只有一个读取线程,这意味着只能有more写操作结束时的空间超出预期。
-
还有其他一些优化:
- 支持它的平台的分支预测提示(
unlikely()
)
- 可以一次推送/弹出一系列元素。如果您需要从一个缓冲区/环形缓冲区虹吸到另一个缓冲区/环形缓冲区,这应该会提高吞吐量,特别是如果原始元素大小不等于缓存行(的整数倍)
- 尽可能使用 std::uninitialized_copy
- 普通构造函数/析构函数的调用将在实例化时进行优化
- 在所有主要标准库实现上,unitialized_copy 将被优化为 memcpy(这意味着,如果您的架构支持,将使用 SSE 指令)
总而言之,我们看到了环形缓冲区的最佳想法
使用什么
Boost 为您提供了所有选择。你can选择使您的元素类型成为指向消息类型的指针。但是,正如您在问题中已经提出的那样,这种间接级别会减少引用的局部性,并且可能不是最佳的。
另一方面,如果复制成本高昂,则将完整消息类型存储在元素类型中可能会变得昂贵。至少要尝试使元素类型很好地适合缓存行(在 Intel 上通常为 64 字节)。
因此,在实践中,您可能会考虑将经常使用的数据存储在值中,并使用指针引用较少使用的数据(除非遍历指针,否则指针的成本会很低)。
如果您需要该“附件”模型,请考虑对引用的数据使用自定义分配器,以便您也可以在那里实现内存访问模式。
让您的分析器指导您。
[1] I suppose say for spsc acq_rel should work, but I'm a bit rusty on the details. As a rule, I make it a point not to write lock-free code myself. I recommend anyone else to follow my example :)