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;

%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

== 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());
}

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

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[] = 3;		// same as s[0] = 3, s[1] = 3, s[2] = 3
	p[0..2] = 3;		// same as p[0] = 3, p[1] = 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])arr)[] = e;" that bearophile proposed, but it does not need any low-level hack:

void main () {
    int[2][2][2] arr3;
    int[2][2] arr2;
    int[2] arr1;
    arr1[] = 1;
    arr2[] = arr1;
    arr3[] = arr2;
    assert(arr3 == [[[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 your 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.

Is D reflexive enough to know at runtime the number of dimensions of an array 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 ☣

spir.wikidot.com

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

Static arrays are value types.

== 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;
}