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

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

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

1> Nova..：

---

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

2> Steve Gilham..：

---

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

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

---

如果您想要真正的无锁代码,对于多个priducers或消费者,那么我就出去了.Sutter的多生产者队列示例不是无锁的 - 有一个锁定序列化生成器,一个锁定序列化消费者.如果你能找到一个,我也会对此感兴趣.

3> Cameron..：

---

是!

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

完全等待(没有CAS循环)

超快速(每秒超过一亿次入队/出队操作)

使用C++ 11移动语义

根据需要增长(但只有你想要它)

是否对元素进行无锁内存管理(使用预先分配的连续块)

独立(两个标题加上许可证和自述文件)

在MSVC2010 +,Intel ICC 13和GCC 4.7.2下编译(并且应该在任何C++ 11完全兼容的编译器下工作)

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

注意事项:

仅适用于单生产者单一消费者体系结构(即两个线程)

在x86(-64)上进行了彻底测试,并且应该在ARM,PowerPC和其他CPU上工作,其中对齐的本机大小的整数和指针加载和存储自然是原子的,但是没有在非x86 CPU上进行现场测试(如果有人有一个测试它让我知道)

不知道是否有任何专利被侵犯(使用风险等等).请注意,我自己从头开始设计和实现它.

---

听起来非常好，但是需要多个生产者和/或多个消费者来利用真正的多线程。

---

@RED:取决于应用程序.单生产者/消费者就是我所需要的,所以我建造的都是;-)

4> André Neves..：

---

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

ProducerConsumerQueue 这里有docs和示例代码.

AtomicHashMap与文档和示例代码这里

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

干杯!

5> 小智..：

---

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

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

http://www.liblfds.org

6> RED SOFT ADA..：

---

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

答案是否定的.

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

---

http://www.liblfds.org

---

100%正确.我在comp.programming.threads新闻组的帮助下得到了相同的结果.一个原因是无锁数据结构的区域是专利矿场.因此,即使像英特尔这样的商业图书馆也在避免它.

---

为什么这个答案会得到如此多的赞成.这个问题很容易编辑.或者这可以在评论中.

7> 小智..：

---

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

公共git存储库

---

这是标准提升的一部分 - 请查看http://www.boost.org/doc/libs/1_53_0/doc/html/lockfree.html上的文档.

8> Nemanja Trif..：

---

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

9> Adisak..：

---

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

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

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

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

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