new List<T>(IEnumrable<T>) & List<T>.AddRange(IEnumerable<T>) doesn't use IIListProvider.

[ActivistInvestor]

Discussed in #98773

^{Originally posted by ActivistInvestor February 21, 2024}

After looking at the source and doing a simple test, I want to be sure that there's nothing wrong with my testing methodology, because I'm seeing much better performance from Enumerable.ToList<T>() verses new List<T>(IEnumerable<T>) and List<T>.AddRange(IEnumerable<T>)

list.AddRange(seq):     20290
new List<int>(seq):     12435
      seq.ToList():      3701

list.AddRange(seq):      9946
new List<int>(seq):     10026
      seq.ToList():      2787

list.AddRange(seq):      9614
new List<int>(seq):     16384
      seq.ToList():      4566

list.AddRange(seq):     16051
new List<int>(seq):     13566
      seq.ToList():      3022

list.AddRange(seq):      9777
new List<int>(seq):     10610
      seq.ToList():      2837

list.AddRange(seq):      8951
new List<int>(seq):      9566
      seq.ToList():      2609

public static class TestListConstruction
{
   public static void Run()
   {
      var seq = Enumerable.Range(0, 100000).Select(i => i / 2);

      List<int> list = new List<int>();
      list.AddRange(seq);
      new List<int>(seq);
      seq.ToList();

      for(int i = 0; i < 6; i++)
      {
         list = new List<int>();
         Write("list.AddRange(seq): ", () => list.AddRange(seq));
         Write("new List<int>(seq): ", () => new List<int>(seq));
         Write("      seq.ToList(): ", () => seq.ToList());
         Console.WriteLine("");
      }
   }

   public static void Write(string label, Action action)
   {
      long result = Time(action);
      Console.WriteLine("{0} {1,8}", label, result);
   }

   public static long Time(Action action)
   {
      GC.Collect();
      GC.WaitForPendingFinalizers();
      Stopwatch stopwatch = Stopwatch.StartNew();
      action();
      stopwatch.Stop();
      return stopwatch.ElapsedTicks;
   }

}

[stephentoub]

LINQ's operators feed information between them using internal interfaces. When you do Enumerable.Range(...).Select(...).ToList(), that whole thing collapses down to a single method here that does all the work:

runtime/src/libraries/System.Linq/src/System/Linq/Select.SpeedOpt.cs

Lines 219 to 225 in 15ff723

	public List<TResult> ToList()
	{
	var results = new List<TResult>(_end - _start);
	Fill(SetCountAndGetSpan(results, _end - _start), _start, _selector);
	return results;
	}

runtime/src/libraries/System.Linq/src/System/Linq/Select.SpeedOpt.cs

Lines 227 to 233 in 15ff723

	private static void Fill(Span<TResult> results, int start, Func<int, TResult> func)
	{
	for (int i = 0; i < results.Length; i++, start++)
	{
	results[i] = func(start);
	}
	}

In contrast, List<T>, which is lower in the stack, knows nothing about the internal types used by LINQ to implement these operators: all it knows is it was given an IEnumerable<T> that it needs to enumerate. And while it does look for ICollection<T> on the type to use as an optimization, that internal SelectRangeIterator type from LINQ doesn't and can't implement ICollection<T>, and thus List<T> is forced to enumerate. The result is that, for this particular input, is thus comparing apples and oranges. If instead of:

var seq = Enumerable.Range(0, 100000).Select(i => i / 2);

you used this:

var seq = CreateInput(0, 100000, i => i / 2);
...
static IEnumerable<int> CreateInput(int start, int count, Func<int, int> func)
{
    int end = start + count;
    for (int i = start; i < end; i++) yield return func(i);
}

I expect you'd find that new List<T>(seq), new List<T>().AddRange(seq), and seq.ToList() all come out roughly the same.

