www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How are 2D static arrays allocated?

reply Jesse Phillips <jessekphillips gmail.com> writes:
In C allocating a static 2D array gives a continues chunk of memory. Java 
creates an array that points to more arrays. Just wondering how D handles 
this.
Nov 03 2008
next sibling parent BCS <ao pathlink.com> writes:
Reply to Jesse,


 In C allocating a static 2D array gives a continues chunk of memory.
 Java creates an array that points to more arrays. Just wondering how D
 handles this.
 


int[5][6] a; // like C
Nov 03 2008
prev sibling next sibling parent reply "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Mon, Nov 3, 2008 at 11:30 PM, Jesse Phillips
<jessekphillips gmail.com> wrote:

 In C allocating a static 2D array gives a continues chunk of memory. Java
 creates an array that points to more arrays. Just wondering how D handles
 this.


If it's a 2D fixed-size array, like:

int[5][6] x;

Then it is allocated as a single chunk of memory, and when you index
it, it calculates the offset into that block of memory.

But 2D dynamic arrays:

int[][] y;

Are handled like in Java - an array of arrays.  When you index it, it
indexes the first array, then indexes the second array.
Nov 03 2008
parent Jesse Phillips <jessekphillips gmail.com> writes:
On Tue, 04 Nov 2008 01:34:26 -0500, Jarrett Billingsley wrote:


 On Mon, Nov 3, 2008 at 11:30 PM, Jesse Phillips
 <jessekphillips gmail.com> wrote:

 In C allocating a static 2D array gives a continues chunk of memory.
 Java creates an array that points to more arrays. Just wondering how D
 handles this.


 
 If it's a 2D fixed-size array, like:
 
 int[5][6] x;
 
 Then it is allocated as a single chunk of memory, and when you index it,
 it calculates the offset into that block of memory.
 
 But 2D dynamic arrays:
 
 int[][] y;
 
 Are handled like in Java - an array of arrays.  When you index it, it
 indexes the first array, then indexes the second array.


Thanks, I figured it would work like this be it for C compatibility or 
not.
Nov 04 2008
prev sibling next sibling parent reply Robert Fraser <fraserofthenight gmail.com> writes:
Jesse Phillips wrote:

 In C allocating a static 2D array gives a continues chunk of memory. Java 
 creates an array that points to more arrays. Just wondering how D handles 
 this.


The only reason static arrays seem to exist at all (as well as good 
explanation for their incongruity with other types) is C compatibility.
Nov 04 2008
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Robert Fraser" wrote

 Jesse Phillips wrote:

 In C allocating a static 2D array gives a continues chunk of memory. Java 
 creates an array that points to more arrays. Just wondering how D handles 
 this.


 The only reason static arrays seem to exist at all (as well as good 
 explanation for their incongruity with other types) is C compatibility.


They are also good for allocating buffer space on the stack.

But I agree that their incongruity with other types sucks.

-Steve
Nov 04 2008
parent reply "Saaa" <empty needmail.com> writes:
 They are also good for allocating buffer space on the stack.


Can dynamic arrays also be on the stack?
(oversimplified question .. sorry :)
If so, do they have the same performance then?


 But I agree that their incongruity with other types sucks.

 -Steve
Nov 04 2008
next sibling parent reply "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Tue, Nov 4, 2008 at 11:25 AM, Saaa <empty needmail.com> wrote:

 They are also good for allocating buffer space on the stack.


 Can dynamic arrays also be on the stack?
 (oversimplified question .. sorry :)
 If so, do they have the same performance then?


You can have a dynamic array that _points_ to the stack, but there is
no general mechanism for allocating a dynamic array directly on the
stack.  You might be able to do something with alloca, but stack space
is usually limited and you wouldn't be able to have very large arrays.

Performance of dynamic arrays is the same no matter where their data
is.  Fixed-size 2D arrays are not faster _because_ they are on the
stack, they just happen to be allocated on the stack.  They are faster
(usually) because they don't need two pointer dereferences.  You can
allocated a fixed-size 2D array on the heap (well.. inside a struct or
class anyway) and it will be just as fast.
Nov 04 2008
next sibling parent reply "Saaa" <empty needmail.com> writes:
 You can have a dynamic array that _points_ to the stack, but there is
 no general mechanism for allocating a dynamic array directly on the
 stack.  You might be able to do something with alloca, but stack space
 is usually limited and you wouldn't be able to have very large arrays.

 Performance of dynamic arrays is the same no matter where their data
 is.  Fixed-size 2D arrays are not faster _because_ they are on the
 stack, they just happen to be allocated on the stack.  They are faster
 (usually) because they don't need two pointer dereferences.  You can
 allocated a fixed-size 2D array on the heap (well.. inside a struct or
 class anyway) and it will be just as fast.


