这个多线程用例的最佳数据结构:Intrusive List是否良好？

Question

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

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

我考虑使用list来添加和删除中间的元素.只有有限的间隔 - 所以可能使用地图是不对的.STL列表不能很好地支持这种访问(一个编写器,多个读取器).boost :: intrusive :: list似乎合适.在侵入列表的顶部,我将不得不获取锁来读/写间隔.

此外,我理解侵入列表可用于比STL列表更好的缓存局部性(以及对所包含对象的适当内存分配).

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

Answer 1

你有两个不同的问题:

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
    };

由于读取数量大大超过写入数量,因此查找需要快速,而修改则不需要.

使用数据结构的列表意味着O(N)查找和O(1)修改 - 完全错误的方式.

最简单的结构表示是矢量.如果间隔按排序顺序保持,则查找为O(logN),修改为O(N).

要实现这一点,只需在Interval中添加一个比较器:

bool operator<(const Interval& rhs) const
{
    return m_start < rhs.m_start;
}

然后,您可以使用std::lower_boundO(logN)查找与搜索间隔相等或更低的第一个间隔.

下一个和上一个间隔是O(1) - 递减或递增返回的迭代器.

拆分间隔意味着在当前的元素之后插入一个新元素并调整当前的长度 - O(N).

连接两个间隔意味着将下一个的长度添加到当前的一个并擦除下一个 - O(N).

reserve()在向量中应该有足够的空间来获得最大数量的元素,以最大限度地减少调整大小开销.

(2).在Knuth之后," 过早优化是所有邪恶的根源 ".

保持向量<Interval>的结构上的单个读/写锁定很可能就足够了.唯一可能的问题是(2a)作家饥饿,因为读者垄断了锁定,或者(2b)读者饥饿,因为作者更新花费的时间太长.

(2a)如果(并且仅当)你面临作家饥饿,你可以使锁定更细粒度.它极有可能,这将不会是这样,虽然.去做这个:

使向量按指针保持其间隔,而不是值.这样调整大小不会在内存中移动对象.每个间隔都包含读/写锁.

对于读取:获取集合的读锁定,然后取出所需的间隔.如果您不需要读取任何其他间隔,请在获得间隔锁定后立即放弃收集锁定,以允许其他线程继续.

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

写作:

获取集合的写锁定,然后取出所需的间隔.请注意,必须为将添加或删除间隔的所有更新保留集合写锁定.如果只更新一个间隔,则可以放弃收集锁定.否则,您需要保持写锁定并在要修改的任何时间间隔内获取写锁定.您可以按任何顺序获取间隔锁,因为没有读取器可以在没有集合锁的情况下获取新的读锁.

上面的工作是通过对作者线程更自私,这应该消除饥饿.

(2b)如果你面临读者饥饿,这更不可能,最好的解决方案是将集合写入和读取分开.通过共享指针保持集合,并在其上有一个写锁定.

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

对于写入:根据阅读器将shared_ptr带到集合中,放弃锁定.制作集合的私有副本并对其进行修改(自私有副本以来不需要锁定).再次执行写入锁定,并将现有的shared_ptr替换为新的集合.完成旧集合的最后一个线程将破坏它.所有未来的线程都将使用新更新的集合.

请注意,根据您的问题描述,此算法仅适用于一个编写器.