Memory footprint of multi-dimensional arrays

[Simen Kjaeraas]

On Fri, 18 Apr 2008 18:15:45 +0200, BCS <BCS at pathlink.com> wrote:

> Ben Mitchell wrote:
>> 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.
>>     -  Ben
>
> one (kinda ugly) solution would be to allocate the whole thing as a  
> single huge ubyte[] array and slice out the 1M 3 byte arrays:
>
>
> auto tmp = new ubyte[](3*10485760 +  5);
>
> ubyte[][] b;
> b.length = 10485760;
> foreach(uint i, ref bp; b) bp = tmp[i*3.. (i+1)*3];
>
> A little template magic might be able to do this recursively for nested  
> dynamic arrays


Wouldn't that end up taking just as much space?  b would be an array of
10485760 slices, each having a pointer/length pair taking up 8 bytes each,  
no?
Might save some due to GC wanting bigger slices than 3 bytes, but still.

Now, using a struct with overloaded opIndex (and opSlice, if you want)
should be lighter. Something like this (untested)?


struct Foo
{
   ubyte[] data;
   size_t sz1, sz2;

   static Foo opCall(size_t size1, size_t size2)
   {
     Foo tmp;
     tmp.data.length = size1 * size2;
     tmp.sz1 = size1;
     tmp.sz2 = size2;
     return tmp;
   }

   ubyte[] opIndex(size_t index)
   {
     return data[index * size2..index * size2 + size1];
   }

   void opIndexAssign(ubyte[] value, size_t index)
   {
     data[index * size2..index * size2 + size1] = value;
   }
}

-- Simen