多线程链表遍历

Question

给定(双重)链接的对象列表(C++),我有一个我想要多线程的操作,以对每个对象执行.每个对象的操作成本不均匀.由于各种原因,链表是这组对象的首选存储.每个对象中的第一个元素是指向下一个对象的指针; 第二个元素是列表中的上一个对象.

我通过构建节点数组并应用OpenMP解决了这个问题.这给了不错的表现.然后我切换到我自己的线程例程(基于Windows原语)并使用InterlockedIncrement()(作用于数组的索引),我可以实现更高的整体CPU利用率和更快的吞吐量.从本质上讲,线程沿着元素"跳跃式"运行.

我的下一个优化方法是尝试消除创建/重用链表中的元素数组.但是,我想继续这种"跳跃式"方法,并以某种方式使用一些不存在的例程,可称为"InterlockedCompareDereference" - 以原子方式比较NULL(列表末尾)和有条件地取消引用和存储,返回解除引用的值.

我不认为InterlockedCompareExchangePointer()会工作,因为我无法原子地取消引用指针并调用此Interlocked()方法.我做了一些阅读,其他人正在建议关键部分或自旋锁.关键部分在这里似乎很重要.我很想尝试旋转锁,但我想我首先在这里提出问题并询问其他人在做什么.我不相信InterlockedCompareExchangePointer()方法本身可以像旋转锁一样使用.然后还必须考虑获取/发布/围栏语义......

想法？谢谢!

Answer 1

关键部分并不是真正的重量级。假设他们可以快速获取锁，那么他们的行为就像自旋锁一样。

问题的解决方案取决于您是否修改列表。如果您不修改列表，您需要做的就是对对象中初始化为 0 的值进行 InterlockedCompareExchange 之类的操作。交换值为 1，如果返回 0，则执行操作，如果返回 1，你跳过。下次您对列表执行操作时，您将交换 2 并检查 1/2 而不是 0/1。

如果您要更改列表，那么这一切都取决于。如果您只想向前移动，并且只删除当前节点，那么您最好的选择是在执行比较交换位、跳跃（获取下一个节点）和删除时锁定的项目中拥有下一个锁节点。