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.

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

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.

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.

"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

>
> 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
> 

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.

"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

>
> 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 :)

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.