In C#, will data be more densely packed together when using an array of value types, or with an array of reference types?
My reasoning is that an array of structs puts all the data together right here, right now, and while the same is true for the reference types (all the references are all together), they can point all over the place.
(I realize that it's encouraged to use C#'s collection interfaces wherever possible, and that readable code trumps premature optimization, but I was merely curious about how it worked.)
It depends on how you define densely packed. Yes the references will be all over the place, but you should also consider the size of the memory required to allocate the array.
An array of references is going to require a smaller contiguous block of memory then an array of large structs. The structs are going to be stored inline and thus each array element is going to be farther away from each other. With references, each array element is essentially a pointer to the reference, thus each element is smaller, and thus the elements are closer together.
The other issue to consider, is an array requires a contiguous block of memory. If allocated on the large object heap, where fragmentation is an issue as it is not compacted by the GC, then you are more likely to get out of memory exceptions for larger arrays. Even if you have plenty of free memory, you may not have enough free contiguous memory due to fragmentation. An array of large structs is going to require more contiguous memory than an array of references.
This isn't really directly applicable, but something else to consider when thinking about the memory requirements for arrays. Collections that use an array for an underlying type, which have a Capacity property, often grow the collection by allocating a new array twice the size of the previous and copying elements to the new array. This means if you have a collection of 256 items and add a 257th, a new 512 element array is allocated and the items are copied to it. The 256 item array will be deallocated, but during the copying process the collection requires memory for 768 items (but not contiguous, the 256 array + 512 array). So you could have enough free memory for 512 items, but not enough for 700 and thus growing the collection will fail with out of memory exception just because you tried to add a 257th item. Thus at times, growing a collection requires ~3 times as much memory as it currently occupies. That combined with the contiguous memory requirement, you can get out-of-memory exceptions when it seems you have plenty of memory.