Corefxlab: DictionarySlim Improvements

[TylerBrinkley]

Potential API Changes

 namespace Microsoft.Collections.Extensions {
     public class DictionarySlim<TKey, TValue> : IReadOnlyCollection<KeyValuePair<TKey, TValue>> where TKey : IEquatable<TKey> {
         // More ref return methods
+        public ref TValue GetValueRef(TKey key); // throws KeyNotFoundException if not contains key
+        public ref TValue TryGetValueRef(TKey key, out bool found); // returns a null reference if possible or else a reference to a private static dummy field when not found

         // Select API differences from Dictionary<K, V>
+        public DictionarySlim(IEnumerable<KeyValuePair<TKey, TValue>> collection); // convenience constructor
+        public int EnsureCapacity(int capacity);
+        public void TrimExcess();
+        public void TrimExcess(int capacity);

         // Existing API
         public DictionarySlim();
         public DictionarySlim(int capacity);
         public int Count { get; }
         public void Clear();
         public bool ContainsKey(TKey key);
         public bool TryGetValue(TKey key, out TValue value);
         public bool Remove(TKey key);
         public ref TValue GetOrAddValueRef(TKey key);
         public Enumerator GetEnumerator();

         public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue> {
             public KeyValuePair<TKey, TValue> Current { get; }
             public void Dispose();
             public bool MoveNext();
         }
     }
 }

Updates

• Removed IDictionary<TKey, TValue> support.

[TylerBrinkley]

@danmosemsft @AnthonyLloyd Thoughts?

[danmoseley]

Would you mind including existing API in the diff above?

[TylerBrinkley]

Done.

[danmoseley]

Should there be a constructor over IDictionary<TKey, TValue> (as well or instead of IEnumerator<KeyValuePair<TKey, TValue>>). That is what Dictionary chooses - not sure why.

Either way, in .NET Core it probes for the concrete Dictionary type, which it treats specially - I guess it could literally copy both the arrays in such a case, although it does not.

[danmoseley]

One thing to consider is the cost of code instantiation - the code must be generated separately for each different size of TKey/TValue (I am not stating this precisely - the point is that while all reference types can share a single instantiation, this is not the case for various structs). That cost has caused us to reject certain more API on Dictionary (mainly where extension methods could be offered instead). Given this type is "Slim" and also perhaps more likely to be used with structs than the regular one, that's a consideration.

[danmoseley]

@jkotas what is the precisely specified criteria for sharing generated code for a generic type? Can two structs with the same width in memory share an instantiation? Also is JIT vs AOT relevant?

[jkotas]

what is the precisely specified criteria for sharing generated code for a generic type?

The sharing is determined by the instantiation arguments as you have said. E.g. Dictionary<string,string>, Dictionary<string,object> and Dictionary<object,object> all have one copy of the code (but each of them has still its own copy of EE data structures). Dictionary<string,int>, Dictionary<int,object> and Dictionary<int,int> all have its own copy of the code.

To make the DictionarySlim extra lean for full AOT, I would drop the specific Key and Value enumerators - they are rarely used. The extra constructor discussed here is not that big of the deal compared to the footprint added by the enumerators.

[danmoseley]

Interesting. Key and Value enumerators could be pulled into non-nested structs, so they were pay for play, but I guess that would not add much value over using simple Linq to get the key or value out of the KVP enumerator.

[TylerBrinkley]

Dictionary<TKey, TValue> added the IEnumerable<KeyValuePair<TKey, TValue>> constructor after the IDictionary<TKey, TValue> constructor was already there. Since IDictionary<TKey, TValue> implements IEnumerable<KeyValuePair<TKey, TValue>> the IDictionary<TKey, TValue> constructor is now superfluous.

I'm not saying we should add all these API's but am simply listing potential API additions that have been incorporated into Dictionary<TKey, TValue> along with a few other API changes. Obviously this is the slim version and should strive to attain that status.

Removing the Key and Value enumerators makes sense to me.

[danmoseley]

OK. Of the list, we already added Clear() since it didn't seem like we could claim to be a self respecting mutable collection otherwise. I will go ahead and remove the Key and Value enumerators. Let's leave this issue open, get it up on NuGet, and see what feedback we get.

[danmoseley]

We should probably hide Capacity as well it's really only there for the tests.

[danmoseley]

I'll add XML comments too.

[danmoseley]

Hmm, how can I enumerate over the dictionary without copying every key and (particularly) value? @stephentoub is there a by ref enumerator pattern? I see some language discussion, meantime what is the recommendation?

[TylerBrinkley]

Since we've removed the Keys and Values collections I suppose it doesn't make much sense to implement IDictionary<TKey, TValue> anymore.

[TylerBrinkley]

Do you think we should remove the standard TryGetValue if we're going to add the TryGetValueRef method?

[buybackoff]

Would be nice to have bool TryAdd(TKey key, TValue value) possibly with an overload with ..., out TValue existing) . With GetOrAddValueRef I need to compare returned value to default and then set the new one. If default value could be in dictionary then one has to call ContainsKey.

[TylerBrinkley]

@buybackoff A GetOrAddValueRef(TKey key, TValue defaultValue) overload would work for your scenario. That was the original overload I proposed with the defaultValue parameter specified as optional.

[buybackoff]

Just found in profiler that TryGetValue was not inlined. Adding [MethodImpl(MethodImplOptions.AggressiveInlining)] improves its performance by 20%. Other methods should probably also benefit from that.

[TylerBrinkley]

TryGetValue is a public method with a sizable body. If it were being used internally it would make sense to inline its use but I don't think external consuming code should inline its body given the body size.

[buybackoff]

@TylerBrinkley I thought that this is maybe intentional, but the purpose of the new dictionary was to get last bits of performance. In my case with rare writes DictionarySlim with SpinLock became 10% faster than ConcurrentDictionary, whose enumerator still allocates.

But never mind, I have DictionarySlim imported as source code.

[danmoseley]

@jkotas @AndyAyersMS what is your feeling about marking public methods as aggressive inline? It does cause arbitrary sized bloat - it's a shame there's not a way for the caller to force the inline instead.

Plus the usual caveat of inlining showing up disproportionately well in microbenchmarks, and the code bloat is multiplied by the instantiations, ..

[jkotas]

marking public methods as aggressive inline?

Marking large public methods like TryGetValue as [MethodImpl(MethodImplOptions.AggressiveInlining)] would hurt majority of our users because of code bloat and slower startup.

The rare cases that need that can include a source copy of the dictionary and tweak it as necessary, just like @buybackoff has done.

[buybackoff]

Plus the usual caveat of inlining showing up disproportionately well in microbenchmarks

This is true of cause. But consider a situation when consumers of this low-level building blocks have their own public methods, which usually call several methods of such primitive building blocks and which are virtual or contain try/catch or other things that prevent inlining (or are deliberately non-inlined with the attribute). For such very hot methods we have already paid for a method call, and it's a pity when some framework method is not inlined either due to such case as this or it has a throw instead of ThrowHelper or switch. This quickly accumulates.

One general solution could be to expose more inner methods that do not have argument checks and marked as inlined but which are probably hidden from Intellisense and have DangerousXxx, XxxInternal, XxxImpl in their names.

[AndyAyersMS]

I'm probably rehashing some discussions I've had elsewhere, but I often feel AggressiveInlining is solving the problem the wrong way around. Usually it's the caller that indicates if an inline is important for perf, not the callee. A per-call-site attribute may not be practical, but a per-method one might be, something like (or perhaps exactly) AggressiveOptimization.

I also expect that someday our tiering will evolve enough smarts to make some of these decisions automatically.