是否有生产就绪的无锁队列或 C++ 中的哈希实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1164023/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is there a production ready lock-free queue or hash implementation in C++
提问by RED SOFT ADAIR
I ve been googling quite a bit for a lock-free queue in C++. I found some code and some trials - but nothing that i was able to compile. A lock-free hash would also be welcome.
我一直在谷歌上搜索 C++ 中的无锁队列。我找到了一些代码和一些试验 - 但我无法编译。无锁哈希也将受到欢迎。
SUMMARY: So far i have no positive answer. There is no "production ready" library, and amazingly none of the existent libraries complies to the API of STL containers.
总结：到目前为止，我还没有肯定的答案。没有“生产就绪”库，令人惊讶的是，现有的库都不符合 STL 容器的 API。
回答by Nova
As of 1.53, boost provides a set of lock free data structures, including queues, stacks and single-producer/single-consumer queues (i.e. ring buffers).
从 1.53 开始，boost 提供了一组无锁数据结构，包括队列、堆栈和单生产者/单消费者队列（即环形缓冲区）。
回答by Steve Gilham
The starting point would be either of Herb Sutter's DDJ articles for either a single producer and consumeror multiple ones. The code he gives (in-line starting on the second page of each article) uses the C++0x style atomic<T> template type; which you can imitate using the Boost interprocess library.
起点将是 Herb Sutter 为单个生产者和消费者或多个生产者和消费者撰写的 DDJ 文章。他给出的代码（从每篇文章的第二页开始）使用 C++0x 风格的 atomic<T> 模板类型；您可以使用 Boost 进程间库来模仿它。
The boost code is buried in the depths of the interprocess library, but having read through the appropriate header file (atomic.hpp) the implementations for the necessary compare-and-swap operations on the systems I am familiar with look sound.
boost 代码隐藏在进程间库的深处，但在阅读了适当的头文件 (atomic.hpp) 后，我熟悉的系统上必要的比较和交换操作的实现看起来很不错。
回答by Cameron
Yes!
是的！
I wrote a lock-free queue. It has Features?:
我写了一个无锁队列。它有特点吗？：
- Fully wait-free (no CAS loops)
- Super fast(over a hundred million enqueue/dequeue operations per second)
- Uses C++11 move semantics
- Grows as needed (but only if you want it to)
- Does lock-free memory management for the elements (using pre-allocated contiguous blocks)
- Stand-alone (two headers plus a license and readme)
- Compiles under MSVC2010+, Intel ICC 13, and GCC 4.7.2 (and should work under any C++11 fully-compliant compiler)
- 完全免等待（无 CAS 循环）
- 超快（每秒超过一亿次入队/出队操作）
- 使用 C++11 移动语义
- 根据需要增长（但仅当您愿意时）
- 对元素进行无锁内存管理（使用预先分配的连续块）
- 独立（两个标题加上许可证和自述文件）
- 在 MSVC2010+、Intel ICC 13 和 GCC 4.7.2 下编译（并且应该在任何 C++11 完全兼容的编译器下工作）
It's available on GitHubunder the simplified BSD license (feel free to fork it!).
它可以在简化的 BSD 许可下在 GitHub 上获得（请随意分叉它！）。
Caveats:
注意事项：
- Only for single-producer single-consumer architecture(i.e. two threads)
- Thoroughly tested on x86(-64), and should work on ARM, PowerPC, and other CPUs where aligned native-sized integers and pointer loads and stores are naturally atomic, but has not been field tested on non-x86 CPUs (if someone has one to test it on let me know)
- No idea if any patents are infringed upon (use at your own risk, etc.). Note that I did design and implement it myself from scratch.
- 仅适用于单生产者单消费者架构（即两个线程）
- 在 x86(-64) 上进行了彻底测试，应该可以在 ARM、PowerPC 和其他 CPU 上运行，其中对齐的本机大小的整数和指针加载和存储自然是原子的，但尚未在非 x86 CPU 上进行现场测试（如果有人一个测试它让我知道）
- 不知道是否有任何专利被侵犯（使用风险自负等）。请注意，我确实从头开始设计并实现了它。
回答by André Neves
Facebook's Follyseems to have lock free data structures based on C++11 <atomic>:
Facebook 的Folly似乎有基于 C++11 的无锁数据结构<atomic>：
ProducerConsumerQueuewith docs and example code here.
AtomicHashMapwith docs and example code here
ProducerConsumerQueue与文档和示例代码在这里。
带有文档和示例代码的AtomicHashMap在这里
I would dare to say these are currently used in production, so I guess they could safely be used in other projects.
我敢说这些目前在生产中使用，所以我想它们可以安全地用于其他项目。
Cheers!
干杯!
回答by André Neves
There is such a library, but it's in C.
有这样一个库，但它是用 C 语言编写的。
Wrapping to C++ should be straightforward.
包装到 C++ 应该很简单。
回答by André Neves
boost.lockfree is an attempt to create c++ implementations of lockfree stack and fifo classes.
boost.lockfree 是尝试创建无锁堆栈和 fifo 类的 C++ 实现。
回答by RED SOFT ADAIR
After having checked most of the given answers, i can only state:
在检查了大部分给出的答案后，我只能说：
The answer is NO.
答案是否定的。
There is no such thing right that could be used right out of the box.
没有这样的东西可以开箱即用。
回答by Nemanja Trifunovic
The closest thing I am aware of is Windows Interlocked Singly Linked Lists. Of course, it is Windows only.
我所知道的最接近的是Windows Interlocked Singly Linked Lists。当然，它仅适用于 Windows。
回答by Adisak
If you have a multiple-producer / single-consumer Queue/FIFO, you can easily make one LockFree using SLIST or a trivial Lock Free LIFO stack. What you do is have a second "private" stack for the consumer (which can also be done as a SLIST for simplicity or any other stack model you choose). The consumer pops items off the private stack. Whenever the private LIFO is exhasted, you do a Flush rather than Pop off the shared concurrent SLIST (grabbing the entire SLIST chain) and then walk the Flushed list in-order pushing items onto the private stack.
如果您有一个多生产者/单消费者队列/FIFO，您可以使用 SLIST 或简单的无锁 LIFO 堆栈轻松制作一个 LockFree。您所做的是为消费者提供第二个“私有”堆栈（为了简单起见，也可以作为 SLIST 或您选择的任何其他堆栈模型来完成）。消费者从私有堆栈中弹出项目。每当私有 LIFO 耗尽时，您会执行 Flush 而不是弹出共享的并发 SLIST（抓取整个 SLIST 链），然后按顺序遍历 Flushed 列表将项目推送到私有堆栈上。
That works for single-producer / single-consumer and for multiple-producer / single-consumer.
这适用于单一生产者/单一消费者和多生产者/单一消费者。
However, it does not work for multiple-consumer cases (with either single-producer or multiple-producers).
但是，它不适用于多个消费者的情况（单个生产者或多个生产者）。
Also, as far as hash tables go, they are an ideal candidate for "striping" which is just dividing the hash into segments having a lock per segments of the cache. This is how the Java concurrent library does it (using 32-stripes). If you have a light-weight reader-writer lock, the hash table can be concurrently accessed for simultaneous reads and you will only stall when write are occurring on contested stripes (and possibly if you allow for growing the hash table).
此外，就哈希表而言，它们是“条带化”的理想候选者，它只是将哈希划分为具有每个缓存段锁定的段。这就是 Java 并发库的工作方式（使用 32 条带）。如果你有一个轻量级的读写器锁，哈希表可以被并发访问以进行同步读取，并且只有在有争议的条带上发生写入时才会停止（如果你允许增长哈希表）。
If you roll your own, make sure to interleave your locks with the hash entries rather than put all your locks in an array next to each other so you're less likely to have false sharing.
如果您自己动手，请确保将您的锁与哈希条目交错，而不是将所有锁放在一个彼此相邻的数组中，这样您就不太可能出现错误共享。
回答by Marwan Burelle
I may come a bit late on this.
我可能来晚了一点。
The absence of solutions (at the question was asked) are mainly due to an important issue in C++ (before C++0x/11): C++ have (has) no concurrent memory model.
没有解决方案（在提出问题时）主要是由于 C++ 中的一个重要问题（在 C++0x/11 之前）：C++ 没有（具有）并发内存模型。
Now, using std::atomic, you can control memory ordering issues and have proper compare-and-swap operations. I've written myself an implementation of Micheal&Scott's lock-free queue (PODC96) using C++11 and Micheal's Hazard Pointers (IEEE TPDS 2004) to avoid early free and ABA problems. It's working fine but it's a quick and dirty implementation and I'm not satisfied with the actual performances. Code is available on bitbucket: LockFreeExperiment
现在，使用 std::atomic，您可以控制内存排序问题并进行适当的比较和交换操作。我已经使用 C++11 和 Micheal's Hazard Pointers (IEEE TPDS 2004) 为自己编写了 Micheal&Scott 的无锁队列 (PODC96) 的实现，以避免早期免费和 ABA 问题。它工作正常，但它是一个快速而肮脏的实现，我对实际表现不满意。代码在 bitbucket 上可用：LockFreeExperiment
It's also possible to implement lock-free queue without hazard pointers using double-words CAS (but 64bit versions will only be possible on x86-64 using cmpxchg16b), I've a blog post about that (with untested code for the queue) here: Implementing generic double-word compare and swap for x86/x86-64(LSE blog.)
也可以使用双字 CAS 实现无锁队列而没有危险指针（但 64 位版本只能在 x86-64 上使用 cmpxchg16b），我有一篇关于此的博客文章（带有未经测试的队列代码）here ：为 x86/x86-64 实现通用双字比较和交换（LSE 博客。）
My own benchmark show me that double-locked queue (also in Micheal&Scott 1996 paper) performs as well as the lock-free one (I haven't reach enough contention so that locked data structures have performances issues, but my bench are too light for now) and the concurrent queue from Intel's TBB seems even better (two time faster) for a relatively small number (depending on the operating system, under FreeBSD 9, the lowest bound I've found so far, this number is 8 threads on an i7 with 4 ht-core, and thus 8 logical CPUs) of threads and have very strange behavior (execution time of my simple benchmark move from seconds to hours !)
我自己的基准测试表明，双锁队列（也在 Micheal&Scott 1996 年的论文中）与无锁队列的性能一样好（我没有达到足够的争用，因此锁定的数据结构存在性能问题，但我的工作台对于现在）并且来自英特尔 TBB 的并发队列似乎更好（快两倍）对于一个相对较小的数量（取决于操作系统，在 FreeBSD 9 下，我迄今为止发现的最低界限，这个数字是 8 个线程） i7 具有 4 个 ht 核心，因此有 8 个逻辑 CPU）的线程并且具有非常奇怪的行为（我的简单基准测试的执行时间从几秒变为几小时！）
Another limitations about lock-free queues following the STL style: having iterators on lock-free queue has no sens.
遵循 STL 风格的无锁队列的另一个限制：在无锁队列上使用迭代器是没有意义的。
