Order-preserving CommonDictionaryStorage - #1908
Conversation
Sorry, something went wrong.
|
Oh, it is not simple code. Looking at the diffs on GitHub I can't see how the thread safety is ensured without locking. I'll have to check it out locally. |
Sorry, something went wrong.
I don't think I altered the locking strategy that was currently in place, however now that I look at it I think switching _buckets to a List<Bucket> might have broken it... Anyway, I need to review this myself since I wrote it two years ago and am a bit foggy on the details. But I would still appreciate a review if you feel like providing one. Side note, net6.0.CPython.test_keyword has been failing intermittently on macOS during Azure CI. I was going to blame a concurrency issue, but it's already annotated with NotParallelSafe=true. I haven't been able to reproduce it (and it's unclear why it would only occur on the mac). |
Sorry, something went wrong.
BCSharp
left a comment
There was a problem hiding this comment.
Well, unfortunately, I think the way it currently is, it is not thread-safe. The main challenge is because of the change from one structure containing data (Bucket[] _buckets) to two (int[] _indices and List<Bucket> _buckets). What was before an atomic operation on _buckets, now is sometimes split into two that are not atomic.
For instance, the call TryGetValue(_buckets, key, out value) would atomically grab field _buckets, and as long as operations that may disrupt readers were done on a new array, which then would be atomically assigned to the field, things were fine.
Now, the call TryGetValue(_indices, _buckets, key, out value) grabs two fields: _indices and _buckets in indeterminate order, that may not be in sync witch each other.
There are various ways of handling it; in my edit suggestions I propose the way based on the following rules:
- There is never a situation that _indices point to some bucket that does not exist. The opposite is OK - there may be a bucket that is not indexed yet.
- If something is added, it is first added to _buckets, and only after to _indices.
- If something is removed, it is first removed from _indices, only then from _buckets, and not really removed but marked as DUMMY/Bucket.Removed.
- List _buckets never gets shorter (except for Clear() - special case).
- If both _indices and _buckets have to be replaced by new objects (e.g. to shorten them like in Clear()), it is done in a predictable order to ensure Rule 1 is always satisfied.
- If they are reset, _indices are reset first, then _buckets.
- If they are read, _buckets are read first, then _indices.
Rule 2 is to ensure that we never get _indices that refer to _buckets that are not (or no longer) around. In other words, if we get a torn read of _indices and _buckets for the lookup, it is always new _indices and old _buckets.
To ensure proper ordering, Thread.MemoryBarrier() was needed in more places than before.
In my code suggestions I tried to demonstrate what I mean by all this. I hope I got all the relevant places, but don't take my word for it.
Sorry, something went wrong.
| => TryGetValue(_indices, _buckets, key, out value); | ||
|
|
||
| /// <summary> | ||
| /// Static helper to try and get the value from the dictionary. |
There was a problem hiding this comment.
Not static anymore.
Sorry, something went wrong.
| /// Used so the value lookup can run against a buckets while a writer | ||
| /// replaces the buckets. |
There was a problem hiding this comment.
This description seems obsolete.
Sorry, something went wrong.
| // we need to clone the buckets so any lock-free readers will only see | ||
| // the old buckets which are homogeneous | ||
| _buckets = (Bucket[])_buckets.Clone(); | ||
| _indices = (int[])_indices.Clone(); |
There was a problem hiding this comment.
| _indices = (int[])_indices.Clone(); | |
| _buckets = new List<Bucket>(_buckets); |
Sorry, something went wrong.
| _indices = new int[(int)(size / Load) + 1]; | ||
| _indices.AsSpan().Fill(FREE); |
There was a problem hiding this comment.
| _indices = new int[(int)(size / Load) + 1]; | |
| _indices.AsSpan().Fill(FREE); | |
| var newIndices = new int[(int)(size / Load) + 1]; | |
| newIndices.AsSpan().Fill(FREE); | |
| _indices = newIndices; |
Sorry, something went wrong.
| indices[pair.Key] = buckets.Count; | ||
| buckets.Add(bucket); | ||
| _count++; |
There was a problem hiding this comment.
| indices[pair.Key] = buckets.Count; | |
| buckets.Add(bucket); | |
| _count++; | |
| _count++; | |
| buckets.Add(bucket); | |
| Thread.MemoryBarrier(); | |
| indices[pair.Key] = buckets.Count; |
Sorry, something went wrong.
| _indices[pair.Key] = DUMMY; | ||
| _buckets[pair.Value] = Bucket.Removed; | ||
| Thread.MemoryBarrier(); |
There was a problem hiding this comment.
| _indices[pair.Key] = DUMMY; | |
| _buckets[pair.Value] = Bucket.Removed; | |
| Thread.MemoryBarrier(); | |
| _indices[pair.Key] = DUMMY; | |
| Thread.MemoryBarrier(); | |
| _buckets[pair.Value] = Bucket.Removed; |
Sorry, something went wrong.
| public override bool TryGetValue(object key, out object value) | ||
| => TryGetValue(_indices, _buckets, key, out value); |
There was a problem hiding this comment.
| public override bool TryGetValue(object key, out object value) | |
| => TryGetValue(_indices, _buckets, key, out value); | |
| public override bool TryGetValue(object key, out object value) { | |
| var buckets = _buckets; | |
| Thread.MemoryBarrier(); | |
| var indices = _indices; | |
| return TryGetValue(indices, buckets, key, out value); | |
| } |
Sorry, something went wrong.
| _indices = new int[8]; | ||
| _indices.AsSpan().Fill(FREE); | ||
| _buckets.Clear(); |
There was a problem hiding this comment.
_buckets.Clear() is not enough. A new list object is needed not to mess up readers in progress.
| _indices = new int[8]; | |
| _indices.AsSpan().Fill(FREE); | |
| _buckets.Clear(); | |
| var newIndices = new int[InitialBucketSize]; | |
| newIndices.AsSpan().Fill(FREE); | |
| _indices = newIndices; | |
| Thread.MemoryBarrier(); | |
| _buckets = new List<Bucket>(); |
Sorry, something went wrong.
When I looked at the error messages from the failing test, it surely looked like a typical example of a concurrent execution of a test that is clearly not parallel-safe: the test creates a test file with a fixed name, uses it, and then deletes it. The error was "file not found" when trying to use the test file. It is exactly the same cause in all failures of test_keyword that I looked into. If I had to guess, I'd say that the mechanism intended to protect tests marked as NotParallelSafe is not working as intended. Why it is happening intermittently, and why only on some OS and some instances could have been a pure incidental timing issue. |
Sorry, something went wrong.
Cherry-picked my PR for 3.6. It's a nice feature to have so why not include it in 3.4...