Optimize string.Join() (internally JoinCore) for IEnumerable<string> that is Collection<string>

[Domik234]

Description

When calling string.Join() that calls JoinCore<T> in String.Manipulation.cs, if the IEnumerable<string> parameter is a Collection<string>, it is ~2x slower than when it is a List<string>.

I guess that this is because line 925 only checks for List<string>, and does not check for IList<string>. As a result, collections that implement IList<string> (such as Collection<string>, ReadOnlyCollection<string>) do not benefit from the optimized path.

The Collection class uses IList as internal items storage (Source) so couldn't be used it's internal IList<T> for this purpose?

Context

• File: String.Manipulation.cs
• Related code line: 925

Simple benchmark

Code

[SimpleJob(RuntimeMoniker.Net80)]
[SimpleJob(RuntimeMoniker.Net90)]
[MemoryDiagnoser]
public class TestCase01
{
    Collection<string> collection;
    List<string> list;
    public TestCase01()
    {
        collection = [];
        for (var i = 0; i < 25; i++)
        {
            collection.Add(Random.Shared.Next(10000, 1000000).ToString());
        }
        list = [.. collection];

    }

    [Benchmark]
    public string CollectionToRangeString_NoStringJoin()
    {
        var count = collection.Count;
        StringBuilder sb = new();
        sb.Append('{');
        for (int i = 0; i < count; i++)
        {
            sb.Append(collection.ElementAt(i));

            if (i < count - 1)
                sb.Append(", ");
        }
        sb.Append('}');

        return sb.ToString();
    }

    [Benchmark]
    public string CollectionToRangeString2_StringJoinChar()
    {
        StringBuilder sb = new();
        sb.Append('{');
        sb.Append(string.Join(',', collection));
        sb.Append('}');

        return sb.ToString();
    }

    [Benchmark]
    public string CollectionToRangeString3_StringJoinString()
    {
        StringBuilder sb = new();
        sb.Append('{');
        sb.Append(string.Join(", ", collection));
        sb.Append('}');

        return sb.ToString();
    }

    [Benchmark]
    public string ListToRangeString_NoStringJoin()
    {
        var count = list.Count;
        StringBuilder sb = new();
        sb.Append('{');
        for (int i = 0; i < count; i++)
        {
            sb.Append(list.ElementAt(i));

            if (i < count - 1)
                sb.Append(", ");
        }
        sb.Append('}');

        return sb.ToString();
    }

    [Benchmark]
    public string ListToRangeString2_StringJoinChar()
    {
        StringBuilder sb = new();
        sb.Append('{');
        sb.Append(string.Join(',', list));
        sb.Append('}');

        return sb.ToString();
    }

    [Benchmark]
    public string ListToRangeString3_StringJoinString()
    {
        StringBuilder sb = new();
        sb.Append('{');
        sb.Append(string.Join(", ", list));
        sb.Append('}');

        return sb.ToString();
    }
}

Results:

