Performance tip about List

If we want to maintain a list of data, the first way that comes to mind is List or Array. In this article, we want to review a point about the space occupied by List. The List class uses an internal array to store elements. When you prototype a list, if you use its default constructor, in the first element adding element, the list array inside the list class is created with 4 elements, and each time you add a new element to the list, it first checks that the array capacity Has the interior reached its maximum capacity or not? If it reaches the maximum value, it creates a new array twice the length of the previous array, copies all the elements of the previous array into the new array, and then adds the new element to the array. The following code shows the status of the internal array of the List class:

var list = new List<char>();   // []   Count:    0  Capacity: 0

list.Add('h');                 // ['h', null, null, null] 	Count: 1	Capacity: 4

list.Add('e');                 // ['h', 'e', null, null] 	Count: 2	Capacity: 4

list.Add('l');                 // ['h', 'e', 'l', null]     Count: 3	Capacity: 4
 
list.Add('l');                 // ['h', 'e', 'l', 'l']   	Count: 4	Capacity: 4  

list.Add('o');                 // ['h', 'e', 'l', 'l', 'o' , null, null, null]   Count:5	Capacity: 8

list.Add(' ');                 // ['h', 'e', 'l', 'l', 'o' , ' ', null, null]    Count:6	Capacity: 8

list.Add('w');                 // ['h', 'e', 'l', 'l', 'o' , ' ', 'w', null]     Count:7	Capacity: 8

list.Add('o');                 // ['h', 'e', 'l', 'l', 'o' , ' ', 'w', 'o']      Count:8	Capacity: 8

list.Add('r');                 // ['h', 'e', 'l', 'l', 'o' , ' ', 'w', 'o', 'r', null, null, null, null, null, null, null]   Count: 9	Capacity: 16

list.Add('l');                 // ['h', 'e', 'l', 'l', 'o' , ' ', 'w', 'o', 'r', 'l', null, null, null, null, null, null]    Count: 10	Capacity: 16

list.Add('d');                 // ['h', 'e', 'l', 'l', 'o' , ' ', 'w', 'o', 'r', 'l', 'd', null, null, null, null, null]     Count: 11	Capacity: 16

As you can see, when the maximum array capacity is reached, a new array with twice the length of the previous array is created: 4 > 8 > 16 > 32 > 64 > 128 ....

But if you specify the space required to add elements at the very beginning of creating the List class as follows:

var list = new List<char>(11);

 You eliminate the cost of new array prototyping and copying, and it will be practically better in terms of performance.

The second point is about deleting items from a list: Unlike adding an element that changes the size of the array, deleting an element from the list does not free up space. You can call the TrimExcess method to remove the occupied space. In the following code, the data of the variable in which the list is located is cleared, but the occupied space is still valid: 

List<int> numbers = new List<int>();
numbers.Add(5);
numbers.Add(1);
numbers.Add(3);
numbers.Add(2);
numbers.Add(0);
Console.WriteLine(numbers.Capacity);
numbers.Clear();
Console.WriteLine(numbers.Capacity);
numbers.TrimExcess();
Console.WriteLine(numbers.Capacity);

On the console screen you will see the following values: 

8
8
0

After the Clear method, the occupied space inside the array has not been cleared yet and shows the same 8. But after the TrimExcess method, the Capacity property value changes to 0. So if you want to clear the occupied space, you must first call the Clear method and then TrimExcess.

To check this out, we used the Benchmark Library: 

[MemoryDiagnoser]
public class ListMemoryAllocationTest
{
    public int Count { get; set; } = 100000;
    [Benchmark]
    public  void DefaultConstructor()
    {
        List<int> numbers = new List<int>();
        for (int i = 0; i < Count; i++)
        {
            numbers.Add(i);
        }
    }
    [Benchmark]
    public  void AddCountToConstructor()
    {
        List<int> numbers = new List<int>(Count);
        for (int i = 0; i < Count; i++)
        {
            numbers.Add(i);
        }
    }
}
public class Program
{
    public static void Main()
    {
        BenchmarkRunner.Run<ListMemoryAllocationTest>();
    }
}

Benchmark result: 

|                Method |     Mean |    Error |   StdDev |    Gen 0 |    Gen 1 |    Gen 2 | Allocated |

|    DefaultConstructor | 753.4 us | 14.80 us | 15.20 us | 628.9063 | 627.9297 | 237.3047 |  1,024 KB |
| AddCountToConstructor | 499.6 us |  9.86 us | 17.78 us | 255.8594 | 255.8594 |  95.7031 |    391 KB |

More memory is occupied when using the default constructor for List class.

:)

Powered by Froala Editor

Posted on Friday, September 10, 2021  |    Author : Farhad Zamani  |  Views : 48914  |  Status : Completed
Tags : C# Performance
Comments