Thread: Dynamic array of unknown number of dimensions

Edit:
Can a mod please rename this thread to "dynamic array of unknown number of dimensions?"
the autofill suggestion popped up, and pressing enter posted the thread instead of selecting the text to autofill


Hi.

I'm working on engineering calculations, which involve hundreds of functions, some of which are called a million times or more.

To speed things up, I wrote a function that would keep track of all argument values a particular function receives, and store them into an array to fetch if those arguments come up again.

To be able to use this precalculation function in any other function regardless of number of arguments, I wanted it to accept a generic double* pointer for the array of precalculated values, because that array will have as many dimensions as there are arguments to the function we're optimizing. It would then be dereferenced an appropriate number of times.



Example of how I would optimize a 3-argument function:

Code:

double f_T_tipspivot (double p, double theta_slide, double w) {
	double f () {
		original function body goes here
		most of these are very expensive to recalculate, like integration or equation solvers (and terms depend on 50 other functions)
	}

	double res;			// result
	double args[3] = {p, theta_slide, w};
	static int nargs[3] = {0};	// number of different values received for each argument
	static double **argarr;		// 2-d array to store collected argument values
	static double ***ooo;		// 3-d array to store results
	static int once = 0;
	if (once == 0) {
		argarr = malloc(3*sizeof(double*));
		argarr[0] = malloc(sizeof(double));	// store values for argument p
		argarr[1] = malloc(sizeof(double));	// 			                theta_slide
		argarr[2] = malloc(sizeof(double));	//			                w
		// for oo array, have to malloc a pointer to pointer for each dimension except last, and malloc the last array with one double (for the value oo[[0][0][0]...)
		ooo = malloc(sizeof(double*));
		ooo[0] = malloc(sizeof(double*));
		ooo[0][0] = malloc(sizeof(double));
		ooo[0][0][0] = NAN;						
		once = 1;
	}
	optany (&f, &res, __func__, 3, args, nargs, &argarr, (double******)&ooo);
	return res;
}

Here's the relevant code from the optimization function, "optany", where I'm trying to dynamically allocate the oo array.

Code:

void optany (double (*f)(), double *res, const char *caller, int n, double *args, int *nargs, double ***argarr, double ******oo) {

	// return pointer to result array location with given indeces
	// lim -> how many dereferencing operations will be performed (how many indeces to "unwrap")
		// if n (number of dimensions) is passed, we get pointer to value oo[index1][index2]...[index_n]
		// anything less, and we get a pointer to array (of values in last dimension if lim = n - 1), or to array of pointers to arrays of values in last dimension, and so forth
	double *ooval (int *indeces, int lim) {
		int m;
		double **curadd = (double**) *oo;	// curadd has to be a lvl2 pointer because we dereference it later and store it into itself after some address arithmetic... and dereferencing a lvl1 pointer would produce a double which we couldn't store into curadd (nor could we cast a double to double*)
		
		for (m=0; m < lim; m++) {
			if (m == n-1) {	// if unwrapping last index
				curadd = curadd + indeces[m]*(int)(((double)sizeof(double)/sizeof(double*)));	// fetching the double value stored at full set of indeces...
			}
			else {
				curadd = (double**) *(curadd + indeces[m]);
			}
		}
		
		return (double*) curadd;
	}
	// get value from the address found above
	double getooval (int *indeces, int lim) {
		return * (ooval (indeces, lim));
	}
	// store value to that address
	void setooval (int *indeces, int lim, double val) {
		*(ooval(indeces, lim)) = val;
	}


	// int inc[n] -> those are set before this part, equal to 1 if that argument value is new (and this dimension needs to be incremented), 0 if not
	// used in dynamic allocation... if a higher dimension was incremented, we need to malloc all of the lower dimensions at that index
	// k always > 0
	void go_down (int k) {
		int l;
		int start = 0;
		// if we're just one dimension below the one that was incremented, only need to malloc at that new index
		if (inc[k-1] == 1) {
			start = nargs[k-1] - 1;
		}
		// otherwise, need to malloc at [new index of incremented dimension][ALL INDECES OF THIS LOWER DIMENSION][ALL INDECES]...
		for (l=start; l<nargs[k-1]; l++) {
			indeces[k-1] = l;
			if (k != n-1) {
				//*((double**)ooval(indeces,k-1)) = malloc(nargs[k]*sizeof(double*));
				
				if (k == 1) {
					*(*oo+indeces[0]) = malloc(nargs[k]*sizeof(double*));
				}
				else if (k == 2) {
					*(*(*oo + indeces[0]) + indeces[1]) = malloc(nargs[k]*sizeof(double*));
				}
				else if (k == 3) {
					*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) = malloc(nargs[k]*sizeof(double*));
				}
				
				go_down (k+1);
			}
			else {
				//*((double**)ooval(indeces,k-1)) = malloc(nargs[k]*sizeof(double));
				
				// same as above, only mallocing as sizeof (double), not (double*)
				if (k == 1) {
					*(*oo + indeces[0]) = malloc(nargs[k]*sizeof(double));
				}
				else if (k == 2) {
					*(*(*oo + indeces[0]) + indeces[1]) = malloc(nargs[k]*sizeof(double));
				}
				else if (k == 3) {
					*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) = malloc(nargs[k]*sizeof(double));
				}
				else if (k == 4) {
					*(*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) + indeces[3]) = malloc(nargs[k]*sizeof(double));
				}
				
				for (o=0; o<nargs[k]; o++) {
					indeces[k] = o;
					setooval(indeces,k+1,NAN);
				}
			}
		}
	}
	// used in dynamic allocation, if a dimension that's not last was incremented, will call go_down to create elements for all lower dimensions... otherwise, will realloc the last dimension
	void loop (int k) {
		int l;
		
		if (inc[k] == 1) {
			if (k != n-1) {
				//*((double**)ooval(indeces,k-1)) = realloc(ooval(indeces,k),nargs[k]*sizeof(double));
				
				if (k == 0) {
					*oo = realloc(*oo,nargs[k]*sizeof(double*));
				}
				else if (k == 1) {
					*(*oo + indeces[0]) = realloc(*(*oo + indeces[0]),nargs[k]*sizeof(double*));
				}
				else if (k == 2) {
					*(*(*oo + indeces[0]) + indeces[1]) = realloc(*(*(*oo + indeces[0]) + indeces[1]),nargs[k]*sizeof(double*));
				}
				else if (k == 3) {
					*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) = realloc(*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]),nargs[k]*sizeof(double*));
				}
				
				
				indeces[k] = nargs[k] - 1;
				go_down(k+1);
			}
			else {
				//*((double**)ooval(indeces,k-1)) = realloc(ooval(indeces,k),nargs[k]*sizeof(double));
					
				if (k == 0) {
					*oo = realloc(*oo,nargs[k]*sizeof(double));
				}
				else if (k == 1) {
					*(*oo + indeces[0]) = realloc(*(*oo + indeces[0]),nargs[k]*sizeof(double));
				}
				else if (k == 2) {
					*(*(*oo + indeces[0]) + indeces[1]) = realloc(*(*(*oo + indeces[0]) + indeces[1]),nargs[k]*sizeof(double));
				}
				else if (k == 3) {
					*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) = realloc(*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]),nargs[k]*sizeof(double));
				}
				else if (k == 4) {
					*(*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) + indeces[3]) = realloc(*(*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) + indeces[3]),nargs[k]*sizeof(double));
				}
				
				
				indeces[k] = nargs[k]-1;
				setooval(indeces,k+1,NAN);
			}
		}
		for (l=0; l < nargs[k]; l++) {
			indeces[k] = l;
			if (k != n-1) {
				loop (k+1);
			}
		}
	}

	loop(0);



}

I'm trying to use dynamic allocation for the ooo array (the precalculated values), mainly to save my own time, because I want to insert this optimization function into many many other functions in many programs. So far I've found searching even through 2000 previous argument values on each call is still faster than recalculating the whole function. Also I'm aware that increasing array size by one every time a new argument value is encountered is not too efficient, but I'll worry about that later.

Anyway, you can see in function loop and go_down a bunch of if statements that basically just do different number of dereferencing operations depending on k.
*(address + index), or
*(*(address + index1) + index2), and so forth

