• %u (11/11) Oct 21 2010 What is the fastest way to fill a static multidimensional array?
• bearophile (14/15) Oct 21 2010 If you want a safe solution, then you probably need nested loops, and a ...
• %u (50/65) Oct 21 2010 stored in a contiguous way in D, so you may use a memset or something li...
• spir (41/56) Oct 22 2010 t to
• %u (32/40) Oct 22 2010 But it does take up more memory (assuming you don't generate the arrays ...
• Trass3r (1/3) Oct 22 2010 Static arrays are value types.

%u <e ee.com> writes:

What is the fastest way to fill a static multidimensional array?

Looping over all dimension's elements sounds inefficient, especially as a
static array is essentially continuous memory.
What is the best practice?

int[2][2][2] arr = 0;
arr[] = 3; //Error: cannot implicitly convert expression (3) of type int to
int[2u][2u][]
arr[][][] = 3; // this would be fine too :)

int[2][2][2] arr2 = [[[1,2],[3,4]],[[5,6],[7,8]]];

Somehow I find it surprising that this copies the whole array.
arr[] = arr2;

bearophile <bearophileHUGS lycos.com> writes:

%u:

 What is the fastest way to fill a static multidimensional array?

If you want a safe solution, then you probably need nested loops, and a array[]
= x; in the inner loop (such loops may be generated with a string mixin too).

Otherwise if speed is more important, fixed sized multidimensional arrays are
stored in a contiguous way in D, so you may use a memset or something like:

import std.stdio: writeln;
void main() {
    int[5][4] mat;
    (cast(int[mat[0].length * mat.length])mat)[] = 10;
    writeln(mat);
}

Or even:
(cast(int[mat.sizeof / int.sizeof])mat)[] = 10;

(If necessary you may use a recursive template trick to find the type of the
basic item of the array).

Bye,
bearophile

%u <e ee.com> writes:

== Quote from bearophile (bearophileHUGS lycos.com)'s article
 %u:
 What is the fastest way to fill a static multidimensional array?

 If you want a safe solution, then you probably need nested loops, and a array[]

= x; in the inner loop (such loops may be generated with a string mixin too).
 Otherwise if speed is more important, fixed sized multidimensional arrays are

stored in a contiguous way in D, so you may use a memset or something like:
 import std.stdio: writeln;
 void main() {
     int[5][4] mat;
     (cast(int[mat[0].length * mat.length])mat)[] = 10;
     writeln(mat);
 }
 Or even:
 (cast(int[mat.sizeof / int.sizeof])mat)[] = 10;
 (If necessary you may use a recursive template trick to find the type of the

basic item of the array).
 Bye,
 bearophile

The code below gave me these timings:

[x][y][z]   : 4569947344
[x][y][]    : 4149326308
cast(int[*]): 3843939416
cast(int[1]): 3978162888

Depending on the dimensions of the array, one consistently wins, but always with
an -I-wouldn't-bother- margin.
How would memset work?

dmd(1) -O -inline -release
----
import std.stdio;
import std.perf;

int[50][50][50] arr;

void main()
{
	auto timer = new HighPerformanceCounter;

	timer.start();
	for(int i = 0; i < 10_000; i++) {
		for(int x = 0; x < 50; x++)
			for(int y = 0; y < 50; y++)
				for(int z = 0; z < 50; z++)
					arr[x][y][z] = i;
	}
	timer.stop();
	writefln("[x][y][z]   : ",timer.periodCount());

	timer.start();
	for(int i = 0; i < 10_000; i++) {
		for(int x = 0; x < 50; x++)
			for(int y = 0; y < 50; y++)
				arr[x][y][] = i;
	}
	timer.stop();
	writefln("[x][y][]    : ",timer.periodCount());

	timer.start();
	for(int i = 0; i < 10_000; i++) {
		(cast(int[arr[0][0].length * arr[0].length * arr.length])arr)[] = i;
	}
	timer.stop();
	writefln("cast(int[*]): ",timer.periodCount());

	timer.start();
	for(int i = 0; i < 10_000; i++) {
		(cast(int[125_000])arr)[] = i;
	}
	timer.stop();
	writefln("cast(int[1]): ",timer.periodCount());
}

spir <denis.spir gmail.com> writes:

On Fri, 22 Oct 2010 01:50:56 +0000 (UTC)
%u <e ee.com> wrote:

 What is the fastest way to fill a static multidimensional array?
=20
 Looping over all dimension's elements sounds inefficient, especially as a
 static array is essentially continuous memory.
 What is the best practice?
=20
 int[2][2][2] arr =3D 0;
 arr[] =3D 3; //Error: cannot implicitly convert expression (3) of type in=

t to
 int[2u][2u][]
 arr[][][] =3D 3; // this would be fine too :)
=20
 int[2][2][2] arr2 =3D [[[1,2],[3,4]],[[5,6],[7,8]]];
=20
 Somehow I find it surprising that this copies the whole array.
 arr[] =3D arr2;

I would use the following feature (from ref):

Array Setting
If a slice operator appears as the lvalue of an assignment expression, and =
the type of the rvalue is the same as the element type of the lvalue, then =
the lvalue's array contents are set to the rvalue.
	int[3] s;
	int* p;
	s[] =3D 3;		// same as s[0] =3D 3, s[1] =3D 3, s[2] =3D 3
	p[0..2] =3D 3;		// same as p[0] =3D 3, p[1] =3D 3

Using this, one could fill a multidimensional array by setting, so to say, =
from inside to outside. This is actually a variant of "(cast(T[n1*n2*n3])ar=
r)[] =3D e;" that bearophile proposed, but it does not need any low-level h=
ack:

