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

@danmosemsft it would be nice if we also made this improvement in DictionarySlim. For specific cache-like use cases we roll our own dictionary and it would be nice to not have to do that.

runtime (Libraries Test Run release coreclr Windows_NT x86 Release) issue #41494

Helix gateway timeout on "runtime (Libraries Test Run release coreclr Windows_NT x86 Release)"

Broken compress variant, but I'm quite impressed there are tests for these scenarios :)

It would be nice to share performance numbers for the different cases.

@danmosemsft it would be nice if we also made this improvement in DictionarySlim. For specific cache-like use cases we roll our own dictionary and it would be nice to not have to do that.

@mjsabby the copy constructor specifically? It would be easy to add if someone would offer a PR.

I am unsure what to do with DictionarySlim. It's encouraging that you're using it, or plan to. That may suggest we should remove the "Experimental" or even put it into the core collections. But @GrabYourPitchforks had concerns about it's "unsafeness" (I think related to mutating the entry in place). Also the name may suggest to people it's optimized for small number of items, which it's not (I happened to just run across @benaadams type with the same name)

The code LGTM. But we don't have evidence that this is a hot path for anybody.

I'm somewhat paranoid that we're going to use this code as a new performance profile, then in the future we'll discover some obscure edge case which means we need to go down a somewhat slower path, then some automated system will kick in and say "Ah, but you regressed this method's performance by 17%!", and then we'll spend days chasing it down - all while continuing not to have evidence that this is actually a hot path for real-world apps. Basically, I'm afraid that it's signing us up for continuing maintenance work for a code path that we didn't want to invest significant resources into.

all while continuing not to have evidence that this is actually a hot path for real-world apps.

Signals Rosyln would move away from ImmuntableDictionary for a fast Dictionary clone method dotnet/roslyn#47503 (comment)

Yes, ImmutableDictionary is really bad. We just haven't had cases yet that fell into the patterns for which we have production-ready alternatives. The main scenario that we have the ability to improve today is collections with the following characteristics:

• The dictionary is built up from empty, as opposed to built by transforming a previous collection through add/remove operations
• The collection has more than a few elements, but less than ~10K elements

For this we could switch to an immutable wrapper around Dictionary<TKey, TValue>, similar to how we use ImmutableArray<T> instead of ImmutableList<T>.

/cc @sharwell

and

My gut tells me this should be a slam dunk win. The vast majority (probably nearly all) of cases where we use ImmutableDict, it's not to benefit from what ID is decent at, but just to ensure it will not be mutated post creation. For that purpose it's actually a pretty terrible choice and adds a tremendous amount of overhead for functionality that we're not needing in those scenarios.

/cc @CyrusNajmabadi

Also for lockless read Dictionary, with very infrequent updates (where reallocating the entire dictionary is more lightweight than taking a lock on every read, or using ConcurrentDictionary) e.g.

class LookupTable
{
    private Dictionary<int, string>? _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;
        }
    }
}

Its also why I wanted to add a clone extension method in #41939

public static class DictionaryExtensions
{
    public static Dictionary<TKey, TValue> Clone<TKey, TValue>(this Dictionary<TKey, TValue> source) where TKey : notnull
    {
        return new Dictionary<TKey, TValue>(source, source.Comparer);
    }
}

Because it's not clear that passing a Dictionary as an IDictionary to the Dictionary constructor is a fast way to copy it and on Full Framework it really isn't https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,106

Released TrimExcess and Copy might as well share the same entity copying code

Released TrimExcess and Copy might as well share the same entity copying code

Nice!

Is there any pending feedback on this PR? If not I'll just merge.

Don't think so; CI wasn't behaving (one job failed in unrelated area), when it was was going to rebase for a clean set of greens, but looking at the open PRs doesn't look like CI is there yet...

Squashed and Rebased

Failing tests seem like unrelated timeouts.

Thanks @benaadams!

Aside it should also improve SparseTensor<T> .Clone() and .ToSparseTensor()

Just wanted to update that we are seeing these wins in the performance lab for both strings and ints.

Run Information

Regressions in System.Collections.CtorFromCollection

Historical Data in Reporting System

Repro

git clone https://github.com/dotnet/performance.git
py .\performance\scripts\benchmarks_ci.py -f netcoreapp5.0 --filter 'System.Collections.CtorFromCollection<String>*'

[ 3227.117 ;  5690.502) | @@@@@@@@@@@@@@@@@@@@
[ 5690.502 ;  7941.971) | 
[ 7941.971 ; 10193.440) | 
[10193.440 ; 12444.908) | 
[12444.908 ; 14336.416) | 
[14336.416 ; 16587.885) | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

Run Information

Regressions in System.Collections.CtorFromCollection

Historical Data in Reporting System

Repro

git clone https://github.com/dotnet/performance.git
py .\performance\scripts\benchmarks_ci.py -f netcoreapp5.0 --filter 'System.Collections.CtorFromCollection<Int32>*'

[1496.277 ; 2414.652) | @@@@@@@@@@@@@@@@@@@@
[2414.652 ; 3307.499) | 
[3307.499 ; 4200.346) | 
[4200.346 ; 5093.193) | 
[5093.193 ; 5775.253) | 
[5775.253 ; 6668.100) | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[6668.100 ; 7562.448) | @@@@@@@@@@@@@

Love it - thank you @DrewScoggins for following up with that positive data.