ChainedConfigurationProvider.GetChildKeys is inefficient

[davidfowl]

Description

ChainedConfigurationProvider.GetChildKeys ends up splitting strings which forces an array allocation even if there are no keys with segments. This has shown up on a couple of performance profiles internally and we should improve it.

Regression?

No

Data

Ask me

Analysis

Ask me

[ghost]

Tagging subscribers to this area: @dotnet/area-extensions-configuration
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

ChainedConfigurationProvider.GetChildKeys ends up splitting strings which forces an array allocation even if there are no keys with segments. This has shown up on a couple of performance profiles internally and we should improve it.

Regression?

No

Data

Ask me

Analysis

Ask me

Author:	davidfowl
Assignees:	-
Labels:	tenet-performance, untriaged, area-Extensions-Configuration
Milestone:	-

[gfoidl]

I can look into this (next week).

Seems there's some potential for improvement.
Use of

runtime/src/libraries/Microsoft.Extensions.Configuration/src/ConfigurationKeyComparer.cs

Line 14 in 12a8819

private static readonly string[] _keyDelimiterArray = new[] { ConfigurationPath.KeyDelimiter };

can also be simplified (it's all static readonly for :).

[vcsjones]

If this shows up on profiles, then I think you could do this allocation free entirely.

The below code is entirely untested and for illustration purposes only 😄. It might be slower for all I know, but it doesn't allocate strings to split. This has a slight behavior change in what is returned when the segments aren't equal, but it conforms to the contract of Compare. If we want to retain identical behavior, it's possible, but would result in doing unnecessary splitting.

namespace Microsoft.Extensions.Configuration
{
    /// <summary>
    /// IComparer implementation used to order configuration keys.
    /// </summary>
    public class ConfigurationKeyComparer : IComparer<string>
    {
        /// <summary>
        /// The default instance.
        /// </summary>
        public static ConfigurationKeyComparer Instance { get; } = new ConfigurationKeyComparer();

        /// <summary>A comparer delegate with the default instance.</summary>
        internal static Comparison<string> Comparison { get; } = Instance.Compare;

        public static void Split(
            ReadOnlySpan<char> str,
            char delimiter,
            out ReadOnlySpan<char> next,
            out ReadOnlySpan<char> remaining,
            bool skipEmpty = true)
        {
            while (true)
            {
                int location = str.IndexOf(delimiter);

                if (location == -1)
                {
                    next = str;
                    remaining = default;
                    return;
                }
                else if (location == 0 && skipEmpty)
                {
                    str = str[1..];
                    continue;
                }
                else
                {
                    next = str[..location];
                    remaining = str[(location + 1)..];
                    return;
                }
            }
        }

        public int Compare(string? x, string? y)
        {
            ReadOnlySpan<char> xRemaining = x;
            ReadOnlySpan<char> yRemaining = y;

            do
            {
                Split(xRemaining, ':', out ReadOnlySpan<char> xPart, out xRemaining);
                Split(yRemaining, ':', out ReadOnlySpan<char> yPart, out yRemaining);

                bool xIsInt = int.TryParse(xPart, out int value1);
                bool yIsInt = int.TryParse(yPart, out int value2);

                int result;

                if (!xIsInt && !yIsInt)
                {
                    // Both are strings
                    result = MemoryExtensions.CompareTo(xPart, yPart, StringComparison.OrdinalIgnoreCase);
                }
                else if (xIsInt && yIsInt)
                {
                    // Both are int
                    result = value1 - value2;
                }
                else
                {
                    // Only one of them is int
                    result = xIsInt ? -1 : 1;
                }

                if (result != 0)
                {
                    // One of them is different
                    return result;
                }
            }
            while (!xRemaining.IsEmpty && !yRemaining.IsEmpty);

            return xRemaining.Length - yRemaining.Length;
        }
    }
}

[Wraith2]

I was going to tinker with using the existing StringSegment Tokenizer in the extensions Primitive namespace. What would be useful is some example input strings to run against.

[SteveDunn]

I'm happy to look at this one. Is there a project with a suitably large set of config to baseline?

[maryamariyan]

Thanks @SteveDunn this issue is currently in progress.

[SteveDunn]

Thanks @SteveDunn this issue is currently in progress.

Sorry, I didn't see a branch/PR

[maryamariyan]

Sorry, I didn't see a branch/PR

@SteveDunn no worries, just added the PR here in #67186