Is it possible to implement lock free map in C++

Question

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.

Andesine

@WhozCraig In all fairness, this specifically says C++ and that specifically says C... They are very different languages, especially when you consider atomic variables. – Radio

@AlexChamberlain an excellent point, sir. I'll yank the link. – Grommet

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. – Hemimorphite

What is the ratio of readers to writers? – Blare

@brianbeuning I edited the post, please see the EDIT part. – Andesine

@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. – Blare

Answer 1

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.

Bashaw

Note that hazard pointers are patented, so you might not be able to use this in production code. Isn't IPR wonderful? – Hamster

Thanks. I have edited the post to add more information, do you have more suggestion? – Andesine

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. – Bashaw

Answer 2

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.

Enallage

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. – Robrobaina

Answer 3

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

Hearn

Answer 4

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++,

Sorption

Answer 5

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

Excessive

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. – Sorption

Answer 6

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).

Ashe