Memory footprint of multi-dimensional arrays

[Sean Kelly]

== Quote from Ben Mitchell (Arisian at gmail.com)'s article
> So, I was watching my D program eat up ~1GB of ram doing something my back of the envelope
calculation said should only be taking a few hundred MB max, and I started playing around.  Turns out
that if I do:
> ubyte[][] b = new ubyte[][](3, 10485760);
> It takes about 30MB of main memory, as would be expected.  If, on the other hand, I reverse the order
of the indexing and do:
> ubyte[][] b = new ubyte[][](10485760, 3);
> It takes about 250MB of main memory.  This seems totally absurd to me; I can only assume this is
because it's an array of (potentially arbitrary size) dynamic arrays, and there's ~220MB of bookkeeping
information being stored.   Is there any way around this?  Can I somehow tell the compiler it's a
symmetric array?  Can I make a dynamic array of static arrays of size 3?  I can reverse the indexing if I
have to, but it would make the rest of my code very counter-intuitive, and it just doesn't seem like it
should make an order of magnitude difference in memory usage.

In the first case, you have an array containing three pointers to arrays of 10485760 bytes each, for a
minimum total of (3 * 4) + (3 * 10485760) bytes -- around 30 MB.  In the second case, you have an
array containing 10485760 pointers to arrays of 3 bytes each, for a minimum total of (10485760 * 4) +
(10485760 * 3) -- about 200 MB.  Now given the actual GC implementation, the minimum block size
allocated is actually 16 bytes rather than 3 bytes so the second number is actually (10485760 * 16),
bringing the memory used for the allocation to roughly 300 MB by my estimation.  The basic issue here
is that this is a ragged array so the memory is not allocated in one large contiguous block but rather a
bunch of linked dynamic blocks.


Sean