dynamic allocation of arrays

[jose at shell]

There is an efficient way for using arrays that grow in size dynamically.
The following three programs and their execution times on a SPARCstation 1
make the point.

--------------------------------------
Program 1.

float old_array[10000000];
main () {

int i, j1, j2;

for (i=0; i<10000000; i++) old_array[i] = (float) i * 2. + 0.5;

}
-------------------------------------
Program 2.
/* declare an array of pointers to float; each element of array[] will be
   pointing to an array of floating-point numbers. */
float *array[160];

/* SIZE is the size of the array of floating-point numbers. */
#define SIZE 64000

/* define the macro Array(n) to index into the appropriate array */
#define Array(n) *(array[n/SIZE] + (n%SIZE))

main () {
int i;

for (i=0; i<160; i++) array[i] = (float *) malloc (SIZE * sizeof(float));
for (i=0; i<10000000; i++) Array(i) = (float) i * 2. + 0.5;
}
--------------------------------------
Program 3.                             
/* declare an array of pointers to float; each element of array[] will be
   pointing to an array of floating-point numbers. */                     
float *array[160];                                    
                   
/* SIZE is the size of the array of floating-point numbers. We'll select
   SIZE to be a power of two, in order to avoid function calls. */       
#define SIZE 64*1024                                               
                     
/* define the macro Array(n) to index into the appropriate array */
#define Array(n) *(array[n>>16] + (n&0xFFFF))                       
                                              
main () {
int i;    

for (i=0; i<160; i++) array[i] = (float *) malloc (SIZE * sizeof(float));
for (i=0; i<10000000; i++) Array(i) = (float) i * 2. + 0.5;
}
---------------------------------------
The execution times measured with the C shell 'time' were in seconds:

Program user    system  wall-clock
1       29.3    12.2    118
2       113.3   12.4    167
3       28.3    9.9     106
---------------------------------------

Jose Barros
Staff Research Computer Scientist
Shell Development Co.
3737 Bellaire
Houston, Tx 77025
{bcm,rice}!shell!jose  --- uucp;  jose at shell.com         --- internet
713-663-2581           --- FAX;   713-663-2660           --- Voice


Jose C. Barros
Senior Research Computer Scientist
Shell Development Company, Bellaire Research Center, Houston  (713) 663-2660
..!{sun,psuvax,bcm,rice,cs.texas.edu,decwrl}!shell!jose      jose at shell.uucp