6

Which STL container has a thread safe insertion process? I want several threads to simultaneously insert in the same container. Any implementation other than STL (i.e., Boost) is welcome!

Tarek
  • 1,060
  • 4
  • 17
  • 38
  • What sort of container are you looking for? What platform requirements? Which C++ version? 98 or 11? – David Heffernan Oct 29 '11 at 16:05
  • 1
    The OP specified this is about linux but since it will likely come up for people like me searching "C++11 thread-safe container", this answer about a Visual-C++ extension may be useful: http://stackoverflow.com/a/7817526/197229 – Mr. Boy Oct 23 '15 at 11:56

6 Answers6

6

The STL containers are not thread safe. You have to impose that yourself, should you so wish, with your own synchronisation.

David Heffernan
  • 601,492
  • 42
  • 1,072
  • 1,490
  • I am trying to avoid the critical region in multi-threading because it deteriorates the performance ! – Tarek Oct 29 '11 at 16:01
  • It doesn't matter what you are trying to do: the libraries still aren't thread safe unless your implementation says otherwise. – Max Lybbert Oct 29 '11 at 16:03
  • 4
    @Tarek even if the container itself is "thread safe", it doesn't magically give you synchronization across threads. For example even if an internal "insert" doesn't cause corruption across threads, if another thread has an open iterator it could become invalid without any way of predicting it. You need to implement your own locks. – tenfour Oct 29 '11 at 16:10
  • 2
    @Tarek: And how would you expect synchronization to be achieved in the container without a lock? There are lock-less data structures, but those are not usually common, and you would have to find one such library and adapt your algorithms to what they offer. – David Rodríguez - dribeas Oct 29 '11 at 16:31
  • @DavidRodríguez-dribeas Well most other modern languages do offer some of those advanced data structures and using a lock less implementation can indeed offer quite large performance improvements. E.g. Java's concurrenthashmap gave me quite some performance boost when compared to the naive "use a global lock before accessing the standard hashmap" solution. – Voo Oct 29 '11 at 16:51
  • 2
    @Voo There is a huge difference between a language of *value* semantics and a language of *reference* semantics, in particular unless all your contained elements offer only atomic operations, you cannot provide a lockless container to hold them, as no matter how good the container operations are, insertion in a *value* language implies *copying* the value, as does *reading* the value, which cannot be performed in a *lock-less* way if the value can be *removed*. That is exactly why I mentioned that you need to *adapt the algorigthm* (program). – David Rodríguez - dribeas Oct 29 '11 at 20:37
6

I am trying to avoid the critical region in multi-threading because it deteriorates the performance !

On the contrary, it improves performance. Because the kind of locking a container class can do is only the very fine-grained kind, having to acquire the lock for each simple operation. That's expensive. When you take care of locking, you have the luxury of acquiring the lock and perform many operations. That does not improve the odds for concurrency but greatly reduces the locking overhead. You can choose the strategy that makes most sense for your app, it isn't forced on you.

Add to this that it is next to impossible to write a thread-safe container implementation that isn't either prone to deadlock or very expensive. Iterators are the problem. The library writer has to choose between taking a lock for the life time of the iterator (risking deadlock) or needs to update all live iterators when another thread changes the collection (expensive). Only the expensive choice is safe. Again, you choose the strategy that makes most sense, the expensive choice is not forced on you.

Hans Passant
  • 922,412
  • 146
  • 1,693
  • 2,536
3

The Standard does not require any STL containers to be thread safe. An implementation could be thread safe, although I'm not sure how they could pull it off with the current API; and changing the API would make them no longer compatible with the Standard.

If the LGPL is acceptable, Intel TBB has thread safe containers (these containers use locks internally, which does affect their performance).

Max Lybbert
  • 19,717
  • 4
  • 46
  • 69
  • Can I install and use TBB on a computer where I am not administrator? – Tarek Oct 29 '11 at 16:08
  • 1
    TBB is a regular library. You should be able to build and link to the library even if you aren't administrator, but you'll have to put the library in the same folder as your application and you won't be able to easily share the library between multiple programs. – Max Lybbert Oct 29 '11 at 16:50
2

Take a look at Boost.Lockfree (http://www.boost.org/doc/libs/1_53_0/doc/html/lockfree.html). It provides threadsafe implementations of:

boost::lockfree::queue
  a lock-free multi-produced/multi-consumer queue
boost::lockfree::stack
  a lock-free multi-produced/multi-consumer stack
boost::lockfree::spsc_queue
  a wait-free single-producer/single-consumer queue (commonly known as ringbuffer)
James Moore
  • 8,636
  • 5
  • 71
  • 90
1

Containers follow KISS principle (Keep It Simple) and therefore do not have synchronization features. Most of the time this hypothetical embedded synchronization is not enough because most of the time access to some other objects must be synchronized with the access to the container. Combine your container with one lock, and that's it really.

Dialecticus
  • 16,400
  • 7
  • 43
  • 103
1

Since you said any other (non-STL) implementation is welcome, I suggest Intel's Thread Building Blocks. They have thread safe concurrent containers that have really good performance characteristics.

Chad
  • 18,706
  • 4
  • 46
  • 63