11

Are .NET collections with large number of items apt to be stored in the LOH?

I'm curious about List and Dictionary specifically. In my code, I store a large number (40k+) of relatively small objects (lets say 1k) in temporary Lists and Dictionarys for processing. Does the number of items in these collections increase the likelihood of being put on the LOH?

For list, assuming that List is implemented as a doubly linked list, then the number of elements should not increase the size of the actual List object, but I'd like to know for sure.

Thanks

Mehrdad Afshari
  • 414,610
  • 91
  • 852
  • 789
Alan
  • 45,915
  • 17
  • 113
  • 134

4 Answers4

14

Objects will only be stored on the LOH if they are over 85,000 bytes. A large list (especially of structs) will often get allocated here.

However, Dictionary's are less likely, since they're storing an array of buckets, so unless the generate enough buckets so the array becomes >85000 bytes, it's unlikely. A list of 40k elements will be stored on the LOH, even if they're classes (since the object references in each element will cause the list to be 160k on x86, 320k on x64 systems). The individual elements will be on the standard heap, though, so will get compacted, etc.

If you are using a doubly linked list instead of a standard List, it is very unlikely that it will get stored on the LOH. Each element of the list will be small (just a single node with references to the next/previous nodes), so no single object will be >85k bytes.

For details on the LOH, this is a great blog entry.

Reed Copsey
  • 554,122
  • 78
  • 1,158
  • 1,373
  • Arrays of doubles have a lower limit, as they are faster when allied on 8 byte bounders, (likewise of List as it uses an array) – Ian Ringrose Jan 29 '10 at 09:47
  • 2
    The implementation of Dictionary is as a coalesced hashtable (chaining, but using an array to store the chained buckets, so as to gain some of the advantages of open addressing as far as cache use goes), so with 40k they will contain an internal array of 40000 * (keysize + valuesize + 8 [an int to memoise the hashcode and one to store the next index in the chain]) and an internal array of 40000 * 4 (int size). That 40000 will actually be at least 43627, maybe as much as 90523 depending on the grown history, as it uses pre-computed primes. As such, there'll definitely be... – Jon Hanna Dec 28 '13 at 01:15
  • 1
    ... at least one 436270-byte array (if key and value were both byte-sized, more for any other size), and at least one 174508-byte array of indices. Hence a 40k element dictionary would **always** have some of its internal representation in the LOH (the dictionary itself is more like 40-80bytes, and in one of the generational heaps, no matter what the size). – Jon Hanna Dec 28 '13 at 01:22
  • Echoing what Jon said. In my experience, Dictionaries are one of the biggest offendors, in using LOH, and leading to memory fragmentation. – ToolmakerSteve May 01 '14 at 03:49
  • Some implementations of linked list do not allocate each node separately; they use an array of structs instead. Instead of references, the links are indices to the array. This decreases allocation cost and number of objects the GC has to handle, i.e. saves work for the GC. For such implementation, this issue is still present. The standard LinkedList is not one of those implementations, though. – Palec Sep 11 '20 at 14:13
4

System.Collections.Generic.List is implemented as an array internally, not a linked list. And yes, if the size of the collection is large it'll be allocated on large object heap (note that the size of the array is important, if you have a small array of large reference types, it won't be allocated on LOH).

Mehrdad Afshari
  • 414,610
  • 91
  • 852
  • 789
4

List is implemented as an array. As such the array will be put into LOH, but the List object itself will not.

The same basically applies to Dictionary as well. It too is using an array of buckets internally, which basically store the key/value pairs you add.

grover
  • 2,265
  • 1
  • 16
  • 15
0

Dictionary has O(LOG N) vector for the key/value, so in 40K+ objects your pretty safe. As said here before List is implemented as array so big list are indeed on the LOH. You can check if you object is on the LOH using SOS.

Shay Erlichmen
  • 31,691
  • 7
  • 68
  • 87