[Regression] ConditionalWeakTable.Add/Remove scales as O(n) on .NET Core when acting on same key
- Dominant language
- C#
- Stars
- 18.3k
- Forks
- 5.6k
- PR merge metrics
- PR metrics pending
Description
### Description
Calling `ConditionalWeakTable.Add`/`ConditionalWeakTable.Remove` with the same key without resizing, clearing, or meaningful quantity of ops on other keys happening in between, causes the performance to grow as O(n) rather than be approximately constant like it is on .NET Framework.
Isolating the other aforementioned factors shows that it grows approximately at the rate `O(RoundUpToPowerOf2(n) - n)` (i.e., scales with the number of free slots).
This can be problematic in scenarios where frequent add/remove can occur with the same key on a CWT that is somewhat large.
Running into this is easy enough if you want to attach a variable number of objects to an object for example; you might use a LinkedList as your value & add/remove to that when it already exists, and remove the list association when done. If you're frequently attaching/detaching based on something that could be prone to giving the same object that may not have died yet a number of times, the performance will get progressively worse (up until any of the aforementioned things happen to occur, or the key dies). In modern .NET we have `DependentHandle` which doesn't run into these issues, but it is a) `unsafe`, b) probably not very commonly used by end-users, and c) not available for anyone targeting .NET Standard 2.0.
### Configuration
```
BenchmarkDotNet v0.15.8, Windows 11 (10.0.26200.8655/25H2/2025Update/HudsonValley2)
AMD Ryzen 9 9900X 4.40GHz, 1 CPU, 24 logical and 12 physical cores
.NET SDK 10.0.301
[Host] : .NET 10.0.9 (10.0.9, 10.0.926.27113), X64 RyuJIT x86-64-v4
.NET 10.0 : .NET 10.0.9 (10.0.9, 10.0.926.27113), X64 RyuJIT x86-64-v4
.NET Framework 4.8 : .NET Framework 4.8.1 (4.8.9325.0), X64 RyuJIT VectorSize=256
```
Should repro on any configuration though.
### Regression?
It takes up to O(n) time in .NET Core; this is a large regression compared to .NET Framework, where it is more or less constant time.
### Data
Note: all numbers are for 1000x add/remove calls on the same key in the steady state.
Benchmark Code
```csharp
using System.Runtime.CompilerServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;
internal class Program
{
private static void Main(string[] args)
{
BenchmarkRunner.Run();
}
}
[SimpleJob(RuntimeMoniker.Net10_0)]
[SimpleJob(RuntimeMoniker.Net48)]
public class Benchmark
{
[Params(1, 10, 100, 1000, 10_000, 100_000, 1_000_000)]
public int N { get; set; }
public object[] _objects = null!;
public object _key = null!;
public object _value = null!;
public ConditionalWeakTable _table = null!;
[GlobalSetup]
public void Setup()
{
_objects = Enumerable.Range(0, N).Select((x) => new object()).ToArray();
_key = new object();
_value = new object();
_table = new ConditionalWeakTable();
for (int i = 0; i < N - 1; i++) _table.Add(_objects[i], new object());
}
[GlobalCleanup]
public void Cleanup()
{
GC.KeepAlive(_objects);
_objects = null!;
_table = null!;
}
[Benchmark]
public void AddRemove1000()
{
for (int i = 0; i < 1000; i++)
{
_table.Add(_key, _value);
_table.Remove(_key);
}
}
}
```
### Analysis
My (and AI's) best guess as to the root cause is that it was introduced in https://github.com/dotnet/runtime/commit/854532c4136a86c06af184dc1234bbcc0df4411a by not releasing the slot immediately, and instead only doing it on resize / clear.
This also lines up with the performance measurements, which show that 1M has similar perf to 100k, which lines up closely since the differences to nearest power of 2 is ~48k vs ~31k, which is ~55% different, and the perf difference betwen ~30.9ms and ~19.6ms is ~57%.
Similarly 19.6ms vs 4.1ms (4.78x) lines up with closely with ~31k vs ~6.4k (4.84x).
/cc @mikernet
Contributor guide
Research direction
Start with ConditionalWeakTable.Add and Remove and compare their current behavior with commit 854532c4136a86c06af184dc1234bbcc0df4411a. Run the supplied BenchmarkDotNet benchmark across the listed N values and runtimes; done means repeated operations on the same key no longer grow with the number of free slots and the regression is covered by appropriate tests.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- csharp
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100