Memory usage, SortedList vs List problem

Question

I was using SortedList() in a class which stores about 15-100K data.

Recently my requirements changed, data should not be stored as sorted any more so I switched to List().

However in this case I noticed that List() consumes about 20%+ more memory.

9K items:

• SortedList: 105MB
• List: 125MB

15K items:

• SortedList: 115MB
• List: 140MB

In the environment I develop, memory is quite crucial. Instead of List() what can I use to avoid this extra memory consumption and still have a non-sorted list?

P.S. I do use a HashSet(Of String) to provide uniqueness check while using List(Of) to simulate SortedList.ContainsKey() although I don't think it can bring such memory overhead.

P.S. 2: My app has got about 80 MB base memory allocation in the startup. So numbers should read as 105-80=25, 125-80 =45 and so on

RESULTS

Thanks for the all answers, final results are:

• You should set the correct capacity to save memory
• Hashset is very bad about memory, and consumes way more than expectations. This was the problem. Somehow SortedList() manages to use less memory for a similar functionality.

Some Bencmarks: 500 chars, 250000 insert

List(OF STring)(50000)

274 ms - 226 MB

SortedList(Of String, String)(50000)

34868 ms - 230 Mb

Hashset

420 ms - 232 MB

Dictionary(OF String, Object)

486 ms - 234 MB

Although when I changed decreased count to 25, then:

Hashset for 600.000 iteration 300 Mb where List() is 286 Mb

Also about Hashset memory usage: http://blog.mischel.com/2008/04/09/hashset-limitations/ Dictionary(Of string, object) was not much better either in my test.

Answer 1

Are you preallocating the List<T> capacity?

Small experiment that I did:

This program takes ~640MB

List<int> list = new List<int>(0);

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

This program takes ~320MB

List<int> list = new List<int>(100000000);

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

Answer 2

A List<T> with 9k items would have a capacity between 9k and 18k, so the overhead for those items would be between 36 and 72 kilobyte (the double on a 64 bit system).

Clearly the 72 kB is not even close to the 20 MB difference that you see, so the memory use of the list itself can not be the cause. Escpecially considering that the sorted list also has to keep a reference to each object, so the memory usage should be the same.

So, either there is something else using memory, or you are not looking at the actual memory usage of the application. If you are looking in the task manager, you are not seeing how much memory is used, only how much the memory manager has allocated.