Still investigating how to get FastAddRange() to be comparable with Enumerable.ToList(), which is showing very peculiar results.
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.InteropServices;
using System.Text;
namespace System.Linq
{
// project config:
//
// <PropertyGroup>
// <ConcurrentGarbageCollection>false</ConcurrentGarbageCollection>
// </PropertyGroup>
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 bool manageGC = true;
static int startcount = 1000; // starting data size, doubles on each step
static int steps = 7; // # of steps
static int count = startcount; // # list elements
static int iterations = 100; // iterations per-test
static int testCount = 7; // # of tests being measured
static int rowCount = testCount + 1; // # rows in output
static Table table;
static List<int> result;
static Func<int, int> func = i => i + 1;
static IEnumerable<int> s1 = null;
static IEnumerable<int> s2 = null;
static IEnumerable<int> s3 = null;
static List<int> list = null;
static string[] labels = new string[]
{
"List.Count",
"new List<int>().AddRange(s1))",
"new List<int>().AddRange(s2))",
"new List<int>().FastAddRange(s3))",
"new List<int>(s1))",
"new List<int>(s2))",
"s1.ToList())",
"s2.ToList())",
};
public static void Run()
{
/// Steps is the number of test steps, with the
/// data volume doubling on each step
/// int steps = 4; // 7; // includes a warm-up step that is discarded
/// Table row 0 is the count/size of the test data list
/// Each subsequent row represents a test.
/// Each column represents the timing for the data size
/// stored in row 0.
table = new Table(steps, testCount + 1);
for(int i = 0; i < steps + 1; i++)
{
s1 = Enumerable.Range(0, count).Select(func);
s2 = CreateInput(0, count, func);
s3 = Enumerable.Range(0, count).Select(func);
long[] times = new long[testCount + 1];
times[0] = count;
times[1] = Measure(() => new List<int>().AddRange(s1));
times[2] = Measure(() => new List<int>().AddRange(s2));
times[3] = Measure(() => new List<int>().FastAddRange(s3));
times[4] = Measure(() => result = new List<int>(s1));
times[5] = Measure(() => result = new List<int>(s2));
times[6] = Measure(() => result = s1.ToList());
times[7] = Measure(() => result = s2.ToList());
if(i > 0) // Discard first step (a warmup/pre-jit).
{
for(int k = 0; k < testCount + 1; k++)
table[i-1, k] = times[k];
}
/// Data volume is doubled on each step
count *= 2;
}
Dump();
}
static void Dump()
{
StringBuilder s = new StringBuilder();
int maxlabel = labels.Select(s => s.Length).Max();
string fmt = $"{{0,{maxlabel}}}: ";
for(int i = 0; i < testCount + 1; i++)
{
s.AppendFormat(fmt, labels[i]);
for(int j = 0; j < steps; j++)
{
s.AppendFormat("{0,8}", table[j, i]);
}
if(i == 0)
s.Append($"\n{new string('-', s.Length)}\n");
s.Append("\n");
}
Console.WriteLine($"\n{s}");
}
public static long Measure(Action action)
{
long ticks = 0;
for(int i = 0; i < iterations; i++)
{
GC.Collect(GC.MaxGeneration, GCCollectionMode.Forced, true, true);
GC.WaitForPendingFinalizers();
Stopwatch stopwatch = Stopwatch.StartNew();
action();
stopwatch.Stop();
ticks += stopwatch.ElapsedTicks;
}
return ticks / iterations;
}
}
class Table
{
int rows;
int columns;
long[,] table;
public Table(int rows, int cols)
{
table = new long[rows, cols];
this.rows = rows;
this.columns = cols;
}
public long this[int row, int col]
{
get { return table[row,col]; }
set { table[row,col] = value; }
}
}
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 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 start = list.Count;
int end = start + count;
CollectionsMarshal.SetCount(list, end);
Debug.Assert(list.Count == end);
Span<T> span = CollectionsMarshal.AsSpan(list);
Debug.Assert(span.Length == list.Count);
int i = start;
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 tried running this on a 7 year-old laptop with 8GB that was mostly in-use and I still see something I can't figure out. The second to last result (Enumerable.ToList() using an iterator that implements IIListProvider), just blows away all the other methods.
List.Count: 2000 4000 8000 16000 32000 64000 128000
--------------------------------------------------------------------------------------------
new List<int>().AddRange(s1)): 248 401 843 1844 820 1908 5038
new List<int>().AddRange(s2)): 606 1137 2073 1086 2183 5375 9717
new List<int>().FastAddRange(s3)): 357 454 636 333 653 1451 3365
new List<int>(s1)): 219 412 1095 441 897 1863 4076
new List<int>(s2)): 594 1208 470 884 1750 3518 8451
s1.ToList()): 247 253 289 96 181 363 1226 <----- !?!?!?
s2.ToList()): 609 1178 470 888 1820 3667 7138
