Consider improving FrozenSet for byte/char

Open
#110,783 2 comments 9 reactions 1 assignee View on GitHub

@MihaZupan is already working on this.

Since Dec 19, 2024.

Assessment

This issue has not been assessed yet.

Description

area-System.Collections in-pr tenet-performance

FrozenSet<T> is the go-to option if you have an arbitary set of values and just need to do a bunch of Contains(T) queries.
Now that SearchValues<T> is a thing, I've seen the question posed a few times of whether one should use that instead, as it also has a Contains(T).

Currently for the best performance you'd want to use FrozenSet for everything except byte/char, where SearchValues will do a better job.
SearchValues<string>.Contains on the other hand is strictly worse as we're just backing it with a HashSet<string>.

We should consider improving FrozenSet to be as good as SearchValues for these two types to make the decision/recommendations easy.

(part of the issue is also that existing docs on SearchValues don't make it obvious that the point of the type is to use it with extension methods on spans)

In practice the interesting cases here IMO are:

  • using a bitmap when all the values are ASCII
  • consider borrowing the perfect-hash O(1) lookup that doesn't need to walk over entries to confirm matches.
Dominant language
C#
Stars
18.3k
Forks
5.6k
PR metrics pending

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from dotnet/runtime

All issues in dotnet/runtime

Similar issues

More C# issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.