[API Proposal]: Volatile Read/Write for the ImmutableArray<T> struct

[theodorzoulias]

Background and motivation

The ImmutableInterlocked class contains static methods that allow to perform lock-free operations on the ImmutableArray<T> struct, like the Update and the InterlockedCompareExchange methods, but there is no API available that allows to perform a direct volatile read on this struct. As far as I can tell, the lack of this API is probably an oversight, rather than intentional. So I am proposing the introduction of a Volatile.Read overload for this struct, along with a corresponding Volatile.Write overload for consistency and completeness. The availability of this API will facilitate the use of the ImmutableArray<T> struct in low-lock multithreading scenarios, without needing to resort to workarounds and hacks, like the ones mentioned in this related issue.

API Proposal

namespace System.Threading
{
    public static class Volatile
    {
        public static ImmutableArray<T> Read<T>(ref ImmutableArray<T> location);
        public static void Write<T>(ref ImmutableArray<T> location, ImmutableArray<T> value);
    }
}

API Usage

Example of using the Volatile.Read and Volatile.Write methods as part of a thread-safe class with members AddItem, ProcessSnapshot and Reset:

private ImmutableArray<Item> _items = ImmutableArray<Item>.Empty;

public void AddItem(Item item)
{
    ImmutableInterlocked.Update(ref _items, (x, y) => x.Add(y), item);
}

public void ProcessSnapshot()
{
    // Ensure that we don't enumerate a stale snapshot of the _items array.
    foreach (var item in Volatile.Read(ref _items))
    {
        //...
    }
}

public void Reset(ImmutableArray<Item> items)
{
    Volatile.Write(ref _items, items);
}

Alternative Designs

These two methods could also be placed inside the ImmutableInterlocked class:

namespace System.Collections.Immutable
{
    public static class ImmutableInterlocked
    {
        public static ImmutableArray<T> VolatileRead<T>(ref ImmutableArray<T> location);
        public static void VolatileWrite<T>(ref ImmutableArray<T> location, ImmutableArray<T> value);
    }
}

...or inside a new static class ImmutableVolatile, located in the System.Collections.Immutable namespace:

namespace System.Collections.Immutable
{
    public static class ImmutableVolatile
    {
        public static ImmutableArray<T> Read<T>(ref ImmutableArray<T> location);
        public static void Write<T>(ref ImmutableArray<T> location, ImmutableArray<T> value);
    }
}

Risks

None that I am aware of.

[ghost]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

The ImmutableInterlocked class contains static methods that allow to perform lock-free operations on the ImmutableArray<T> struct, like the Update and the InterlockedCompareExchange methods, but there is no API available that allows to perform a direct volatile read on this struct. As far as I can tell, the lack of this API is probably an oversight, rather than intentional. So I am proposing the introduction of a Volatile.Read overload for this struct, along with a corresponding Volatile.Write overload for consistency and completeness. The availability of this API will facilitate the use of the ImmutableArray<T> struct in low-lock multithreading scenarios, without needing to resort to workarounds and hacks, like the ones mentioned in this related issue.

API Proposal

namespace System.Threading
{
    public static class Volatile
    {
        public static ImmutableArray<T> Read<T>(ref ImmutableArray<T> location);
        public static void Write<T>(ref ImmutableArray<T> location, ImmutableArray<T> value);
    }
}

API Usage

Example of using the Volatile.Read and Volatile.Write methods as part of a thread-safe class with members AddItem, ProcessSnapshot and Reset:

private ImmutableArray<Item> _items = ImmutableArray<Item>.Empty;

public void AddItem(Item item)
{
    ImmutableInterlocked.Update(ref _items, (x, y) => x.Add(y), item);
}

public void ProcessSnapshot()
{
    // Ensure that we don't enumerate a stale snapshot of the _items array.
    foreach (var item in Volatile.Read(ref _items))
    {
        //...
    }
}

public void Reset(ImmutableArray<Item> items)
{
    Volatile.Write(ref _items, items);
}

Alternative Designs

These two methods could also be placed inside the ImmutableInterlocked class:

namespace System.Collections.Immutable
{
    public static class ImmutableInterlocked
    {
        public static ImmutableArray<T> VolatileRead<T>(ref ImmutableArray<T> location);
        public static void VolatileWrite<T>(ref ImmutableArray<T> location, ImmutableArray<T> value);
    }
}

