问题标签 [libcds]

我正在使用libcds，他们有一个 Michael Hash Map 和 Split order list 的实现。

根据我从文档中收集的信息，我是如何实现它们的：

包括：

代码：

代码：

和：

我通过调用来启动结构：

但是，当 CDSSplit 启动或 Michael 执行第一次插入时，我会遇到分段错误。

库安装良好，没有任何警告，我使用其他哈希表没有任何错误。

谢谢你的帮助

（也发布了，在图书馆的讨论页面上的细节较少，但那里似乎没有太多的存在，如果那里发布了任何内容，将会回复）

编译标志：-std=c++0x -O3 -msse2 -m32 -DNDEBUG -DINTEL -g -D_REENTRANT -lrt -pthread -fno-strict-aliasing -l cds -l tbb -lllalloc

GDB 输出：

所以我真的很想看到一些并行的速度测试（比如从 100 到 10000 个并行线程），其中每个线程在至少 3 种类型的并发映射上插入、查找、删除 - std::map （带有一些互斥体）vs libcds（并发数据结构） ...

因此，例如，如果这种比较尚不存在，请帮助我创建一个。

直接相关： LibCds：Michael Hashmap 和拆分顺序列表

想象我们有

而不是如何创建这样的测试来创建N个线程并且每个线程都会调用create，find delete...我开始写一些东西，但它现在可以用boost 1.47.0编译代码...

我正在使用带有默认优化设置 (/O2) 的 VS2012，并且此问题仅在发布模式下存在。

我有一些代码使用michael_deque（使用标准 GC）和指向（抽象）类型的指针T。
当我尝试将一个指向派生自 的类型的指针推回时T，应用程序在退出 的push_back()函数时崩溃michael_deque。

问题似乎完全取决于这个特定的类型T，因为编写一个虚拟类foo，在类中从它派生bar（并在构造函数中打印一些东西以避免它被优化掉）然后推回new bar()michael_deque 不会导致崩溃。

有问题的课程T是这样的：

该错误可以在一个最小的程序中重现（如果您碰巧有一个可以像我一样执行此操作的环境，只需放置一个std::atomic<unsigned int> taskIDCounterTask 类可以看到它的地方）：

这可能是什么原因？我是否在类 Task 中做了一些未定义的事情，这会导致优化问题出现问题？

我尝试创建将映射std::string到的哈希映射，std::string到目前为止我使用了以下代码：

它基于 libcds 文档。但我不确定我是否正确使用哈希映射......根据描述 SplitListMap 底层列表的论文应该按键的哈希排序，但文档建议使用 std::less<TKey>指定迈克尔列表顺序。使用std::less<std::string>正确吗？

我正在寻找C++ 中的无锁数据结构来替换以下内容：

该集合应该支持.insert()并且.size()最多具有 O(logN) 复杂度，具有迭代器，并且应该能够使用自定义比较器保持其顺序。基本上与Java中的相同ConcurrentSkipListSet。理想情况下，它应该独立于平台。

我正在查看 CDS： http: //libcds.sourceforge.net/doc/cds-api/modules.html但不确定哪种数据结构可以实现目标。该文档对于某些数据结构并没有真正的复杂性。

任何建议都会很棒，谢谢！

我已经./build.sh -b 64 -z '-std=c++0x' -l '-L /usr/lib/x86_64-linux-gnu' --with-boost /usr/include/boost --amd64-use-128bit在build文件夹中安装了带有命令的 cds 库。

在我尝试编译文件夹的示例init.cpp后，我在终端中输入了这个： ，终端显示：。srcg++ init.cpp -o initfatal error: cds/init.h: No such file or directory

这种情况下编译命令该怎么办？谢谢。

我正在寻找可组合操作- 使用事务内存相当容易。（感谢阿米·塔沃里）

使用锁（互斥锁/自旋锁）很容易做到——但它会导致死锁——因此基于锁的算法只能通过手动调整来组合。

无锁算法不存在死锁问题，但它不可组合。需要将 2 个或更多容器设计为单个组合的无锁数据结构。

是否有任何方法、辅助实现或一些无锁算法 - 以原子方式使用多个无锁容器以保持一致性？

• 检查一个项目是否同时在两个容器中
• 以原子方式将元素从一个容器移动到另一个容器

...

或者 RCU 或危险指针可以帮助做到这一点吗？

