List capacity and performance

Daily Knowledge Drop

When declaring an instance of List, explicitly specifying the expected capacity can improve performance when adding items to the list. However, specifying the capacity incorrectly could be detrimental to performance.

Example

No capacity

In the first example, a new List is declared without specifying a capacity, and then 20 items are added to the the list:

var list = new List<int>();

for (int i = 0; i < 20; i++)
{
    list.Add(i);
        Console.WriteLine($"List count: {list.Count} and " +
        $"the capacity is: {list.Capacity}");
}

Looking at the output, the default capacity when not explicitly specified is 4, and when this capacity is reached, the capacity is doubled:

List count: 1 and the capacity is: 4
List count: 2 and the capacity is: 4
List count: 3 and the capacity is: 4
List count: 4 and the capacity is: 4
List count: 5 and the capacity is: 8
List count: 6 and the capacity is: 8
List count: 7 and the capacity is: 8
List count: 8 and the capacity is: 8
List count: 9 and the capacity is: 16
List count: 10 and the capacity is: 16
List count: 11 and the capacity is: 16
List count: 12 and the capacity is: 16
List count: 13 and the capacity is: 16
List count: 14 and the capacity is: 16
List count: 15 and the capacity is: 16
List count: 16 and the capacity is: 16
List count: 17 and the capacity is: 32
List count: 18 and the capacity is: 32
List count: 19 and the capacity is: 32
List count: 20 and the capacity is: 32

With capacity

To specify the capacity, the value is passed to the constructor of the List:

// set the capacity to 10. Half the expected capacity
var list = new List<int>(10);

for (int i = 0; i < 20; i++)
{
    list.Add(i);
    Console.WriteLine($"List count: {list.Count} and " +
        $"the capacity is: {list.Capacity}");
}

Looking at the output, the capacity starts at 10, and is only doubled once:

List count: 1 and the capacity is: 10
List count: 2 and the capacity is: 10
List count: 3 and the capacity is: 10
List count: 4 and the capacity is: 10
List count: 5 and the capacity is: 10
List count: 6 and the capacity is: 10
List count: 7 and the capacity is: 10
List count: 8 and the capacity is: 10
List count: 9 and the capacity is: 10
List count: 10 and the capacity is: 10
List count: 11 and the capacity is: 20
List count: 12 and the capacity is: 20
List count: 13 and the capacity is: 20
List count: 14 and the capacity is: 20
List count: 15 and the capacity is: 20
List count: 16 and the capacity is: 20
List count: 17 and the capacity is: 20
List count: 18 and the capacity is: 20
List count: 19 and the capacity is: 20
List count: 20 and the capacity is: 20

Benchmarks

So how does specifying the capacity effect performance?

In the below examples, a List instance is declared, with the capacity explicitly set to varying sizes and then filled with values. The benchmarks evaluated performance when:

• no capacity specified
• the capacity was defined as exactly the expected size
• the capacity was defined as a half of the expected size
• the capacity was defined as a quarter of the expected size
• the capacity was defined as a tenth of the expected size

The code snippets for the benchmarks were as follows:

[Benchmark(Baseline = true)]
public void NoCapacity()
{
    /// no capacity specified
    var list = new List<int>();

    // Iterations was either 10, 1000, or 100000
    for (int i = 0; i < Iterations; i++)
    {
        list.Add(i);
    }
}

[Benchmark]
public void WithExactCapacity()
{
    // here the list defined with exact capacity
    var list = new List<int>(Iterations);

    for (int i = 0; i < Iterations; i++)
    {
        list.Add(i);
    }
}

[Benchmark]
public void WithHalfCapacity()
{
    // for the fractional tests, Iterations
    // was divided by 2, 4 and 10 (not all shown here)
    var list = new List<int>(Iterations / 2);

    for (int i = 0; i < Iterations; i++)
    {
        list.Add(i);
    }
}

// other tests trimmed

10 items

Benchmarking adding 10 items to the list:

Benchmarking adding 1000 items to the list:

1000 items

Benchmarking adding 100 000 items to the list:

100 000 items

From the results, one can see:

• In all cases, setting the list capacity to the exact expected size is twice as fast as not setting a capacity
• In most cases, setting the list capacity explicitly can result in significantly faster performance over not setting the capacity
• In some cases however, explicitly setting the list capacity to a value which is too small, is slower than not setting a capacity at all - in the benchmarks, setting the capacity to 1/10th of the expected values

Notes

When instantiating a list, it can be beneficial to set the capacity to the estimated final size. Even setting it to a fraction of the final expected size can be beneficial to performance.
However setting the capacity to a value too small can be detrimental to performance, in which case its better to not set a capacity at all. Benchmark the specific use case, with the expected capacity and make an informed decision on how to set (or not set) the capacity.

References

What’s new in C# 11? Dev friendly features

Daily Drop 196: 07-11-2022

At the start of 2022 I set myself the goal of learning one new coding related piece of knowledge a day.
It could be anything - some.NET / C# functionality I wasn't aware of, a design practice, a cool new coding technique, or just something I find interesting. It could be something I knew at one point but had forgotten, or something completely new, which I may or may never actually use.

The Daily Drop is a record of these pieces of knowledge - writing about and summarizing them helps re-enforce the information for myself, as well as potentially helps others learn something new as well.