2

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)

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
Atul
  • 3,778
  • 5
  • 47
  • 87
  • Use mutex, i.e. boost::mutex and scope_lock. And the most important lock only when you must and just for a little time. For example when you insert element into the map and when you get the value. That's all. By the way, think about using hashmap i.e. std::unordered_map - it's more effective in some cases. – LukeCodeBaker Aug 30 '13 at 10:40
  • `Provided STL map are not thread safe, (i.e. no other thread should access map when it is being updated)` Not quite, I've already answered similar question here http://stackoverflow.com/questions/16130494/are-stdmap-and-stdvector-thread-safe/16130513#16130513 if you don't modify map itself it is ok to access it's elements for both read and write, provided that there is no race conditions for a given element. – alexrider Aug 30 '13 at 11:04
  • @LukeCodeBaker He needs synchronization all of his operations in some way. – James Kanze Aug 30 '13 at 13:55
  • and how you've implemented your map_read_lock, map_write_lock.. with C++? several std::mutex? – Johy Mar 06 '21 at 17:46
  • 1
    @Johy I used [libuv's](http://libuv.org/) [thread sync functions](http://docs.libuv.org/en/v1.x/guide/threads.html). For read lock [uv_rwlock_rdlock and for write uv_rwlock_wrlock](http://docs.libuv.org/en/v1.x/threading.html) Internally they have used relevant OS's locking functions and not std, But I don't remember exactly. Pretty old memories :) But you may refer their documentation. Thanks for asking. – Atul Mar 07 '21 at 15:38

3 Answers3

3

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.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • If the students are reference counted and "delete" is just "remove from map" (depending on the reference count to actually free the data) then do you still need to lock the map when modifying marks? – Wandering Logic Aug 30 '13 at 11:52
  • @WanderingLogic How can the students be reference counted? They exist _in_ the map. – James Kanze Aug 30 '13 at 12:02
  • We're about to add a mutex to each object of type `Marks`. So I was assuming that we could make `Marks` a smart ptr to a struct at the same time. (Or alternatively I guess since Marks is currently just an integer we could make it a `std::atomic_int` and then just use the `rwlock` on the map.) – Wandering Logic Aug 30 '13 at 12:23
  • There's certainly no reason to use dynamic allocation anywhere here, and thus no smart pointers. The idea of using `std::atomic_int` is a good one, however; whatever its overhead, it would be significantly less than using a mutex per entry. – James Kanze Aug 30 '13 at 13:48
  • So, "Keeping Marks of type std::atomic_int and having rwlock on the map" would be best solution? Also, do we have inbuilt rwlock functions in STL or you referring to use boost etc? – Atul Aug 30 '13 at 18:32
  • Well, bad news is atomic_int are not available in Visual Studio 2010 :( – Atul Aug 30 '13 at 19:08
  • @Andrew I was speaking in general. On Windows, you may have to end up implemented the `rwlock` yourself, based on a conditional, or whatever Windows has which is similar. Or maybe Boost has something along those lines. – James Kanze Aug 30 '13 at 23:46
0
  • 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.

stefaanv
  • 14,072
  • 2
  • 31
  • 53
  • Number of students would be really high (20k or more) and inputs to decide increase/decrease marks, are from different sources. Hence, multithreading. – Atul Aug 30 '13 at 18:37
0
  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 :)

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
  • std::atomic would help in increment/decrements of marks. But what if another thread deletes map element? Guess we still need locks? Plz correct me if wrong. – Atul Aug 30 '13 at 18:34
  • @Andrew: that is why the reader/writer lock on the map itself is. To increment/decrement you take the lock (read-mode) and thus precludes any add/delete operation on the map itself for the duration. – Matthieu M. Aug 31 '13 at 10:55
  • and what will be the best implementation for "each element needs its own lock" in modern C++? several std::mutex or shared_mutex? – Johy Mar 07 '21 at 10:47
  • @Johy: Given how basic the application is, one `std::mutex` per element would be amply sufficient... though given how old C++11 is, I'd really encourage one to use `std::atomic` for the marks it'll be much more lightweight. – Matthieu M. Mar 07 '21 at 11:55
  • @MatthieuM. but if I don't know in advance how many elements there will be in container, how can I use atomic, as I can't make a container of them – Johy Mar 07 '21 at 15:47
  • @Johy: You seem to be very confused. I invite you to try creating a `std::map`: _it just works_. – Matthieu M. Mar 07 '21 at 15:50
  • @MatthieuM. hm,I will try. Though I was trying to create std::vector and it wasn't working – Johy Mar 07 '21 at 16:11
  • @Johy: Ah! Here be dragons! Despite the name similarity `std::atomic_flag` is a completely different beast. It has special wait/notify operations which require its address to be stable in memory, and has a result its copy & move constructors & assignment operators are deleted -- hence it will not work in a `std::vector` (the vector cannot grow), though it would work in a `std::map`. The regular `std::atomic` and `std::atomic_int_t` will not suffer from this problem. – Matthieu M. Mar 07 '21 at 17:04