Jump to page: 1 2
Thread overview
arrays && functions && pointers
Jun 18, 2006
MM
Jun 19, 2006
Regan Heath
Jun 19, 2006
MM
Jun 19, 2006
MM
Jun 19, 2006
Hasan Aljudy
Jun 19, 2006
Daniel Keep
Jun 19, 2006
Regan Heath
Jun 19, 2006
MM
Jun 19, 2006
Regan Heath
Jun 19, 2006
MM
Jun 19, 2006
Regan Heath
Jun 19, 2006
Derek Parnell
Jun 19, 2006
Derek Parnell
Jun 19, 2006
MM
June 18, 2006
Here a simple question, I hope.

In C I was always told arrays should not be send to my functions as if, but only a pointer should be supplied. Which was a *****.

How is this done in D?


June 19, 2006
On Sun, 18 Jun 2006 23:49:09 +0000 (UTC), MM <MM_member@pathlink.com> wrote:
> Here a simple question, I hope.
>
> In C I was always told arrays should not be send to my functions as if, but only
> a pointer should be supplied. Which was a *****.

Are you referring to something like (in C):

void foo(char *string) {}
char array[100];
foo(array);

In this case C automatically passes a pointer to the first element of the array, rather than copying the entire array.

> How is this done in D?

In D and array is a pseudo reference pseudo value type. It is in reality a struct in the form:

struct array {
  int length;
  void *data;
}

or similar where "data" refers to the actual content of the array. Passing the array passes a copy of the structure (like a value type) but does not cause a copy of the data (like a reference type). This is fast and efficient enough that there is no reason not to just pass it, much as you do in C, eg.

void foo(char[] string) {}
char[100] array;
foo(array);

note that the above "array" is a fixed/static array of 100 characters, but it can be passed as a dynamic array [] of variable length because the function gets a copy of the structure which in turn refers to the original static data.

Therefore..

If you pass an array as "in" (the default method) any modifications you make to the array length or to the data pointer (by assigning a new array slice to it or similar) will not be propagated back to the array you passed to the function as they only happen to the copy you get inside the function. However, any changes you make to the data to which the array refers does propagate, because there is only 1 copy of it. eg.

void foo(char[] string) {
  string.length = 5;    //does not propagate
  string = string[1..$] //does not propagate
  string[0] = 'a';      //does propagate (actually modifies 2nd char (index 1) of external array)
}

However..

If you pass an array as "inout" or "out" then you do not get a copy of the structure but you get the actual structure itself, so when/if you change the length or data pointer you're change the array which you passed directly and you will see the changes propagate.

void foo(inout char[] string) {
  string.length = 5;    //does propagate
  string = string[1..$] //does propagate
  string[0] = 'a';      //does propagate
}

Meaning..

You cannot pass a fixed/static array as "inout" or "out" to a function expecting a dynamic char[] because you cannot modify a fixed/static array length or data pointer, you'll get an error like this if you try to pass one.
  cast(char[])(test) is not an lvalue

In short, just pass your D arrays to functions as is, whether they're fixed or dynamic.

Regan
June 19, 2006
In C I used to do stuff like:

void foo (TILE (*tiles)[TILEW][TILEH]){
(*tiles)[0][0].z++; //random operation :)
}

But as I see in your (very complete :) explanation I can just do:

Void foo (TILE tiles[TILEW][TILEH]){
tiles[0][0].z++;
}

This is not slower? I ask this because this foo will be an excessively used function in the game loop ;)

btw. How do I reset all the data of a rectangular array?
something like:
tiles[][]=0;


>Are you referring to something like (in C):
>
>void foo(char *string) {}
>char array[100];
>foo(array);
>
>In this case C automatically passes a pointer to the first element of the array, rather than copying the entire array.
>
>> How is this done in D?
>
>In D and array is a pseudo reference pseudo value type. It is in reality a struct in the form:
>
>struct array {
>   int length;
>   void *data;
>}
>
>or similar where "data" refers to the actual content of the array. Passing the array passes a copy of the structure (like a value type) but does not cause a copy of the data (like a reference type). This is fast and efficient enough that there is no reason not to just pass it, much as you do in C, eg.
>
>void foo(char[] string) {}
>char[100] array;
>foo(array);
>
>note that the above "array" is a fixed/static array of 100 characters, but it can be passed as a dynamic array [] of variable length because the function gets a copy of the structure which in turn refers to the original static data.
>
>Therefore..
>
>If you pass an array as "in" (the default method) any modifications you make to the array length or to the data pointer (by assigning a new array slice to it or similar) will not be propagated back to the array you passed to the function as they only happen to the copy you get inside the function. However, any changes you make to the data to which the array refers does propagate, because there is only 1 copy of it. eg.
>
>void foo(char[] string) {
>   string.length = 5;    //does not propagate
>   string = string[1..$] //does not propagate
>   string[0] = 'a';      //does propagate (actually modifies 2nd char
>(index 1) of external array)
>}
>
>However..
>
>If you pass an array as "inout" or "out" then you do not get a copy of the structure but you get the actual structure itself, so when/if you change the length or data pointer you're change the array which you passed directly and you will see the changes propagate.
>
>void foo(inout char[] string) {
>   string.length = 5;    //does propagate
>   string = string[1..$] //does propagate
>   string[0] = 'a';      //does propagate
>}
>
>Meaning..
>
>You cannot pass a fixed/static array as "inout" or "out" to a function expecting a dynamic char[] because you cannot modify a fixed/static array length or data pointer, you'll get an error like this if you try to pass one.
>   cast(char[])(test) is not an lvalue
>
>In short, just pass your D arrays to functions as is, whether they're fixed or dynamic.
>
>Regan


