8 ms·

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

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.collections.hashtable https://learn.microsoft.com/en-us/dotnet/api/system.collecti...

leosanchez 3y ago
Is it same for Dictionary? .People hardly use Hashtable these day
- codeflo 3y ago
  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.collections.generic.dictionary-2?view=net-7.0#thread-safety https://learn.microsoft.com/en-us/dotnet/api/system.collecti... Maybe that guarantee was too strong and prevented a more efficient implementation.
abacate 3y ago
You can easily write a concurrent hash table in C++ or Rust. I fail to understand your point.
- ridiculous_fish 3y ago
  How? I honestly don't know how to do it in C++ or Rust, without using exotic techniques like hazard pointers.
  - foota 3y ago
    This seems to be an implementation built on RCU, iiuc: https://github.com/urcu/userspace-rcu/blob/master/src/rculfhash.c https://github.com/urcu/userspace-rcu/blob/master/src/rculfh...
    - ridiculous_fish 3y ago
      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).
  - aidenn0 3y ago
    An atomic reference count seems sufficient, but I could be wrong.
    - gpderetta 3y ago
      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.
  - vlovich123 3y ago
    https://docs.rs/arc-swap/latest/arc_swap/ 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)
iknowstuff 3y ago
https://lib.rs/crates/dashmap https://lib.rs/crates/dashmap
- ridiculous_fish 3y ago
  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.
afc 3y ago
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/const_tree.h 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/8fdf7f76ffa167497a7e9e9228b26b1f2dcf95e9/src/language/text/line_sequence.h#L21 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.
adhesive_wombat 3y ago
> Shared ref or exclusive mut There's std::shared_mutex, which allows multiple readers and a writer.
- tialaramex 3y ago
  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.
  - adhesive_wombat 3y ago
    Oh I see, sorry I misunderstood that. Yes indeed the readers won't be able read while the writer is writing.
tialaramex 3y ago
.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.
ismailmaj 3y ago
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/ https://docs.rs/left-right/latest/left_right/
- clappski 3y ago
  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.
- gpderetta 3y ago
  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.
- legobmw99 3y ago
  The author of left_right has a really great YouTube channel on Rust programming: https://youtube.com/@jonhoo https://youtube.com/@jonhoo
junon 3y ago
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.
- bonzini 3y ago
  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.
- iudqnolq 3y ago
  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.
deleted 3y ago
[deleted]

leosanchez 3y ago

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

codeflo 3y ago
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.collections.generic.dictionary-2?view=net-7.0#thread-safety https://learn.microsoft.com/en-us/dotnet/api/system.collecti... Maybe that guarantee was too strong and prevented a more efficient implementation.

abacate 3y ago

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

ridiculous_fish 3y ago
How? I honestly don't know how to do it in C++ or Rust, without using exotic techniques like hazard pointers.
- foota 3y ago
  This seems to be an implementation built on RCU, iiuc: https://github.com/urcu/userspace-rcu/blob/master/src/rculfhash.c https://github.com/urcu/userspace-rcu/blob/master/src/rculfh...
  - ridiculous_fish 3y ago
    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).
- aidenn0 3y ago
  An atomic reference count seems sufficient, but I could be wrong.
  - gpderetta 3y ago
    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.
- vlovich123 3y ago
  https://docs.rs/arc-swap/latest/arc_swap/ 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)

iknowstuff 3y ago

https://lib.rs/crates/dashmap https://lib.rs/crates/dashmap

ridiculous_fish 3y ago
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.

afc 3y ago

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/const_tree.h 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/8fdf7f76ffa167497a7e9e9228b26b1f2dcf95e9/src/language/text/line_sequence.h#L21 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.

adhesive_wombat 3y ago

> Shared ref or exclusive mut There's std::shared_mutex, which allows multiple readers and a writer.

tialaramex 3y ago
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.
- adhesive_wombat 3y ago
  Oh I see, sorry I misunderstood that. Yes indeed the readers won't be able read while the writer is writing.

tialaramex 3y ago

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

ismailmaj 3y ago

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/ https://docs.rs/left-right/latest/left_right/

clappski 3y ago
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.
gpderetta 3y ago
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.
legobmw99 3y ago
The author of left_right has a really great YouTube channel on Rust programming: https://youtube.com/@jonhoo https://youtube.com/@jonhoo

junon 3y ago

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.

bonzini 3y ago
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.
iudqnolq 3y ago
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.

deleted 3y ago

[deleted]