A resizable concurrent map

preshing.com

108 points·alanfranzoni··6 comments

Dr. Cliff Click's Google talk on Lock-Free Hashtable is here: https://youtu.be/HJ-719EGIts

Acc to Dr. Click, if you do not have 30+ CPUs in a single machine, ConcurrentHashMap (built-in to the JDK) will do the trick more often than not. The talk is really worth it, if you're curious about the design, esp.

Dr. Click also had memorable debate with Rich Hickey over STMs. He works at h2o.ai and wrote about building a Key-Value store two years ago: http://blog.h2o.ai/2014/02/kv-store-memory-analytics/

Ok, but this is more about practice then theory. Theory we already have a lot, however for C++ i can't find any usable thread safe map except the intel tbb which i was unable to compile last time in my specific environment (seems to play nice only with visual c++ on windows). This one looks more compact.

When this last came up I started looking into Split-Ordered Lists, which are fascinating.

http://www.cs.tau.ac.il/~afek/SplitOrderListHashSS03.pdf

Fascinating perhaps, but slow. All that pointer-hopping is far more expensive than open addressed collision resolution.

The difference appears to be that you can resize concurrently with lookups. From reading this article it seems they are not that happy with this aspect of the implementation:

Right now, if a get call encounters a Redirect, it helps complete the migration. Perhaps it would be better for scalability if it immediately read from the new table instead. That’s something worth investigating.

Good to see this is alive.

Old thread: https://news.ycombinator.com/item?id=11016350

Reply on news.ycombinator.com