Optimize ArrayBuilder.ToDictionary to use SmallDictionary when appropriate

[Youssef1313]

roslyn/src/Dependencies/PooledObjects/ArrayBuilder.cs

Lines 458 to 499 in 2fb8ad0

	internal Dictionary<K, ImmutableArray<T>> ToDictionary<K>(Func<T, K> keySelector, IEqualityComparer<K>? comparer = null)
	where K : notnull
	{
	if (this.Count == 1)
	{
	var dictionary1 = new Dictionary<K, ImmutableArray<T>>(1, comparer);
	var value = this[0];
	dictionary1.Add(keySelector(value), ImmutableArray.Create(value));
	return dictionary1;
	}
	if (this.Count == 0)
	{
	return new Dictionary<K, ImmutableArray<T>>(comparer);
	}
	// bucketize
	// prevent reallocation. it may not have 'count' entries, but it won't have more.
	var accumulator = new Dictionary<K, ArrayBuilder<T>>(Count, comparer);
	for (var i = 0; i < Count; i++)
	{
	var item = this[i];
	var key = keySelector(item);
	if (!accumulator.TryGetValue(key, out var bucket))
	{
	bucket = ArrayBuilder<T>.GetInstance();
	accumulator.Add(key, bucket);
	}
	bucket.Add(item);
	}
	var dictionary = new Dictionary<K, ImmutableArray<T>>(accumulator.Count, comparer);
	// freeze
	foreach (var pair in accumulator)
	{
	dictionary.Add(pair.Key, pair.Value.ToImmutableAndFree());
	}
	return dictionary;
	}

1. The method should return IDictionary and return SmallDictionary for small number of elements where it will be more efficient.
2. If there are no elements, I don't think it should allocate a new dictionary every time. If it will return IDictionary<TKey,ImmutableArray<TValue>>, then we can just use ImmutableDictionary<K, ImmutableArray<T>>.Empty. Otherwise, create our own cached empty.

Motivation:

It looks like GetSimpleNonTypeMembers has 7.7% of CPU time in this trace, with most of its time in TryGetValue. I'd imagine that there are some of these calls where the number of elements in the dictioanry is small enough that SmallDictionary can bring a better performance.

[jaredpar]

I feel like we're not getting a lot of context on these issues. I appreciate there is a screen shot of PerfView here but there isn't surrounding context. I don't know what you're measuring, how that scenario relates to other work we're doing, etc ...

[Youssef1313]

@jaredpar The scenario is referencing a very large dll with too many generic extension methods. The dll is about 9MB, and it's only code.

[Youssef1313]

What I'm measuring is IntelliSense performance. Basically just start collecting a trace and start typing in IDE for a while. That's it. IntelliSense and classification appear to be both slow. Most of the time is spent in the compiler, so it doesn't appear to be an IDE issue.

The semantic model calls get veery slow with too many generic extension methods (there are ones with multiple overloads) in metadata symbols.

A similar scenario existed for retargeting symbols, which has improved in #69011