[System.Linq] Performance: .ToList() counter-intuitively slower than .ToArray()

[ymarcov]

Pertaining to LINQ extension optimizations, such as defined in:
https://github.com/dotnet/runtime/blob/main/src/libraries/System.Linq/src/System/Linq/Select.SpeedOpt.cs

Synopsis

.ToArray() uses an optimized LargeArrayBuilder internally, whereas .ToList() simply uses the slower List.

Details

At this point in time -- historical considerations aside -- LargeArrayBuilder works fairly similarly to List in how it dynamically grows its internal storage. But it is more aggressive its internal array space management, and it can afford to do so because these internal arrays are promptly discarded in favor of an immediate compacted array result of the .ToArray() call.

While the implementation of List itself is understandably not as aggressive with space usage, because it is expected to hold on to its memory long-term, there is arguably no reason why the .ToList() builder call wouldn't also benefit from the performance enhancements offered by LargeArrayBuilder.SpeedOpt as used in the file referred to above.

Suggested Implementation

Use LargeArrayBuilder in .ToList() and add an internal constructor to List that directly accepts an array.

Benchmark Results

BenchmarkDotNet results that show the performance difference between .ToArray() and .ToList():

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19043.1165 (21H1/May2021Update)
Intel Core i7-1065G7 CPU 1.30GHz, 1 CPU, 8 logical and 4 physical cores
.NET SDK=5.0.303
  [Host]     : .NET 5.0.9 (5.0.921.35908), X64 RyuJIT
  DefaultJob : .NET 5.0.9 (5.0.921.35908), X64 RyuJIT


|    Method | Count |          Mean |       Error |        StdDev | Ratio | RatioSD |  Gen 0 |  Gen 1 | Allocated |
|---------- |------ |--------------:|------------:|--------------:|------:|--------:|-------:|-------:|----------:|
| ToArray() |     0 |      5.554 ns |   0.1692 ns |     0.3785 ns |  1.00 |    0.00 |      - |      - |         - |
|  ToList() |     0 |      9.580 ns |   0.2557 ns |     0.4545 ns |  1.71 |    0.12 | 0.0076 |      - |      32 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |     1 |     17.963 ns |   0.5613 ns |     1.6463 ns |  1.00 |    0.00 | 0.0172 |      - |      72 B |
|  ToList() |     1 |     26.034 ns |   1.0104 ns |     2.9792 ns |  1.46 |    0.23 | 0.0249 |      - |     104 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |     6 |     24.747 ns |   1.1511 ns |     3.3577 ns |  1.00 |    0.00 | 0.0210 |      - |      88 B |
|  ToList() |     6 |     34.518 ns |   1.4124 ns |     3.9605 ns |  1.42 |    0.24 | 0.0287 |      - |     120 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |    10 |     27.708 ns |   0.6925 ns |     1.9644 ns |  1.00 |    0.00 | 0.0249 |      - |     104 B |
|  ToList() |    10 |     42.672 ns |   1.2192 ns |     3.4981 ns |  1.55 |    0.17 | 0.0325 |      - |     136 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |    39 |     51.100 ns |   1.0536 ns |     1.7013 ns |  1.00 |    0.00 | 0.0535 |      - |     224 B |
|  ToList() |    39 |     95.026 ns |   1.7949 ns |     1.4014 ns |  1.84 |    0.07 | 0.0612 |      - |     256 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |   100 |     97.097 ns |   1.9491 ns |     2.0855 ns |  1.00 |    0.00 | 0.1109 |      - |     464 B |
|  ToList() |   100 |    214.146 ns |   4.1949 ns |     4.9937 ns |  2.21 |    0.09 | 0.1185 |      - |     496 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |   666 |    488.799 ns |   9.7951 ns |    14.3576 ns |  1.00 |    0.00 | 0.6523 |      - |   2,728 B |
|  ToList() |   666 |  1,580.520 ns |  44.4041 ns |   130.9264 ns |  3.27 |    0.31 | 0.6580 |      - |   2,760 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |  1000 |    788.373 ns |  17.0116 ns |    49.3537 ns |  1.00 |    0.00 | 0.9708 |      - |   4,064 B |
|  ToList() |  1000 |  2,240.906 ns |  41.5358 ns |    88.5163 ns |  2.85 |    0.20 | 0.9766 |      - |   4,096 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |  1337 |  1,012.680 ns |  19.6211 ns |    47.0110 ns |  1.00 |    0.00 | 1.2932 |      - |   5,416 B |
|  ToList() |  1337 |  3,058.555 ns |  61.2440 ns |   138.2378 ns |  3.02 |    0.21 | 1.3008 |      - |   5,448 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() | 10000 |  7,450.089 ns | 154.5205 ns |   455.6073 ns |  1.00 |    0.00 | 9.5215 | 0.0076 |  40,064 B |
|  ToList() | 10000 | 25,091.368 ns | 497.8067 ns | 1,371.1043 ns |  3.40 |    0.32 | 9.5215 | 0.0305 |  40,096 B |