June 19, 2006
"MM" <MM_member@pathlink.com> wrote in message news:e74tk9$213l$1@digitaldaemon.com...

> This is not slower? I ask this because this foo will be an excessively
> used
> function in the game loop ;)

No.  All that's being passed to the function is a pointer to the array data and the length.  In C, you see all the pointer mechanics out in the open; in D, it's implicit.

> btw. How do I reset all the data of a rectangular array?
> something like:
> tiles[][]=0;


June 19, 2006
On Mon, 19 Jun 2006 01:11:37 +0000 (UTC), MM <MM_member@pathlink.com> wrote:
> In C I used to do stuff like:
>
> void foo (TILE (*tiles)[TILEW][TILEH]){
> (*tiles)[0][0].z++; //random operation :)
> }

I dont think the (*tiles) is necessary, to confirm this I tried this test program:

#include <sys/types.h>
#include <sys/timeb.h>
#include <stdlib.h>
#include <stdio.h>

#define TILEW 1000
#define TILEH 1000

typedef struct _TILE { int x,y; } TILE;

void foo(TILE arr[TILEW][TILEH]) {
	arr[0][0].x = rand();
	arr[0][0].y = rand();
}
void bar(TILE (*arr)[TILEW][TILEH]) {
	(*arr)[0][0].x = rand();
	(*arr)[0][0].y = rand();

}

double now()
{
	struct timeb b;
	ftime(&b);
	return (double)b.time + (double)(b.millitm/1000.0);
}

void main()
{
	TILE (*data)[TILEW][TILEH];
	double start,end;
	int i;

	//allocated on the heap (not enough room on the stack)
	data = calloc(TILEW*TILEH,sizeof(TILE));
	printf("alloc ok\n");

	//pass as pointer
	start = now();
	for(i = 0; i < 10000000; i++) bar(data);
	end = now();
	printf("bar took: %f\n",end-start);

	//pass as array
	start = now();
	for(i = 0; i < 10000000; i++) foo(*data);
	end = now();
	printf("foo took: %f\n",end-start);
}

My results were very similar for both "foo" and "bar".

I believe the reason for this is that in "foo" we pass the array, in C this causes the address of the first element to be passed. In "bar" we pass a pointer to the array (AKA a pointer to the first element), so in effect both functions do exactly the same thing, except that "bar" involves and extra dereference of the pointer and might even take longer on average.

> But as I see in your (very complete :) explanation I can just do:
>
> Void foo (TILE tiles[TILEW][TILEH]){
> tiles[0][0].z++;
> }
>
> This is not slower? I ask this because this foo will be an excessively used function in the game loop ;)

I wrote up the same test in D:

import std.c.stdlib;
import std.stdio;
import std.perf;

const int TILEW = 1000;
const int TILEH = 1000;

struct TILE { int x,y; }

void foo(TILE arr[TILEW][TILEH]) {}
void bar(TILE (*arr)[TILEW][TILEH]) {}

void main()
{
	PerformanceCounter c = new PerformanceCounter();
	TILE (*arr)[TILEW][TILEH];	
	int i;
	
	arr = cast(TILE (*)[TILEW][TILEH])calloc(TILEW*TILEH,TILE.sizeof);
	writefln("alloc ok");

	c.start();
	for(i = 0; i < 100000000; i++) foo(*arr);
	c.stop();
	writefln("foo took: ",c.milliseconds());
	
	c.start();
	for(i = 0; i < 100000000; i++) bar(arr);
	c.stop();
	writefln("bar took: ",c.milliseconds());
}

My results were interesting, it appears "bar" takes 3 times longer than "foo"!

