-
Notifications
You must be signed in to change notification settings - Fork 4.6k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Non-blocking ConcurrentDictionary #50337
Closed
Closed
Changes from 11 commits
Commits
Show all changes
12 commits
Select commit
Hold shift + click to select a range
cab5fbe
initial port
VSadov 0f4a468
a few cleanups, some comments
VSadov 9c1e158
valueFactory vaidation gone missing after refactoring
VSadov 9ebcd6a
Disable NullableAttributesOnPublicApiOnly test for now. Not sure what…
VSadov 60e04ba
a few minor cleanups after porting.
VSadov 769bbf6
ContainsKey does not need the value
VSadov d964a8c
remove use of GetTypeInfo
VSadov a7c2923
some refactoring
VSadov 022114f
a few changes based on the benchmark results
VSadov ae40c9c
fix after rebasing onto main
VSadov 7736b4b
tweak Etw tests for AcquiringAllLocksEventId, since no locks are ever…
VSadov a86ab16
use nuint when computing counter stripe index
VSadov File filter
Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1,522 changes: 308 additions & 1,214 deletions
1,522
...s/System.Collections.Concurrent/src/System/Collections/Concurrent/ConcurrentDictionary.cs
Large diffs are not rendered by default.
Oops, something went wrong.
213 changes: 213 additions & 0 deletions
213
...ns.Concurrent/src/System/Collections/Concurrent/ConcurrentDictionary/Counter/Counter32.cs
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,213 @@ | ||
// Licensed to the .NET Foundation under one or more agreements. | ||
// The .NET Foundation licenses this file to you under the MIT license. | ||
|
||
using System; | ||
using System.Collections.Generic; | ||
using System.Diagnostics; | ||
using System.Runtime.CompilerServices; | ||
using System.Runtime.InteropServices; | ||
using System.Threading; | ||
|
||
#nullable disable | ||
|
||
namespace System.Collections.Concurrent | ||
{ | ||
/// <summary> | ||
/// Scalable 32bit counter that can be used from multiple threads. | ||
/// </summary> | ||
internal sealed class Counter32: CounterBase | ||
{ | ||
private class Cell | ||
{ | ||
[StructLayout(LayoutKind.Explicit, Size = CACHE_LINE * 2 - OBJ_HEADER_SIZE)] | ||
public struct SpacedCounter | ||
{ | ||
[FieldOffset(CACHE_LINE - OBJ_HEADER_SIZE)] | ||
public int count; | ||
} | ||
|
||
public SpacedCounter counter; | ||
} | ||
|
||
// spaced out counters | ||
private Cell[] cells; | ||
|
||
// default counter | ||
private int count; | ||
|
||
// delayed estimated count | ||
private int lastCount; | ||
|
||
/// <summary> | ||
/// Initializes a new instance of the <see | ||
/// cref="Counter32"/> | ||
/// </summary> | ||
public Counter32() | ||
{ | ||
} | ||
|
||
/// <summary> | ||
/// Returns the value of the counter at the time of the call. | ||
/// </summary> | ||
/// <remarks> | ||
/// The value may miss in-progress updates if the counter is being concurrently modified. | ||
/// </remarks> | ||
public int Value | ||
{ | ||
get | ||
{ | ||
var count = this.count; | ||
var cells = this.cells; | ||
|
||
if (cells != null) | ||
{ | ||
for (int i = 0; i < cells.Length; i++) | ||
{ | ||
var cell = cells[i]; | ||
if (cell != null) | ||
{ | ||
count += cell.counter.count; | ||
} | ||
else | ||
{ | ||
break; | ||
} | ||
} | ||
} | ||
|
||
return count; | ||
} | ||
} | ||
|
||
/// <summary> | ||
/// Returns the approximate value of the counter at the time of the call. | ||
/// </summary> | ||
/// <remarks> | ||
/// EstimatedValue could be significantly cheaper to obtain, but may be slightly delayed. | ||
/// </remarks> | ||
public int EstimatedValue | ||
{ | ||
get | ||
{ | ||
if (this.cells == null) | ||
{ | ||
return this.count; | ||
} | ||
|
||
var curTicks = (uint)Environment.TickCount; | ||
// more than a millisecond passed? | ||
if (curTicks != lastCountTicks) | ||
{ | ||
lastCountTicks = curTicks; | ||
lastCount = Value; | ||
} | ||
|
||
return lastCount; | ||
} | ||
} | ||
|
||
/// <summary> | ||
/// Increments the counter by 1. | ||
/// </summary> | ||
public void Increment() | ||
{ | ||
int curCellCount = this.cellCount; | ||
var drift = increment(ref GetCountRef(curCellCount)); | ||
|
||
if (drift != 0) | ||
{ | ||
TryAddCell(curCellCount); | ||
} | ||
} | ||
|
||
/// <summary> | ||
/// Decrements the counter by 1. | ||
/// </summary> | ||
public void Decrement() | ||
{ | ||
int curCellCount = this.cellCount; | ||
var drift = decrement(ref GetCountRef(curCellCount)); | ||
|
||
if (drift != 0) | ||
{ | ||
TryAddCell(curCellCount); | ||
} | ||
} | ||
|
||
/// <summary> | ||
/// Increments the counter by 'value'. | ||
/// </summary> | ||
public void Add(int value) | ||
{ | ||
int curCellCount = this.cellCount; | ||
var drift = add(ref GetCountRef(curCellCount), value); | ||
|
||
if (drift != 0) | ||
{ | ||
TryAddCell(curCellCount); | ||
} | ||
} | ||
|
||
[MethodImpl(MethodImplOptions.AggressiveInlining)] | ||
private ref int GetCountRef(int curCellCount) | ||
{ | ||
ref var countRef = ref count; | ||
|
||
Cell[] cells; | ||
if ((cells = this.cells) != null && curCellCount > 1) | ||
{ | ||
var cell = cells[GetIndex((uint)curCellCount)]; | ||
if (cell != null) | ||
{ | ||
countRef = ref cell.counter.count; | ||
} | ||
} | ||
|
||
return ref countRef; | ||
} | ||
|
||
private static int increment(ref int val) | ||
{ | ||
return -val - 1 + Interlocked.Increment(ref val); | ||
} | ||
|
||
private static int add(ref int val, int inc) | ||
{ | ||
return -val - inc + Interlocked.Add(ref val, inc); | ||
} | ||
|
||
private static int decrement(ref int val) | ||
{ | ||
return val - 1 - Interlocked.Decrement(ref val); | ||
} | ||
|
||
private void TryAddCell(int curCellCount) | ||
{ | ||
if (curCellCount < s_MaxCellCount) | ||
{ | ||
TryAddCellCore(curCellCount); | ||
} | ||
} | ||
|
||
[MethodImpl(MethodImplOptions.NoInlining)] | ||
private void TryAddCellCore(int curCellCount) | ||
{ | ||
var cells = this.cells; | ||
if (cells == null) | ||
{ | ||
var newCells = new Cell[s_MaxCellCount]; | ||
cells = Interlocked.CompareExchange(ref this.cells, newCells, null) ?? newCells; | ||
} | ||
|
||
if (cells[curCellCount] == null) | ||
{ | ||
Interlocked.CompareExchange(ref cells[curCellCount], new Cell(), null); | ||
} | ||
|
||
if (this.cellCount == curCellCount) | ||
{ | ||
Interlocked.CompareExchange(ref this.cellCount, curCellCount + 1, curCellCount); | ||
} | ||
} | ||
} | ||
} |
Oops, something went wrong.
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
❔ Is 'stale' a better word choice here? Concern is the reader could interpret "slightly delayed" to mean "slower to return". Stale has its own downsides (e.g. is it eventually consistent?) so would leave the call to y'all.