dotnet / dotnet/runtime

Investigate load factor and size tuning strategy of Frozen collections

Open
#126,205 2 comments 0 reactions 0 assignees View on GitHub
area-System.Collections help wanted tenet-performance
Dominant language
C#
Stars
18.3k
Forks
5.6k
PR merge metrics
PR metrics pending

Description

Per discussion here https://github.com/dotnet/runtime/pull/125939#issuecomment-4122651329 the FrozenDictionary/FrozenSet have a couple points to investigate

1) Perf measurements at various sizes and key types found no measurable difference in lookup speeds with and without the size tuning loop. This is the code that tries different primes to reduce the collision rate.

> Result: zero measurable difference for FrozenSet, FrozenDictionary, and FrozenDictionary at sizes 1K–500K. This is expected: the tuning loop tries to push collision rate below 5%, but the birthday problem makes this mathematically impossible at medium+ sizes. With MaxLargeBucketTableMultiplier=3, the best achievable collision rate at 100K entries is ~14.5% (N²/2M with M=3N). The loop exhausts its search range and falls back to the starting prime anyway.

2) Related and same area of code. investigate intermediate load factors. We know 1.0 is worse than the 0.5 it chooses (at least up until the 3.5M hashcode threshold where it drops to 1.0)

> We tested LF ~0.5 and LF ~1.0 but not values in between. An intermediate LF like ~0.75 (~1.33N buckets) would save ~33% memory vs 0.5 while only 53% of buckets have chains (vs 39% at 0.5). The regression might be small enough to accept for the memory savings.

No urgency to investigate these, it works perfectly well. Any investigation will have to benchmark different strategies thoroughly to give confidence in whether to make any change. That would include key types, collision rates, sizes, load factors, with and without the tuning. (Being frozen, at least there's only two metrics that matter: construction time to a small extent, and lookup time. And a distant secondary priority: memory usage. No mutation to benchmark.)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.