Proposal for ImmutableInterlocked.ApplyChange API

[AArnott]

Folks using immutable collections in multi-threaded environments frequently want to leverage the immutability to use lock-free patterns of updating the fields that store those collections.

Interlocked.CompareExchange leaves quite a bit of insight into the runtime and threading requirements to the programmer when it comes to lock-free mutations of immutable collections. While we already have the ImmutableInterlocked class with several methods on it, all methods are special purpose and aren't suitable for such simple and common operations as adding or removing an element to an ImmutableList<T> or ImmutableHashSet<T>.

I propose adding this API:

/// <summary>
/// Mutates a value in-place with optimistic locking transaction semantics
/// via a specified transform function.
/// The transform is retried as many times as necessary to win the optimistic locking race.
/// </summary>
/// <typeparam name="T">The type of data.</typeparam>
/// <typeparam name="TArg">The type of the argument to be passed to the transformer</typeparam>
/// <param name="location">
/// The variable or field to be changed, which may be accessed by multiple threads.
/// </param>
/// <param name="transformer">
/// A function that mutates the value. This function should be side-effect free, 
/// as it may run multiple times when races occur with other threads.</param>
/// <returns>
/// <param name="transformerArgument">
/// An argument to pass to the <paramref name="transformer"/> function.
/// </param>
/// <c>true</c> if the location's value is changed by applying the result of the 
/// <paramref name="transformer"/> function;
/// <c>false</c> if the location's value remained the same because the last 
/// invocation of <paramref name="transformer"/> returned the existing value.
/// </returns>
public static bool ApplyChange<T, TArg>(ref T location, Func<T, TArg, T> transformer, TArg transformerArgument) where T : class

public static bool ApplyChange<T>(ref T location, Func<T, T> transformer) where T : class

The ImmutableInterlocked.ApplyChange method makes such lock-free mutations trivial:

// Add "2" to the list in this.field in a thread-safe, lock-free manner.
ImmutableInterlocked.ApplyChange(ref this.field, list => list.Add(2));

More complex functions are of course also supported, allowing search of a collection, computation, and a subsequent prescribed change returned. In each case, an "optimistic locking" style transaction is used to execute the provided function (repeatedly, if necessary in the case of a lost race) to update the field without locks.

I plan to send a pull request once this issue is reviewed. I'm attempting to follow the process proposed in #13938 since this change adds to the public API.

Change log:

• renamed parameters hotLocation to location and transformation to transformer.
• added overload that takes a TArg

[justinvp]

Minor naming suggestions/questions:

• Instead of hotLocation for the first parameter, consider location for consistency with the naming of the parameter on other methods of ImmutableInterlocked.
• tranformation is perfectly reasonable -- just wondering if it should be named something else like transformer to be more consistent with names like selector in LINQ, or even factory? Although, transformation does sound reminiscent of comparison used as the name of parameters that take Comparison<T> on Array.Sort and List<T>.Sort.

Should there be an overload that takes a TArg like ImmutableInterlocked.GetOrAdd<TKey, TValue, TArg>() to avoid closure allocations?

[AArnott]

Thanks for the suggestions, @justinvp. I've applied those changes. I was thinking about the TArg overload myself but wanted to wait to see if anyone else would suggest it before I add the API.

[karldodd]

Love this idea. Would be very handy and useful!

Btw, could you shed some light on choosing boolean as the return value instead of the updated immutable instance itself?

Take the above example:

// Add "2" to the list in this.field in a thread-safe, lock-free manner.
ImmutableInterlocked.ApplyChange(ref this.field, list => list.Add(2));

Do we lose the ability to grab the updated instance right after the operation?

Thanks,

[terrajobst]

Is the implementation specific to immutable collections at all? Looking at the signature it seems it's not. In that case, the method should probably not live in ImmutableInterlocked but on Interlocked itself.

[AArnott]

FYI This method can already be found in the VS SDK as ThreadTools.ApplyChangeOptimistically.

@karldodd The method returns bool because as I said, this API has already shipped elsewhere, and in my experience the callers are very typically more interested in whether the value needed to be updated than what the updated value is. For example, if you're implementing an atomic Add operation, you may want to know whether the value actually as added (as opposed to already being in the collection) rather than what the final value was exactly at the point of the update being completed. It's true that returning T allows you to get both kinds of data as the caller whereas returning bool only provides one kind, so that's a point for returning T. But returning T requires quite a bit more code for the caller to convert that to a bool. If enough folks still feel T is useful as the return value though, we can perhaps return T and then add another method that wraps this one and returns bool instead.

@terrajobst No, there's nothing actually specific to immutable collections in this method. Is adding it to Interlocked instead an option?

[terrajobst]

It is; it just might be too late for adding to the .NET Framework 4.6 as we're looking it down very aggressively. However, there is nothing stopping us from adding to .NET Core and later on port to .NET Framework 4.6.

[AArnott]

Where is the source code for Interlocked in .NET Core? Is it part of this project yet?

[karldodd]

@AArnott Agree with you. As you pointed out, there is 'a point for returning T'. For the immutable list referenced in this.field:

// Add "2" to the list in this.field in a thread-safe, lock-free manner.
ImmutableInterlocked.ApplyChange(ref this.field, list => list.Add(2));

If we want to grab the new list count caused by this add operation, returning T helps. If returning bool, there is probably no way to tell which operation caused a count increment from x to x+1.

So yes, personally I would vote for 'return T and then add another method that wraps this one and returns bool'. Returning T also looks consistent with most methods in static class Interlocked.

[terrajobst]

We've reviewed this proposal and think it's a good addition and thus accept PRs.