?
Solved

Thread safe std map

Posted on 2009-12-23
18
Medium Priority
?
792 Views
Last Modified: 2012-06-27
Hi All,
I need help to use a global map for storing and reading strings. I basically need a thread safe accessor to the map in order to read and write to the map while not impact performace.

Thx

P.S. The platform is windows
0
Comment
Question by:bachra04
  • 7
  • 6
  • 3
  • +2
18 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 26113793
Well, if you want to use the STL map, you'll need to write some code around the map that makes all accesses thread safe. This could be as simple as a mutex for all accesses. Or as complex as a complete (thread safe) wrapper around the STL map.

The alternative of course is to use a different map implementation - one that is thread safe.
0
 
LVL 86

Expert Comment

by:jkr
ID: 26114788
You might find this one interesting: http://www.threadingbuildingblocks.org/ ("Intel® Threading Building Blocks"), especially the 'concurrent_hash_map' (http://cache-www.intel.com/cd/00/00/30/11/301132_301132.pdf#page=32)
0
 
LVL 86

Accepted Solution

by:
jkr earned 1400 total points
ID: 26114878
BTW, a simple encapsulation to sync' access to a map on Windows could be the following:
template<typename K, typename T,class P = std::less<K>, class A = std::allocator<T> >
class MapLock {

public:

   MapLock () { InitializeCriticalSection(&m_cs);}
   ~MapLock () { DeleteCriticalSection(&m_cs);}
   std::map<K,T,P,A>& get () { Lock(); return m_map;}
   void release() { Unlock();}

protected:

   void Lock() { EnterCriticalSection(&m_cs);}
   void Unlock() { LeaveCriticalSection(&m_cs);}

   CRITICAL_SECTION m_cs;
   std::map<K,T,P,A> m_map;
};

Open in new window

0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 600 total points
ID: 26121821
>> I basically need a thread safe accessor to the map in order to read and write to the map while not impact performace.

If you have many readers you don 't want to make reading synchronous by making each read mutually exclusive as this introduced a huge bottle neck. It is only when writing you need mutual exclusion. What you want are a multiple-reader/single-writer mutual exclusion semantics, where-upon many readers can all access the map at the same time but once you need to write to the map the writer obtains exclusive access.

The boost shared mutex provides these semantics in a since simple to use object model.

You create a shared mutex object like so...

boost::shared_mutex mtx;

You lock it for read access thus (this allows multiple reads to access)...

boost::shared_lock<boost::shared_mutex> sl(mtx);

You can upgrade that lock to a write lock thus (waits for readers to finish then upgrades to unique lock)...

boost::upgrade_lock<boost::shared_mutex> wl(sl);

You can obtain a unque lock directly on the mutex like so (waits for readers to finish then invokes a unique lock)...

boost::unique_lock<boost::shared_mutex> ul(mtx);

So, the idea is if you are only reading from the map you use a shared lock on the mutex, if your read becomes a write you upgrade the lock and if you just was to write then you use a unique lock. Using this pattern reads don't contend with each other and the access to the object only becomes exclusive if you upgrade a read lock or you use a unique lock.

More info can be found here: http://www.boost.org/doc/libs/1_41_0/doc/html/thread/synchronization.html

0
 
LVL 2

Author Comment

by:bachra04
ID: 26134123
I don't have a very high performance constraints. worst case I can have a few readers (no more than 5) two writers at the same time.
0
 
LVL 86

Expert Comment

by:jkr
ID: 26134136
Then you should be fine with the 'simple encapsulation'.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 26134206
>> I don't have a very high performance constraints. worst case I can have a few readers (no more than 5) two writers at the same time.
What is the ratio of reads to writes? If the number of reads is far greater than the number of writes you are creating an unnecessary bottle-neck (thread contention) if you use standard mutual exclusion semantics. Each reader will, unnecessarily, block all other readers. You are, effectively, negating the point (to some extent) of using threads.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 26138750
>>>> It is only when writing you need mutual exclusion.
That isn't true. Any iteration or find operation may fail - worse case crashing - when there are parallel updates to the map.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 26138819
>>>> Each reader will, unnecessarily, block all other readers.
You only can make that safe by using a second mutex. Writers must wait for both mutexes, readers only for the writer mutex.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 26139051
>> That isn't true. Any iteration or find operation may fail - worse case crashing - when there are parallel updates to the map.
If you are only reading there are no updates to the map -- did you not get that? With your examples, iteration and find are read-only actions (hence iterators and the find function may be const).
http://www.cplusplus.com/reference/stl/map/find/

