Hacker News Reader

Comment by abacate | Hacker News Reader

You can easily write a concurrent hash table in C++ or Rust. I fail to understand your point.

How? I honestly don't know how to do it in C++ or Rust, without using exotic techniques like hazard pointers.

This seems to be an implementation built on RCU, iiuc: https://github.com/urcu/userspace-rcu/blob/master/src/rculfh...

This looks rough: it spawns background "worker threads" for tasks like lazy resizing; and even with that it still sometimes takes locks (see resize_mutex).

An atomic reference count seems sufficient, but I could be wrong.

It is actually quite tricky to lock-free swap a concurrently-accessed reference counted pointer. The reference count is not associated with the pointer, but with the pointee, so a 2CAS is not enough.

Typically you need hazard pointers or similar deferred reclamation tricks.

https://docs.rs/arc-swap/latest/arc_swap/ Is a basic rcu mechanism that doesn’t have the exotic requirements of urcu (but probably not as efficient). If you make the interior nodes of your data structure Arc (assuming they are large or expensive enough to warrant it), then updating is relatively fast. Of course you also want to be careful here to batch as many changes at once if you’re doing this at all frequently.

But ultimately I don’t recall anything special about the runtime semantics the first time I came across this technique which if I recall correctly came from the brilliant folk at Azul Systems for their JVM. You just need a way to atomically adjust certain nodes. And if I recall correctly Azul’s supported N concurrent writers that were all wait free (ie every thread participated in forward progress)

To be fair, RCU is about as exotic as hazard pointers. Then again, there is plenty of documentation for both and once you are familiar with them they lose a lot of their mystique.

You’re thinking of the kernel and urcu implementations. The RCU implementation that I linked here isn’t exotic at all. It creates a duplicate structure and atomically swaps pointers. If the swap fails because another update occurred, it tries creating a new duplicate structure running your RCU closure and swapping again. Forward progress is eventually made although it scales poorly if you have a lot of concurrent updaters.

So not quite as performant but in terms of having a writer and lots of concurrent readers, it achieves that requirement. And it’s data structure agnostic and you only need to pay this cost if you really have concurrency.

Well, my point is that hazard pointers are not really that exotic either :D.

If you search for "concurrent hash table <language>" or "concurrent map <language>" (being <language> Rust or C++) you get a number of open source libraries written using different techniques. I consider "exotic" a matter of opinion.

Reply on news.ycombinator.com