Ok, so when I want a multimillion array with speed I should use a static
array on the heap. That would be using new, right :)
Nov 04 2008
parent reply "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Tue, Nov 4, 2008 at 11:41 AM, Saaa <empty needmail.com> wrote:

 You can have a dynamic array that _points_ to the stack, but there is
 no general mechanism for allocating a dynamic array directly on the
 stack.  You might be able to do something with alloca, but stack space
 is usually limited and you wouldn't be able to have very large arrays.

 Performance of dynamic arrays is the same no matter where their data
 is.  Fixed-size 2D arrays are not faster _because_ they are on the
 stack, they just happen to be allocated on the stack.  They are faster
 (usually) because they don't need two pointer dereferences.  You can
 allocated a fixed-size 2D array on the heap (well.. inside a struct or
 class anyway) and it will be just as fast.


 Ok, so when I want a multimillion array with speed I should use a static
 array on the heap. That would be using new, right :)


You.. can't actually allocate a static array on the heap using new.
At least not directly.  It's kind of an embarrassing hole in the
syntax.  In fact, I'm not sure if you can even get a static array to
point onto the heap, since a static array "reference" is treated like
a value type when assigned to, so if you do something like:

int[3][4] b = (new int[3][4][](1))[0];

The weirdness on the right-hand-side is needed to get around the
compiler "helpfully" rewriting "new int[3][4]" as "new int[][](3, 4)".
 But this code will simply allocate a static array on the heap, and
then copy its contents onto the stack.  Dumb.

Other than using a struct/class that contains a static array and
allocating _that_ on the heap, I don't know of any way of getting it
on the heap.  But then you'd be double-dereferencing anyway since
you'd have to go through the struct pointer or class reference!  Sigh.
Nov 04 2008
parent reply "Saaa" <empty needmail.com> writes:
erm, so what would be the best way to get a large array?
which is also fast.


 You can have a dynamic array that _points_ to the stack, but there is
 no general mechanism for allocating a dynamic array directly on the
 stack.  You might be able to do something with alloca, but stack space
 is usually limited and you wouldn't be able to have very large arrays.

 Performance of dynamic arrays is the same no matter where their data
 is.  Fixed-size 2D arrays are not faster _because_ they are on the
 stack, they just happen to be allocated on the stack.  They are faster
 (usually) because they don't need two pointer dereferences.  You can
 allocated a fixed-size 2D array on the heap (well.. inside a struct or
 class anyway) and it will be just as fast.


 Ok, so when I want a multimillion array with speed I should use a static
 array on the heap. That would be using new, right :)


 You.. can't actually allocate a static array on the heap using new.
 At least not directly.  It's kind of an embarrassing hole in the
 syntax.  In fact, I'm not sure if you can even get a static array to
 point onto the heap, since a static array "reference" is treated like
 a value type when assigned to, so if you do something like:

 int[3][4] b = (new int[3][4][](1))[0];

 The weirdness on the right-hand-side is needed to get around the
 compiler "helpfully" rewriting "new int[3][4]" as "new int[][](3, 4)".
 But this code will simply allocate a static array on the heap, and
 then copy its contents onto the stack.  Dumb.

 Other than using a struct/class that contains a static array and
 allocating _that_ on the heap, I don't know of any way of getting it
 on the heap.  But then you'd be double-dereferencing anyway since
 you'd have to go through the struct pointer or class reference!  Sigh.
Nov 04 2008
parent "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Tue, Nov 4, 2008 at 1:36 PM, Saaa <empty needmail.com> wrote:

 erm, so what would be the best way to get a large array?
 which is also fast.