(As an aside, it's generally better to use a tool like benchmarkdotnet to do these kinds of measurements, rather than the approach taken above.)

[stephentoub]

Right. How is that counter to what I said? I wrote:
"If instead of [...Enumetable.Range.Select...] you used [... CreateInput...] I expect you'd find that new List(seq), new List().AddRange(seq), and seq.ToList() all come out roughly the same." and you wrote "I don't see how that could be".

[ActivistInvestor]

Well, you said that the result would be comparable to using Range(...).Select(....), which In the cases where ToList() finds the IIListProvider and is able to get a count, it is not comparable.

[stephentoub]

But if I know that using Range(...).Select(...) is going to allow the internal optimizations to be done, why would I want to use a method that uses yield return, which precludes those optimizations?

I wasn't suggesting that you use an iterator instead in production. I was using it as an example to highlight the difference because of the implementation detail I was explaining.

[stephentoub]

Well, you said that the result would be comparable to using Range(...).Select(....),

No, I didn't. I said that ToList and new List would be comparable when using an iterator as the input.

[ActivistInvestor]

ok, that was my misunderstanding. I thought you were suggesting I use something like the CreateInput() method for production.

And while on that topic, I am trying to understand why IIListProvider is internal to begin with.

If I have a type that implements IEnumerable<T>, why should it be precluded from participating in or responding to TryGetNonEnumeratedCount()? I mean I understand the problem with compiler-generated iterators that result from yield return, but not with a custom IEnumerator<T>,

[stephentoub]

If I have a type that implements IEnumerable, why should it be precluded from participating in or responding to TryGetNonEnumeratedCount()?

You're not precluded. Implement ICollection<T> or ICollection and TryGetNonEnumeratedCount will use your Count.

(The presizing is also just a part of the difference you're seeing. A large chunk of the difference comes instead from what I cited initially, that the Enumerable.Range.Select.ToList implementation is able to avoid layers of interface dispatch and write directly into the list's backing store. That relies on passing more information between all these operators.)

I am trying to understand why IIListProvider is internal to begin with.

Because it's an implementation detail added as an internal optimization within LINQ. We evolve and change it over time. It's not even used in all builds; on targets where we care more about size, like for the browser, it's not implemented. It wasn't designed to be a public extensibility point.

[ActivistInvestor]

You're not precluded. Implement ICollection or ICollection and TryGetNonEnumeratedCount will use your Count.

I would surely implement ICollection<T> if it were possible. The problem is that some of those types must work with data from different sources, some of which can be remote and/or of indeterminant quantity. So, it isn't until runtime that they can indicate if they can produce a determinant count, or not.

After doing a little digging I understand what you say about that the optimizations for ToList() involving more than just pre-sizing the result. for example:

public static void FastAddRange<T>(this List<T> list, IEnumerable<T> items)
{
   if(items == null)
      throw new ArgumentNullException(nameof(items));
   if(list == null)
      throw new ArgumentNullException(nameof(list));
   if(items.TryGetNonEnumeratedCount(out int count) && count > 0)
   {
      int current = list.Count;
      CollectionsMarshal.SetCount(list, current + count);
      Span<T> span = CollectionsMarshal.AsSpan(list);
      int i = current;
      int end = current + count;
      using(IEnumerator<T> enumerator = items.GetEnumerator())
      {
         while(enumerator.MoveNext())
         {
            Debug.Assert(i < end, "Count mismatch");
            span[i++] = enumerator.Current;
         }
         Debug.Assert(i == end, "Count mismatch");
      }
   }
   else
   {
      list.AddRange(items);
   }
}

I'm coming out of this with the opinion that IIListProvider can certainly be useful beyond what it does internally as you cite above. I think it should be public, and that it should be in the same layer as IEnumerable<T>.

It's not uncommon for custom types that implement IEnumerable<T> to serve as upstream data sources that are extensively used with Linq operations, so I don't see why it shouldn't be possible to have a standardized way to query those custom types to find out if the volume of data they provide is determinant or not, via an interface that can leveraged by both Linq internals, as well as other user code. The same interface could provide a way for those custom types to efficiently expose their data as a List or array, as the IIListProvider interface provides for.

14 years ago, when I originally proposed IListProvider and TryGetNonEnumeratedCount(), (which I had coined ICountableEnumerable, and TryGetCount() respectively), Microsoft said "naa, we can't do that cause the selector function passed to Enumerable.Select() could have side effects that could alter the number of elements produced by the input sequence".

I'm not sure what has changed over the past 14 years, but Is that still an issue?

For reference, attached is that proposal with proof-of-concept from 14 years ago.
FastEnumerableExtensions.zip

[ActivistInvestor]

Thanks for your comments and insight

In contrast, List<T>, which is lower in the stack, knows nothing about the internal types used by LINQ to implement these operators: all it knows is it was given an IEnumerable<T> that it needs to enumerate. And while it does look for ICollection<T> on the type to use as an optimization, that internal SelectRangeIterator type from LINQ doesn't and can't implement ICollection<T>, and thus List<T> is forced to enumerate.

I believe that enumeration is always required if the source is not a collection, but I was focusing on the optimization of allocating the storage for the result (allocating space for the entire result in a single operation, verses incrementally growing the capacity as needed).

I tried your suggestion and here's what I get. I'll investigate further using BenchmarkDotNet when time permits:

  list.AddRange(seq):     12844
list2.AddRange(seq2):     33058
list3.AddRange2(seq):     15004
  new List<int>(seq):     12898
 new List<int>(seq2):     40059
        seq.ToList():      3269
       seq2.ToList():     32332

  list.AddRange(seq):     10632
list2.AddRange(seq2):     30746
list3.AddRange2(seq):     11180
  new List<int>(seq):     14702
 new List<int>(seq2):     38718
        seq.ToList():      1633
       seq2.ToList():     28701

  list.AddRange(seq):     10458
list2.AddRange(seq2):     31754
list3.AddRange2(seq):     10567
  new List<int>(seq):     11235
 new List<int>(seq2):     43103
        seq.ToList():      2011
       seq2.ToList():     31557

  list.AddRange(seq):     10450
list2.AddRange(seq2):     31943
list3.AddRange2(seq):     10679
  new List<int>(seq):     10981
 new List<int>(seq2):     44779
        seq.ToList():      2282
       seq2.ToList():     36013

public static class TestListConstruction
{

   static IEnumerable<int> CreateInput(int start, int count, Func<int, int> func)
   {
      int end = start + count;
      for(int i = start; i < end; i++) yield return func(i);
   }

   static int count = 100000;
   static Func<int, int> func = i => i + 1;
   public static void Run()
   {
      var seq = Enumerable.Range(0, count).Select(func);
      var seq2 = CreateInput(0, count, func);

      /// JIT code 
      List<int> list = new List<int>();
      List<int> list2 = new List<int>();
      List<int> list3 = new List<int>();
      list.AddRange(seq);
      new List<int>(seq);
      seq.ToList();
      list = new List<int>();
      list2 = new List<int>();
      list2.AddRange(seq2);
      list3.AddRange2(seq);
      new List<int>(seq2);
      seq2.ToList();

      for(int i = 0; i < 4; i++)
      {
         list = new List<int>();
         list2 = new List<int>();
         list3 = new List<int>();
         Write("  list.AddRange(seq): ", () => list.AddRange(seq));
         Write("list2.AddRange(seq2): ", () => list2.AddRange(seq2));
         Write("list3.AddRange2(seq): ", () => list3.AddRange2(seq));
         Write("  new List<int>(seq): ", () => new List<int>(seq));
         Write(" new List<int>(seq2): ", () => new List<int>(seq2));
         Write("        seq.ToList(): ", () => seq.ToList());
         Write("       seq2.ToList(): ", () => seq2.ToList());
         Console.WriteLine("");
      }
   }

   public static void Write(string label, Action action)
   {
      long result = Time(action);
      Console.WriteLine("{0} {1,8}", label, result);
   }

   public static long Time(Action action)
   {
      GC.Collect();
      GC.WaitForFullGCComplete();
      Stopwatch stopwatch = Stopwatch.StartNew();
      action();
      stopwatch.Stop();
      return stopwatch.ElapsedTicks;
   }

}

public static class ListExtension
{
   /// <summary>
   /// Surrogate for List<T>.AddRange()
   /// 
   /// Attempts to deduce the number of elements needed
   /// to hold the result, and if successful, increases 
   /// the list's capacity to same.
   /// 
   /// </summary>

   public static void AddRange2<T>(this List<T> list, IEnumerable<T> items)
   {
      if(items == null)
         throw new ArgumentNullException(nameof(items));
      if(list == null)
         throw new ArgumentNullException(nameof(list));
      if(items.TryGetNonEnumeratedCount(out int count))
      {
         CollectionsMarshal.SetCount(list, count);
         Span<T> span = CollectionsMarshal.AsSpan(list);
         int i = 0;
         using(IEnumerator<T> enumerator = items.GetEnumerator())
         {
            while(enumerator.MoveNext())
            {
               if(i >= count)
                  throw new InvalidOperationException("Count mismatch");
               span[i++] = enumerator.Current;
            }
            if(i != count)
               throw new InvalidOperationException("Count mismatch");
         }
      }
   }
}

[ghost]

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

Issue Details

---

Discussed in #98773

^{Originally posted by ActivistInvestor February 21, 2024}

After looking at the source and doing a simple test, I want to be sure that there's nothing wrong with my testing methodology, because I'm seeing much better performance from Enumerable.ToList<T>() verses new List<T>(IEnumerable<T>) and List<T>.AddRange(IEnumerable<T>)

list.AddRange(seq):     20290
new List<int>(seq):     12435
      seq.ToList():      3701

list.AddRange(seq):      9946
new List<int>(seq):     10026
      seq.ToList():      2787

list.AddRange(seq):      9614
new List<int>(seq):     16384
      seq.ToList():      4566

list.AddRange(seq):     16051
new List<int>(seq):     13566
      seq.ToList():      3022

list.AddRange(seq):      9777
new List<int>(seq):     10610
      seq.ToList():      2837

list.AddRange(seq):      8951
new List<int>(seq):      9566
      seq.ToList():      2609

public static class TestListConstruction
{
   public static void Run()
   {
      var seq = Enumerable.Range(0, 100000).Select(i => i / 2);

      List<int> list = new List<int>();
      list.AddRange(seq);
      new List<int>(seq);
      seq.ToList();

      for(int i = 0; i < 6; i++)
      {
         list = new List<int>();
         Write("list.AddRange(seq): ", () => list.AddRange(seq));
         Write("new List<int>(seq): ", () => new List<int>(seq));
         Write("      seq.ToList(): ", () => seq.ToList());
         Console.WriteLine("");
      }
   }

   public static void Write(string label, Action action)
   {
      long result = Time(action);
      Console.WriteLine("{0} {1,8}", label, result);
   }

   public static long Time(Action action)
   {
      GC.Collect();
      GC.WaitForPendingFinalizers();
      Stopwatch stopwatch = Stopwatch.StartNew();
      action();
      stopwatch.Stop();
      return stopwatch.ElapsedTicks;
   }

}

Author:	ActivistInvestor
Assignees:	-
Labels:	area-System.Linq, untriaged
Milestone:	-