Runtime: Fast Dictionary<K,V>.Clone() api

[benaadams]

Background and Motivation

There isn't a fast way to copy a Dictionary, either for snapshotting https://github.com/dotnet/roslyn/pull/47503#issuecomment-687917289; or where its mostly entirely read only with an occasional write where updating it via cloning + adds and then switching the dictionary reference would allow a lock free read path that may be more suitable than switching to a ConcurrentDictionary.

Roslyn currently uses .ToImmutableDictionary https://github.com/dotnet/roslyn/pull/47503#issuecomment-688046501 for snapshotting which is quite expensive, when a fast .Clone and readonly wrapper would be more suitable (as its snapshots)

Proposed API

namespace System.Collections.Generic
{
    public static class DictionaryExtensions
    {
        public static Dictionary<TKey, TValue> Clone<TKey, TValue>(this Dictionary<TKey, TValue> source) where TKey : notnull
    }
}

Usage Examples

For lockless reads, with very infrequent updates (where reallocating the entire dictionary is more lightweight than taking a lock on every read, or using ConcurrentDictionary)
``` C#
class LookupTable
{
private Dictionary? _lookUp;
private readonly object _lock = new ();

public bool TryGetValue(int key, [MaybeNullWhen(false)] out string value)
{
    // No locks required for read
    var lookUp = _lookUp;
    if (lookUp is null)
    {
        value = default;
        return false;
    }

    return lookUp.TryGetValue(key, out value);
}

public void Add(int key, string value)
{
    lock (_lock)
    {
        // Clone + Add
        var dict = _lookUp?.Clone() ?? new (capacity: 1);
        dict.Add(key, value);
        // Switch reference
        _lookUp = dict;
    }
}

public void AddRange(IEnumerable<KeyValuePair<int, string>> collection)
{
    lock (_lock)
    {
        // Clone + Add
        var dict = _lookUp?.Clone() ?? new(capacity: 8);
        foreach (var entry in collection)
        {
            dict.Add(entry.Key, entry.Value);
        }
        // Switch reference
        _lookUp = dict;
    }
}

}

## Alternative Designs
Add to `System.Linq.Enumerable` and add `ToDictionary` overload without having to specify both a `Func<KeyValue<TKey, TElement>, TKey>` keySelector and `Func<KeyValue<TKey, TElement>, TElement>` elementSelector; however `dict.ToDictionary()` seems an unclear way of copying?
```csharp
namespace System.Linq
{
    public static partial class Enumerable
    {
        public static ToDictionary<TKey, TValue> Clone<TKey, TValue>(this Dictionary<TKey, TValue> source) where TKey : notnull
    }
}

Risks

Code bloat

Adding directly to Dictionary as an instance method would cause generic asm code bloat as it would be use for particular dictionaries rather than every dictionary; hence an extension method would be better.

Performance

Currently can copy via foreach on the dictionary with an .Add for each element to an empty (correctly sized) Dictionary or via Linq.Enumerable.ToDictionary; which uses IEnumerable, however these methods are slow as need to reshash and bucket all the elements and second is additionally alocatey.

In order to create a fast Dictionary Clone method it would be better to do it in bulk duplicating its internal arrays, so it would need to be in the same assembly to have access to these internals e.g.

public static class DictionaryExtensions
{
    public static Dictionary<TKey, TValue> Clone<TKey, TValue>(this Dictionary<TKey, TValue> source) where TKey : notnull
    {
        Dictionary<TKey, TValue> dict = new ();
        int[]? buckets = source._buckets;
        if (buckets is not null)
        {
            dict._buckets = new int[buckets.Length];
            buckets.CopyTo(dict._buckets.AsSpan());
        }

        Dictionary<TKey, TValue>.Entry[]? entries = source._entries;
        if (entries is not null)
        {
            dict._entries = new Dictionary<TKey, TValue>.Entry[entries.Length];
            entries.CopyTo(dict._entries.AsSpan());
        }

#if TARGET_64BIT
        dict._fastModMultiplier = source._fastModMultiplier;
#endif
        dict._count = source._count;
        dict._freeList = source._freeList;
        dict._freeCount = source._freeCount;
        dict._version = source._version;
        dict._comparer = source._comparer;

        return dict;
    }
}

[msftbot[bot]]

Tagging subscribers to this area: @eiriktsarpalis, @jeffhandley
See info in area-owners.md if you want to be subscribed.

[stephentoub]

Dictionary already has a public ctor that takes an IDictionary and that special-cases Dictionary. Can't that just be improved?

[benaadams]

Dictionary already has a public ctor that takes an IDictionary and that special-cases Dictionary. Can't that just be improved?

Wait what? How did I miss that 🤣

[benaadams]

Though question on what to do with comparer as it doesn't copy that; so would need to do something like?

var newDict = new Dictionary(dict, dict.Comparer);

Which has complexity with the string comparer switching meaning the Entitys array can't just be copied directly...

[ayende]

If the comparer is different, you have to rehash the values again, so I don't think that this matters.

[benaadams]

Yes, but if you are cloning the dictionary you want the comparer to be the same; however copying the internal comparer is not conveyed by the Dictionary(IDictionary<TKey, TValue> dictionary) and Dictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey>? comparer) constructors?

[stephentoub]

Which has complexity with the string comparer switching meaning the Entitys array can't just be copied directly.

If they're the same instance (or special-cases) they can be. Yes, there's the overhead of the check, but is that prohibitive?

[benaadams]

If they're the same instance (or special-cases) they can be. Yes, there's the overhead of the check, but is that prohibitive?

Not worried about the cost of the check. However if I did this:

var dict = new Dictionary<string, string>(StringComparer.OrdinalIgnoreCase);
var newDict = new Dictionary<string, string>(dict);

dict has an OrdinalIgnoreCase comparer and newDict is an Ordinal comparer; as the comparer is not copied

And Dictionary.Comparer lies about what it's comparer actually is so as to not expose internals (though only for string)

[benaadams]

Added an improvement for that method of copying https://github.com/dotnet/runtime/pull/41944