C# List<> should I lower capacity as I remove items?

Question

I have a List container which can potentially have up to 100,000 items in to start with. While the program is running this list will slowly empty, should I alter the capacity as I empty the list?

I have done some testing and execution time seems to be the same, but is there much overhead to lowering the capacity of a list? I can find lots of information about increasing the capacity but not much on lowering it.

Answer 1

Unless you have a very low amount of memory, this is a micro-optimization.

Normally, there is no need to change the capacity of a List<>.

From the TrimExcess method documentation:

This method can be used to minimize a collection's memory overhead if no new elements will be added to the collection. The cost of reallocating and copying a large List<T> can be considerable, however, so the TrimExcess method does nothing if the list is at more than 90 percent of capacity. This avoids incurring a large reallocation cost for a relatively small gain.

Answer 2

Do the math: 100,000 items * 4 bytes per item = roughtly 400KB. If that's too much memory overhead for your program, you can call TrimExcess, as Oded points out recreate smaller lists once it gets smaller. (I'm not sure that reducing the capacity will actually have the effect you're going for.)

Answer 3

Lowering the capacity of a list involves a new backing array and copying the data across, so it's a relatively expensive operation.

In your particular case I would say it is not worth it unless you start hitting memory problems.

One strategy that can be employed if it were to become a real problem is to create a 'chunked' implementation of IList<> which uses not one array, but multiple, each of preconfigured size , with additional chunks (fixed size arrays) added as the previous fills up. This also allows the list to shrink relatively inexpensively by releasing unused chunks as items are removed, whilst minimizing the memory overhead to just one non-full chunk (the last).

This approach adds a performance overhead to all operations on the list though, as the list has to calculate which chunk an items resides and create new chunks as required. So it is not useful unless you truly have a memory problem and a list that truly changes size dramatically over time.