c++ - 此多线程用例的最佳数据结构 : Is Intrusive List good?

Question

我需要设计一个支持以下操作的数据结构:

• 搜索数据结构中的元素是基于一个区间的键。例如1-5区间内的值可能是3，6-11区间内的值可能是5等等。间隔是连续的，它们之间没有重叠。
• 查找上一个和下一个间隔 - 这几乎与搜索间隔一样频繁。
• 拆分间隔，加入连续间隔
• 并发性:我已将设计限制为一个编写器线程和其他读取器线程，如下所示。写入线程可以拆分或加入间隔，或修改间隔中的值。任何读取器线程仅在一个时间间隔内读取值(读取器可以读取多个时间间隔，但我不必序列化所有读取 - 在两次读取之间进行写入是可以的)。每个读者每次写入大约有 20-80 次读取。此外，我还必须决定读者的数量，但大约是 2-8 人。

我考虑使用列表在中间添加和删除元素。只有有限数量的间隔 - 所以可能使用 map 是不正确的。 STL 列表不支持这种访问方式(一个作者，多个读者)。 boost::intrusive::list 似乎是合适的。在侵入式列表之上，我将必须获取锁以读/写间隔。

此外，据我所知，与 STL 列表相比，侵入式列表可用于更好的缓存局部性(以及为包含的对象分配适当的内存)。

方法好吗？如果是，我也有兴趣了解您使用侵入式::列表的体验，尤其是对于多线程应用程序。

Answer 1

这里有 2 个不同的问题:

1. 如何表示你的数据结构
2. 如何以高效的方式使其线程安全

您的数据结构将为每次写入执行 (20-80) x (2-8) 次读取。

(1)。首先，假设您的范围是如下数据结构

    struct Interval
    {
        Interval(int start, int length)
          : m_start(start),
            m_length(length)
        {}
        int m_start;
        int m_length;
        int value; // Or whatever
    };



<p>Since reads massively outnumber writes, lookup needs to be fast, while modifications don't.</p>

<p>Using a list for your data structure means O(N) lookups and O(1) modification - exactly the wrong way around.</p>

<p>The simplest possible representation of your structure is a vector. If the intervals are held in sorted order, lookups are O(logN) and modifications are O(N).</p>

<p>To implement this, just add a comparator to Interval:</p>

<pre><code>bool operator<(const Interval& rhs) const
{
return m_start < rhs.m_start;
}
</code></pre>

<p>You can then use <code>std::lower_bound</code> to find the first interval equal or lower to your search interval in O(logN).</p>

<p>Next and previous interval are O(1) - decrement or increment the returned iterator.</p>

<p>Splitting an interval means inserting a new element after the current one and adjusting the length of the current - O(N).</p>

<p>Joining two intervals means adding the length of the next one to the current one and erasing the next one - O(N).</p>

<p>You should <code>reserve()</code> enough space in the vector for the maximum number of elements to minimise resizing overhead.</p>

<p>(2). Following Knuth, '<em>premature optimisation is the root of all evil</em>'.</p>



A single read/write lock on the structure holding your vector<Interval>很可能就足够了。唯一可能的问题是 (2a) 由于读者独占锁而导致写入者饥饿，或 (2b) 由于写入者更新时间过长而导致读者饥饿。

(2a) 如果(且仅当)您面临写入饥饿，您可以使锁定更细化。不过，极有可能情况并非如此。为此:

让你的 vector 通过指针而不是值来保持它的间隔。这样调整大小就不会在内存中移动对象。让每个间隔包含一个读/写锁。

对于阅读:获取集合的读取锁，然后获取所需间隔的读取锁。如果不需要读取任何其他间隔，则在获得间隔锁后立即放弃集合锁，以允许其他线程继续进行。

如果您需要读取其他存储桶，您可以按任何顺序对它们进行读取锁定，直到您放弃集合读取锁定，此时写入器可以添加或删除您尚未锁定的任何间隔。获取这些锁时顺序无关紧要，因为当您持有集合上的读锁时，作者无法更改 vector ，并且读锁不会竞争。

对于写入:

获取集合的写锁，然后获取你想要的时间间隔。请注意，对于将添加或删除间隔的任何更新，您必须持有集合写锁。如果你只更新一个间隔，你可以放弃集合锁。否则，您需要持有写锁并在您将要修改的任何时间间隔内获取写锁。您可以按任何顺序获取间隔锁，因为没有集合锁，任何读者都无法获取新的读锁。

以上的工作原理是对 writer thread 更加自私，这应该会消除饥饿。

(2b) 如果您面临读者饥饿，这种情况更不可能发生，最好的解决方案是将集合的写入和读取分开。通过共享指针持有集合，并在其上有一个写锁。

对于阅读:获取写锁和 shared_ptr 的拷贝。放弃写锁。读者现在可以在没有任何锁定的情况下读取集合(它是不可变的)。

对于写入:按照读者的要求将 shared_ptr 带到集合中，放弃锁。制作该集合的私有(private)拷贝并对其进行修改(因为它是私有(private)拷贝，所以不需要锁定)。再次获取写锁并将现有的 shared_ptr 替换为您的新集合。完成旧集合的最后一个线程将销毁它。所有 future 的线程都将使用新更新的集合。

请注意，根据您的问题描述，此算法仅适用于一位作者。