[API Proposal]: Dictionary<TKey, TValue>.KeysCollection.Contains

[stephentoub]

Background and motivation

Dictionary<TKey, TValue>.Keys returns a Dictionary<TKey, TValue>.KeysCollection. This type implements ICollection<TKey> and has an efficient implementation of ICollection<TKey>.Contains... but it's explicitly implemented. That means if you do:

Dictionary<TKey, TValue> d = ...;
...
if (d.Keys.Contains(...)) { ... }

you end up invoking Enumerable.Contains. This does a dynamic check for ICollection and delegates to it, but that's still unnecessary overhead. We can easily fix this by making KeysCollection.Contains public / implicitly implemented.

API Proposal

namespace System.Collections.Generic;

public class Dictionary<TKey, TValue>
{
    public sealed class KeyCollection
    {
-        bool ICollection<TKey>.Contains(TKey item)
+        public bool Contains(TKey item);
    }
}

public class SortedDictionary<TKey, TValue>
{
    public sealed class KeyCollection
    {
-        bool ICollection<TKey>.Contains(TKey item)
+        public bool Contains(TKey item);
    }
}

API Usage

if (dictionary.Keys.Contains(...))

Alternative Designs

No response

Risks

No response

[ghost]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

Dictionary<TKey, TValue>.Keys returns a Dictionary<TKey, TValue>.KeysCollection. This type implements ICollection<TKey> and has an efficient implementation of ICollection<TKey>.Contains... but it's explicitly implemented. That means if you do:

Dictionary<TKey, TValue> d = ...;
...
if (d.Keys.Contains(...)) { ... }

you end up invoking Enumerable.Contains. We can easily fix this by making KeysCollection.Contains public / implicitly implemented.

API Proposal

namespace System.Collections.Generic;

public class Dictionary<TKey, TValue>
{
    public sealed class KeyCollection
    {
-        bool ICollection<TKey>.Contains(TKey item)
+        public bool Contains(TKey item);
    }
}

API Usage

if (dictionary.Keys.Contains(...))

Alternative Designs

No response

Risks

No response

Author:	stephentoub
Assignees:	-
Labels:	api-suggestion, area-System.Collections
Milestone:	8.0.0

[eiriktsarpalis]

SGTM

[tfenise]

Shouldn't we encourage calling Dictionary<TKey,TValue>.ContainsKey rather than optimize Dictionary<TKey, TValue>.KeysCollection.Contains?

[stephentoub]

Shouldn't we encourage calling Dictionary<TKey,TValue>.ContainsKey rather than optimize Dictionary<TKey, TValue>.KeysCollection.Contains?

We do; there's an analyzer that does exactly that (https://learn.microsoft.com/dotnet/fundamentals/code-analysis/quality-rules/ca1841). Doesn't mean we shouldn't fix Contains as well, especially when all it takes to fix it is changing its visibility.

[tfenise]

I guess originally it was made private intentionally to prevent people from calling it, but later LINQ came...

[tfenise]

you end up invoking Enumerable.Contains. This does a dynamic check for ICollection and delegates to it, but that's still unnecessary overhead.

https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBDAzgWwB8ABAJgEYBYAKGIAYACY8lAbhvqfIDoAZASwB2AR3bUOAZiakGAYQYBvGgxVMpxFAwCy5ABQARfmAz8Ig7FACeAHiEY0DOwD4GAEyMBKBgF4X7sNwA0jCWuNyyZhjYQri65B5iqgzKqsTqmlqkBkYmZhY2dg7Obp4+Lrq6AJIRADY1MMamgraCGE4e/kEhuB7hkdGCsfFiAL40QA
It seems that the JIT is able to inline Enumerable.Contains and eliminate the dynamic check for ICollection. Probably the JIT will do better (eliminate the extra branch), and there will be no difference between the codegen of public void M1(Dictionary<int, int> dic) => dic.Keys.Contains(1);(going through LINQ) and public void M2(Dictionary<int, int> dic) => ((ICollection<int>)dic.Keys).Contains(1);.

[stephentoub]

What is your objection to making the existing method (that's there and that has to be there) just be public?

Today (.NET 7) they are not the same:

[Benchmark(Baseline = true)]
public bool Contains1() => _dict.Keys.Contains(42);

[Benchmark]
public bool Contains2() => ((ICollection<int>)_dict.Keys).Contains(42);

Method	Mean	Ratio	Code Size
Contains1	2.715 ns	1.00	465 B
Contains2	2.344 ns	0.86	437 B

and even if in the future it could make them the same there are still downsides, such as having to carry around System.Linq.dll and load it even if it's not otherwise needed, not being able to trim it out of an app if it's not otherwise needed, having the JIT have to do more work to inline Enumerable.Contains in order to optimize it away, and so on.

[tfenise]

In Intellisense, the extension method Dictionary<TKey, TValue>.KeysCollection.Contains has a different icon than an ordinary instance method like ICollection<TKey, TValue>.Contains. It acts as a signal that the extension method may not be optimal and tells the developer that maybe they should try something else, like Dictionary<TKey, TValue>.ContainsKey. Yes, this benefit of keeping Dictionary<TKey, TValue>.KeysCollection.Contains private may seem slight, and may be redundant as there is an analyzer, but the performance improvement is also slight, at least with future JIT improvements. Maybe it's worth it, maybe it's not. I don't really have a strong opinion.

[stephentoub]

We already have such a signal: we have an analyzer that's on by default (info/suggestion) that tells you explicitly to use ContainsKey instead.

If this were expensive, I'd agree with you. But this costs almost nothing to fix. Our conversation is already more investment than making the change would cost. It's not even a new method; the method already exists, and has to exist in support of the interface.

[terrajobst]

Video

• Looks good as proposed
  • We should also apply that to ReadOnlyDictionary<TKey, TValue>
  • We should ensure the existing analyzer does the right thing with these changes.

namespace System.Collections.Generic;

public class Dictionary<TKey, TValue>
{
    public sealed class KeyCollection
    {
-        bool ICollection<TKey>.Contains(TKey item)
+        public bool Contains(TKey item);
    }
}

public class SortedDictionary<TKey, TValue>
{
    public sealed class KeyCollection
    {
-        bool ICollection<TKey>.Contains(TKey item)
+        public bool Contains(TKey item);
    }
}

[eiriktsarpalis]

We should also apply that to ReadOnlyDictionary<TKey, TValue>

public class SortedDictionary<TKey, TValue>

@terrajobst are we making the change to ReadOnlyDictionary, SortedDictionary or both?