0

Suppose I have a std::map which is written by many threads concurrently. Looks like there is no lock-free map in C++ or boost yet.

I'm thinking of adding a boost::lockfree::queue before my map. One thread will be reading this queue and write to map, those threads that were writing to map now write to the queue:

[std::map] <- (lockfree::queue) <= threads

It seems the whole structure is lock free now, but it requires at least one condition variable and one mutex, so that when queue is not empty, the thread get notified and get data from queue.

Does it have better performance than simply using a std::lock_guard when writing to map?

Community
  • 1
  • 1
Deqing
  • 14,098
  • 15
  • 84
  • 131
  • 5
    it will depend on your use case. you need to measure and find out. if you don't need ordering, then unordered_map will reduce the contention time. – Richard Hodges Aug 19 '16 at 14:28
  • @RichardHodges Data requires ordering. As Insert/Delete of std::map takes logN, so I guess maybe using condition variable is better. It's still at very beginning of design so no data for testing yet. – Deqing Aug 19 '16 at 14:33
  • If you're at the beginning I would suggest writing it the most simple and elegant way you can, with the smallest possible interface. When your users start complaining that your server is too slow, measure it then. You'll find that the problem will be somewhere else. Almost all multithreaded programs spend almost all their time converting string to numbers and vice-versa. The problem is never in the work queue. – Richard Hodges Aug 19 '16 at 14:36
  • 1
    In addition, you ought to know that every implementation I can think of has optimistic mutexes - i.e. a spinlock + mutex. You'll gain almost nothing by trying to outwit the implementor of your standard library/pthreads etc. unless you have thousands of concurrent writers.... in which case you need to redesign with fewer writers which write more data less often. – Richard Hodges Aug 19 '16 at 14:39
  • 1
    Other design option might be to use per-thread maps and periodically merge them into a single master map. Either stop all threads and merge or use a per-thread counter to merge one thread with master every 100,000 entries or so. If ordering is very important then some kind of generation counter or one of the very complicated distributed clock algorithms could be used. – Zan Lynx Aug 19 '16 at 16:09
  • Related: http://preshing.com/20111118/locks-arent-slow-lock-contention-is/ – Peter Cordes Aug 19 '16 at 16:38
  • I assume someone eventually reads from the map? (Otherwise it is pretty useless.) How is reading safe? Is the single thread that updates the map from the queue the only one that reads from the map? – tony Aug 29 '16 at 20:11

0 Answers0