...or inside a new static class ImmutableVolatile, located in the System.Collections.Immutable namespace:

namespace System.Collections.Immutable
{
    public static class ImmutableVolatile
    {
        public static ImmutableArray<T> Read<T>(ref ImmutableArray<T> location);
        public static void Write<T>(ref ImmutableArray<T> location, ImmutableArray<T> value);
    }
}

Risks

None that I am aware of.

Author:	theodorzoulias
Assignees:	-
Labels:	area-System.Collections, untriaged
Milestone:	-

[stephentoub]

Ensure that we don't enumerate a stale snapshot of the _items array.

Volatile doesn't really make any guarantees about how stale the data is, just about reordering of instructions around that access.

The availability of this API will facilitate the use of the ImmutableArray struct in low-lock multithreading scenarios

We've had a slow trickle of requests for APIs related to ImmutableArray<T>, many of which could be addressed simply by providing some kind of marshaling API that gives back a reference to the underlying T[] (this is already possible but convoluted and not apparent by using Unsafe.As). I'd rather we expose such a marshaling API than continue to author one-off methods each time someone actually needs the array reference, e.g. for interop.

[theodorzoulias]

@stephentoub thanks for the feedback!

I'd rather we expose such a marshaling API than continue to author one-off methods each time someone actually needs the array reference, e.g. for interop.

I am OK with that. I updated the proposal with this possibility as an alternative design.

Volatile doesn't really make any guarantees about how stale the data is, just about reordering of instructions around that access.

What API would you suggest for the purpose of avoiding reading stale data, without acquiring a lock, and with minimal overhead? Does the Interlocked.CompareExchange (with equal value and comparand arguments) provide this guarantee?

[GSPP]

The Volatile class is as low level as it gets: It only knows about "memory". Any memory at all. It shouldn't know about specific collection classes. If this API is added, it should be added to a class that can know about immutable collections.

There are quite a few types that could receive volatile-like treatment but it's not supported in-box. For example, DateTime, TimeSpan and essentially and other word-sized struct. Maybe we should develop a generalized approach for how to deal with this.

Clearly, we don't want to add APIs for all of this to Volatile or Interlocked. It's a layering violation and a cross-product of APIs.

Maybe the new guidance can be: Add APIs for cases that are worthwhile. For everything else, the user makes a workaround using unsafe casting.

[theodorzoulias]

There are quite a few types that could receive volatile-like treatment but it's not supported in-box. For example, DateTime, TimeSpan and essentially and other word-sized struct. Maybe we should develop a generalized approach for how to deal with this.

Maybe the new guidance can be: Add APIs for cases that are worthwhile. For everything else, the user makes a workaround using unsafe casting.

@GSPP do you mean something like this?

DateTime VolatileRead(ref DateTime location)
{
    ref ulong unsafeLocation = ref Unsafe.As<DateTime, ulong>(ref location);
    ulong result = Volatile.Read(ref unsafeLocation);
    return Unsafe.As<ulong, DateTime>(ref result);
}

void VolatileWrite(ref DateTime location, DateTime value)
{
    ref ulong unsafeLocation = ref Unsafe.As<DateTime, ulong>(ref location);
    ref ulong unsafeValue = ref Unsafe.As<DateTime, ulong>(ref value);
    Volatile.Write(ref unsafeLocation, unsafeValue);
}

Is this guaranteed to be forward-compatible, or it's as brittle as using reflection?

My argument for going the extra mile and offering this functionality out of the box for the ImmutableArray<T> struct is because there are already methods in the ImmutableInterlocked class that enable the usage of immutable arrays in lock-free scenarios. And AFAIK it's quite common to combine Interlocked and Volatile in such scenarios. See the implementation of the ImmutableInterlocked.Update method for example.

[GSPP]

Yes, @theodorzoulias. This is what I had in mind, and I have posted code to this effect in

• Remove Interlocked.{Compare}Exchange generic constraint #65184

Your request is to add a specialized API for ImmutableArray, and I do support that. ImmutableInterlocked seems like a decent place to add it. Or does there need to be an ImmutableVolatile?

For DateTime there's currently nothing that guarantees that it can be treated as a long. This would need to be documented, or an in-box API would need to be added.

