Runtime: HashSet.GetOrAdd(T)

[jnm2]

There are many times when there is a custom equality comparison being done but I need access to the original instance.

What I'd like:

```c#
var mergedItems = new HashSet();

foreach (var item in items)
{
mergedItems.GetOrAdd(item).RelatedInfo.Add(x);
}

public sealed class Item : IEquatable
{
public DateTime Date { get; }
public int Amount { get; }
public List RelatedInfo { get; }

public bool Equals(Item other) => other != null && other.Date == Date && other.Amount == Amount;

public override bool Equals(object obj) => obj is Item item && Equals(item);

public override int GetHashCode() => // ...

}

Today I'm forced to use a Dictionary which duplicates storage of the key for no reason.
A dictionary is also wasteful because it has to do two hash lookups, one for `TryGetValue` and one for `Add`:
```c#
var mergedItems = new Dictionary<Item, Item>();

foreach (var item in items)
{
    if (!mergedItems.TryGetValue(item, out var otherItem))
        mergedItems.Add(item, otherItem = item);
    otherItem.RelatedInfo.Add(x);
}

This is no better; it's a lot more to maintain, unnecessarily coupled to the definition of equality, it's still duplicate storage of the key, and it's still duplicating the number of hash lookups:
```c#
var mergedItems = new Dictionary<(DateTime, int), Item>();

foreach (var item in items)
{
if (!mergedItems.TryGetValue((item.Date, item.Amount), out var otherItem))
mergedItems.Add((item.Date, item.Amount), otherItem = item);
otherItem.RelatedInfo.Add(x);
}
```

KeyedCollection is the worst of all because in addition to the dictionary, it keeps a list I'll never use.

[jnm2]

Similar to https://github.com/dotnet/corefx/issues/11291 but not exactly a duplicate, since I don't want a generic parameter for the key or any other distinctions between keys and values.

[svick]

Today I'm forced to use a Dictionary which duplicates storage of the key for no reason.

You're not, if you're on .Net Core 2.0, you can use HashSet<T>.TryGetValue() (https://github.com/dotnet/corefx/issues/15691), though it still requires two lookups.

On one hand, the addition of TryGetValue indicates that retrieving a value from a HashSet based on a equal, but distinct value makes sense. On the other hand, it means adding GetOrAdd is less important: it improves performance and convenience, but doesn't add new capabilities.

[jnm2]

Sweet! That was the thread I couldn't find! So implementing GetOrAdd should be a piece of cake. @TylerBrinkley? :D

[danmosemsft]

@jnm2 there is a code size cost to adding new API to commonly instantiated generic types which means there is a higher bar for adding them. Consensus we achieved is here https://github.com/dotnet/corefx/issues/17275#issuecomment-291636863
Given this one could be achieved by an extension method, that might be the most palatable approach.,

[jnm2]

The extension method still has a downside, which is the duplicate hashtable lookup. In that sense, this is a fundamental operation. Too bad it can't be the other way around, other instance methods like Contains as extension methods implemented in terms of the fundamentals.

[TylerBrinkley]

I think this one falls under the first criteria @terrajobst set for #17275 which is

1. CONSIDER making rare methods on generic types extension methods to avoid forcing the code gen to instantiate all these methods

While there is a performance hit of 2 lookups I don't think this method would be used all that much.

[kellypleahy]

If we're going to do this, can we also have a GetOrAdd that takes the factory function? This is something that seems also quite valuable? Also, can we put these on Dictionary<TKey,TValue> (as extension methods) if they don't already exist too? Is there already a ticket for Dictionary<TKey,TValue>?

[danmosemsft]

@jnm2 can you clarify how this is not satisfied by dotnet/runtime#20073 ? I'm missing it.

[jnm2]

@danmosemsft dotnet/runtime#20073 doesn't provide any way to do GetOrAdd without a duplicate hash lookup, that I can see. It enables us to do this, but in the 'add' scenario, there is duplicate work being done in the calls to TryGetValue and Add:

public static T GetOrAdd<T>(this HashSet<T> hashSet, T equalValue)
{
    if (hashSet.TryGetValue(equalValue, out var actualValue))
    {
        return actualValue;
    }

    hashSet.Add(equalValue);
    return equalValue;
}

@TylerBrinkley makes the point above that the performance hit of these duplicate lookups may not be important enough to add the instance method (requiring a bit more JIT time per generic instantiation).

There is indeed precedent for preferring extension methods at the cost of duplicate hash lookups:

https://github.com/dotnet/corefx/blob/b9ce86fbec92349c203a4c33805cffb8ca24c10f/src/System.Collections/src/System/Collections/Generic/CollectionExtensions.cs#L25-L39

However, see the opposite point being made by @jamesqo in the Dictionary.GetOrAdd issue: https://github.com/dotnet/corefx/issues/2877#issuecomment-319244808

[danmosemsft]

Ah yes i forgot we made an extension method. Given that decision it sounds like this issue can be closed?
The cost of growing commonly used generic types is the code size. Dictionary is one of the most sensitive, a small change can grow hello world size significantly.

[jnm2]

@danmosemsft dotnet/runtime#15059 is about Dictionary.GetOrAdd; this one is about HashSet.GetOrAdd. As far as I'm aware there is no extension method for GetOrAdd for either one.

[kellypleahy]

@danmosemsft I'm a bit confused here. Does this really have such a big impact on code size? I think I'd be more worried personally about the performance impact of the second lookup than a tiny bit more code for each generic instantiation, but I guess that's just me (and I guess it really depends on whether people will actually use this instance method on hot code paths). Am I understanding properly that the impact would be an additional JITed function and an additional vtable entry (one each per generic instantiation, not per instance of objects), and the cost to perform the JIT on first use of said function?

[danmosemsft]

@jnm2 my bad, there's of course two asks here, one was "a custom equality comparison being done but I need access to the original instance." which seems now satisfied by HashSet<T>.TryGetValue (as already observed above) and the other is to be able to "GetOrAdd", which as you say is not currently satisfied, although on Dictionary<K,V> there is TryAdd it doesn't return the value.

As for the cost of adding to the type itself (in this case, necessary to avoid dual lookups) it is not the JIT time but the code duplication. Dictionary<K,V> is instantiated many times in a typical app - once for reference types, then once for (I guess - not my area of expertise) each sized value type, and that can add up significantly. So several proposed additions to the type were either abandoned or moved to extension methods (which is unfortunate if like in this case it would be less efficient). I would expect this to be a lesser concern for HashSet since it's presumably instantiated for fewer types.

@jkotas can you remind me of the kind of size increase you were quoting for a reasonably sized method addition to Dictionary?

[jkotas]

can you remind me of the kind of size increase you were quoting for a reasonably sized method addition to Dictionary?

I have been looking at the code size vs. benefit. I do not think I have said a universal number on how much it is ok to add.

[danmosemsft]

I meant, if I add a new 10-20 line method to Dictionary, as a rule of thumb how much does that increase the size of a typical app. I believe you gave a number but I cannot find it.

[eiriktsarpalis]

I feel like we should close this. Given we're going down the CollectionsMarshal route for #15059, we should probably consider a similar approach for HashSet. cc @GrabYourPitchforks