C#•14mo ago

✅ Can anyone give example code of using an Immutable Data Structure for Concurrency?

Can anyone give an example that shows how using these types are thread safe?

16 Replies

cap5lut•14mo ago

the whole mechanism is basically about the atomic Interlocked.CompareExchange() method this is used to set a reference to a new value if it contains the a given value and returns the value that was originally stored so Interlocked.CompareExchange(ref fieldOrVariable, newValue, oldValue) != oldValue would mean that the exchange was successful so u simply loop until that change happens pseudo code:

do {
  oldValue = currentValue
  newValue = computeNewValueFromOldValue(oldValue);
} while (exchange did not happen);

do {
  oldValue = currentValue
  newValue = computeNewValueFromOldValue(oldValue);
} while (exchange did not happen);

because int is immutable i use it as substitution for now and here would be an example implementation:

public class Counter
{
    private volatile int _data;
    public int Current => _data;
    public void Increment()
    {
        int oldData;
        int newData;
        do
        {
            // get the value
            oldData = _data;
            // generate a new value
            newData = oldData + 1;
        } while (Interlocked.CompareExchange(ref _data, newData, oldData) != oldData);
    }
}

public class Counter
{
    private volatile int _data;
    public int Current => _data;
    public void Increment()
    {
        int oldData;
        int newData;
        do
        {
            // get the value
            oldData = _data;
            // generate a new value
            newData = oldData + 1;
        } while (Interlocked.CompareExchange(ref _data, newData, oldData) != oldData);
    }
}

lets assume 2 threads are calling Increment() at the same time thread 1 gets oldData (0) thread 2 gets oldData (0) thread 1 computes newData (1) thread 2 computes newData (1) thread 1 executes CompareExchange, _data is 0, so it sets it to 1 because the comparand (oldData) is also 0 thus thread 1 is done. thread 2 executes CompareExchange, but does not change _data, because its currently 1 and the comparand is 0, so thread 2 loops again: gets oldData (1) computes newData (2) executes CompareExcahnge, sets _data is 1, so it sets it to 2 because the comparand is also 1 thats the whole process behind it, any questions?

zxa4fdOP•14mo ago

I'm still trying to understand the explanation 😆 Will it be possible to get an example with collections involved? I'm not really sure if the example above is thread-safe I mean immutable vs mutable collections?

cap5lut•14mo ago

well the only place where u have write access is the Interlocked.CompareExchange(ref _data, newData, oldData) call, and that is atomic and thread safe, no 2 threads can do this at the same time for the same ref

zxa4fdOP•14mo ago

What would happen if 2 threads can do it at the same time? That's what I don't understand

cap5lut•14mo ago

lets assume this isnt about ints, but ImmutableArray<int>s and instead of incrementing we are adding an element: instead of newData = oldData + 1, u would build a new ImmutableArray<int> that contains both the elements of oldData and the element u want to add well, the whole point of Interlocked.CompareExchange() is that it can not happen, this is on hardware level a compare-and-swap instruction i can write up an example using immutable arrays, but that is a bit complexer because - besides for the numeric versions - the Interlocked.CompareExchange<T>() requires T to be a class and immutable arrays are structs (so u need a a small wrapper) so i wanted to make sure i explained the basic concept understandable first

zxa4fdOP•14mo ago

Will it be possible with ImmutableList? Can we get an example of what will happen to a normal List if two threads add to it vs. using ImmutableList?

cap5lut•14mo ago

while smoking i just realized i explained the wrong thing, this is more about using lock-free thread safety. so just dont think about it for now and i explain it with a simple lock statement first

public class Elements
{
  private readonly object _syncObj = new();
  private volatile ImmutableList<int> _list;
  public ImmutableList<int> Data => _list;
  public void Add(int element)
  {
    lock(_syncObj)
    {
      _list = _list.Add(element);
    }
  }
}

public class Elements
{
  private readonly object _syncObj = new();
  private volatile ImmutableList<int> _list;
  public ImmutableList<int> Data => _list;
  public void Add(int element)
  {
    lock(_syncObj)
    {
      _list = _list.Add(element);
    }
  }
}

so when u work with immutable data structures, and u want, for example print the count and then all elements, lets add a method for that PrintAll() usually u would do something like

public void PrintAll()
{
  lock (_syncObj)
  {
    Console.WriteLine($"Count: {Data.Count}");
    foreach(var element in Data)
    {
      Console.WriteLine($"\t{element}");
    }
  }
}

public void PrintAll()
{
  lock (_syncObj)
  {
    Console.WriteLine($"Count: {Data.Count}");
    foreach(var element in Data)
    {
      Console.WriteLine($"\t{element}");
    }
  }
}

meaning that u would the whole thing locked up while u process the data, which might be quite time consuming so with immutable data structures u take out the current snapshot (the list) and use that instead:

public void PrintAll()
{
  ImmutableList<int> data;
  lock (_syncObj)
  {
    data = Data;
  }

  Console.WriteLine($"Count: {data.Count}");
  foreach(var element in data)
  {
    Console.WriteLine($"\t{element}");
  }
}

public void PrintAll()
{
  ImmutableList<int> data;
  lock (_syncObj)
  {
    data = Data;
  }

  Console.WriteLine($"Count: {data.Count}");
  foreach(var element in data)
  {
    Console.WriteLine($"\t{element}");
  }
}

and thats more or less it using locks

zxa4fdOP•14mo ago

Okay, I get how the locks work

cap5lut•14mo ago

so the immutable list is more or less just used instead of a normal list, so u can not mess with it in an not thread safe manner, but can keep the time its locked small

zxa4fdOP•14mo ago

How does the immutable list help with adding elements?

cap5lut•14mo ago

it doesnt, its there to get a current snapshot of the state u could also have something like

public class Elements
{
  private readonly object _syncObj = new();
  private readonly List<int> _list = new();
  public void Add(int element)
  {
    lock(_syncObj)
    {
      _list.Add(element);
    }
  }
  public List<int> Data
  {
    get {
      lock(_syncObj)
      {
        return new(_list);
      }
    }
  }
}

public class Elements
{
  private readonly object _syncObj = new();
  private readonly List<int> _list = new();
  public void Add(int element)
  {
    lock(_syncObj)
    {
      _list.Add(element);
    }
  }
  public List<int> Data
  {
    get {
      lock(_syncObj)
      {
        return new(_list);
      }
    }
  }
}

this is called a defensive copy, but u will create a copy each time someone accesses the Data property the immutably is there so that u do not have to create defensive copies but still have a small lock time and still can not mess in a thread unsafe manner

zxa4fdOP•14mo ago

Okay, I think I get it in that example 👍

cap5lut•14mo ago

lock, Semaphore and what i explained at the beginning (Interlocked.CompareExchange()) are also about thread safety, but this time about optimistic and pessimistic locking optimistic means, that the chances are reeeeeeally low that multiple threads at the same try to modify the underlying state (the list) pessimistic means, that chances are high lock, Semaphore and alike are pessimistic locks, they have some overhead under the hood, but that overhead is "stable" (doesnt spike much) Interlock.CompareExchange() is an optimistic lock, meaning that u have next to zero overhead for reading and writing with one thread, but quite some overhead when multiple threads want write access

zxa4fdOP•14mo ago

I understand, thank you

cap5lut•14mo ago

glad i could help, and sorry for the earlier mix up if all ur questions are answered, please $close the thread

MODiX•14mo ago

Use the /close command to mark a forum thread as answered

Gaming

Programming

✅ Can anyone give example code of using an Immutable Data Structure for Concurrency?