dotnet / dotnet/runtime

[Regression] ConditionalWeakTable.Add/Remove scales as O(n) on .NET Core when acting on same key

Open
#130,215 4 comments 0 reactions 0 assignees View on GitHub
area-System.Runtime tenet-performance
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.

Image

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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.