1

我需要以只读方式几乎不断地迭代一系列结构，但是对于每 1M+ 次读取，其中一个线程可能会附加一个项目。我认为在这里使用互斥锁会有点矫枉过正，我还在某处读到读/写锁对读者有其自身的缺点。

我正在考虑在 std::vector 上使用 reserve() 但这个答案Iterate over STL container using indices safe way to avoid using locks? 似乎使这一点无效。

关于哪种方式可能最快的任何想法？最重要的是让读者能够在尽可能少的争用情况下快速有效地进行迭代。写入操作对时间不敏感。

更新：我的另一个用例是“列表”可以包含指针而不是结构。即，std::vector。同样的要求也适用。

更新 2：假设示例

全球可访问：

typedef std::vector<MyClass*> Vector;
Vector v;
v.reserve(50);

阅读器线程 1-10：（这些几乎一直在运行）

.
.
int total = 0;
for (Vector::const_iterator it = v.begin(); it != v.end(); ++it)
{
   MyClass* ptr = *it;
   total += ptr->getTotal();
}
// do something with total
.
.

作家线程 11-15：

MyClass* ptr = new MyClass();
v.push_back(ptr);

这基本上就是这里发生的事情。线程 1-15 都可以同时运行，尽管通常只有 1-2 个读取线程和 1-2 个写入线程。

4

2 回答 2

4

What I think could work here is own implementation of vector, something like this:

template <typename T> class Vector
{
// constructor will be needed of course
public:
    std::shared_ptr<const std::vector<T> > getVector()
        { return mVector; }
    void push_back(const T&);

private:
    std::shared_ptr<std::vector<T> > mVector;
};

Then, whenever readers need to access a specific Vector, they should call getVector() and keep the returned shared_ptr until finished reading.

But writers should always use Vector's push_back to add new value. This push_back should then check if mVector.size() == mVector.capacity() and if true, allocate new vector and assign it to mVector. Something like:

template <typename T> Vector<T>::push_back(const T& t)
{
    if (mVector->size() == mVector->capacity())
    {
        // make certain here that new_size > old_size
        std::vector<T> vec = new std::vector<T> (mVector->size() * SIZE_MULTIPLIER);

        std::copy(mVector->begin(), mVector->end(), vec->begin());
        mVector.reset(vec);
    }
// put 't' into 'mVector'. 'mVector' is guaranteed not to reallocate now.
}

The idea here is inspired by RCU (read-copy-update) algorithm. If storage space is exhausted, the new storage should not invalidate the old storage as long as there is at least one reader accessing it. But, the new storage should be allocated and any reader coming after allocation, should be able to see it. The old storage should be deallocated as soon as no one is using it anymore (all readers are finished).

Since most HW architectures provide some way to have atomic increments and decrements, I think shared_ptr (and thus Vector) will be able to run completely lock-less.

One disadvantage to this approach though, is that depending on how long readers hold that shared_ptr you might end up with several copies of your data.

PS: hope I haven't made too many embarrassing errors in the code :-)

于 2013-03-14T09:23:36.297 回答
0

... 在 std::vector 上使用 reserve() ...

仅当您可以保证向量永远不需要增长时，这才有用。您已声明如果项目的数量不受上述限制，因此您无法提供该保证。

Notwithstanding the linked question, you could conceivable use std::vector just to manage memory for you, but it would take an extra layer of logic on top to work around the problems identified in the accepted answer.

The actual answer is: the fastest thing to do is minimize the amount of synchronization. What the minimal amount of synchronization is depends on details of your code and usage that you haven't specified.

For example, I sketched a solution using a linked-list of fixed-size chunks. This means your common use case should be as efficient as an array traversal, but you're able to grow dynamically without re-allocating.

However, the implementation turns out to be sensitive to questions like:

  • whether you need to remove items
    • whenever they're read?
    • only from the front or from other places?
  • whether you want the reader to busy-wait if the container is empty
    • whether this should use some kind of backoff
  • what degree of consistency is required?
于 2013-03-13T16:56:09.497 回答