Efficient thread synchronization technique for std::map

Question

I am having std::map< StudentName, Marks > where StudentName is std::string and Marks is an integer.

Now, in my application, multiple threads are accessing this map to:

1. Find StudentName. If exist, increase its Marks.
2. Decrease Marks of StudentName.
3. Add StudentName to the map.
4. Delete StudentName from the map.

Question: What is the most efficient approach to do above operations on std::map in a multi-threaded environment?

Current Solution: The code that does all these operations on the map is put inside critical section. But this degrades performance.
(For example, If a thread is adding marks for a particular student, why do other threads who want to add marks for different students need to wait?)

This is what I think can be done:
I gathered info on multithreading on maps from other similar questions/answers on SO and here is what I think I need to do. Provided std::map are not thread safe, (i.e. no other thread should access map when it is being updated)

1. I want to put only last two (add/delete StudentName) activities exclusive (No other activity should be done in parallel while adding/deleting elements to/from map)
2. Do not allow multiple threads to access same element of map (So that multiple threads cannot try to increase/decrease marks of same student simultaneously)

But I am not sure how can I achieve this (what thread synchronization objects/technologies can be used) I am developing this application on Windows through VS2010

Any suggestions or alternative approaches here please?

Update: Thanks for everyone's input. Unfortunately no atomic ints available in VS2010. So, here is what I plan to do based on your inputs. I'll have three kind of locks: On map: map_read_lock, map_write_lock On elements: element_write_lock (For each element)

Now,

When finding element in map: Get map_read_lock (This will allow me concurrent finds)

When adding/deleting elements to map: Get map_write_lock (This will prevent concurrent updates of the container, which I believe, is not recommended)

When changing values: Get (map_read_lock & element_write_lock) (This will allow parallel changes to different values, but will prevent concurrent change to the same value. Also, will prevent changes to values when container is being updated and vice versa)

Answer 1

And what happens when one thread is increasing the marks of student A, and another thread deletes student A? You need a lock on the map even when just modifying the marks. Or you need more complex transaction management (which probably isn't justified for such a simple case).

Alternatively, you can use a rwlock on the map, and an exclusive lock on each element in the map. To modify the marks, you take a read lock on the map, and an exclusive lock on the element; to add or delete a studen, you take a write lock on the map. But this requires significant extra resources.

Answer 2

• First question: how efficient should grading students be?
• Second question: is multithreading really needed? If it is for efficiency, maybe it isn't even helping.

After that, you can consider Reader/Writer lock, where Reader locks aren't exclusive. But watch out, because the actual grading is writing, so you probably need another lock per student to avoid contention.

Answer 3

1. I want to put only last two (add/delete StudentName) activities exclusive (No other activity should be done in parallel while adding/deleting elements to/from map)

For this, you need a reader/writer lock on the map.

• adding/deleting requires exclusive access (writer)
• accessing a student requires (only) shared access (reader)

1. Do not allow multiple threads to access same element of map (So that multiple threads cannot try to increase/decrease marks of same student simultaneously)

This is, also, relatively simple: each element of the map should have its own lock. This way, when accessing the elements without modifying the map structure you can just:

• lock the map in shared access
• lock the individual element (ie, each element needs its own lock)

and thus access multiple individual elements in parallel.

In your particular case of a Mark, you may also look into std::atomic. No need to go using locks when a simple atomic can do what you want :)