23

We are developing a network application based C/S, we find there are too many locks adding to std::map that the performance of server became poor.

I wonder if it is possible to implement a lock-free map, if yes, how? Is there any open source code there?

EDIT: Actually we use the std::map to store sockets information, we did encapsulation based on the socket file description to include some other necessary information such as ip address, port, socket type, tcp or udp, etc.

To summary, we have a global map say it's

map<int fileDescriptor, socketInfor*> SocketsMap,

then every thread which is used to send data needs to access SocketsMap, and they have to add mutex before reading from SocketsMap or writing to SocketsMap, thus the concurrency level of the whole application would be greatly decreased because of so many locks addding to SocketsMap.

To avoid the concurrency level problem, we have two solutions: 1. store each socketInfor* separately 2. use some kind of lock-free map.

I would like to find some kind of lock-free map, because codes changes required by this solution are much less than that of solution 1.

Cœur
  • 37,241
  • 25
  • 195
  • 267
Wallace
  • 561
  • 2
  • 21
  • 54
  • @WhozCraig In all fairness, this specifically says C++ and that specifically says C... They are very different languages, especially when you consider atomic variables. – Alex Chamberlain Jan 15 '13 at 13:33
  • @AlexChamberlain an excellent point, sir. I'll yank the link. – WhozCraig Jan 15 '13 at 13:35
  • If you need an associative container, but don't require ordering, it might be simpler to use a hash like `std::unordered_map`. It might be faster even with your current coarse locking (especially if you can move any expensive hash computation outside the locked portion), but I suspect an occasional expensive re-hash is also simpler to handle than an occasional re-balance, for the optimistic lockfree version. – Useless Jan 15 '13 at 14:31
  • What is the ratio of readers to writers? – brian beuning Jan 15 '13 at 14:35
  • @brianbeuning I edited the post, please see the EDIT part. – Wallace Jan 16 '13 at 22:27
  • @StevePeng Have you looked at reader-writer locks? Code doing lookup use a reader lock. Code doing insert or delete use a writer lock. Multiple readers can access the data concurrently. RW locks are good if you have lots more readers than writers. – brian beuning Jan 17 '13 at 01:14

6 Answers6

22

Actually there's a way, although I haven't implemented it myself there's a paper on a lock free map using hazard pointers from eminent C++ expert Andrei Alexandrescu.

Ylisar
  • 4,293
  • 21
  • 27
  • 2
    Note that hazard pointers are patented, so you might not be able to use this in production code. Isn't IPR wonderful? – David Rodríguez - dribeas Jan 15 '13 at 15:26
  • Thanks. I have edited the post to add more information, do you have more suggestion? – Wallace Jan 16 '13 at 22:27
  • 1
    Going by the new information leads me to believe that you're off on an architectural level. If you're using one thread per client you'll never be able to make it scale well, check out proactor pattern for more details. If that's to much work perhaps an easy fix which might net you the extra juice would be to use multiple maps: ie `std::map< int, socketInfor* > info[10]; mutex mutexes[10]; ... mutexes[ fileDesc % 10 ].lock(); info[ fileDesc % 10 ][ fileDesc ]; ...`. In any case rolling a bug free lock free map on your own is likely to take _a lot_ of time to verify & debug. – Ylisar Jan 16 '13 at 23:14
9

Yes, I have implemented a Lock-Free Unordered Map (docs) in C++ using the "Split-Ordered Lists" concept. It's an auto-expanding container and supports millions of elements on a 64-bit CAS without ABA issues. Performance-wise, it's a beast (see page 5). It's been extensively tested with millions of random ops.

Qarterd
  • 280
  • 3
  • 5
  • 1
    This looks lovely. However, it relies on clang that appears to be broken since release 3.4 (I'm currently on 3.7). It fails to find a system include file. I don't have the bandwidth to research this further. – Nicole Feb 16 '16 at 20:54
2

HashMap would suit? Have a look at Intel Threading Building Blocks, they have an interesting concurrent map. I'm not sure it's lock-free, but hopefully you're interested in good multithreading performance, not particularly in lock-freeness. Also you can check CityHash lib

EDIT:

Actually TBB's hash map is not lock-free

Andriy Tylychko
  • 15,967
  • 6
  • 64
  • 112
2

I'm surprised nobody has mentioned it, but Click Cliff has implemented a wait-free hashmap in Java, which I believe could be ported to C++,

Adam Kurkiewicz
  • 1,526
  • 1
  • 15
  • 34
2

If you use C++11, you can have a look at AtomicHashMap of facebook/folly

Sam Kellett
  • 1,277
  • 12
  • 33
nkout
  • 491
  • 4
  • 11
  • This is probably not what OP wants. The map you're linking to is not entirely lock-free. From the docs: AHArray is a fixed size contiguous block of value_type cells. When writing a cell, the key is locked while the rest of the record is written. – Adam Kurkiewicz Apr 22 '15 at 10:43
1

You can implement the map using optimistic design or transactional memory.

This approach is especially effective if the chance of two operations concurrently addressing the map and one is changing the structure of it is relatively small - and you do not want the overhead of locking every time.

However, from time to time - collision will occur, and you will have to result it somehow (usually by rolling back to the last stable state and retrying the operations).

If your hardware support good enough atomic operations - this can be easily done with Compare And Swap (CAS) - where you change the reference alone (and whenever you change the map, you work on a copy of the map, and not the original, and set it as the primary only when you commit).

amit
  • 175,853
  • 27
  • 231
  • 333