4 ms·

A resizable concurrent map

108 points by alanfranzoni 11y ago

fenesiistvan 11y ago
Good to see this is alive. Old thread: https://news.ycombinator.com/item?id=11016350 https://news.ycombinator.com/item?id=11016350
ruggeri 11y ago
When this last came up I started looking into Split-Ordered Lists, which are fascinating. http://www.cs.tau.ac.il/~afek/SplitOrderListHashSS03.pdf http://www.cs.tau.ac.il/~afek/SplitOrderListHashSS03.pdf
- jemfinch 11y ago
  Fascinating perhaps, but slow. All that pointer-hopping is far more expensive than open addressed collision resolution.
ignoramous 11y ago
Dr. Cliff Click's Google talk on Lock-Free Hashtable is here: https://youtu.be/HJ-719EGIts 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/ http://blog.h2o.ai/2014/02/kv-store-memory-analytics/
- fenesiistvan 11y ago
  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.
chubot 11y ago
Related thread: https://news.ycombinator.com/item?id=8362040 https://news.ycombinator.com/item?id=8362040 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.

108 points by alanfranzoni 11y ago

Good to see this is alive. Old thread: https://news.ycombinator.com/item?id=11016350 https://news.ycombinator.com/item?id=11016350

ruggeri 11y ago

When this last came up I started looking into Split-Ordered Lists, which are fascinating. http://www.cs.tau.ac.il/~afek/SplitOrderListHashSS03.pdf http://www.cs.tau.ac.il/~afek/SplitOrderListHashSS03.pdf

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

ignoramous 11y ago

Dr. Cliff Click's Google talk on Lock-Free Hashtable is here: https://youtu.be/HJ-719EGIts 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/ http://blog.h2o.ai/2014/02/kv-store-memory-analytics/

fenesiistvan 11y ago
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.

chubot 11y ago

Related thread: https://news.ycombinator.com/item?id=8362040 https://news.ycombinator.com/item?id=8362040 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.