STL::Map in multithreaded application

[Shvalb]

Hi.

My program has 2 threads, one thread always insert object to the map, and the 2nd thread always removes or extracts those object from the map.

It's important to say that there can't be a situation where the 2 threads are trying to access the map with the same key at the same moment.

And my question is: Is this scenario is thread safe or I need to use CRITICAL SECTION to lock all activities on map??

Thanks.

Oren.

[Arjay]

STL collections aren't threadsafe, but it's pretty simple to add thread safety to one.

It helps if you use a RAII based synchronization library. Many of us have our own implementation. I know JVene has spoke of his. Mine is available in the articles listed in my subject line. My implementation has wrappers for critical sections, mutexes, and a Single Writer/Multiple Reader lock.

Here is what is required to add synchronization to a stl map with my implementation.

Add thread safety to the stl map

#include "Autolock.h"
class CThreadSafeMap : public std::map< K, V>, public CLockableCS
{
};


Lock the map before accessing it (assumes m_ThreadSafeMap has been declared and is shared across threads).

{
CAutoLockT< CThreadSafeMap > lock(&m_ThreadSafeMap);

//
// Access the map here
//
}

[exterminator]

The scenario is not thread safe. A map is a node-based container - a tree in the most basic sense. The tree node will have nearby node pointers. Suppose the two threads are accessing two nodes which manage the state of the previous and next (or parent/child) pointers. In that case, lets say you are doing a key based insert from first thread that can pop in between those two nodes (due to the internal key based sorting/re-ordering of the map). And from the second thread is try to remove one of those nodes. Both acquire locks to keep their operation isolated from other threads intervention. If there is no locking, there can be a completely messed up tree structure with the inserted node pointing to the node that got removed or the next of the removed node pointing to the older node before the inserted one (considering the pointer adjustments happened in a random fashion wherein the node being removed adjusts the next pointer of the existing node to the next to itself and previous of the next node to the newly inserted one - all the steps of insert/remove can happen in a random order - i.e. they are not atomic operations). The will mess up the whole data structure.

You would definitely need to have locking mechanism while sharing the map across the threads. Basically, a thread safe wrapper to the map. All modifiers would need to be redefined and would need to be synchronized to not change the map/elements via any such interface in 2 or more parallel execution paths.

I guess you can have a more granular locking mechanism that controls all the modifiers of the map upto the node level but I am not really sure if that is possible or how to go about it. You might need to write the map from scratch with synchronized node access. Put locks on nodes and their immediate dependents. Might not be worth the pain as I am not sure if it will surely give you some performance improvements. But if the insert and remove and changes are very frequent, it might.

[Arjay]

I guess you can have a more granular locking mechanism that controls all the modifiers of the map upto the node level but I am not really sure if that is possible or how to go about it. You might need to write the map from scratch with synchronized node access. Put locks on nodes and their immediate dependents. Might not be worth the pain as I am not sure if it will surely give you some performance improvements. But if the insert and remove and changes are very frequent, it might.You can get a more granular locking mechanism, by having the V of the map store pointers to the object (rather than the actual object) and each object would also contain a lock.

The map gets locked for inserts/deletes and the object would get locked for changes to the object (without locking the map). Of course for deletes, the [pointer to the object] would be removed from the map, but you would need to lock the individual object before calling delete on it.

[Up on RAII soapbox] Using a RAII type locking mechanism, this type of functionality is fairly easy to implement as the coder just needs worry about locking the object because the unlocks are a performed with the stack unwind.

[exterminator]

The map gets locked for inserts/deletes and the object would get locked for changes to the object (without locking the map). Of course for deletes, the [pointer to the object] would be removed from the map, but you would need to lock the individual object before calling delete on it.That is a better idea. Because holding locks on individual items while doing operations that affect the map as a whole (for example, insert/delete) will causes huge problems (with pointer adjustment requirements as I thought about in the last post). It might even cause deadlocks when two items (parent-child) get locks individually for 2 concurrent removes. Or cause corrupt data structure. For node data changes, holding off a single element locked should do as it doesn't need pointer adjustments in the map nodes.

[NMTop40]

This was asked elsewhere and I posted a solution.

I do not like Arjay's solution because you are not supposed to derive from std::map and in any case you are expecting your users to lock before accessing rather than doing the locking in your extended class.