However, I'm limited in number of dimensions to however many if statements I write.
I tried returning the address of the pointer that I need to realloc with my function ooval, but of course the left side has to be an l-value.

Then I tried this (commented out before each big block of if's):
*((double**)ooval(indeces,k-1)) = malloc(nargs[k]*sizeof(double))
which is supposed to replace all the if statements. However, that gave me the error you get when you try reallocing something that hasn't been malloced yet.
(And I did have a separate if to handle the case of k=0 for the above call).

I haven't been able to find what exactly they mean in the reference for realloc function when they say your pointer has to be a "Pointer to a memory block previously allocated with malloc, calloc or realloc". Apparently passing the address my pointer points to doesn't work if I obtain it from a function call.

Does anyone know how I can replace these big if statements with something that would work for any number of dimensions?

Why do you need more than 2 dimension? One dimension for the function, and one for the arguments to each function. Or maybe three, one for each different set of arguments passed to the function. I can't see why you would need an unknown number of arguments. You are basically just making an array of arguments, with the argument number unknown, that's fine, because you can have that dimension's length be dynamic.

But why is it you think you need a 10D array exactly? I'm just not seeing it.

Also, if any of your realloc calls fails, the way you are doing it now, you lose everything you have allocated. Never directly assign to the same pointer you are calling realloc on.

So anyway, from where I sit, all you really need is a two or three D array. I can't figure out why you think you need an infinite number of dimensions.


Quzah.

Some of the functions that I want to apply this to have 5 arguments, so I need a 5d array for any combination of values that those arguments can take. I know that some of those arguments take on only a few different values, so it's not a problem to store, say, something like 100 * 100 * 50 * 10 * 3.


Others have 4 arguments, others 3.

I've already written the if statements for up to 5 dimensions, but I'd like to know if there's a cleaner way to do it.
And why doesn't this work:

int *a = malloc (sizeof(double));
int *b = a;
b = realloc (b, 2*sizeof(double));

Why is this not the same as reallocing "a" directly? Does realloc care about variable names when establishing if something was allocated before?
(This is essentially what I tried to do instead of the big if blocks, only b is returned by function ooval).


And thanks for reminding me to check for what realloc returns. I usually leave things like that till the end if things work out while testing.

Why not just malloc an array to fit those values, as quzah said a more than two dimensional array just doesn't make much sense. In two dimensional array, one array have the function name as the key and link to an array for the function arguments.

array 1................................................. .............. array 2
---------------------------------------------------
|function name| pointer to argument values| -------->| 100 | 50 | 25 | 1 |
---------------------------------------------------
|another name | pointer to argument values| -------->|2 | 3|
---------------------------------------------------
.
.
.

as a some what dynamic array, make the array 1 like a hundred starting size and if that ran out then malloc a new array like double the previous size of increase by a fixed size then copy the array 1 memory to the new array.

Have you considered something like hashing or a tree style since you said that there are gonna be many functions that you want to store and access. Arrays are not very good.

Originally Posted by gamask

@quzah - The optimization function "optany" receives an argument n for number of dimensions, equal to number of arguments that a given function takes.

And returns what exactly?

Originally Posted by gamask

That can range from 1 to 5. I don't see how I could use a 2d array.

Why?

Originally Posted by gamask

As for linked lists, I don't think that would work for me. How would I go about looking up the precalculated value for a 5-argument function, with each argument taking on 50 different values?
That's 50^5 combinations that I need to store.

Code:

struct args
{
    size_t argc;
    void **argv;

    struct args *next;
} argtable[ numoffunctions ];

No then, since I have no idea what it is your function is thinking it's returning, you get a list of void pointers to play with. If you actually knew what it was you were doing, you could tailor that to match each set of args. Now loop through it:

Code:

struct args *n;
for( n = argtable[ functionindexbyname( "foo" ) ]; n; n = n->next )
    if( compargs( n ) == whateveritisithinkiwant )
        return n or whateveritisithinkiamtoreturn;
return fail;

You could also make that a crude hash table, or even just an array of lists arguments, 0 to 5, to speed up your search by 5.


Quzah.