View mode: basic / threaded / horizontal-split · Log in · Help
June 18, 2006
arrays && functions && pointers
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
Re: arrays && functions && pointers
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
Re: arrays && functions && pointers
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
Re: arrays && functions && pointers
"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
Re: arrays && functions && pointers
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
Re: arrays && functions && pointers
"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
Re: arrays && functions && pointers
"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
Re: arrays && functions && pointers
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
Re: arrays && functions && pointers
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
Re: arrays && functions && pointers
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
Top | Discussion index | About this forum | D home