3 ms·

> The big difference between a concurrent hash map and ArcSwap is that ArcSwap requires swapping out the entirety of the underlying data with every write but tr

> The big difference between a concurrent hash map and ArcSwap is that ArcSwap requires swapping out the entirety of the underlying data with every write but trades this off with very cheap reads. Writers don’t even have to wait for all readers to finish since a new epoch is created with the new version of data. This is where tree data structures win out. Git and subversion and pure functional languages don’t replace the entire data structure. They make a new element and attach it to the tree by creating a new version of the intended parent, and a new version of its parent, on up to the root element. So somewhere out there is space for a hybrid of ArcSwap and DashMap that uses sharded copy on write. These guys probably don’t need it given their low write rate, but shards should help with write contention for other use cases.

masklinn 1y ago
You still need something close to ArcSwap with your persistent data structure, because once you’ve built your new tree (possibly using transients) you need to overwrite the old root with the new, atomically (and probably in a CAS loop really). Left-right is an option which iirc avoids the CAS loop, as it’s a single writer primitive.
cmrdporcupine 1y ago
im::HashMap is a great tool I would love, though, to have a similar persistent structure where the node pointers at each level were thread shareded, instead of using e.g. atomics. A mutation at a branch could record that the mutation is "just" for thread ID X that did the mutation. At some later point a "commit" could reconcile the storage to global, maybe
cryptonector 1y ago
You could easily organize the hashmap hierarchically, yes.
deepsun 1y ago
So the root element single point of congestion for all writes, right?
- hinkley 1y ago
  With a filesystem based trees that’s often sufficient to help reduce the amount of write contention. Because you’re not serializing the whole goddamned thing back to disk, just the parts that changed, which are logarithmic to the size of the edit history. And git uses GC to deal with writes that get to the end and then fail due to concurrent access collisions. For in-memory problems, there are B-trees, which are an older solution to many problems than most of HN’s userbase, including myself. Then you still have the sharding which I did in fact point out would be part of a better hybrid solution.

masklinn 1y ago

You still need something close to ArcSwap with your persistent data structure, because once you’ve built your new tree (possibly using transients) you need to overwrite the old root with the new, atomically (and probably in a CAS loop really). Left-right is an option which iirc avoids the CAS loop, as it’s a single writer primitive.

cmrdporcupine 1y ago

im::HashMap is a great tool I would love, though, to have a similar persistent structure where the node pointers at each level were thread shareded, instead of using e.g. atomics. A mutation at a branch could record that the mutation is "just" for thread ID X that did the mutation. At some later point a "commit" could reconcile the storage to global, maybe

cryptonector 1y ago

You could easily organize the hashmap hierarchically, yes.

deepsun 1y ago

So the root element single point of congestion for all writes, right?

hinkley 1y ago
With a filesystem based trees that’s often sufficient to help reduce the amount of write contention. Because you’re not serializing the whole goddamned thing back to disk, just the parts that changed, which are logarithmic to the size of the edit history. And git uses GC to deal with writes that get to the end and then fail due to concurrent access collisions. For in-memory problems, there are B-trees, which are an older solution to many problems than most of HN’s userbase, including myself. Then you still have the sharding which I did in fact point out would be part of a better hybrid solution.