Repository navigation
FrozenDictionary is incorrectly case sensitive in some cases #93974
Description
Description
When optimizing a FrozenDictionary in KeyAnalyzer we look for the possibility to use case sensitive string comparison on a substring which is ascii and does not have letters (canSwitchIgnoreCaseToCaseSensitive).
The problem is that since analysis.IgnoreCase is false, we choose certain classes like OrdinalStringFrozenDictionary_LeftJustifiedSubstringCaseInsensitive, OrdinalStringFrozenDictionary_LeftJustifiedSingleChar etc.
These classes implement Equals as follows:
private protected override bool Equals(string? x, string? y) => string.Equals(x, y);
The above implementation ignores the original comparer and assumes case sensitivity.
When TryGetValue is called, it uses Equals which thus uses case sensitive comparison as described above.
The 'naive' solution is obvious - change Equals to be
private protected override bool Equals(string? x, string? y) => Comparer.Equals(x, y);
However (and this is where I'm guessing) - this has a pretty detrimental performance problem in that Equals will no longer be aggressively inlined into SequenceEquals. If (and it's a big IF) this is shown to be correct, then we are left with the following options which I can think of:
- Create another class
OrdinalStringFrozenDictionary_FullCaseSensitiveHashButCaseInsensitiveEquals - Stop calculating
canSwitchIgnoreCaseToCaseSensitive.
As .NET 8 is about to launch and the cutoff for new development has long passed, I would suggest (2) as the immediate change. I am happy to verify my assumptions about using comparer and submit a PR with tests.
I am also happy to implement the immediate fix, however I'd need to know which branch since I assume we want this to be patched into .NET 8.
As for. NET 9, I (or anybody else) can find time to implement (1) it shouldn't be that hard without the time pressure.
Reproduction Steps
using System.Collections.Frozen;
using static System.Console;
var dictionary1 = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase)
{
{"1xxx", 1},
{"2xxx", 2},
{"3xxx", 3},
{"4xxx", 4},
{"5xxx", 5},
{"6xxx", 6},
{"7xxx", 7},
{"8xxx", 8},
{"9xxx", 9}
};
var frozen1 = dictionary1.ToFrozenDictionary(StringComparer.OrdinalIgnoreCase);
WriteLine("Dictionary1 Upper: " + dictionary1.TryGetValue("1XXX", out _));
WriteLine("Dictionary1 Lower: " + dictionary1.TryGetValue("1xxx", out _));
WriteLine("FrozenDictionary1 Upper: " + frozen1.TryGetValue("1XXX", out _));
WriteLine("FrozenDictionary1 Lower: " + frozen1.TryGetValue("1xxx", out _));
WriteLine("FrozenDictionary1 Type: " + frozen1.GetType());Expected behavior
FrozenDictionary1 Upper: True
Actual behavior
Results:
Dictionary1 Upper: True
Dictionary1 Lower: True
FrozenDictionary1 Upper: False
FrozenDictionary1 Lower: True
FrozenDictionary1 Type: System.Collections.Frozen.OrdinalStringFrozenDictionary_LeftJustifiedSingleChar`1[System.Int32]
Regression?
No - this is a new feature and we are probably in time to fix.
Known Workarounds
No response
Configuration
8.0.0-rc.1.23419.4
Looking at source code 1 week old tells me the bug is still there.
Other information
I haven't looked at the code for FrozenSet but a quick test shows me it's got the same bug.
Also side note API design complaint... It's very misleading that the following intentionally returns a case sensitive dictionary but I'm guessing there was a good reason to make that decision.
var dictionary = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase)
{
{"1xxx", 1},
{"2xxx", 2}
};
var frozen = dictionary.ToFrozenDictionary();
Activity
andrewjsaid commentedon Oct 25, 2023
On my branch I attempted to do the naive change:
And ended up with the following. Not nice.
Editor's note: turns out I forgot to copy all benchmarks and confirm which table this is for, but based on the fact that
SubstringFrozenDictionarycomes last I assume it's that one for the below. We should probably double check if this is important.eiriktsarpalis commentedon Oct 26, 2023
Good catch, we should try to service a fix in .NET 8. FYI @adamsitnik @stephentoub
Fix incorrect case sensitivity in FrozenDictionary and FrozenSet for …
Disable optimization which sometimes results in incorrect case sensit…