If the map is only being read it doesn't need mutual exclusion semantics, it's only when a writer tries to modify it that these semantics are required. A read/write lock (implemented as a shared_mutex in Boost) will ensure these semantics are only enabled during the writing phase. During reading all threads are free to access the resource without contention.

>> You only can make that safe by using a second mutex. Writers must wait for both mutexes, readers only for the writer mutex
There are primitives already designed to implement a Read/Write Lock RWL design pattern. Both Posix threads and Boost provide solutions. Unfortunately, I suspect you are looking at this from a Win32 API only point of view, where no such primitives exist.

The RWL design pattern is a fundamental pattern for implementing efficient/effective multi-threaded solutions that implement high-ratio reads to low-ration writes. Without it you, effectively, make all access to your resource synchronous in the cases of both read and write. This is an unnecessary contention that can be avoided in the case of reading, when no writing is in progress.

Please take a look at the Wkikipedia entry for the RWL design pattern for more information.
http://en.wikipedia.org/wiki/Read/write_lock_pattern
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 26139153
>>> did you not get that?
No, sorry.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 26139189
>>>> iteration and find are read-only actions
Any parallel writing to the map may spoil any of the pointers currently used in a read operation.

BTW, I would like to discuss that without any personal touch. So expressions like 'don't you get that' are not very helpful, especially when made by a ZA.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 26139223
>> BTW, I would like to discuss that without any personal touch. So expressions like 'don't you get that' are not very helpful, especially when made by a ZA.
Well, I actually said, "did you not get that?" and I was merely enquiring as to whether you understood the point I was trying to make in the previous posts... if you hadn't then, clearly, I had done a poor job of explaining things previously.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 26139253
>> Any parallel writing to the map may spoil any of the pointers currently used in a read operation.
The point is, ANY writing to the map MUST be protected by a shared_mutex and locked for write activity (apply a unique lock or upgrade a read lock to a write lock). This will, then, block until all readers are done and then lock for exclusive write access.

It doesn't matter what design pattern you use to provide mutual exclusion, if you don't do it properly it will fail and lead to (most probably) a race condition situation.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 26139275
>>>> Unfortunately, I suspect you are looking at this from a Win32 API only point of view, where no such primitives exist.
We are in the C++ TA. Why do you think I would WINAPI use a base of view when discussing a C++ topic?

>>>> There are primitives already designed to implement a Read/Write Lock RWL design pattern. Both Posix threads and Boost provide solutions.
Interesting. Would you mind to elaborate more on that especially for Posix Threads? I worked a lot with pthreads and it is alway interesting to learn about 'design patterns' of a theme where you wouldn't expect one.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 26139372
>> Why do you think I would WINAPI use a base of view when discussing a C++ topic?
Just a hunch :) Apologies if I was wrong.

>> Would you mind to elaborate more on that especially for Posix Threads?
Well, I've already explained the semantics they provide. You can find out more by reading the OpenGroup documentation if you are interested. The following two links are for the read and write locks, you can following the links provided in there pages for information on the other related functions associated with them.
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_wrlock.html
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_rdlock.html

Links for Boost shared_mutex can be found in my previous posts, above.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 26140171
>>>> There are primitives already designed to implement a Read/Write Lock RWL design pattern.

Hmmm. The term 'design pattern' has a special meaning in C++. I don't think we should use it for primitive read/write locking mechanisms which might be even older than Posix Threads as I remember them well on VAX/VMS which was in the Eighties (and they were old even then).

But you are right. It is somewhat tricky to implement read/write locking mechanisms using mutexes from WINAPI. But the pthread library is available also for Windows. So that should be the way to go if performance is an issue here. You also should consider that locking cases when using threads are rare cases even if you were using many threads and don't do else but trying to get a lock. So if not writing a DBMS server I wouldn't put much efforts into preventing readers from mutual locking.

0
 
LVL 40

Expert Comment

by:evilrix
ID: 26144536
>> Hmmm. The term 'design pattern' has a special meaning in C++.
Apologies, my post here is a little off-topic, but I am curious as to what you mean by "The term 'design pattern' has a special meaning in C++".
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

850 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question