In practical terms, I'd personally be comfortable doing this, though. Altering DateTime to not be backed by a long would break many codebases and no reason comes to mind why such a change would be made. I'm very hesitant to rely on undocumented behavior, but, in practical terms, there is a place for doing it.

[theodorzoulias]

The Volatile class is as low level as it gets: It only knows about "memory". Any memory at all. It shouldn't know about specific collection classes. If this API is added, it should be added to a class that can know about immutable collections.

Clearly, we don't want to add APIs for all of this to Volatile or Interlocked. It's a layering violation and a cross-product of APIs.

@GSPP regarding where to put this API, personally I don't have a strong opinion. It could be located anywhere, in an obscure class in the System.Runtime.InteropServices namespace for example, and I would be OK. For the sake of the discussion though, the Volatile class seems like a reasonable place to put it. The definition of this class is not overly restrictive:

Contains methods for performing volatile memory operations.

It doesn't specify on what types these volatile memory operations are performed. Personally if I ever needed to perform a volatile read on a DateTime or a TimeSpan, the first place where I would look would be there (with the second place being a web search engine).

[theodorzoulias]

We've had a slow trickle of requests for APIs related to ImmutableArray<T>, many of which could be addressed simply by providing some kind of marshaling API that gives back a reference to the underlying T[] (this is already possible but convoluted and not apparent by using Unsafe.As). I'd rather we expose such a marshaling API than continue to author one-off methods each time someone actually needs the array reference, e.g. for interop.

@stephentoub do you mean something like this API?

public static class CollectionsMarshal
{
    public static ref T[] GetArrayRef<T> (ref ImmutableArray<T> immutableArray);
}

I tried to make a VolatileRead method out of this API, but I am not sure that I got it right:

static ImmutableArray<T> VolatileRead<T>(ref ImmutableArray<T> location)
{
    ref T[] array = ref CollectionsMarshal.GetArrayRef(ref location);
    array = Volatile.Read(ref array);
    return location;
}

Overwriting the array in the second line looks suspicious, because it is a ref. A Read method is not supposed to change the thing it reads.

[theodorzoulias]

Maybe this is the correct way to do it:

static ImmutableArray<T> VolatileRead<T>(ref ImmutableArray<T> location)
{
    ImmutableArray<T> result = default;
    ref T[] locationArray = ref CollectionsMarshal.GetArrayRef(ref location);
    ref T[] resultArray = ref CollectionsMarshal.GetArrayRef(ref result);
    resultArray = Volatile.Read(ref locationArray);
    return result;
}

Not thrilled with having to maintain such code in my codebase though. Not easy to reason about its correctness.

[theodorzoulias]

I had a need for this API again recently. I used the VolatileRead implementation below.

public static ImmutableArray<T> VolatileRead<T>(ref ImmutableArray<T> location)
{
    T[] array = Unsafe.As<ImmutableArray<T>, T[]>(ref location);
    T[] result = Volatile.Read(ref array);
    return Unsafe.As<T[], ImmutableArray<T>>(ref result);
}

I would like to ask if this implementation is correct. Does it read the immutable array, while also preventing the reordering of instructions that appears after this method in the code, to be moved before this method?

[timcassell]

#98837

[hamarb123]

I had a need for this API again recently. I used the VolatileRead implementation below.

public static ImmutableArray<T> VolatileRead<T>(ref ImmutableArray<T> location)
{
    T[] array = Unsafe.As<ImmutableArray<T>, T[]>(ref location);
    T[] result = Volatile.Read(ref array);
    return Unsafe.As<T[], ImmutableArray<T>>(ref result);
}

I would like to ask if this implementation is correct. Does it read the immutable array, while also preventing the reordering of instructions that appears after this method in the code, to be moved before this method?

This will read the ImmutableArray with standard volatile read guarantees. Note, the version you posted was incorrect as it read the memory on the first line normally, and then volatile read the variable on the stack (which achieves nothing).

public static ImmutableArray<T> VolatileRead<T>(ref ImmutableArray<T> location)
{
    ref T[] array = ref Unsafe.As<ImmutableArray<T>, T[]>(ref location);
    T[] result = Volatile.Read(ref array);
    return Unsafe.As<T[], ImmutableArray<T>>(ref result);
}