Saturday, August 30, 2014

A Lock-Free Hash Table by Cliff Click

Some years ago, Cliff Click came up with a resizable lock-free HashMap, which is a pretty cool feat.
The source code can be seen on github

The algorithm is not trivial at all with many interesting subtleties, like the key and the value being in adjacent entries in the array to reduce cache-misses, or the entry on the array for each key being "immutable" once assigned.

You can check out his presentation at Google
https://www.youtube.com/watch?v=HJ-719EGIts



There is another version of the same presentation given at Stanford just a few days before
https://www.youtube.com/watch?v=WYXgtXWejRM



Unlike what it is mentioned in some places, this data structure is not wait-free, at least not for the put() or get() methods, but it is lock-free for both.
Notice that in his presentation he mentions that he uses CAS without fences to write the key and value, which I think would not be correct, but anyways, the code on github is using the version that does not allow reordering, so that version of the code is correct (as far as I could tell)... and yes, it is correct to do the loads of the key and value in the get_impl() method without any fence or volatile semantics!
Again, nothing we didn't already know, but there are some very smart details in this data structure, so very worth the time to go through it.


Saturday, August 23, 2014

Lock-Free Programming in C++1x by Tony Van Eerd

Here is a nice talk about lock-free programming in C++ by Tony Van Eerd at Boostcon
https://www.youtube.com/watch?v=O4Jdq4PtfPA



He gives some nice examples with std::atomic<>, talks about the ABA problem, etc.

He's going to give another talk soon at CppCon2014, so I'm really looking forward to it.


There is also some guy that's going to talk about wait-free data structures at CppCon2014 which I'm really looking forward to  ;)


Saturday, August 16, 2014

Cliff Click on In-Memory Processing

Here is a nice interview Cliff Click about in-Memory Processing, H2O framework, low-latency java, and GCs:

http://www.infoq.com/interviews/click-0xdata
http://www.infoq.com/interviews/click-0xdata

this is a bit "off-topic" because it is about parallelism and not concurrency, but this guy is worth listening to, so I'll open an exception!