Threadsafe Vector class for C++

Question

Does anyone know a quick and dirty threadsafe vector class for c++? I am multithreading some code, and I believe the problem I have is related to the way the vectors are used. I plan to rewrite the code, but before I go crazy redoing the code, I would like to test it with a threadsafe vector to be sure. I also figure if such a thing is out there, it would be much easier than writing my own version.

Dogmatist

Answer 1

This is difficult because of algorithms.

Suppose you wrapped vector so that all its member functions are serialised using a mutex, like Java synchronized methods. Then concurrent calls to std::remove on that vector still wouldn't be safe, because they rely on looking at the vector and changing it based on what they see.

So your LockingVector would need to specialize every template in the standard algorithms, to lock around the whole thing. But then other algorithms like std::remove_if would be calling user-defined code under the lock. Doing this silently behind the scenes is a recipe for locking inversion as soon as someone starts creating vectors of objects which themselves internally take locks around all their methods.

In answer to your actual question: sorry, no, I don't know of one. For a quick test of the kind you need, I recommend that you start out with:

template <typename T>
class LockedVector {
    private:
    SomeKindOfLock lock;
    std::vector<T> vec;
};

Then drop it in as a replacement container, and start implementing member functions (and member typedefs, and operators) until it compiles. You'll notice pretty quickly if any of your code is using iterators on the vector in a way which simply cannot be made thread-safe from the inside out, and if need be you can temporarily change the calling code in those cases to lock the vector via public methods.

Too

I was hoping I wouldn't have to write my own, but looks like that is probably the quickest way. – Dogmatist

Answer 2

You can check out TBB (like concurrent_vector). I've never used it though, honestly, I find putting the scope guard objects around access easier (especially if the vector is properly encapsulated).

Chuckwalla

Answer 3

I think you'll find it far easier to continue to use std::vector, but to protect concurrent access using some kind of mutex or other operating system synchronization object. You'll also definitely want to use RAII if you are using a mutex.

Tidbit

This is what I intend to do eventually, but the way the code was written, I have 10 vectors in this class, all of which are public(!), not to mentioned they are directly accessed and mutated in probably over a few hundred different spots in other code so it will be quite an effort when I redo the code with mutexes. Right now I just want to replace the std::vector with some working multi-threaded version (which I may have to write) just to test it and be sure it is my problem. – Dogmatist

I don't envy you. If you don't already know where multiple threads access the same vector you might as well start over with a design that has multi-threading in mind from the beginning. Good luck. – Tidbit

Answer 4

As Scott Meyers explains in the effective STL book, by a thread safe container you can expect that:

• Multiple reads are safe
• Multiple writes to different containers are safe.

Thats all. You can not expect many other things such as multiple writes to the same container be thread safe. If this is all what you want then you can take a look at STLPort. If not then the only option I see is to contain the vector in a class that synchronizes the access to the vector.

Gandy

stlport is a just STL implementation. It has nothing to do with concurrency. – Dunkirk

STLPort is an STL implementation that offers (from the home page) "# Exception safety and thread safety." ALL STL implementations are supposed to offer exception safety by design, but there is no requirement to offer thread safety. STLPort does. – Metalanguage

You can see what STLPort means by "thread-safety" here. Basically, they mean the stuff that C++ and/or the hardware give you for free — which is to say, Scott Meyers' conditions. The only way for a library implementor to screw up that kind of "thread safety" is by deliberate sabotage; e.g. he could add a global variable x (unprotected by a lock) and touch it on every write, or he could add a mutable member that's touched by reads, or something like that. – Photocomposition

Answer 5

I forget who discussed this, but one strategy for making a thread-safe container is as follows:

1. All your class's public methods must lock the vector, and must return a boolean for if they succeeded (and they might not succeed!). So instead of using f = myvec[i], use if (myvec.tryGet(i, &f)) {...} and implement the class accordingly.
2. Do not provide a count method. Users must use iterators to traverse the vector.

Note: Be careful with iteration. You must be clever about maintaining a never-shrinking vector with bounds-checking iterators or you might have code that has buffer-overflow type errors.

The lame and easy way to provide a "thread-safe" vector is to just take a standard vector and lock the vector on every method. But if you do this, you could still end up with broken code (e.g. a loop that iterates from 0 to vec.count may have count change while it is iterating).

A 2nd means of providing "thread-safe" containers is to create immutable containers (every method returns a new container. This was definitely discussed by Eric Lippert. It's C#, but easily translates to C++ code, mostly. You'll still need to lock the container when you use it, but all the scary issues involving buffer overflows when iterators break and whatnot go away. Implementing an immutable container is probably relatively 2nd nature to those who are experienced with functional programming.

Spoon

The bit about locking a collection wasn't me. You might be thinking of my article about how we rejiggered how the lock statement is codegen'd in C# 4. – Warrin

The whole "immutable containers" thing sounds like it could be hugely inefficient given a large enough vector.size() logical-or sizeof(vector::value_type) – Upandcoming

Answer 6

If you haven't already, consider using concurrent_vector from the tbb library. C++ STL vectors are not thread safe so if you plan on modifying vector resource from multiple threads, the easiest solution i found is to use concurrent_vector.

Latimer