["RFC"] convenient, race-free mutability
- Dominant language
- Rust
- Stars
- 580
- Forks
- 50
- PR merge metrics
- No merged PRs in 30d
Description
# Abstract
As I see it we have no built in support for mutating data in a race-free way, this "RFC" will look into how we could implement this.
# The Problem
Say a user wants to mutate some data in the list. Currently they need to use some kind of lock around their data (`HashMap>` || `HashMap>`). The downside to this it that it incurs overhead, even if no concurrent accesses are made.
Now a "naive" solution would be this:
```rust
let mut item = map.get(...).clone();
// modify `item` ...
map.insert(..., item);
```
However this basically the definition of a [race condition](https://en.wikipedia.org/wiki/Race_condition), since while we modify `item` another thread could overwrite the data in the map thus making our `clone` of it stale.
# The "easy" solution:
The easiest way to implement this would be to expose a `compare_and_set` or `compare_and_swap` function. This would alow users to make sure, the data they got, mutated and that they are now planning to store is still what it was, when they first read it.
### pro
- relatively simple
### con
- still impractical to use
- users need to write loops for every modification, so that they can repeat it, if the store "failed".
- non 0 overhead for additional atomic `cas` operations.
# Proposed solution
I propose we add a variant to `BinEntry`:
`Mutating((std::sync::Condvar, Node))`
Which is basically the same as `BinEntry::Node` with an additional [Condvar](https://doc.rust-lang.org/std/sync/struct.Condvar.html), which is notified once the write has finished.
This would allow us to have a `get_mut` function which returns a `WriteGuard`(we'll have to use guards anyways, see #16).
This function finds the BinEntry for the key (if it exists), `clone`s it's contents and replaces it with a `BinEntry::Mutating`(containing the original `Node`). All immutable reads can (/will have to be able to) just read the node data, but `get_mut` can wait on the `Condvar` for the ongoing read to be done and only `clone` the node data again once it has finished.
The `WriteGuard` would have to:
- store the cloned `Node` / `V`, mutably (`deref` to it) and allow mutating it.
- write the modified value to the map on `drop`, which does the following:
- Make the `BinEntry::Mutating` a `BinEntry::Node` again.
- Call `notify_all` on the `Condvar`
### pro
- No additional atomics in the fast path and a single `Condvar` when writing concurrently to the same entry.
- Less CPU zycles, since we can block the thread while waiting for a write instead of repeatedly modifying the copy we get, without being able to write it.
- Fasted than an additional lock, since we use the same atomic we already need to load.
- No additional overhead if no writes are made.
### con
- we probably need to rewrite a lot of functions that expect only `BinEntry::Node` and `BinEntry::Moved` (or only `BinEntry::Node` as a >1st item of the LL)
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.