众所周知，我们可以使用无锁容器，这在其实现中很困难，例如来自并发数据结构 (CDS) 库： http: //libcds.sourceforge.net/doc/cds-api/group__cds__nonintrusive__map.html

例如，我们可以使用像SkipList CDS-lib这样的无锁有序映射

但即使是简单的无锁算法在任何情况下都不是无锁的：

1. 迭代器 文档链接

您只能在 RCU lock 下迭代跳过列表集项目。只有在这种情况下，迭代器是线程安全的，因为当 RCU 被锁定时，任何集合的项目都不能被回收。迭代期间对 RCU 锁定的要求意味着元素的删除（即擦除）是不可能的。

2. ::contains(K const &key)-文档链接

该函数在内部应用 RCU 锁。

3. 要::get(K const &key)更新我们得到的元素，我们应该使用 lock：documentation-link

例子：

但是如果我们使用 2 个无锁容器而不是 1 个，并且如果我们只使用总是无锁的方法，或者其中一个无锁的方法，那么我们可以在不锁定两个容器的情况下做到这一点吗？

我们可以map_1在map_2 不锁定两个容器的情况下原子地移动 1 个元素- 即map_1.erase(K const &key)，map_2.insert(K const &key, V const &val)如果我们想保持原子性和一致性：

• 其他线程没有看到第一个容器中没有元素，他仍然没有出现在第二个容器中

• 其他线程看不到第一个容器中有元素，而第二个容器中已经存在相同的元素

如果我们想保持原子性和一致性，我们可以用两个或多个无锁容器原子地做一些事情而不锁定两者吗？

回答：我们不能通过简单地使用它的常用函数来一次对两个或多个无锁容器进行任何原子操作而无需锁。

仅当我们在容器 API 中执行无锁算法提供的 1 次简单操作时，对于 2 个无锁容器来说，1 个锁就足够了，排除上述 3 种情况，即使在无锁容器中也使用锁。

如果您对无锁算法进行了复杂的自定义改进，那么“但可能会有一些额外的开销”，那么您可以提供一些可组合的，例如，“两个队列彼此了解，并且查看它们的代码是精心设计”，正如 Peter Cordes 所说。

我正在实现Anthony Williams 在“C++ Concurrency in Action”中描述的无锁队列。我将它作为libcds的新容器进行测试。弹出和推送测试工作正常。但是多个生产者，多个消费者测试有时会失败。VLD（或 Intel Inspector XE 或 ASan）显示内存泄漏。我通过添加节点析构函数来修复它，但所有元素存在的问题仍然存在。我怎样才能解决这个问题？谢谢。

威廉姆斯无锁队列：

测试结果：

Visual Leak Detector 从以下位置读取设置：D:\Development\COMMON_UTILS\Visual Leak Detector\vld.ini Visual Leak Detector 版本 2.5 已安装。libcds 版本 2.1.0 测试开始于 2017 年 1 月 31 日 01:19:03 使用测试配置文件：test-debug.conf 系统拓扑：逻辑处理器数：4

d:\development\libcds\tests\unit\queue\queue_reader_writer.cpp(253) : CPPUNIT_CH ECK(nTotalPops + nPostTestPops == nQueueSize: popped=99997 必须是 99999); 测试弹出序列的一致性...

警告：Visual Leak Detector 检测到内存泄漏！---------- Block 116955 at 0x00DB33D0: 8 bytes ---------- Leak Hash: 0xD835B211, Count: 1, Total 8 bytes Call Stack (TID 2836): ucrtbased.dll！ malloc() f:\dd\vctools\crt\vcstartup\src\heap\new_scalar.cpp (19): unit-queue_d.exe!operator new() + 0x9 bytes d:\development\libcds\cds\container\ williams_queue.h (297): unit-queue_d.exe !cds::container::WilliamsQueue::push() d:\development\libcds\tests\unit\queue\queue_reader_writer.cpp (85): unit-que eue_d。 exe!queue::Queue_ReaderWriter::WriterThread >::test() + 0xF 字节

然后我通过添加带有数据删除的节点析构函数来修复内存泄漏。但测试失败仍然存在。

试运行代码

我在窗户上工作。如何在 VS 项目中包含 CDS 库？我找不到“include”目录，也找不到“lib”目录。

http://libcds.sourceforge.net/doc/cds-api/index.html

我想在我的项目中使用来自 libCDS 的关联容器。问题是libCDS中有很多。请告知哪张卡更好用，前提是它应该能够扩展和擦除数据。