Hacker News Reader

Comment by ridiculous_fish | Hacker News Reader

A fascinating design decision of Hashtable in .NET is its support for multiple readers AND a single writer.

In C++ or Rust, we get multiple readers OR a single writer. Shared ref or exclusive mut, pick one. But in .NET we have AND not OR: one writer AND multiple readers, all concurrent.

This works because .NET's GC can tolerate the race. A writer may trigger a table rehash, and a reader will read either the old or new table. If the reader loads the old table, it won't be deallocated until it's done: the GC will keep it alive.

Any cool uses of this one writer AND multiple readers?

https://learn.microsoft.com/en-us/dotnet/api/system.collecti...

View on HN

I'm surprised nobody mentioned the Rust crate left_right[1].

It's also a map that supports multiple readers AND a writer.

It does this by maintaining two maps, one used by the writer and one used by the readers and atomically swap the two when useful, the cool part is that reads are wait-free but the cost is at least double memory usage and slow writes (twice the work).

[1]: https://docs.rs/left-right/latest/left_right/

Nice! As far as I understand, it uses RCU-like epochs, except that the reclaimed memory is immediately used for the new version of the data, bounding the memory usage at the cost of having the writer block. The oplog seems quite an additional complication, but I guess it makes sense for costly updates. The simplest solution is to just copy the last version over the stale version.

edit: note this is not just a map datastructure. As far as I understand, left_right can wrap any data structure.

Reminds me of the shadow paging used in LMDB, which is effectively the same but at the page level rather than the whole tree and allows each reader their own context to read from, rather than a shared reader context.

The author of left_right has a really great YouTube channel on Rust programming: https://youtube.com/@jonhoo

How about many readers and zero writers? :)

For my text editor, I went with an immutable balanced tree. I was surprised by how easily I was about to implement all operations I needed with reasonable runtime complexity (log N mostly, operations like "give me a copy with element at position i removed"): https://github.com/alefore/edge/blob/master/src/language/con...

I use this throughout my editor. For example, I load a file into a sequence of lines represented here: https://github.com/alefore/edge/blob/8fdf7f76ffa167497a7e9e9...

I found that the good performance, relatively straightforward implementation and very strong thread safety (making the data immutable means a whole class of problems just disappears) works very well.

.NET Hashtable is roughly the same lousy bucketed hash table from C++ std::unordered_map. So, the hash table trick gets you to one of N linked lists (the buckets), and then you walk that linked list you found to see if a matching element is in the list.

Writing sometimes needs to "re-bucket" everything and during that process it's mayhem if you were stupid enough to be simultaneously looking something up (but in .NET this will be prevented†) but before and afterwards even write operations "just" add or remove elements to linked lists, which you're correct in a GC language it's not crucial to care that some reader may look at an element which you have meanwhile removed [in C++ that would be a use-after-free]

> Enumerating through a collection is intrinsically not a thread safe procedure. Even when a collection is synchronized, other threads can still modify the collection, which causes the enumerator to throw an exception. To guarantee thread safety during enumeration, you can either lock the collection during the entire enumeration or catch the exceptions resulting from changes made by other threads.

So, you know, congratulations you played silly games and you have won yourself a stupid prize.

This has basically the same "cool uses" as with an RwLock, AFAIU the readers aren't actually allowed to look at the hash table while it is being rehashed, they're silently held by the implementation.

You could do the "Reclaim data only once nobody is looking" in a non-GC language with any of the other concurrent reclamation techniques such as RCU or Hazard Pointers and in many cases you'd be fine with a reference counting approach (not always which is why these other techniques exist).

Edited To Add: † Huh. Maybe under GC they get away with doing all the work and then just pivoting to the new hashtable after rebucketing with a single writer? So then readers just get obsolete data for a while and it's the poor GC which has to cope with the mess.

Is it same for Dictionary? .People hardly use Hashtable these day

No, the documentation for Dictionary doesn’t make this guarantee, it’s explicit that readers are only allowed as long as the collection isn’t modified: https://learn.microsoft.com/en-us/dotnet/api/system.collecti...

Maybe that guarantee was too strong and prevented a more efficient implementation.

Rust has this as well but makes you explicitly state it using a wrapper type called refcell (internal vs external borrow checking, I think are the terms).

They're faster than mutexes, which themselves also internal borrow check, but also have the logic mechanic.

This allows you to make any type work similarly but eschew the overhead in cases where it's not needed.

No, RefCell relaxes the rules from requiring the borrowcheck rules be provably always followed at compile time to requiring the borrowcheck rules be actually followed in the codepaths actually run at runtime. You still can't have a mutation concurrently with a reader.

Sort of, refcell still enforces that shared and mutable borrows cannot coexist.

A similar case to what the parent describes is RCU or crossbeam's epoch-based reclaim.

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.

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.

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

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.

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://lib.rs/crates/dashmap

First time seeing dashmap, but a cursory inspection shows it works via sharded locks:

    pub struct DashMap<K, V, S = RandomState> {
        shift: usize,
        shards: Box<[RwLock<HashMap<K, V, S>>]>,
        hasher: S,
    }

so an array of RwLocks.

That's quite different than what .NET offers, which is multiple readers and a single writer with NO locks outside of the allocator/GC.

I'm not shilling for .NET (I've never written a .NET app) but it does have a really cool hash table.

> Shared ref or exclusive mut

There's std::shared_mutex, which allows multiple readers and a writer.

That's exactly the scenario your parent is describing. You can have (multiple) readers or a single writer. You cannot have both.

The analogous Rust type is std::sync::RwLock<T> (but as with Mutex, RwLock is a wrapper, so it is actually protecting something inside it, not just providing the raw mutex type).

If you've been using std::shared_mutex assuming you can have both then, I guess it's good luck that you didn't cause a deadlock of some sort, but at least this API unlike most C++ APIs isn't just "LOL, if you use this wrong it's Undefined Behaviour, all bets are off, goodbye" in the respect that matters to you.

Oh I see, sorry I misunderstood that. Yes indeed the readers won't be able read while the writer is writing.

Reply on news.ycombinator.com