C#•3y 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?

cap5lut•10/18/23, 12:22 PM

the whole mechanism is basically about the atomic

Interlocked.CompareExchange()

Interlocked.CompareExchange()

method

cap5lut•10/18/23, 12:25 PM

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

cap5lut•10/18/23, 12:26 PM

Interlocked.CompareExchange(ref fieldOrVariable, newValue, oldValue) != oldValue

Interlocked.CompareExchange(ref fieldOrVariable, newValue, oldValue) != oldValue

would mean that the exchange was successful

cap5lut•10/18/23, 12:28 PM

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);

cap5lut•10/18/23, 12:31 PM

because

int

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);
    }
}

cap5lut•10/18/23, 12:40 PM

lets assume 2 threads are calling

Increment()

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

cap5lut•10/18/23, 12:43 PM

thats the whole process behind it, any questions?

zxa4fdOP•10/18/23, 3:43 PM

I'm still trying to understand the explanation

zxa4fdOP•10/18/23, 3:48 PM

Will it be possible to get an example with collections involved? I'm not really sure if the example above is thread-safe

zxa4fdOP•10/18/23, 3:57 PM

I mean immutable vs mutable collections?

cap5lut•10/18/23, 3:58 PM

well the only place where u have write access is the

Interlocked.CompareExchange(ref _data, newData, oldData)

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

ref

zxa4fdOP•10/18/23, 3:59 PM

What would happen if 2 threads can do it at the same time?

zxa4fdOP•10/18/23, 3:59 PM

That's what I don't understand

Zzxa4fd I mean immutable vs mutable collections?

cap5lut•10/18/23, 4:01 PM

lets assume this isnt about

int

int

s, but

ImmutableArray<int>

ImmutableArray<int>

s and instead of incrementing we are adding an element:
instead of

newData = oldData + 1

newData = oldData + 1

, u would build a new

ImmutableArray<int>

ImmutableArray<int>

that contains both the elements of

oldData

oldData

and the element u want to add

Zzxa4fd What would happen if 2 threads can do it at the same time?

cap5lut•10/18/23, 4:02 PM

well, the whole point of

Interlocked.CompareExchange()

Interlocked.CompareExchange()

is that it can not happen, this is on hardware level a compare-and-swap instruction

cap5lut•10/18/23, 4:05 PM

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>()

Interlocked.CompareExchange<T>()

requires

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•10/18/23, 4:06 PM

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•10/18/23, 4:14 PM

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

lock

statement first

cap5lut•10/18/23, 4:16 PM

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);
    }
  }
}

cap5lut•10/18/23, 4:21 PM

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()

PrintAll()

cap5lut•10/18/23, 4:25 PM

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}");
    }
  }
}

cap5lut•10/18/23, 4:26 PM

meaning that u would the whole thing locked up while u process the data, which might be quite time consuming

cap5lut•10/18/23, 4:28 PM

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}");
  }
}

cap5lut•10/18/23, 4:29 PM

and thats more or less it using locks

zxa4fdOP•10/18/23, 4:32 PM

Okay, I get how the locks work

cap5lut•10/18/23, 4:34 PM

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•10/18/23, 4:36 PM

How does the immutable list help with adding elements?

cap5lut•10/18/23, 4:36 PM

it doesnt, its there to get a current snapshot of the state

cap5lut•10/18/23, 4:40 PM

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

Data

property

cap5lut•10/18/23, 4:42 PM

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•10/18/23, 4:42 PM

Okay, I think I get it in that example

cap5lut•10/18/23, 4:44 PM

lock

lock

Semaphore

Semaphore

and what i explained at the beginning (

Interlocked.CompareExchange()

Interlocked.CompareExchange()

) are also about thread safety,
but this time about optimistic and pessimistic locking

cap5lut•10/18/23, 4:45 PM

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

cap5lut•10/18/23, 4:48 PM

lock

lock

Semaphore

Semaphore

and alike are pessimistic locks, they have some overhead under the hood, but that overhead is "stable" (doesnt spike much)

cap5lut•10/18/23, 4:50 PM

Interlock.CompareExchange()

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•10/18/23, 4:55 PM

I understand, thank you

cap5lut•10/18/23, 4:55 PM

glad i could help, and sorry for the earlier mix up

cap5lut•10/18/23, 4:59 PM

if all ur questions are answered, please $close the thread

Ccap5lut if all ur questions are answered, please $close the thread

MODiX•10/18/23, 4:59 PM

Use the </close:1007753098107813888> command to mark a forum thread as answered

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 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 void PrintAll() { ImmutableList<int> data; lock (_syncObj) { data = Data; } Console.WriteLine($"Count: {data.Count}"); foreach(var element in data) { Console.WriteLine($"\t{element}"); } }

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); } } } }