Practical size limits of a Hashtable and Dictionary in C#

Question

What are the practical limits for the number of items a C# 4 Dictionary or Hashtable can contain and the total number of bytes these structures can reasonable contain?

I'll be working with large numbers of objects and want to know when these structures start to experience issues.

For context, I'll be using a 64-bit system with tons of memory. Also, I'll need to find objects using some form or 'key'. Given the performance demands, these objects will need to reside in memory, and many will be long-lived.

Feel free to suggest other approaches/patterns, although I need to avoid using third-party or open-source libraries. For specification reasons, I need to be able to build this using native C# (or C++\CLI).

Answer 1

One thing to point out is that the Dictionary is not going to hold the object itself (which may have a large memory footprint) but only a reference to the object so if the objects are complex this has no impact on the Dictionary size.

I have had collected several thousand items together in a Dictionary in memory and the issue is not the size of the Dictionary but the size of the objects themselves in memory. In these cases the Dictionary itself was a tiny portion of the memory involved.

One thing to think about in the cases of large Dictionaries is manually configuring and managing the Dictionary capacity. Under normal circumstances .Net manages this fine (in the current implementation if it runs out of space it resizes to a prime number that is at least twice the Dictionary current size). However, if you know you are going to create a large Dictionary or are going to expand the Dictionary instead of .Net guessing and resizing the Dictionary for you (which is relatively costly) it is probably better you doing this yourself (certainly with the initial size and probably managing later resizes). This can be done by managing the Dictionary capacity if you have a reasonable heuristic idea of what the capacity of the Dictionary should be. Microsoft recommends this on MSDN in their remarks on the Dictionary object. However, there seems to be some debate on the real value of this approach although I am not sure how rigorous that test is and if there are other optimisations that the .Net platform puts in place when a dictionary is resizing extremely rapidly.

This is a useful Stack Overflow question about object and memory size.

Answer 2

Practical limits can be relative to the machine your software is running on as well as how many objects you actually plan to contain within these data structures. As Oded mentioned, int.MaxValue is a large number, but does 2 billion items equate to a practical limit? Storing that many items in memory is likely not very practical.

Answer 3

Since the documentation does not tell where is the data physically stored and it does not specify the limit, I suggest you perform an experiment with the maximum expected size that you are likely to have and note the system memory before and after the storage allocation.

Answer 4

I recently updated the GitHub project hash-table-shootout. The standard GCC unordered map has about 1.8 gigabyte of overhead to store 40 million objects. This seems pretty atrocious to me, but even the best performer memory wise, the Google sparse_hash_map, takes 600 megabytes, and you pay a performance penalty for using it.

If you want speed, of the algorithms included, the Glib GHashTable is the fastest and has good memory performance (around 1.3 gigabyte overhead). The benchmark results are posted in Hash Table Shootout on GitHub.