From b0d3fb7ebab39bd7f3a6a60cac3f0a6eb7dbb550 Mon Sep 17 00:00:00 2001 From: Stephen Toub Date: Tue, 8 Oct 2019 14:46:26 -0400 Subject: [PATCH] Add ImmutableInterlocked.Update overloads for ImmutableArray (dotnet/corefx#41600) * Add ImmutableInterlocked.Update overloads for ImmutableArray The implementations and tests just copy the exist Update overloads, tweaked to work with ImmutableArray. * Address PR feedback Commit migrated from https://github.com/dotnet/corefx/commit/9de37814fe28f497c8679b52772f2e5dd7f73306 --- .../ref/System.Collections.Immutable.cs | 2 + .../Collections/Immutable/ImmutableInterlocked.cs | 86 ++++++++++ .../tests/ImmutableInterlockedTests.cs | 190 ++++++++++++++++++++- 3 files changed, 275 insertions(+), 3 deletions(-) diff --git a/src/libraries/System.Collections.Immutable/ref/System.Collections.Immutable.cs b/src/libraries/System.Collections.Immutable/ref/System.Collections.Immutable.cs index 0fd48ec..2aa625a 100644 --- a/src/libraries/System.Collections.Immutable/ref/System.Collections.Immutable.cs +++ b/src/libraries/System.Collections.Immutable/ref/System.Collections.Immutable.cs @@ -515,6 +515,8 @@ namespace System.Collections.Immutable public static bool TryUpdate(ref System.Collections.Immutable.ImmutableDictionary location, TKey key, TValue newValue, TValue comparisonValue) { throw null; } public static bool Update(ref T location, System.Func transformer) where T : class { throw null; } public static bool Update(ref T location, System.Func transformer, TArg transformerArgument) where T : class { throw null; } + public static bool Update(ref System.Collections.Immutable.ImmutableArray location, Func, System.Collections.Immutable.ImmutableArray> transformer) { throw null; } + public static bool Update(ref System.Collections.Immutable.ImmutableArray location, Func, TArg, System.Collections.Immutable.ImmutableArray> transformer, TArg transformerArgument) { throw null; } } public static partial class ImmutableList { diff --git a/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableInterlocked.cs b/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableInterlocked.cs index 5e64564..d668b29 100644 --- a/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableInterlocked.cs +++ b/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableInterlocked.cs @@ -98,6 +98,92 @@ namespace System.Collections.Immutable return true; } + /// + /// Mutates an immutable array in-place with optimistic locking transaction semantics + /// via a specified transformation function. + /// The transformation is retried as many times as necessary to win the optimistic locking race. + /// + /// The type of data in the immutable array. + /// + /// The immutable array to be changed. + /// + /// + /// A function that produces the new array from the old. This function should be side-effect free, + /// as it may run multiple times when races occur with other threads. + /// + /// true if the location's value is changed by applying the result of the + /// function; + /// false if the location's value remained the same because the last + /// invocation of returned the existing value. + /// + public static bool Update(ref ImmutableArray location, Func, ImmutableArray> transformer) + { + Requires.NotNull(transformer, nameof(transformer)); + + bool successful; + T[] oldArray = Volatile.Read(ref location.array); + do + { + ImmutableArray newImmutableArray = transformer(new ImmutableArray(oldArray)); + if (ReferenceEquals(oldArray, newImmutableArray.array)) + { + // No change was actually required. + return false; + } + + T[] interlockedResult = Interlocked.CompareExchange(ref location.array, newImmutableArray.array, oldArray); + successful = ReferenceEquals(oldArray, interlockedResult); + oldArray = interlockedResult; // we already have a volatile read that we can reuse for the next loop + } + while (!successful); + + return true; + } + + /// + /// Mutates an immutable array in-place with optimistic locking transaction semantics + /// via a specified transformation function. + /// The transformation is retried as many times as necessary to win the optimistic locking race. + /// + /// The type of data in the immutable array. + /// The type of argument passed to the . + /// + /// The immutable array to be changed. + /// + /// + /// A function that produces the new array from the old. This function should be side-effect free, + /// as it may run multiple times when races occur with other threads. + /// The argument to pass to . + /// + /// true if the location's value is changed by applying the result of the + /// function; + /// false if the location's value remained the same because the last + /// invocation of returned the existing value. + /// + public static bool Update(ref ImmutableArray location, Func, TArg, ImmutableArray> transformer, TArg transformerArgument) + { + Requires.NotNull(transformer, nameof(transformer)); + + bool successful; + T[] oldArray = Volatile.Read(ref location.array); + do + { + ImmutableArray newImmutableArray = transformer(new ImmutableArray(oldArray), transformerArgument); + if (ReferenceEquals(oldArray, newImmutableArray.array)) + { + // No change was actually required. + return false; + } + + T[] interlockedResult = Interlocked.CompareExchange(ref location.array, newImmutableArray.array, oldArray); + successful = ReferenceEquals(oldArray, interlockedResult); + oldArray = interlockedResult; // we already have a volatile read that we can reuse for the next loop + } + while (!successful); + + return true; + } + #region ImmutableArray members /// diff --git a/src/libraries/System.Collections.Immutable/tests/ImmutableInterlockedTests.cs b/src/libraries/System.Collections.Immutable/tests/ImmutableInterlockedTests.cs index e305023..90c3e2c 100644 --- a/src/libraries/System.Collections.Immutable/tests/ImmutableInterlockedTests.cs +++ b/src/libraries/System.Collections.Immutable/tests/ImmutableInterlockedTests.cs @@ -2,7 +2,6 @@ // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. -using System.Linq; using System.Threading; using System.Threading.Tasks; using Xunit; @@ -12,6 +11,7 @@ namespace System.Collections.Immutable.Tests public class ImmutableInterlockedTests { private delegate bool UpdateDelegate(ref T location, Func transformer); + private delegate bool UpdateArrayDelegate(ref ImmutableArray location, Func, ImmutableArray> transformer); [Fact] public void Update_StartWithNull() @@ -26,6 +26,30 @@ namespace System.Collections.Immutable.Tests } [Fact] + public void UpdateArray_StartWithDefault() + { + UpdateArrayHelper(func => + { + ImmutableArray array = default; + Assert.True(func(ref array, l => { Assert.Equal(default, l); return ImmutableArray.Create(1); })); + Assert.Equal(1, array.Length); + Assert.Equal(1, array[0]); + }); + } + + [Fact] + public void UpdateArray_StartWithEmpty() + { + UpdateArrayHelper(func => + { + ImmutableArray array = ImmutableArray.Empty; + Assert.True(func(ref array, l => { Assert.Equal(0, l.Length); return ImmutableArray.Create(1); })); + Assert.Equal(1, array.Length); + Assert.Equal(1, array[0]); + }); + } + + [Fact] public void Update_IncrementalUpdate() { UpdateHelper>(func => @@ -39,6 +63,19 @@ namespace System.Collections.Immutable.Tests } [Fact] + public void UpdateArray_IncrementalUpdate() + { + UpdateArrayHelper(func => + { + ImmutableArray array = ImmutableArray.Create(1); + Assert.True(func(ref array, l => l.Add(2))); + Assert.Equal(2, array.Length); + Assert.Equal(1, array[0]); + Assert.Equal(2, array[1]); + }); + } + + [Fact] public void Update_FuncThrowsThrough() { UpdateHelper>(func => @@ -49,6 +86,16 @@ namespace System.Collections.Immutable.Tests } [Fact] + public void UpdateArray_FuncThrowsThrough() + { + UpdateArrayHelper(func => + { + ImmutableArray array = ImmutableArray.Create(42); + Assert.Throws(() => func(ref array, l => throw new InvalidOperationException())); + }); + } + + [Fact] public void Update_NoEffectualChange() { UpdateHelper>(func => @@ -59,6 +106,16 @@ namespace System.Collections.Immutable.Tests } [Fact] + public void UpdateArray_NoEffectualChange() + { + UpdateArrayHelper(func => + { + ImmutableArray array = ImmutableArray.Create(42); + Assert.False(func(ref array, l => l)); + }); + } + + [Fact] public void Update_HighConcurrency() { UpdateHelper>(func => @@ -70,7 +127,7 @@ namespace System.Collections.Immutable.Tests var barrier = new Barrier(tasks.Length); for (int i = 0; i < tasks.Length; i++) { - tasks[i] = Task.Run(delegate + tasks[i] = Task.Factory.StartNew(delegate { // Maximize concurrency by blocking this thread until all the other threads are ready to go as well. barrier.SignalAndWait(); @@ -79,7 +136,7 @@ namespace System.Collections.Immutable.Tests { Assert.True(func(ref list, l => l.Add(l.Count))); } - }); + }, CancellationToken.None, TaskCreationOptions.LongRunning, TaskScheduler.Default); } Task.WaitAll(tasks); @@ -92,6 +149,39 @@ namespace System.Collections.Immutable.Tests } [Fact] + public void UpdateArray_HighConcurrency() + { + UpdateArrayHelper(func => + { + ImmutableArray array = ImmutableArray.Create(); + int concurrencyLevel = Environment.ProcessorCount; + int iterations = 500; + Task[] tasks = new Task[concurrencyLevel]; + var barrier = new Barrier(tasks.Length); + for (int i = 0; i < tasks.Length; i++) + { + tasks[i] = Task.Factory.StartNew(delegate + { + // Maximize concurrency by blocking this thread until all the other threads are ready to go as well. + barrier.SignalAndWait(); + + for (int j = 0; j < iterations; j++) + { + Assert.True(func(ref array, l => l.Add(l.Length))); + } + }, CancellationToken.None, TaskCreationOptions.LongRunning, TaskScheduler.Default); + } + + Task.WaitAll(tasks); + Assert.Equal(concurrencyLevel * iterations, array.Length); + for (int i = 0; i < array.Length; i++) + { + Assert.Equal(i, array[i]); + } + }); + } + + [Fact] public void Update_CarefullyScheduled() { UpdateHelper>(func => @@ -151,6 +241,65 @@ namespace System.Collections.Immutable.Tests } [Fact] + public void UpdateArray_CarefullyScheduled() + { + UpdateArrayHelper(func => + { + var array = ImmutableArray.Create(); + var task2TransformEntered = new AutoResetEvent(false); + var task1TransformExited = new AutoResetEvent(false); + + var task1 = Task.Run(delegate + { + int transform1ExecutionCounter = 0; + func( + ref array, + s => + { + Assert.Equal(1, ++transform1ExecutionCounter); + task2TransformEntered.WaitOne(); + return s.Add(1); + }); + task1TransformExited.Set(); + Assert.Equal(1, transform1ExecutionCounter); + }); + + var task2 = Task.Run(delegate + { + int transform2ExecutionCounter = 0; + func( + ref array, + s => + { + switch (++transform2ExecutionCounter) + { + case 1: + task2TransformEntered.Set(); + task1TransformExited.WaitOne(); + Assert.True(s.IsEmpty); + break; + case 2: + Assert.True(s.Contains(1)); + Assert.Equal(1, s.Length); + break; + } + + return s.Add(2); + }); + + // Verify that this transform had to execute twice. + Assert.Equal(2, transform2ExecutionCounter); + }); + + // Wait for all tasks and rethrow any exceptions. + Task.WaitAll(task1, task2); + Assert.Equal(2, array.Length); + Assert.True(array.Contains(1)); + Assert.True(array.Contains(2)); + }); + } + + [Fact] public void InterlockedExchangeArrayDefault() { ImmutableArray array = default(ImmutableArray); @@ -439,6 +588,22 @@ namespace System.Collections.Immutable.Tests } /// + /// Executes a test against both + /// and . + /// + /// The type of value under test. + /// + /// The test to execute. Invoke the parameter instead of calling + /// the ImmutableInterlocked method so that the delegate can test both overloads + /// by being executed twice. + /// + private static void UpdateArrayHelper(Action> test) + { + test(ImmutableInterlocked.Update); + test(UpdateArrayWrapper); + } + + /// /// A wrapper that makes one overload look like another so the same test delegate can execute against both. /// /// The type of value being changed. @@ -457,5 +622,24 @@ namespace System.Collections.Immutable.Tests }, 1); } + + /// + /// A wrapper that makes one overload look like another so the same test delegate can execute against both. + /// + /// The type of value being changed. + /// The variable or field to be changed. + /// The function that transforms the value. + /// The result of the replacement function. + private static bool UpdateArrayWrapper(ref ImmutableArray location, Func, ImmutableArray> transformer) + { + return ImmutableInterlocked.Update( + ref location, + (t, arg) => + { + Assert.Equal(1, arg); + return transformer(t); + }, + 1); + } } } -- 2.7.4