www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Allocating large 2D array in D

reply "Sparsh Mittal" <sparsh0mittal gmail.com> writes:
I am allocating 2d array as:

double[gridSize][gridSize] gridInfo;

which works for small dimension, but for large dimension, 16Mb 
limit comes.

Would you please tell me how do allocate a large 2d array (which 
has to be done as a dynamic array)? It is a square grid and 
dimensions are already known.

I also searched internet but could not find an answer. Thanks.
Feb 04 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Sparsh Mittal:

 I am allocating 2d array as:

 double[gridSize][gridSize] gridInfo;

 which works for small dimension, but for large dimension, 16Mb 
 limit comes.
Walter has decided to introduce a very low limit for the size of static arrays. (Both Clang and G++ support larger ones).
 Would you please tell me how do allocate a large 2d array 
 (which has to be done as a dynamic array)? It is a square grid 
 and dimensions are already known.
This allocates your array, filled with NaNs: auto gridInfo = new double[][](gridSize, gridSize); If you want to skip most or all the initialization then take a look at two functions in std.array. In most cases the "partially initialized" function is enough, and it's quite safer. Bye, bearophile
Feb 04 2013
parent "Sparsh Mittal" <sparsh0mittal gmail.com> writes:
Thanks for your prompt reply. It was very helpful.
Feb 04 2013
prev sibling next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 4 February 2013 at 15:23:20 UTC, Sparsh Mittal wrote:
 I am allocating 2d array as:

 double[gridSize][gridSize] gridInfo;

 which works for small dimension, but for large dimension, 16Mb 
 limit comes.

 Would you please tell me how do allocate a large 2d array 
 (which has to be done as a dynamic array)? It is a square grid 
 and dimensions are already known.

 I also searched internet but could not find an answer. Thanks.
If all (but last of) the dimensions are known at compile time, then you can dynamically allocate an array of fixed sized arrays: //---- enum size_t gridSize = 4_000; enum size_t total = gridSize * gridSize; static assert (total == 16_000_000); //16 million doubles total static assert (total * double.sizeof == 128_000_000); //126 Megs allocated void main() { double[gridSize][] gridInfo = new double[gridSize][](gridSize); } //---- This will give you a dense array: Eg: all the data is contiguous in memory. You can also use the "convenient 2D notation": //---- import std.stdio; enum gridSize = 4; enum total = gridSize * gridSize; void main() { double[][] gridInfo = new double[][](gridSize, gridSize); } //---- DO NOTE though that in this case, you have a (probably compact but) jagged array. What this means is that instead of having one single solid block of data, you have a top level array, that references a second level of arrays. EG: It is (should be) equivalent to: //---- enum size_t gridSize = 4_000; enum size_t total = gridSize * gridSize; void main() { double[][] gridInfo = new double[][](gridSize); //Create an array of empty array; //Initialize gridInfo. Scope block to avoid polution { double[] megaBlock = new double[](total); //Create all the data foreach (i ; 0 .. gridSize) //Iterate on each gridInfo entry { size_t offset = i * gridSize; gridInfo[i] = megaBlock[offset .. offset + gridSize];//Connect the arrays; } } } //---- It's not a big deal, but indexing *might* be a little slower with this scheme.
Feb 04 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:

 If all (but last of) the dimensions are known at compile time, 
 then you can dynamically allocate an array of fixed sized 
 arrays:

 //----
 enum size_t gridSize = 4_000;
 enum size_t total   = gridSize * gridSize;
 static assert (total == 16_000_000); //16 million doubles total
 static assert (total * double.sizeof == 128_000_000); //126 
 Megs allocated

 void main()
 {
     double[gridSize][] gridInfo = new 
 double[gridSize][](gridSize);
 }
 //----

 This will give you a dense array: Eg: all the data is 
 contiguous in memory.
Nice. This idiom should be added to the D docs. Bye, bearophile
Feb 04 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 04 Feb 2013 10:58:36 -0500, bearophile <bearophileHUGS lycos.com>  
wrote:

 monarch_dodra:

 If all (but last of) the dimensions are known at compile time, then you  
 can dynamically allocate an array of fixed sized arrays:

 //----
 enum size_t gridSize = 4_000;
 enum size_t total   = gridSize * gridSize;
 static assert (total == 16_000_000); //16 million doubles total
 static assert (total * double.sizeof == 128_000_000); //126 Megs  
 allocated

 void main()
 {
     double[gridSize][] gridInfo = new double[gridSize][](gridSize);
 }
 //----

 This will give you a dense array: Eg: all the data is contiguous in  
 memory.
Nice. This idiom should be added to the D docs.
Wow, this is something I didn't know was possible. Very useful! BTW, "all (but last of) the dimensions" isn't correct, you know them all in your example, and it looks great! -Steve
Feb 04 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Steven Schveighoffer:

 Wow, this is something I didn't know was possible.  Very useful!
It's it cute when you use a language almost daily for few years, and then you see a new way to allocate built-in arrays? :-) Bye, bearophile
Feb 04 2013
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 4 February 2013 at 16:54:37 UTC, bearophile wrote:
 Steven Schveighoffer:

 Wow, this is something I didn't know was possible.  Very 
 useful!
It's it cute when you use a language almost daily for few years, and then you see a new way to allocate built-in arrays? :-) Bye, bearophile
Technically, the straight up "C - style" syntax also does this just as well: "int[2][] a = new int[2][2];" Since the last "[2]" gets rewritten to "[](2)" But when written that way, I find it is not very clear what happens. Ideally, I wish we could allocate static arrays on the heap easily: "int[2]* p = new int[2]()" Anybody know why this doesn't work? In a GC language like D, that has to track "capacity/usage" of its dynamic arrays, there is a real gain to being able to specify: I want my damn array to be fixed in size: Don't track any growing information for me.
Feb 04 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:

 Ideally, I wish we could allocate static arrays on the heap 
 easily:

 "int[2]* p = new int[2]()"