| Method                                    |  Job/Rt  | Mean     | Error   | StdDev  | Gen0   | Gen1   | Allocated |
|------------------------------------------ |--------- |---------:|--------:|--------:|-------:|-------:|----------:|
| CollectionToRangeString_NoStringJoin      | .NET 8.0 | 284.4 ns | 5.22 ns | 6.41 ns | 0.1025 |      - |   1.26 KB |
| CollectionToRangeString2_StringJoinChar   | .NET 8.0 | 304.7 ns | 3.67 ns | 3.43 ns | 0.1335 |      - |   1.64 KB |
| CollectionToRangeString3_StringJoinString | .NET 8.0 | 265.5 ns | 2.50 ns | 2.09 ns | 0.1483 | 0.0005 |   1.82 KB |
| ListToRangeString_NoStringJoin            | .NET 8.0 | 283.3 ns | 3.33 ns | 2.95 ns | 0.1030 |      - |   1.27 KB |
| ListToRangeString2_StringJoinChar         | .NET 8.0 | 153.7 ns | 2.38 ns | 2.23 ns | 0.1326 |      - |   1.63 KB |
| ListToRangeString3_StringJoinString       | .NET 8.0 | 210.6 ns | 2.49 ns | 2.08 ns | 0.1478 | 0.0005 |   1.81 KB |
|--.NET 9.0-------------------------------- |--------- |---------:|--------:|--------:|-------:|-------:|----------:|
| CollectionToRangeString_NoStringJoin      | .NET 9.0 | 222.7 ns | 3.00 ns | 2.66 ns | 0.1032 | 0.0002 |   1.27 KB |
| CollectionToRangeString2_StringJoinChar   | .NET 9.0 | 305.6 ns | 3.96 ns | 3.51 ns | 0.1354 |      - |   1.66 KB |
| CollectionToRangeString3_StringJoinString | .NET 9.0 | 244.3 ns | 4.82 ns | 4.74 ns | 0.1516 |      - |   1.86 KB |
| ListToRangeString_NoStringJoin            | .NET 9.0 | 214.9 ns | 4.04 ns | 3.78 ns | 0.1032 | 0.0002 |   1.27 KB |
| ListToRangeString2_StringJoinChar         | .NET 9.0 | 143.7 ns | 1.73 ns | 1.45 ns | 0.1326 |      - |   1.63 KB |
| ListToRangeString3_StringJoinString       | .NET 9.0 | 199.4 ns | 2.90 ns | 2.57 ns | 0.1459 | 0.0002 |   1.79 KB |

[dotnet-policy-service]

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

[elgonzo]

The optimized path uses CollectionsMarshal.AsSpan, hence why List<T> and not IList<T>

[huoyaoyuan]

The Collection class uses IList as internal items storage (Source) so couldn't be used it's internal IList<T> for this purpose?

It changes merely nothing. Collection<T>.GetEnumerator delegates to list.GetEnumerator. The virtual calls will be performed on the same object.

Collection<T> is much less common than List<T> and other enumerables. Adding a special path will hurt the performance for others, especially LINQ.

[Domik234]

I understand the case that AsSpan() is used by design with List<string>, so it wouldn't be that simple.

Internal IList<T> is always new List<T>() but it's not accessible (protected IList<T> Items => items; => private readonly IList<T> items;).

My thinking led me to the conclusion that there is no need for Enumerator:

1. Collection<T> uses internal List<T> -> Collection<string>.items / Collection<string>.Items type must be List<string>. Collection ctor
2. If it is List<string> internally - it could use faster alternative for processing. JoinCore

But currently it jumps to GetEnumerator() because if (values.GetType() == typeof(List<string?>)) returns false.

Simple explanation (not an idea of the outcome)

public static string Join<T>(char separator, Collection<T> values) =>
    JoinCore(new ReadOnlySpan<char>(in separator), values.Items);

public static string Join<T>(string? separator, Collection<T> values) =>
    JoinCore(separator.AsSpan(), values.Items);

or

if (values is Collection<string?> collection)
{
    return JoinCore(separator, CollectionsMarshal.AsSpan(Unsafe.As<List<string?>>(collection.Items)));
}

I see another problem now that there are possibly more classes that are implementing ICollection/IList but may not use List<T> or string[] at all. It would propably grow codebase too much for so little. Closing this, thanks for your answers.

[stephentoub]

Internal IList is always new List()

It's not: the other ctor allows it to be specified:

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/ObjectModel/Collection.cs

Lines 23 to 29 in 6ab0311

	public Collection(IList<T> list)
	{
	if (list == null)
	{
	ThrowHelper.ThrowArgumentNullException(ExceptionArgument.list);
	}
	items = list;

[Domik234]

OMG... I was looking to it for like an hour with thinking what I am missing and it was right before my eyes. I found this ctor on ReadOnlyCollection but missed it onto Collection. 🤦🏻

Thanks 😅