Can someone else "insanity check" my two test cases above both the C and the D in case I have missed something.

> btw. How do I reset all the data of a rectangular array?
> something like:
> tiles[][]=0;

If it's an array of structs then setting to "0" will not work, however <struct>.init does, eg.

struct TILE { int x,y; }
..

TILE small[2][2];
	
writefln("small array");
small[0][0].x = 1;
small[0][0].y = 1;
small[1][1].x = 2;
small[1][1].y = 2;
foreach(row; small) foreach(t; row) writefln("{",t.x,",",t.y,"}");
writefln("");

writefln("clearing array");	
foreach(inout row; small) row[] = TILE.init;
foreach(row; small) foreach(t; row) writefln("{",t.x,",",t.y,"}");
writefln("");

Note the use of the foreach to access each 'row' of data.

Note the use of "inout" which causes our changes in the foreach to be applied to the actual row of data and not just to a copy of it.

Regan
June 19, 2006
"Jarrett Billingsley" <kb3ctd2@yahoo.com> wrote in message news:e751ri$2709$1@digitaldaemon.com...

>> btw. How do I reset all the data of a rectangular array?
>> something like:
>> tiles[][]=0;

Damn news client.  Ctrl + Enter posts, apparently.

I assume your array is of a static size (thus making it a rectangular array).  You can do this:

foreach(/* auto */ a; tiles)
    a[] = 0;

(I just put the /* auto */ in there to let me know when I'm using the dirty, nonobvious foreach index type inference)

Or, and this is a little hackish, but you can take advantage of the layout of rectangular arrays, which is a single block of memory:

((cast(TILE*)tiles.ptr)[0 .. TILEW * TILEH])[] = 0;

Basically, you're converting the rectangular array type into a linear array type, and setting all those elements to 0.  I would imagine this would be somewhat faster, since it's doing one block set, rather than one block for each row.


June 19, 2006
"Jarrett Billingsley" <kb3ctd2@yahoo.com> wrote in message news:e752c0$27i8$1@digitaldaemon.com...

> foreach(/* auto */ a; tiles)
>    a[] = 0;

This is why I hate newsgroups.

foreach(inout /* auto */ a; tiles)
    a[] = 0;


June 19, 2006
On Mon, 19 Jun 2006 01:11:37 +0000 (UTC), MM wrote:

> In C I used to do stuff like:
> 
> void foo (TILE (*tiles)[TILEW][TILEH]){
> (*tiles)[0][0].z++; //random operation :)
> }
> 
> But as I see in your (very complete :) explanation I can just do:
> 
> Void foo (TILE tiles[TILEW][TILEH]){
> tiles[0][0].z++;
> }
> 
> This is not slower? I ask this because this foo will be an excessively used function in the game loop ;)
> 
> btw. How do I reset all the data of a rectangular array?
> something like:
> tiles[][]=0;

D does not *yet* support rectangular arrays. Here is a demo program that simulates them.

import std.stdio;
import std.string;

// Define the layout of a single tile.
struct TILE
{
    int z;
    int y;
    long x;
    real w;
}

// Define a map, which is rectangular array of tiles.
class Map
{
    TILE[] mTiles;  // The tiles are stored in the dynamic array.
    int mWidth;     // Record the dimensions used to create it.
    int mHeight;

    // Create a map of a specific size.
    this(int w, int h)
    {
        mTiles.length = w*h;
        mWidth = w;
        mHeight = h;
    }

    // Overload the array '[]' fetch operator.
    // I've chosen to return a pointer to the requested tile rather
    // than pass the title data. This is a performance issue but
    // opens it up to potential bugs (eg. accidental updates).
    // e.g.
    //     TILE local_copy = vMap[w,h];
    //     int zValue = vMap[w,h].z;

    TILE* opIndex(int w, int h)
    {
        if (w > mWidth || w < 0)
            throw new Exception(std.string.format("Bad Width '%s'", w));
        if (h > mHeight || h < 0)
            throw new Exception(std.string.format("Bad Height '%s'", h));
        return (&(mTiles[w*mHeight + h]));
    }


    // Overload the array '[]' store operator.
    // This needs to return the address of the tile so that the caller
    // can easily access a tile's members by name.
    // e.g.
    //     vMap[w,h].z = somevalue;
    TILE* opIndexAssign(int w, int h)
    {
        if (w > mWidth || w < 0)
            throw new Exception(std.string.format("Bad Width '%s'", w));
        if (h > mHeight || h < 0)
            throw new Exception(std.string.format("Bad Height '%s'", h));
        return (&(mTiles[w*mHeight + h]));
    }

