Skip to content

Concurrency improvements (AtomHashMap, Atom, Ref)
Compare
Choose a tag to compare
@louthy louthy released this 09 Oct 16:40
· 845 commits to main since this release
v3.5.63-beta
320be0f

This release features improvements to the concurrency elements of language-ext:

  • Atom - atomic references
  • STM / Ref - software-transactional memory system
  • AtomHashMap - new atomic data-structure

Atom and STM

The atomic references system (Atom) that wraps a value and allows for atomic updates; and the STM system that allows many Ref values (that also wrap a value, but instead work within an atomic sync transaction), have both been updated to never give up trying to resolve a conflict.

Previously they would fail after 500 attempts, but now any conflicts will cause the conflicting threads to back-off and eventually yield control so that the other thread(s) they were in conflict with eventually win and can update the atomic reference. This removes the potential time-bomb buried deep within the atomic references system, and creates a robust transactional system.

AtomHashMap<K, V>

One pattern I noted I was doing quite a lot was wrapping HashMap in an atom, usually for shared cached values:

   var atomData = Atom(HashMap<string, int>());

   atomData.Swap(static hm => hm.AddOrUpdate("foo", 123));

It struck me that it would be very useful to have atomic versions of all of the collection data-structures of language-ext. The first one is AtomHashMap. And so, instead of the code above, we can now write:

    var atomData = AtomHashMap<string, int>();

    atomData.AddOrUpdate("foo", 123);

All operations on AtomHashMap are atomic and lock-free. The underling data structure is still an immutable HashMap. It's simply the reference to the HashMap that gets protected by AtomHashMap, preventing two threads updating the data structure with stale data.

The main thing to understand with AtomHashMap is that if a conflict occurs on update, then any transformational operation is re-run with the new state of the data-structure. Obviously conflicts are rare on high-performance CPUs, and so we save processing time from not taking locks on every operation, at the expense of occasional re-running of operations when conflicts arise.

Swap

AtomHashMap also supports Swap, which allows for more complex atomic operations on the underlying HashMap. For example, if your update operation relies on data within the AtomHashMap, then you might want to consider wrapping everything within a Swap call to allow for fully idempotent transformations:

    atomData.Swap(data => data.Find("foo").Case switch
                          {
                              int x => data.SetItem("foo", x + 1),
                              _     => data.Add("foo", 1)
                          });

NOTE: The longer you spend inside a Swap function, the higher the risk of conflicts, and so try to make sure you do the bare minimum within swap that will facilitate your idempotent operation.

In Place Operations

Most operations on AtomHashMap are in-place, i.e. they update the underlying HashMap atomically. However, some functions like Map, Filter, Select, Where are expected to process the data-structure into a new data-structure. This is usually wanted, but we also want in-place filtering and mapping:

    // Only keeps items with a value > 10 in the AtomHashMap
    atomData.FilterInPlace(x => x > 10);

    // Maps all items in the AtomHashMap 
    atomData.MapInPlace(x => x + 10);

The standard Map, Filter, etc. all still exist and work in the 'classic' way of generating a new data structure.

ToHashMap

At any point if you need to take a snapshot of what's in the AtomHashMap you can all:

    HashMap<string, int> snapshot = atomData.ToHashMap();

This is a zero allocation, zero time (well in the order of nanoseconds), operation. And so we can easily take snapshots and work on those whilst the atomic data structure can carry on being mutated without consequence.

The Rest

As well as AtomHashMap<K, V> there's also AtomHashMap<EqK, K, V> which maps to HashMap<EqK, K, V>.

This is just the beginning of the new Atom based data-structures. So watch this space!

Assets 2
Loading