To do that I wrap the array inside a static struct: struct Arr { int[2] a; } Arr* data = new Arr; writeln(data.a[1]);
 Anybody know why this doesn't work?
Maybe it's just a matter of syntax. You see it if you use: struct Arr { int[2] a; alias this = a; } Arr* data = new Arr; Now what's data[1]? It's data.a[1] or is it the second (missing) struct Arr? So to do that you need transparent references, like "ref int[2]", that in D are only present inside functions. Bye, bearophile
Feb 04 2013
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
See also:

http://d.puremagic.com/issues/show_bug.cgi?id=9265

Bye,
bearophile
Feb 04 2013
prev sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 4 February 2013 at 22:02:48 UTC, bearophile wrote:
 monarch_dodra:

 Ideally, I wish we could allocate static arrays on the heap 
 easily:

 "int[2]* p = new int[2]()"
To do that I wrap the array inside a static struct: struct Arr { int[2] a; } Arr* data = new Arr; writeln(data.a[1]); [SNIP] Bye, bearophile
Yeah... but then I do that, I also tend to smash against the initial: //---- struct Arr { double[4000][4000] a; } Arr* data = new Arr; writeln(data.a[1]); //---- "Error: index 4000 overflow for static array" //---- I don't fully understand what this means, so I haven't complained yet. Is this a "legit error" on my end, with the compiler protecting me, or a false positive, where the compiler thinks I want to allocate Arr on the stack...?
Feb 04 2013
prev sibling parent Denis Shelomovskij <verylonglogin.reg gmail.com> writes:
04.02.2013 20:54, bearophile пишет:
 Steven Schveighoffer:

 Wow, this is something I didn't know was possible.  Very useful!
It's it cute when you use a language almost daily for few years, and then you see a new way to allocate built-in arrays? :-)
Just a small obvious note that this trick will work for every n-dimentional array. And it's not cute when there is a sliceable multidimensional rectangular array implementation for a few years and almost nobody knows about it. http://denis-sh.github.com/phobos-additions/unstd.multidimensionalarray.html From examples: --- // The head array can be dynamic int[4][3][] darr3 = sarr3[]; auto matrix31 = mdimArray(darr3); // Works like previous one --- -- Денис В. Шеломовский Denis V. Shelomovskij
Feb 07 2013
prev sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On 2013-13-04 17:02, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 BTW, "all (but last of) the dimensions" isn't correct, you know them all  
 in your example, and it looks great!
I believe his point was that this also works if you don't know the last dimension beforehand. -- Simen
Feb 04 2013
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Feb 04, 2013 at 04:58:36PM +0100, bearophile wrote:
 monarch_dodra:
 
If all (but last of) the dimensions are known at compile time,
then you can dynamically allocate an array of fixed sized arrays:

//----
enum size_t gridSize = 4_000;
enum size_t total   = gridSize * gridSize;
static assert (total == 16_000_000); //16 million doubles total
static assert (total * double.sizeof == 128_000_000); //126 Megs
allocated

void main()
{
    double[gridSize][] gridInfo = new
double[gridSize][](gridSize);
}
//----

This will give you a dense array: Eg: all the data is contiguous
in memory.
Nice. This idiom should be added to the D docs.
[...] Added to wiki: http://wiki.dlang.org/Dense_multidimensional_arrays T -- If Java had true garbage collection, most programs would delete themselves upon execution. -- Robert Sewell
Feb 05 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
H. S. Teoh:

 Added to wiki: 
 http://wiki.dlang.org/Dense_multidimensional_arrays
It contains: enum columns = 100; int rows = 100; double[gridSize][] gridInfo = new double[columns][](rows); gridSize is undefined. I suggest to write something like: enum nColumns = 100; int nRows = 120; double[nColumns][] matrix2 = new double[nColumns][](nRows); Bye, bearophile
Feb 05 2013
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Feb 05, 2013 at 07:38:40PM +0100, bearophile wrote:
 H. S. Teoh:
 
Added to wiki: http://wiki.dlang.org/Dense_multidimensional_arrays
It contains: enum columns = 100; int rows = 100; double[gridSize][] gridInfo = new double[columns][](rows); gridSize is undefined.
[...] Oops, that was a typo. Fixed. P.S. Feel free to edit the page yourself if you see a mistake. That's what a wiki is for, after all. T -- "I suspect the best way to deal with procrastination is to put off the procrastination itself until later. I've been meaning to try this, but haven't gotten around to it yet. " -- swr
Feb 05 2013
prev sibling parent "Sparsh Mittal" <sparsh0mittal gmail.com> writes:
 It's not a big deal, but indexing *might* be a little slower 
 with this scheme.
Thanks a lot for your reply. It was extremely useful, since I am optimizing for performance.
Feb 04 2013
prev sibling parent Denis Shelomovskij <verylonglogin.reg gmail.com> writes:
04.02.2013 19:23, Sparsh Mittal пишет:
 I am allocating 2d array as:

 double[gridSize][gridSize] gridInfo;

 which works for small dimension, but for large dimension, 16Mb limit comes.

 Would you please tell me how do allocate a large 2d array (which has to
 be done as a dynamic array)? It is a square grid and dimensions are
 already known.

 I also searched internet but could not find an answer. Thanks.
A common problem. Use unstd.multidimensionalarray to obtain a sliceable multidimensional rectangular arrays (currently only implemented for dimensions count (not lengths) known at CT): http://denis-sh.github.com/phobos-additions/unstd.multidimensionalarray.html -- Денис В. Шеломовский Denis V. Shelomovskij
Feb 07 2013