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

Question

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

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

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

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

这个方法好吗？如果是，我也有兴趣了解您使用 intrusive::list 的经验，特别是对于多线程应用程序。

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 ，并且读锁不会竞争。

对于写入:

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

上述方法的工作原理是对编写线程更加自私，这应该可以消除饥饿。

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

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

对于写入: 根据读者的要求，将一个shared_ptr放入集合中，放弃锁。制作集合的私有(private)拷贝并修改它(由于它是私有(private)拷贝，因此不需要锁)。再次获取写锁并用新集合替换现有的shared_ptr。最后一个完成旧集合的线程将销毁它。所有 future 的线程都将使用新更新的集合。

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