5

After reading the excellent accepted answer in this question:

How is the c#/.net 3.5 dictionary implemented?

I decided to set my initial capacity to a large guess and then trim it after I read in all values. How can I do this? That is, how can I trim a Dictionary so the gc will collect the unused space later?

My goal with this is optimization. I often have large datasets and the time penalty for small datasets is acceptable. I want to avoid the overhead of reallocating and copying the data that is incured with small initial capacities on large datasets.

Community
  • 1
  • 1
philologon
  • 2,093
  • 4
  • 19
  • 35
  • Resizing a dictionary is indeed expensive. Be sure to benchmark both approaches, because downsizing can also cost a lot of time. – usr Mar 15 '14 at 21:11
  • 1
    Given that the capacity increases are exponential, it ends up not being particularly costly, when aggregated over all of the items being added. Doing all of this work may not be as much of an improvement as you'd expect. – Servy Mar 15 '14 at 21:13
  • While watching answers come in on this, I am also attempting something similar with a List, but in this instance, I know the List initial size: 3,039,104. Setting this initial size I am getting about a 4% speed improvement -- pretty much the "not worth it" that Servy and others have pointed out. – philologon Mar 15 '14 at 21:28

3 Answers3

3

According to Reflector, the Dictionary class never shrinks. void Resize() is hard-coded to always double the size.

You can probably create a new dictionary and use the respective constructor to copy over the items. This will be quite inefficient.

Or, implement your own dictionary with the existing one as a blue-print. This is less work than you might think at first.

Be sure to benchmark both approaches.

usr
  • 168,620
  • 35
  • 240
  • 369
  • I should add, 7 years later, that this answer reflects the state of previous .NET versions. – usr Jun 29 '21 at 10:41
2

You might consider putting your data in a list first. Then you know the list's size, and can create a dictionary with that capacity (now exactly right for the data you want) and populate it.

Allowing the list to dynamically resize (as you add the elements) should be cheaper than allowing a dictionary to resize. (But, as others have noted, test the performance yourself!) Resizing a dictionary involves a rehashing operation, which means every element's GetHashCode will get called again, as well as the reference being copied into the new data structure. Resizing a list just means copying the references, so should be cheaper.

Joe White
  • 94,807
  • 60
  • 220
  • 330
2

In .NET 5 there is the method TrimExcess doing exactly what you're asking:

Sets the capacity of this dictionary to what it would be if it had been originally initialized with all its entries.

Phate01
  • 2,499
  • 2
  • 30
  • 55