Benchmark Code

[MemoryDiagnoser]
public class Benchmarks
{
    [Params(0, 1, 6, 10, 39, 100, 666, 1000, 1337, 10000)]
    public int Count { get; set; }

    public IEnumerable<int> Items => Enumerable.Range(0, Count);

    [Benchmark(Description = "ToArray()", Baseline = true)]
    public int[] ToArray() => Items.ToArray();

    [Benchmark(Description = "ToList()")]
    public List<int> ToList() => Items.ToList();

}

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

Tagging subscribers to this area: @eiriktsarpalis
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Pertaining to LINQ extension optimizations, such as defined in:
https://github.com/dotnet/runtime/blob/main/src/libraries/System.Linq/src/System/Linq/Select.SpeedOpt.cs

Synopsis

.ToArray() uses an optimized LargeArrayBuilder internally, whereas .ToList() simply uses the slower List.

Details

At this point in time -- historical considerations aside -- LargeArrayBuilder works fairly similarly to List in how it dynamically grows its internal storage. But it is more aggressive its internal array space management, and it can afford to do so because these internal arrays are promptly discarded in favor of an immediate compacted array result of the .ToArray() call.

While the implementation of List itself is understandably not as aggressive with space usage, because it is expected to hold on to its memory long-term, there is arguably no reason why the .ToList() builder call wouldn't also benefit from the performance enhancements offered by LargeArrayBuilder.SpeedOpt as used in the file referred to above.

Suggested Implementation

Use LargeArrayBuilder in .ToList() and add an internal constructor to List that directly accepts an array.

Benchmark Results

BenchmarkDotNet results that show the performance difference between .ToArray() and .ToList():

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19043.1165 (21H1/May2021Update)
Intel Core i7-1065G7 CPU 1.30GHz, 1 CPU, 8 logical and 4 physical cores
.NET SDK=5.0.303
  [Host]     : .NET 5.0.9 (5.0.921.35908), X64 RyuJIT
  DefaultJob : .NET 5.0.9 (5.0.921.35908), X64 RyuJIT


|    Method | Count |          Mean |       Error |        StdDev | Ratio | RatioSD |  Gen 0 |  Gen 1 | Allocated |
|---------- |------ |--------------:|------------:|--------------:|------:|--------:|-------:|-------:|----------:|
| ToArray() |     0 |      5.554 ns |   0.1692 ns |     0.3785 ns |  1.00 |    0.00 |      - |      - |         - |
|  ToList() |     0 |      9.580 ns |   0.2557 ns |     0.4545 ns |  1.71 |    0.12 | 0.0076 |      - |      32 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |     1 |     17.963 ns |   0.5613 ns |     1.6463 ns |  1.00 |    0.00 | 0.0172 |      - |      72 B |
|  ToList() |     1 |     26.034 ns |   1.0104 ns |     2.9792 ns |  1.46 |    0.23 | 0.0249 |      - |     104 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |     6 |     24.747 ns |   1.1511 ns |     3.3577 ns |  1.00 |    0.00 | 0.0210 |      - |      88 B |
|  ToList() |     6 |     34.518 ns |   1.4124 ns |     3.9605 ns |  1.42 |    0.24 | 0.0287 |      - |     120 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |    10 |     27.708 ns |   0.6925 ns |     1.9644 ns |  1.00 |    0.00 | 0.0249 |      - |     104 B |
|  ToList() |    10 |     42.672 ns |   1.2192 ns |     3.4981 ns |  1.55 |    0.17 | 0.0325 |      - |     136 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |    39 |     51.100 ns |   1.0536 ns |     1.7013 ns |  1.00 |    0.00 | 0.0535 |      - |     224 B |
|  ToList() |    39 |     95.026 ns |   1.7949 ns |     1.4014 ns |  1.84 |    0.07 | 0.0612 |      - |     256 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |   100 |     97.097 ns |   1.9491 ns |     2.0855 ns |  1.00 |    0.00 | 0.1109 |      - |     464 B |
|  ToList() |   100 |    214.146 ns |   4.1949 ns |     4.9937 ns |  2.21 |    0.09 | 0.1185 |      - |     496 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |   666 |    488.799 ns |   9.7951 ns |    14.3576 ns |  1.00 |    0.00 | 0.6523 |      - |   2,728 B |
|  ToList() |   666 |  1,580.520 ns |  44.4041 ns |   130.9264 ns |  3.27 |    0.31 | 0.6580 |      - |   2,760 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |  1000 |    788.373 ns |  17.0116 ns |    49.3537 ns |  1.00 |    0.00 | 0.9708 |      - |   4,064 B |
|  ToList() |  1000 |  2,240.906 ns |  41.5358 ns |    88.5163 ns |  2.85 |    0.20 | 0.9766 |      - |   4,096 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() |  1337 |  1,012.680 ns |  19.6211 ns |    47.0110 ns |  1.00 |    0.00 | 1.2932 |      - |   5,416 B |
|  ToList() |  1337 |  3,058.555 ns |  61.2440 ns |   138.2378 ns |  3.02 |    0.21 | 1.3008 |      - |   5,448 B |
|           |       |               |             |               |       |         |        |        |           |
| ToArray() | 10000 |  7,450.089 ns | 154.5205 ns |   455.6073 ns |  1.00 |    0.00 | 9.5215 | 0.0076 |  40,064 B |
|  ToList() | 10000 | 25,091.368 ns | 497.8067 ns | 1,371.1043 ns |  3.40 |    0.32 | 9.5215 | 0.0305 |  40,096 B |

