srw@lasspvax.UUCP (Steve White) (01/13/85)
A few months ago I realized there was a better way to do multidimensional
arrays in C. This way is not new; in fact, it is discussed on page 110
of Kernighan and Ritchie. But after reading the discussions in net.lang.c
concerning the subject of multidimensional arrays I decided a lot of
people might not be aware of it or might not appreciate its advantages.
Here's how it works.
The following program illustrates the idea (go ahead, try it!):
main()
{
double **array; /* This will be a 10 x 12 array */
int i;
array = (double **) calloc(10,sizeof(double *));
/* Number of rows = 10 */
for (i = 0; i < 10; i++)
array[i] = (double *) calloc(12,sizeof(double));
/* Number of columns = 12 */
array[2][3] = 3.14159265359;
array[4][5] = 2.71828182846;
anyfunc(array);
}
anyfunc(a)
double **a;
{
printf("%.14g %.14g\n",a[2][3],a[4][5]);
}
We first allocate space for an array of pointers, the length of which is
the number of rows. Then each of these pointers is set to point to
enough space for one row of the array. Once this is done, then we can
pretend we have a regular 2-dimensional array, except that we never have
to specify its dimensions to any subroutines that use it.
There are a couple of DISADVANTAGES to the above method:
1. It uses slightly more storage.
2. You have to initialize the pointers, as in the above program.
It has, however, lots more ADVANTAGES:
1. All storage allocation can be done dynamically.
2. Subroutines don't need to know the dimensions of the array to
access its elements.
3. Non-rectangular arrays are as easy as rectangular.
4. The indices do not have to start at zero! Say we wanted our
indices to start at 1 instead of 0 in the above program (as in
Fortran). Then the initialization would be changed to
array = (double **) calloc(10,sizeof(double *)) - 1;
for (i = 1; i <= 10; i++)
array[i] = (double *) calloc(12,sizeof(double)) - 1;
5. It is FASTER than the standard way (since there is no multiplication
needed to calculate the address).
To test the relative speeds of this way and the standard way, I ran the
following programs:
/* Old way */
main()
{
double array[200][200];
register int i, j, l;
for (l = 0; l < 10; l++)
for (i = 0; i < 200; i++)
for (j = 0; j < 200; j++)
array[i][j] = array[j][i];
}
/* New way */
main()
{
double **array;
register int i, j, l;
array = (double **) calloc(200,sizeof(double *));
for (i = 0; i < 200; i++)
array[i] = (double *) calloc(200,sizeof(double));
for (l = 0; l < 10; l++)
for (i = 0; i < 200; i++)
for (j = 0; j < 200; j++)
array[i][j] = array[j][i];
}
The "Old way" took 22 sec. on our Vax 11/750, while the "New way"
took 17.4 sec. (When the optimizer was invoked with -O, the times were
21.4 and 16.2 sec., for the old and new ways, respectively.)
I think this way of handling multidimensional arrays is definitely
superior to the standard way, at least where speed and flexibility
are important.
Hoping this was useful to you
(or at least interesting),
Steve White
Cornell Univ. Dept. of Physicsgwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (01/15/85)
Steve's suggestion of using vectored-row matrices is a good one; indeed I think I'll include it in the matrix package in our support library. There need to be alloc/free routines (with alloc taking care of setting up the vectors) but for large matrices it would be worth it since double indirection will usually be faster than index arithmetic. This brings me to one of my oldest gripes: There are not enough standardized programming support routines in the C library. Everyone ends up inventing his own set of routines for common operations, such as complex arithmetic or queueing. There have been a few useful additions recently but there should be more.
Bob Larson <BLARSON%ECLD@usc-ecl.ARPA> (01/15/85)
Of course we could all use Bliss-10, which did this automatically :-) Only one instruction is needed per array reference, indexing and indirection were set up as part of the table. (What? Your computer doesn't have indexed indirect indexed indirect addressing? Are you sure your bytes are variable size and that you word size is 36 bits? :-) Sorry for the digression, (I must be getting senile at 24) Bob Larson -------
rpw3@redwood.UUCP (Rob Warnock) (01/15/85)
+--------------- | A few months ago I realized there was a better way to do multidimensional | arrays in C. This way is not new; in fact, it is discussed on page 110 | of Kernighan and Ritchie... | Steve White | Cornell Univ. Dept. of Physics +--------------- If my memory serves me, in the Algol-60 community these arrays of pointers to arrays are called "Illiffe vectors" or "dope vectors". The PDP-10 Algol compiler used them, and due to the PDP-10's ability to indirect-and-index through memory, you could access a multi-dimensional array in ONE instruction, if the subscripts were in registers (as they often are in inner loops). (The best I could do on a 68000 was 3n+1 instructions, where "n" is the number of dimensions in the array, and 4n+1 if you don't want to destroy the subscripts. Could someone who knows the VAX comment on the use of Illiffe vectors on that machine?) For example, suppose we have a three-dimensional array declared "A[17,12,25]". Then let memory location "A_" be the first word of a 17-word array of addresses of the second-level pointers. In each element of "A_" the indirect bit will be turned on, and the index field will name (say) register "T2". To assist the description, call the (normally nameless) second-level arrays A_0 through A_16. Then "A_" is: OPDEF Z [0] ;allow the index and indirect syntax to work. A: Z @A_0(T2) ;A_0 indexed by T2, then indirect Z @A_2(T2) ; through memory. ... Z @A_16(T2) Then the second-level pointers are 12-word vectors (using A_13 as an example): A_13: Z A_13_0(T3) ;note that the 2nd level uses T3 Z A_13_1(T3) ; and since it's the last level ... ; of pointers, no indirect bit ("@"). Z A_13_11(T3) And on the final level are just the array elements themselves: A: ;also the address of the "real" A A_0_0: BLOCK 25 ;size of third dimension A_0_1: BLOCK 25 ... A_13_11: BLOCK 25 A_14_0: BLOCK 25 ... A_16_11: BLOCK 25 Now put the first subscript in register T1, the second in T2, and the third in T3. Then to load register T0 with A[T1,T2,T3], simply say: MOVE T0,@A_(T1) ;could also be an ADD, FMUL, etc. That's nice! On a 68000, the same "instruction" is: lshl #2,d1 ;multiply indices by 4 lshl #2,d2 ; (plus more work if you needed to lshl #2,d3 ; save them for later) addl #A_,d1 movl d1,a0 addl a0@,d2 movl d2,a0 addl a0@,d3 movl d3,a0 movl a0@,d0 (Unfortunately, when I tried this on the C compiler I use, even with "-O" it didn't realize you could "addl a0@,d?". It did "movl a0@,d0" instead, and then added the index to d0, before moving it to a0. Oh well...) ANyway, Illiffe vectors are the way to go for *speed*. They do cost you a size penalty, which can be small if the last dimension is large. How messy would it be to get the compiler to allocate the vectors for you? (...for static arrays only, please!) Or if you don't want to fool with the compiler, a simple pre-processor (driven from pragmats) could compute the vectors and the initializers for them. Rob Warnock Systems Architecture Consultant UUCP: {ihnp4,ucbvax!dual}!fortune!redwood!rpw3 DDD: (415)572-2607 USPS: 510 Trinidad Lane, Foster City, CA 94404