在C++中是否有生产就绪的无锁队列或散列实现

Question

我一直在谷歌搜索C++中的无锁队列.我发现了一些代码和一些试验 - 但我没有能够编译.也欢迎无锁哈希.

摘要:到目前为止,我没有正面答案.没有"生产就绪"库,令人惊讶的是现有的库都没有符合STL容器的API.

Answer 1

从1.53开始,boost提供了一组无锁数据结构,包括队列,堆栈和单生成器/单用户队列(即环缓冲区).

Answer 2

其出发点是,要么香草萨特的文章DDJ对于任何一个单一的生产者和消费者或多个的.他给出的代码(在每篇文章的第二页开始内联)使用C++ 0x样式的atomic <T>模板类型; 您可以使用Boost进程间模型进行模拟.

增强代码隐藏在进程间库的深处,但是通过读取相应的头文件(atomic.hpp),我熟悉的系统上必要的比较和交换操作的实现看起来很合理.

Answer 3

是!

我写了一个无锁队列.它有Features™:

• 完全等待(没有CAS循环)
• 超快速(每秒超过一亿次入队/出队操作)
• 使用C++ 11移动语义
• 根据需要增长(但只有你想要它)
• 是否对元素进行无锁内存管理(使用预先分配的连续块)
• 独立(两个标题加上许可证和自述文件)
• 在MSVC2010 +,Intel ICC 13和GCC 4.7.2下编译(并且应该在任何C++ 11完全兼容的编译器下工作)

它可以在GitHub上以简化的BSD许可证获得(随意分叉!).

注意事项:

• 仅适用于单生产者单一消费者体系结构(即两个线程)
• 在x86(-64)上进行了彻底测试,并且应该在ARM,PowerPC和其他CPU上工作,其中对齐的本机大小的整数和指针加载和存储自然是原子的,但是没有在非x86 CPU上进行现场测试(如果有人有一个测试它让我知道)
• 不知道是否有任何专利被侵犯(使用风险等等).请注意,我自己从头开始设计和实现它.

Answer 4

Facebook的Folly似乎拥有基于C++ 11的无锁数据结构<atomic>:

• ProducerConsumerQueue 这里有docs和示例代码.

• AtomicHashMap与文档和示例代码这里

我敢说这些目前在生产中使用,所以我猜他们可以安全地用于其他项目.

干杯!

Answer 5

有这样一个图书馆,但它在C.

包装到C++应该是直截了当的.

http://www.liblfds.org

Answer 6

在检查了大部分给定答案后,我只能说:

答案是否定的.

没有这样的东西可以直接使用.

Answer 7

boost.lockfree试图创建lockfree堆栈和fifo类的c ++实现.

公共git存储库

Answer 8

我所知道的最接近的是Windows Interlocked Singly Linked Lists.当然,它只是Windows.

Answer 9

如果你有一个多生产者/单一消费者队列/ FIFO,你可以使用SLIST或一个简单的无锁LIFO堆栈轻松制作一个LockFree.你所做的是为消费者提供第二个"私人"堆栈(为简单起见,你也可以将其作为SLIST或你选择的任何其他堆栈模型).消费者将物品从私人堆栈中弹出.每当私有LIFO被呼出时,你会执行Flush而不是Pop共享并发SLIST(抓取整个SLIST链),然后按顺序将Flushed列表推送到私有堆栈.

这适用于单一生产者/单一消费者和多生产者/单一消费者.

但是,它不适用于多个消费者案例(单一生产者或多生产者).

此外,就哈希表而言,它们是"条带化"的理想候选者,其仅将哈希分成具有每个高速缓存段锁定的段.这就是Java并发库的工作方式(使用32条纹).如果你有一个轻量级的读写器锁,可以同时访问哈希表以便同时读取,并且只有在有争议的条带上发生写入时才会停止(并且可能如果你允许增加哈希表).

如果您自己滚动,请确保将您的锁与哈希条目交错,而不是将所有锁定放在一个数组中,这样您就不太可能进行错误共享.