Good day. I hope you are doing well. I'm trying to perform a unit test to test a Wrapper for a data structure I created (SortedList). This Wrapper is "thread-safe". First, I conducted a test where 10 threads accessed and added information to see if there was concurrency. Initially, I tested an unsynchronized list, and in this case, it was expected to have concurrency issues, which indeed happened. Then, I applied a synchronized list and the problem was resolved. Here is the code for the test (If you think it can be improved, any suggestions would be greatly appreciated).
Test Case:
//Arrange
SortedList<int> list = new();
var synchronizedList = list.Synchronized();
var expected = new SortedList<int> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int len = 10;
ParallelOptions options = new()
{
MaxDegreeOfParallelism = len
};
//Act
Parallel.For(0, len, options, synchronizedList.Add);
//Asserts
Assert.Equal(len, list.Count);
Assert.Equal(expected, list);
In this case, there was no issue; everything worked as expected. The problem arises when I want to create the typical concurrency example, where N threads are created and they increase a value N times. In this example, there must be concurrency without fail. So, I prepared a small test case to verify if it can handle such a problem. Here is the code:
Test Case 2:
//Arrange
SortedList<int> list = new()
{
0
};
var synchronizedList = list.Synchronized();
int len = 2, maxIter = 1;
ParallelOptions options = new()
{
MaxDegreeOfParallelism = len
};
//Act
Parallel.For(0, len, options, i =>
{
for (int j = 0; j != maxIter; ++j)
{
synchronizedList[0]++;
}
});
//Asserts
Assert.Equal(maxIter * len, list[0]);
When I tested the test case, for some strange reason, the expected result was 2 (I initially tested with 10,000 iterations and 10 threads). However, it was giving me 1. Perplexed, I went to check the code for the issue, but I didn't see any. Here is the code snippet of the indexer in the Wrapper class:
Index:
public T this[int index]
{
get
{
lock (_lock)
{
return _sortedList[index];
}
}
set
{
lock (_lock)
{
_sortedList[index] = value;
}
}
}
As we can see, i have the lock, so it accesses safely. In fact, I did a debug test, and in that case, it passes the test. After this, I went to the code where I initialize the _lock.
Constructor:
internal SynchronizedSortedList(SortedList<T> sortedList)
{
_sortedList = sortedList;
_lock = _sortedList.SyncRoot;
}
After verifying that everything was "fine", I proceed to the get method of SyncRoot in the SortedList class.
SyncRoot:
public object SyncRoot
{
get
{
if (_syncRoot == null)
{
Interlocked.CompareExchange<object>(ref _syncRoot, new object(), null);
}
return _syncRoot;
}
}
In theory, everything is fine. In fact, I went to check the source code of a much earlier version of the List class, and I saw that it had it the same way. Therefore, there shouldn't be any issues. Finally, I will show the Synchronized method.
Synchronized:
public ISortedList<T> Synchronized()
{
return new SynchronizedSortedList(this);
}
One obvious way to fix it would be as follows:
//Arrange
SortedList<int> list = new()
{
0
};
var synchronizedList = list.Synchronized();
int len = 2, maxIter = 1;
ParallelOptions options = new()
{
MaxDegreeOfParallelism = len
};
//Act
Parallel.For(0, len, options, i =>
{
for (int j = 0; j != maxIter; ++j)
{
lock(list.SyncRoot)
{
synchronizedList[0]++;
}
}
});
//Asserts
Assert.Equal(maxIter * len, list[0]);
In this way, it would work excellently, but it's not the way I want to do it because this Wrapper already has locks that protect the resource to prevent threads from accessing it and avoid concurrency. If someone could help me, I would greatly appreciate it because I've been dealing with this problem since yesterday and I can't think of much. Greetings.
It's a very long code, but I can provide the link to the integration test on GitHub, and here is the code for SortedList with the Wrapper.
Your problem is that, in the following code, synchronizedList[0]++ is not thread safe and atomic:
Parallel.For(0, len, options, i =>
{
for (int j = 0; j != maxIter; ++j)
{
// The following is not thread safe:
synchronizedList[0]++;
}
});
That's because synchronizedList[0]++ performs the following actions:
The getting and setting are atomic but the overall sequence is not. Thus threads could interrupt and contend with each other. E.g. thread #1 gets a value, thread #2 gets the same value, thread #2 sets back its incremented value, then thread #1 sets back its incremented value. In such a case the value will be incremented only once -- which is exactly what you are seeing.
The correct fix for this is to make the increment atomic -- which is precisely your obvious way to fix it:
Parallel.For(0, len, options, i =>
{
for (int j = 0; j != maxIter; ++j)
{
lock(list.SyncRoot)
{
synchronizedList[0]++;
}
}
});
Notes:
As currently implemented, your SortedList<T> actually reindexes the list inside its setter. I can't really recommend this approach as it could lead to surprising results.
For instance, imagine you have a SortedList<int> with two zero values instead of one and increment the first value like so:
SortedList<int> list = new() { 0, 0 };
list[0]++;
Then the value of list[0] will be 0 not 1, because the incremented value will have been moved to the end of the list.
The fact that there's no obvious way to integer-index a sorted collection explains why SortedSet<T>, SortedList<TKey,TValue> and the old SortedList do not implement IList or IReadOnlyList<T>.
In general writing correct thread-safe code without locks is very hard. You might take a look at Eric Lippert's articles on thread safety, particularly Can I skip the lock when reading an integer?, which wraps up with:
Code which avoids locks is extremely difficult to reason about, so make your life easier: if you can, don’t write shared memory code to begin with. If you have to, use locks consistently.
(Emphasis his.) Jon Skeet's Volatility, Atomicity and Interlocking is also worth a look.
The fact that the increment operator is not atomic is why Interlocked.Increment() needs to exist. It isn't useful to you however. Since your setter currently reindexes the list merely incrementing a value atomically would not be sufficient.