A large 2D array that is fast?  Write it yourself.  It's not terribly
hard; it'd just be a templated struct with overloaded opIndex and
opIndexAssign.
Nov 04 2008
prev sibling parent reply Lars Kyllingstad <public kyllingen.NOSPAMnet> writes:
Jarrett Billingsley wrote:

 Performance of dynamic arrays is the same no matter where their data
 is.  Fixed-size 2D arrays are not faster _because_ they are on the
 stack, they just happen to be allocated on the stack.  They are faster
 (usually) because they don't need two pointer dereferences.  You can
 allocated a fixed-size 2D array on the heap (well.. inside a struct or
 class anyway) and it will be just as fast.


Your "usually" interests me. I was under the impression, and it seems 
quite logical, that static arrays are faster than dynamic ones. However, 
recently I did some simple experiments with matrix operations 
(multiplication, etc.), in which performance was actually a little bit 
better for dynamic arrays.

Is there a general "rule" for when dynamic arrays are faster than static 
ones, and vice versa?

Also, I tried multiplying large matrices both using arrays in D and 
using a C BLAS implementation. The BLAS algorithm is the same as the one 
I've written in D, and additionally includes a lot of runtime checks. 
Still, multiplication using BLAS was about four times faster. Is this 
simply because C compilers are a lot better at optimisation than the D 
compilers?

-Lars
Nov 05 2008
next sibling parent reply Lars Kyllingstad <public kyllingen.NOSPAMnet> writes:
Lars Kyllingstad wrote:

 Jarrett Billingsley wrote:

 Performance of dynamic arrays is the same no matter where their data
 is.  Fixed-size 2D arrays are not faster _because_ they are on the
 stack, they just happen to be allocated on the stack.  They are faster
 (usually) because they don't need two pointer dereferences.  You can
 allocated a fixed-size 2D array on the heap (well.. inside a struct or
 class anyway) and it will be just as fast.


 
 Your "usually" interests me. I was under the impression, and it seems 
 quite logical, that static arrays are faster than dynamic ones. However, 
 recently I did some simple experiments with matrix operations 
 (multiplication, etc.), in which performance was actually a little bit 
 better for dynamic arrays.
 
 Is there a general "rule" for when dynamic arrays are faster than static 
 ones, and vice versa?
 
 Also, I tried multiplying large matrices both using arrays in D and 
 using a C BLAS implementation. The BLAS algorithm is the same as the one 
 I've written in D, and additionally includes a lot of runtime checks. 
 Still, multiplication using BLAS was about four times faster. Is this 
 simply because C compilers are a lot better at optimisation than the D 
 compilers?


I just remembered that D also does bounds checking on arrays. To work 
around this, I tried accessing the array elements through pointers. To 
my surprise, this actually didn't affect the results very much.

Therefore my question still stands.

-Lars
Nov 05 2008
parent Don <nospam nospam.com> writes:
Lars Kyllingstad wrote:

 Lars Kyllingstad wrote:

 Jarrett Billingsley wrote:

 Performance of dynamic arrays is the same no matter where their data
 is.  Fixed-size 2D arrays are not faster _because_ they are on the
 stack, they just happen to be allocated on the stack.  They are faster
 (usually) because they don't need two pointer dereferences.  You can
 allocated a fixed-size 2D array on the heap (well.. inside a struct or
 class anyway) and it will be just as fast.


 Your "usually" interests me. I was under the impression, and it seems 
 quite logical, that static arrays are faster than dynamic ones. 
 However, recently I did some simple experiments with matrix operations 
 (multiplication, etc.), in which performance was actually a little bit 
 better for dynamic arrays.

 Is there a general "rule" for when dynamic arrays are faster than 
 static ones, and vice versa?

 Also, I tried multiplying large matrices both using arrays in D and 
 using a C BLAS implementation. The BLAS algorithm is the same as the 
 one I've written in D, and additionally includes a lot of runtime 
 checks. Still, multiplication using BLAS was about four times faster. 
 Is this simply because C compilers are a lot better at optimisation 
 than the D compilers?


 
 I just remembered that D also does bounds checking on arrays. To work 
 around this, I tried accessing the array elements through pointers. To 
 my surprise, this actually didn't affect the results very much.


