Avoid bloom filter checks for IndexOfAnyExcept in ProbabilisticMap#85203
Avoid bloom filter checks for IndexOfAnyExcept in ProbabilisticMap#85203stephentoub merged 1 commit intodotnet:mainfrom
Conversation
|
Tagging subscribers to this area: @dotnet/area-system-buffers Issue DetailsThe point of For an input value that isn't in the set, the bloom filter will save us from doing the verification step, but that will by definition happen only once per This PR avoids doing those bloom filter checks for
In practice
|
3d1f79d to
d590107
Compare
The point of
ProbabilisticMapis to avoid doing expensivevalues.Contains(char)checks for every input character by applying a bloom filter first. This works well forIndexOfAny, but withIndexOfAnyExceptwe still have to check each character since we don't have an "inverse bloom filter".For an input value that isn't in the set, the bloom filter will save us from doing the verification step, but that will by definition happen only once per
IndexOfAnyExceptcall. The overhead of checking it for all the characters that are in the set is wasted.This PR avoids doing those bloom filter checks for
IndexOfAnyExceptpaths.In practice
IndexOfAnyExceptinIndexOfAnyCharValuesProbabilisticnow isn't doing anything interesting with theProbabilisticMap, but that's just a convenient place to share some of the logic thatProbabilisticMapneeds anyway.