void main () {
    int[2][2][2] arr3;
    int[2][2] arr2;
    int[2] arr1;
    arr1[] =3D 1;
    arr2[] =3D arr1;
    arr3[] =3D arr2;
    assert(arr3 =3D=3D [[[1, 1], [1, 1]], [[1, 1], [1, 1]]]);
}

I find the syntax somewhat wrong, would prefere it explicit like:
    arr.fill(element);
or
    arrayFill(arr, element);
How does this method perform? would you be kind enough to include it in you=
r tests, %u? Even if it's slightly slower than "(cast(int[n1*n2*n3])arr)[] =
=3D e;", I would use it because I find it cleaner.

Is D reflexive enough to know at runtime the number of dimensions of an arr=
ay and their sizes, and write a generic
    arrayDeepFill(arr, element);
where element is the "terminal" value? Or maybe
    arrayDeepFill(arr, element, [sizes]);


Denis
-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com

%u <e ee.com> writes:

== Quote from spir (denis.spir gmail.com)'s article
 How does this method perform? would you be kind enough to include it in you
 r tests, %u? Even if it's slightly slower than "(cast(int[n1*n2*n3])arr)[]
 = e;", I would use it because I find it cleaner.

But it does take up more memory (assuming you don't generate the arrays every
fill).
And, it performs worse than the casts (with this array length).
If you really want to investigate, I suggest disassembling ;)

Here is the added code:
int[50][50] arr2;
int[50] arr1;

timer.start();
for(int i = 0; i < 10_000; i++) {
    arr1[] = i;
    arr2[] = arr1;
    arr3[] = arr2;
}
timer.stop();
writefln("123         : ",timer.periodCount());

And killing almost every process on my computer the new timings are:
[x][y][z]   : 37..
[x][y][]    : 38..
cast(int[*]): 28..
cast(int[1]): 28..
123         : 36..
fill        : 28..

 Is D reflexive enough to know at runtime the number of dimensions of an arr
 ay and their sizes, and write a generic
     arrayDeepFill(arr, element);
 where element is the "terminal" value? Or maybe
     arrayDeepFill(arr, element, [sizes]);

Yeah, wouldn't that be nice ?!
arr.Fill(elem);

:D

template BaseType(T: T[]) { alias BaseType!(T) BaseType; }
template BaseType(T) { alias T BaseType; }

void Fill(T,E)(T arr, E elem) {
	static assert( isStaticArray!(T) );
	static assert( is( BaseType!(T) == E ) );
	(cast(E[arr.sizeof / elem.sizeof])arr)[] = elem;
}

Trass3r <un known.com> writes:

 Somehow I find it surprising that this copies the whole array.
 arr[] = arr2;

Static arrays are value types.