[exterminator]

This was asked elsewhere and I posted a solution.Problem related to STL containers thread-safety or granularity of locking? Could you please post a link, NMTop40?I do not like Arjay's solution because you are not supposed to derive from std::map and in any case you are expecting your users to lock before accessing rather than doing the locking in your extended class.Inheritance can be easily turned into private and a bunch of using directives. But why do you think that encapsulating the locking inside a specialized map type container is a not a first choice? Would it not help isolate the synchronization code at one place? Are there any drawbacks?

[Arjay]

Rather than using multiple inheritance as I've shown, you can certainly create a std::map class wrapper which holds a CLockableCS member and wraps all map operations. Sometimes I do it this way and sometimes I use MI.

When I use the MI approach, the resultant derived class (e.g. CThreadSafeMap) is never used as a base class - it's only ever used as a member within another class. I suspect the issues that folks run into deriving from std collections are a result having the std collection as the base of some long inheritance chain, but I don't use it that way - the end of the chain in my usage is at the derived class (CThreadSafeMap).

As far as expecting the users to lock as NMTop40 mentioned, generally I use the derived thread safe map within another class that only exposes a limited set of threadsafe operations (as opposed to every feature the original stl container has available).

[NMTop40]

My solution is here:

http://www.codeguru.com/forum/showthread.php?t=429088&highlight=STL%3A%3AMap

but it is not a full solution as you have to write the Mutex class. I have implemented one for Windows though unlike Arjay's it is not a template.

I do have a thread-safe producer-consumer queue implementation too but I have only implemented that for POSIX so far.

[NMTop40]

Rather than using multiple inheritance as I've shown, you can certainly create a std::map class wrapper which holds a CLockableCS member and wraps all map operations. Sometimes I do it this way and sometimes I use MI.

When I use the MI approach, the resultant derived class (e.g. CThreadSafeMap) is never used as a base class - it's only ever used as a member within another class. I suspect the issues that folks run into deriving from std collections are a result having the std collection as the base of some long inheritance chain, but I don't use it that way - the end of the chain in my usage is at the derived class (CThreadSafeMap).

As far as expecting the users to lock as NMTop40 mentioned, generally I use the derived thread safe map within another class that only exposes a limited set of threadsafe operations (as opposed to every feature the original stl container has available).

std::map provides 5 basic operations, insert, overwrite, erase, lookup and iteration.

The first 4 are straightforward to implement in a thread-safe environment but iteration in some ways is application-based as to whether you want to lock the entire map while you iterate, whether you wish to take a snapshot, iterate through that and allow modifications to the map while you do, or whether you are going to somehow implement "smart" locking, i.e. you will allow modifications to nodes other than the specific one you have locked and then continue iterating "live" from your locked node onward. Doing the latter would probably require writing your own whole map implementation and is not simply a matter of wrapping the existing one.

As I have said before, I don't think that C++ is necessarily "complete" i.e. there is nothing left in collections that needs to be written.

[Arjay]

My task of writing the synchronization wrapper classes was made much easier because I never targetted cross-platform. My stuff is Windows only, which is great unless you need to run on non-Windows. :)

I have one templated locking class, CAutoLockT that locks/unlocks the lock objects. For the locking objects, I have a critical section lock, a mutex lock, and a Single Writer/Multiple Reader lock.

I find that using the RAII approach (which most of these sychronization wrappers seem to be patterned after), really frees the developer up to work on the design and not sweat the multithreading aspect of things.

The concept of thread safety is actually simple: in that a shared resource can't be accessed for at least one write from more than one thread at a time. (Btw, I'm not speaking directly to you guys, NMTop40 or Exterminator - I know you guys understand this).

What can be difficult is how to achieve this. If you forego any sort of wrapper classes (which utiliize RAII) and choose to explicitly lock and unlock for each resource access, life is going to be difficult. One reason for this is because you need to always ensure you unlock - even under error conditions and this may be difficult depending on the structure of your code. On the other hand, with RAII this becomes much easier.

NMTop40, you are correct with regard to the enumeration case in that even if you make a class safe wrapper, you'll still need to lock/unlock outside the class during the enumeration operations. As far as I know, there aren't any ways around this.