My experience is that using indexing is faster in DMD. I don't know why.
To compare D and C, compile your C code with DMC. Then you'll get the 
same code generation capability. DMD and DMC are extremely weak on 
floating-point optimisation. You shouldn't see any difference between them.
Nov 06 2008
prev sibling parent Christopher Wright <dhasenan gmail.com> writes:
Lars Kyllingstad wrote:

 Jarrett Billingsley wrote:

 Performance of dynamic arrays is the same no matter where their data
 is.  Fixed-size 2D arrays are not faster _because_ they are on the
 stack, they just happen to be allocated on the stack.  They are faster
 (usually) because they don't need two pointer dereferences.  You can
 allocated a fixed-size 2D array on the heap (well.. inside a struct or
 class anyway) and it will be just as fast.


 
 Your "usually" interests me. I was under the impression, and it seems 
 quite logical, that static arrays are faster than dynamic ones. However, 
 recently I did some simple experiments with matrix operations 
 (multiplication, etc.), in which performance was actually a little bit 
 better for dynamic arrays.


Indexing on a static 2d array is a multiplication and and addition. 
Indexing on a dynamic one is a dereference and an addition. If the 
compiler optimizes the dereference out but not the multiplication, you 
can get cases where dynamic arrays are faster.

There are probably other cases where the efficiency differs from 
expectations, but I'm not familiar with them.
Nov 05 2008
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Saaa" wrote

 They are also good for allocating buffer space on the stack.


 Can dynamic arrays also be on the stack?
 (oversimplified question .. sorry :)
 If so, do they have the same performance then?


Not easily.  A stack frame is a constant size usually.  So allocating a 
runtime-decided amount is not doable.  You could probably write some 
assembly to do it, but generally, static arrays are the only way.

If you do that, they probably have the same performance.

BTW, static arrays implicitly cast to dynamic arrays, so you can create a 
dynamic array that points to a static array, or call a function which takes 
a dynamic array:
void foo(byte[] b) {...}

byte[1024] buf;
byte[] buffer = buf; // points to stack data
foo(buf); // call a function

-Steve
Nov 04 2008
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Robert Fraser:

 The only reason static arrays seem to exist at all (as well as good 
 explanation for their incongruity with other types) is C compatibility.


They also can give you more performance, if you know how to use them well.


Jarrett Billingsley>Fixed-size 2D arrays are not faster _because_ they are on
the
stack, they just happen to be allocated on the stack.  They are faster
(usually) because they don't need two pointer dereferences.<

Right. You can allocate a single block of dynamic memory, and then find items
using something like: col+row*ncols. But fixed-size 2D arrays can be faster
also because the compiler knows the sides of the matrix at compile time. So to
find the position of the cells it can often (if you have chosen the right
sizes) use shifts and similar tricks, that are faster than that general
multiplication row*ncols.

For example here I have written a small C program (exactly the same code can be
written in D, I have used C because GCC optimizes more than DMD):
http://www.fantascienza.net/leonardo/js/wirun2.c

As main data structure it uses a large matrix:
#define SIZEX 1024
#define SIZEY 1024
int lists[4][SIZEX * SIZEY];

That program wastes some space on the right of that tensor, to keep the sizes
as powers of two. Those numbers are powers of two, so to compute the index
positions it uses just shifts, and it's fast. If you use the same code in D you
have a higher performance than using dynamic arrays, even if you carve it from
a single chunk of heap memory.
Note that modern caches have quite weird performance problems with arrays with
sizes as powers of two, so you have to benchmark your code every time, or you
have to know a LOT of details about your CPU caches.

Bye,
bearophile
Nov 04 2008
prev sibling parent ore-sama <spam here.lot> writes:
Jarrett Billingsley Wrote:


 You.. can't actually allocate a static array on the heap using new.
 At least not directly.  It's kind of an embarrassing hole in the
 syntax.  In fact, I'm not sure if you can even get a static array to
 point onto the heap, since a static array "reference" is treated like
 a value type when assigned to, so if you do something like:
 
 int[3][4] b = (new int[3][4][](1))[0];
 
 The weirdness on the right-hand-side is needed to get around the
 compiler "helpfully" rewriting "new int[3][4]" as "new int[][](3, 4)".
  But this code will simply allocate a static array on the heap, and
 then copy its contents onto the stack.  Dumb.


	auto rg2=new int[10][20];
	writeln(typeof(rg2).stringof); //int[10u][]
	writeln(cast(size_t)&rg2[1]-cast(size_t)&rg2[0]); //40

As you can see it allocates contunous int[10][20] and assigns it to dynamic
array int[10][]. Which is nearly what topicstarter wants. Well, border checks
will be dynamic for the first index.
Nov 07 2008