Reevaluate default capacity for List<T>

[IrisClasson]

Reevaluating the default capacity in List

The current default capacity for the internal array for the List type is set to 4 and a user has little to no control over how the internal array grows unless they implement their own generic List type.

This number, 4, with unknown origins, has remained unchanged since it's first implementation and might not be the optimal default capacity. The language has evolved with new types, and a new approach that extends beyond traditional OOP.

Would it make sense to reevaluate the default capacity?
It's current number as well as it's role in resizing the internal array?
And what about giving the user more control over how the internal array grows?

Note:
This discussion started between me and a Java developer when we compared the internal array default capacities between the two languages (Java uses 10). The number was based on an empirical study, and the author seemed to be regretful :)

[CyrusNajmabadi]

Moving to runtime. This is an api question, not a lang question. Thanks! :)

Note: you might be interested in the work we're looking into in the next C# with collections: dotnet/csharplang#5354

[IrisClasson]

Thank you! Apologies for that!
I'm reading through the link you provided, and I've gone down the rabbit hole of capacity discussions. I'll keep reading as I find this oddly fascinating :)

[EgorBo]

Would it make sense to reevaluate the default capacity?

Probably? Whoever wants to change that needs to do some sort of analysis of different workloads to estimate impact (how many lists are not small? what is the potential working set impact from a more aggressive resizing policy?)

And what about giving the user more control over how the internal array grows?

This is one is not easy - it is unlikely we want to introduce a new field in List<> to keep user's policy on how to grow it. It, probably, can be a static [readonly] field.

[jpluimers]

This number, 4, with unknown origins, has remained unchanged since it's first implementation and might not be the optimal default capacity.

I know that back in the days the .NET team did serious research into hard-coded numbers like this, but over the years lot's of useful publication material got lost due to various reasons. Like you I could not find any material on this particular number any more, but I really hope someone can shed some light on the origin of it.

[dajbych]

It would make sense to me if the default size would be 0 and increased to 4 with the addition of the first element. This doesn't matter much. If the programmer is interested in optimization, he enters his own value in the second constructor.

[CyrusNajmabadi]

that sounds like it would penalize every existing case where someone adds a value.

[IrisClasson]

Thanks for the input!
The default size is 0 and increased to 4 when the first item is added. If capacity is set to 0 when the list is created, it will default to 4 when the first item is added.
Anything >0 will skip the internal default capacity, however the internal is still going to grow by doubling when the internal array is at capacity and another item(s) is added.

[bartonjs]

It would make sense to me if the default size would be 0 and increased to 4 with the addition of the first element.

That's how it works.

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs

Lines 23 to 40 in 264d739

	private const int DefaultCapacity = 4;
	internal T[] _items; // Do not rename (binary serialization)
	internal int _size; // Do not rename (binary serialization)
	internal int _version; // Do not rename (binary serialization)
	#pragma warning disable CA1825 // avoid the extra generic instantiation for Array.Empty<T>()
	private static readonly T[] s_emptyArray = new T[0];
	#pragma warning restore CA1825
	// Constructs a List. The list is initially empty and has a capacity
	// of zero. Upon adding the first element to the list the capacity is
	// increased to DefaultCapacity, and then increased in multiples of two
	// as required.
	public List()
	{
	_items = s_emptyArray;
	}

[TonyValenti]

I imagine that the best initial default for List should have changed around the time .ToList() came into existence.