Skip to content

Consider improving FrozenSet for byte/char #110783

@MihaZupan

Description

@MihaZupan

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.

Metadata

Metadata

Assignees

Labels

area-System.Collectionsin-prThere is an active PR which will close this issue when it is mergedtenet-performancePerformance related issue

Type

No type

Projects

No projects

Relationships

None yet

Development

No branches or pull requests

Issue actions