    // Overload the array '[]' store operator.
    // This version allows you to replace an entire TILE in one go.
    // This returns the address of the tile so that the caller
    // can easily chain assignments.
    // e.g.
    //     TILE someTile;
    //     vMap[w,h] = someTile;
    //     zValue = (vMap[w,h] = someTile).z;
    TILE* opIndexAssign(TILE pData, int w, int h)
    {
        if (w > mWidth || w < 0)
            throw new Exception(std.string.format("Bad Width '%s'", w));
        if (h > mHeight || h < 0)
            throw new Exception(std.string.format("Bad Height '%s'", h));

        mTiles[w*mHeight + h] = pData;
        return (&(mTiles[w*mHeight + h]));
    }

    // Used to clear every TILE in the map.
    void Clear()
    {
        mTiles[] = TILE.init;
    }
}

const TILEW = 256;
const TILEH = 512;

void foo (Map pTiles)
{
    // Grab a reference to a tile.
    auto lTile = pTiles[3,2];

    // Update some members.
    lTile.z++;
    lTile.x = 30000;
    lTile.w = 4.123;
}
void main()
{
    // Create the map of tiles.
    auto vMap = new Map(TILEW, TILEH);

    // Use 'foo' to update a specific tile.
    foo(vMap);
    writefln("A z=%s x=%s w=%s", vMap[3,2].z, vMap[3,2].x, vMap[3,2].w);

    // Clear all tiles.
    vMap.Clear();
    writefln("B %s", vMap[3,2].z);

    // Update a member of a specific tile.
    vMap[3,2].z = 17;
    writefln("C %s", vMap[3,2].z);

    // Replace a specific tile with a totally new one.
    TILE lTile;
    lTile.z = 42;
    vMap[3,2] = lTile;
    writefln("D %s", vMap[3,2].z);

    // Try to reference a tile out of the map.
    writefln("E %s", vMap[3000,2000].z);

}


-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Down with mediocrity!"
19/06/2006 12:52:45 PM
June 19, 2006
On Mon, 19 Jun 2006 12:55:01 +1000, Derek Parnell wrote:

> Here is a demo program that simulates them.

If you don't like the idea of a Map class, you can use a Map struct instead.

Just change the "class Map" to "struct Map", replace the 'this' function
with ...
    // Create a map of a specific size.
    static Map opCall(int w, int h)
    {
        Map lNew;
        lNew.mTiles.length = w*h;
        lNew.mWidth = w;
        lNew.mHeight = h;
        return lNew;
    }

and replace the creation of vMap with ...

    // Create the map of tiles.
    auto vMap = Map(TILEW, TILEH);

Everything else remains the same.

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Down with mediocrity!"
19/06/2006 12:59:28 PM
June 19, 2006

Jarrett Billingsley wrote:
> "Jarrett Billingsley" <kb3ctd2@yahoo.com> wrote in message news:e751ri$2709$1@digitaldaemon.com...
> 
> 
>>>btw. How do I reset all the data of a rectangular array?
>>>something like:
>>>tiles[][]=0;
> 
> 
> Damn news client.  Ctrl + Enter posts, apparently.
> 
> I assume your array is of a static size (thus making it a rectangular array).  You can do this:
> 
> foreach(/* auto */ a; tiles)
>     a[] = 0;
> 
> (I just put the /* auto */ in there to let me know when I'm using the dirty, nonobvious foreach index type inference)
> 
> Or, and this is a little hackish, but you can take advantage of the layout of rectangular arrays, which is a single block of memory:
> 
> ((cast(TILE*)tiles.ptr)[0 .. TILEW * TILEH])[] = 0;
> 
> Basically, you're converting the rectangular array type into a linear array type, and setting all those elements to 0.  I would imagine this would be somewhat faster, since it's doing one block set, rather than one block for each row. 
> 
> 


This won't work if the array is dynamically allocated.

Dynamic 2D arrays in are not exactly c-style rectangular arrays; they are arrays of pointers to arrays of pointers. In C# they call this "jagged arrays".

see:
http://www.digitalmars.com/d/arrays.html
scroll down to "Rectangular Arrays"
<quote>
(Dynamic arrays are implemented as pointers to the array data.) Since the arrays can have varying sizes (being dynamically sized), this is sometimes called "jagged" arrays. Even worse for optimizing the code, the array rows can sometimes point to each other! Fortunately, D static arrays, while using the same syntax, are implemented as a fixed rectangular layout
</quote>

> I assume your array is of a static size

Is there a way in D to test for this? anything like:
assert( isStaticallyAllocated( tiles ) );
would be nice in this case, but I don't think it's possible.

I would rather use a one-dimensional array and treat it as if it were rectangular. Maybe a little template magic can help ease this task.


« First   ‹ Prev
1 2