boost lockfree spsc_queue缓存内存访问

Question

我需要非常关注当前多线程项目中的速度/延迟.

缓存访问是我想要更好地理解的东西.而且我不清楚无锁队列(例如boost :: lockfree :: spsc_queue)如何在缓存级别访问/使用内存.

我已经看到了使用队列中需要操作的大对象的指针的队列.

如果消费者核心从队列中弹出一个元素,我认为这意味着元素(在这种情况下是一个指针)已经加载到消费者核心的L2和L1缓存中.但是要访问该元素,是否需要通过从L3缓存或互连中查找和加载元素(如果另一个线程位于不同的cpu套接字上)来访问指针本身？如果是这样,简单地发送可由消费者处理的对象副本可能更好吗？

谢谢.

Answer 1

C++主要是为您所需要的生态系统付费.

任何常规队列都允许您选择存储语义(按值或按引用).

但是,这次你订购了一些特别的东西:你订购了一个无锁队列.为了无锁,它必须能够执行所有可观察的修改操作作为原子操作.这自然地限制了可以直接在这些操作中使用的类型.

您可能怀疑是否有可能具有超出系统本机寄存器大小的值类型(例如int64_t).

好问题.

输入Ringbuffers

实际上,任何基于节点的容器都只需要指针交换用于所有修改操作,这在所有现代体系结构上都是原子的.但是,以非原子序列复制多个不同内存区域的任何事情是否真的会造成无法解决的问题呢？

不.想象一下POD数据项的平面数组.现在,如果将数组视为循环缓冲区,则只需要以原子方式维护缓冲区前端和末尾位置的索引.容器可以在内部 "脏前面指数" 中随意更新,同时在外部前面复制.(副本可以使用轻松的内存排序).只有在知道整个副本完成后,才会更新外部前端索引.此更新需要采用acq_rel/cst内存顺序^[1].

只要容器能够保护front永不完全包裹和到达的不变量back,这是一个甜蜜的交易.我认为这个想法在Disruptor Library(LMAX成名)中得到了普及.你得到的机械共振从

• 读/写时的线性存储器访问模式
• 如果你可以使记录大小与(多个)物理缓存行对齐,那就更好了
• 除非POD包含该记录之外的原始引用,否则所有数据都是本地的

Boost如何spsc_queue实际做到这一点？

1. 是的,spqc_queue存储在一个连续的内存块对齐的原始元素的值:(例如,从compile_time_sized_ringbuffer其中underlies 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,但它必须是默认构造和可复制的).

2. 是的,读和写指针是原子积分值.请注意,boost devs已经注意应用足够的填充来避免读/写索引的缓存行上的False Sharing :( from 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_;
   

3. 事实上,正如您所看到的,在读取或写入方面只有"内部"索引.这是可能的,因为只有一个写入线程,也只有一个读取线程,这意味着在写入操作结束时只能有比预期更多的空间.

4. 还有其他一些优化:

   • 支持它的平台的分支预测提示(unlikely())
   • 可以一次推送/弹出一系列元素.如果您需要从一个缓冲区/环形缓冲区虹吸到另一个缓冲区/环形缓冲区,这应该可以提高吞吐量,特别是如果原始元素大小不等于缓存行的(整数倍)
   • 尽可能使用std :: unitialized_copy
   • 在实例化时,将优化调用琐碎的构造函数/析构函数
   • unitialized_copy将优化为所有主要标准库实现的memcpy(意味着如果您的架构支持它将使用例如SSE指令)

总而言之,我们看到了一个环形缓冲器的最佳可能想法

使用方法

Boost为您提供了所有选择.您可以选择使元素类型成为指向消息类型的指针.但是,正如您在问题中提出的那样,这种间接级别会降低引用的局部性,并且可能不是最佳的.

另一方面,如果复制费用昂贵,则将完整的消息类型存储在元素类型中会变得昂贵.至少尝试使元素类型很好地适应缓存行(通常在Intel上为64字节).

因此在实践中,您可能会考虑将常用数据存储在值中,并使用指针引用较少使用的数据(指针的成本将低,除非它被遍历).

如果您需要"附件"模型,请考虑为引用数据使用自定义分配器,以便您也可以在其中实现内存访问模式.

让你的探查器指导你.

^[1]我想说spsc acq_rel应该可行,但我对细节有点生疏.作为一项规则,我强调不要自己编写无锁代码.我建议其他人按照我的例子:)