Benchmark Code

[MemoryDiagnoser]
public class Benchmarks
{
    [Params(0, 1, 6, 10, 39, 100, 666, 1000, 1337, 10000)]
    public int Count { get; set; }

    public IEnumerable<int> Items => Enumerable.Range(0, Count);

    [Benchmark(Description = "ToArray()", Baseline = true)]
    public int[] ToArray() => Items.ToArray();

    [Benchmark(Description = "ToList()")]
    public List<int> ToList() => Items.ToList();

}

Author:	ymarcov
Assignees:	-
Labels:	area-System.Linq, tenet-performance, untriaged
Milestone:	-

[huoyaoyuan]

add an internal constructor to List that directly accepts an array

The implementation is in List(IEnumerable<T>), so there is no need to add a constructor

[ymarcov]

@huoyaoyuan It's possible to use that one, but it would entail an extra copy of the resulr

[Clockwork-Muse]

and add an internal constructor to List that directly accepts an array.

Wouldn't this have to be a public constructor, though? Since Linq is in a completely separate package/assembly?
If so, that would be a (fairly major) breaking change.

[eiriktsarpalis]

It's possible to use that one, but it would entail an extra copy of the resulr

Unless there is a compelling use case, we try to avoid adding new code to popular generic types like List<T> out of codegen performance considerations. Not necessarily convinced that this qualifies as compelling, LINQ was never intended to be a high performance library. I would recommend switching to ToArray() if improving performance while still using LINQ is important for the application.

and add an internal constructor to List that directly accepts an array.

Wouldn't this have to be a public constructor, though? Since Linq is in a completely separate package/assembly?
If so, that would be a (fairly major) breaking change.

We could proxy it via CollectionsMarshal, but I wouldn't necessarily be comfortable exposing something so unsafe.

[ymarcov]

@eiriktsarpalis I understand, there's a trade-off that needs to make sense first of all.
Could you please elaborate a bit on what you mean by codegen performance considerations?
If I can come up with some possible solutions, I'd like to understand what it means so that I don't propose something else that conflicts with those considerations.

[stephentoub]

Could you please elaborate a bit on what you mean by codegen performance considerations?

There is a lot of code in LINQ's ToArray implementation (so much that I'm not entirely sure it's worth it and have considered deleting it on multiple occasions). Every generic instantiation of ToArray with a different value type ends up duplicating the assembly for all of that code. For List<T>, it's even worse, because List<T> is used everywhere, and so every use of List<T> with a different value type would incur a copy of that assembly for that large ToArray implementation. That has size on disk implications, download performance implications (e.g. for Blazor AOT), working set implications, JIT-time implications, etc.

[ymarcov]

@stephentoub Thanks for the detailed explanation!

Maybe the amount of IL code might be reduced significantly in most practical usage by using a non-generic object based LargeArrayBuilder for all reference types (that is, if most uses of .ToList() tend to be on reference types).

Regarding the issue here, from the explanations given I can see why neither adding to List<T>'s public API nor adding more code to its implementation is a good idea.

One way to work around it is to hook into List<T>'s (IEnumerable<T>) constructor which has an optimization for ICollection<T>. LargeArrayBuilder could provide another method, in addition to .ToArray(), that, instead of concatenating the array on its own, returns a provisional ICollection<T> (the count is known at that point) whose enumerator goes through each of the internal buffers and their items in order of addition. This way, the concatenation and compaction would be delegated to the existing implementation in List<T>.

Of course one problem with this approach is, once again, the added assembly for this provisional ICollection<T>. But it might turn out to be a very thin layer, and, if the trick with reference types mentioned above is added, then when both are taken together the total IL size could potentially be reduced.

If this is interesting, then research is needed to verify these assumptions, but if the basic idea sounds reasonable I could look into it and report back with quantitative data.

[stephentoub]

One way to work around it is to hook into List<T>'s (IEnumerable<T>) constructor which has an optimization for ICollection<T>

Yes, it'll use the ICollection<T>'s Count and CopyTo methods. If you wanted to experiment with an internal ICollection<T> implementation that wrapped LargeArrayBuilder and existed purely to have an instance passed to List<T>'s ctor, that'd be reasonable to explore. It of course has the possibility to regress performance as well, especially for small lists (as does this more complicated ToArray implementation, something else I don't love about it).