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 "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
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 "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 next sibling parent "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
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 next sibling parent "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
prev sibling next sibling 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 "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
prev sibling next sibling 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 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 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