Perf bottleneck because of SortedDictionary in Annotatable.FindAnnotation

[roji]

The following was reported offline by @feng-yuan (thanks!)

Found an expensive EF stack:

GetValueComparer is costing 139 k CPU samples, 6% in this hot stream, mostly due to SortedDictionary lookup in Annotable.FindAnnotation.

We know sorted dictionary is slower than dictionary because its lookup is O(Ln(N)), but there is something more to make the code slower, or even incorrect here.

protected virtual Annotation SetAnnotation([NotNull] string name, [NotNull] Annotation annotation, [CanBeNull] Annotation oldAnnotation)
{
    if (this._annotations == null)
    {
        this._annotations = new SortedDictionary<string, Annotation>();
    }
    this._annotations[name] = annotation;
    return this.OnAnnotationSet(name, annotation, oldAnnotation);
}

SortedDictionary<string, Annotation> is allocated with default constructor. So the comparer is using String.Compare which is using current culture. Here is the evidence:

String.CompareTo is on the right. Zoom-in:

So lookup is now dependent on current thread culture.

At least, you need to change the code to :

if (this._annotations == null)
{
    this._annotations = new SortedDictionary<string, Annotation>(StringComparer.Ordinal);
}

If order is not important, Dictionary<string, Annotation> would be even faster and smaller.

[roji]

Split off the (possible) correctness issue to #25489 (use ordinal comparison)

[AndriySvyryd]

In 6.0.0 we introduced the optimized runtime model and RuntimeProperty.GetValueComparer() doesn't look for an annotation, as it's now stored in a field. So this bottleneck should be gone.

[roji]

Great, have added verified-fixed to make sure.

[roji]

Profiling the repro application in #20135 shows that almost 30% of the model building time is spent doing SortedDictionary.TryGetValue inside Annotatable.FindAnnotation... We may still want to revisit this even if it no longer impacts runtime (and even if we have compiled models).

(but confirm first that runtime isn't impacted)

[AndriySvyryd]

Since GetAnnotations isn't used frequently we could sort on demand and use Hashtable/Dictionary<string, Annotation>

[AndriySvyryd]

Done in d8e9f61