memory - boost 锁无锁spsc_queue缓存访问

Question

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

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

我已经看到了队列，其中需要由使用者核心操作的大对象的指针被推入队列。

如果使用者核心从队列中弹出一个元素，则我认为这意味着该元素（在本例中为指针）已经加载到使用者核心的L2和L1缓存中。但是要访问该元素，是否不需要通过从L3缓存或跨互连（如果另一个线程位于不同的cpu套接字上）查找并加载该元素来访问指针本身？如果是这样，那么简单地发送消费者可以丢弃的对象的副本会更好吗？

谢谢。

Answer 1

C ++主要是按需付费的生态系统。

任何常规队列都可以让您选择存储语义（按值或按引用）。

但是，这次您订购了一些特殊的东西：订购了无锁队列。
为了免于锁定，它必须能够将所有可观察到的修改操作作为原子操作执行。这自然限制了可以直接在这些操作中使用的类型。

您可能会怀疑是否有可能使用超出系统本机寄存器大小的值类型（例如，int64_t）。

好问题。

输入环形缓冲区

实际上，任何基于节点的容器都只需要针对所有修改操作进行指针交换，这在所有现代体系结构中都是原子的。
但是，涉及以非原子顺序复制多个不同的存储区的事情真的构成了无法解决的问题吗？

否。想象一下POD数据项的平面阵列。现在，如果您将数组视为循环缓冲区，则只需原子地维护缓冲区前端和终止位置的索引即可。容器有空时可以在内部“脏前沿索引”中进行更新，同时在外部前沿之前进行复制。 （副本可以使用宽松的内存顺序）。仅在已知整个副本完成后，才更新外部前端索引。此更新需要按照acq_rel / cst内存顺序进行[1]。

只要容器能够保护front永远不会完全包裹并到达back的不变式，这是很不错的选择。我认为这个想法在（LMAX声望很高的）Disruptor Library中得到了普及。您会从中获得机械共振


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




Boost的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开发人员已采取足够的填充措施，以避免在高速缓存行上使用 False Sharing进行读/写索引：（来自 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_;

实际上，如您所见，在读取或写入侧只有“内部”索引。这是可能的，因为只有一个写入线程，也只有一个读取线程，这意味着写入操作结束时只能有比预期更多的空间。
存在其他一些优化：


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



总而言之，我们看到了关于环形缓冲区的同类最佳方案

使用什么

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

另一方面，如果复制昂贵，则将完整的消息类型存储在元素类型中可能会变得昂贵。至少要尝试使元素类型很好地适合高速缓存行（在Intel上通常为64字节）。

因此，在实践中，您可以考虑将经常使用的数据存储在该值中，并使用指针引用较少使用的数据（除非遍历指针，否则指针的开销会很低）。

如果您需要“附加”模型，请考虑对引用的数据使用自定义分配器，以便在那里也可以实现内存访问模式。

让您的分析器引导您。



[1]我想说对于spsc acq_rel应该可行，但是我对细节有些不满意。通常，我要指出自己不要编写无锁代码。我建议其他人都遵循我的示例：）