Introduction
When working with collections in C#, especially List<T>, understanding how they grow and the implications on performance is very important. This blog post looks into the inner workings of the List<T> in C# and examines optimising performance by defining the length of a c# list when you create it.
Understanding the List<T> in C#
List<T> is one of the most frequently used collections in C#. Under the hood, List<T> is implemented as an array. It’s a dynamic array, meaning it can grow in size as needed. However, this convenience comes at a cost, particularly when it comes to performance.
How Lists Grow
When you create a List<T> without specifying its size, it starts with a default capacity. In .NET, this default capacity is typically small, like 4. As you add elements, and the list reaches its capacity, it needs to grow. Here’s where the performance hit comes in.
The Process of Extending a List
- Allocate New Array: When the current capacity is reached, the list creates a new array. This new array is typically double the size of the previous one. For example, if the list had a capacity of 4, the new array will have a capacity of 8.
- Copy Elements: The elements from the old array are copied to the new, larger array. This copying process is time-consuming, especially as the list grows larger.
- Deallocate Old Array: The old array is then deallocated. The repeated allocation and deallocation also add to the time complexity.
The Cost of Growing
This process of growing has two main costs:
- Time Cost: Each time the list grows, it incurs a performance penalty due to the copying of elements to the new array.
- Memory Overhead: The doubling strategy often means that the list might allocate more memory than it immediately needs, leading to inefficient memory usage.
Defining List Length
You can mitigate these costs by initialising the List<T> with a predefined capacity. For instance, if you know you’ll be storing approximately 1000 elements, you can initialise the list as follows:
List<int> myList = new List<int>(1000);Benefits of Predefining List Capacity
- Reduced Memory Allocations: By specifying the capacity, you reduce the number of times the list needs to reallocate memory as it grows. This is especially beneficial in performance-critical applications or when dealing with very large lists.
- Efficient Memory Usage: Predefining the length ensures that the list uses only as much memory as it needs, avoiding the overhead of over-allocated memory.
- Performance Improvement: The time saved by reducing memory allocation and copying operations can be significant, especially in scenarios where lists are frequently resized.
Best Practices
- Estimate Capacity When Possible: If you have an estimate of the number of elements expected, always initialise the list with that capacity.
- Balance Between Memory and Performance: Overestimating the capacity might lead to wasted memory. Aim for a balance based on your application’s needs.
- Use the Default Constructor When Size is Unpredictable: If the size of the list is highly unpredictable, using the default constructor is still a good choice.
- Profile Your Application: Use profiling tools to understand the performance implications in your specific context. Optimisation needs can vary widely based on how your application uses lists.
Conclusion
Understanding the internal mechanics of List<T> in C#, and the impact of list resizing on performance is crucial.
Optimising performance by defining the length of a c# list when you create it, can yield significant performance improvements, especially in scenarios with large or frequently modified collections.
As with any optimisation technique, it’s important to consider your application’s specific needs and behaviours and use profiling tools to guide your optimisation strategies.
Remember, small software development optimisations can substantially improve your applications’ overall efficiency and responsiveness.
I have written a number of other blog posts about collections and performance testing here HashSet<T> v List<T>, Integrating BenchmarkDotNet in Azure DevOps Pipeline for Performance Measurement.
The official dotnet documentation for lists is here: – https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1?view=net-8.0
