C Programming * Pima Community College * CIS265 -- 5.11 Arrays

5.11 Arrays

5.11 Arrays

The first index is zero(0).
Index(s) use [ ] square braces.
Watch out for the , operator.
Multi-dimension arrays use multiple [ ] square braces.
Subscripts are NOT checked.
Arrays are tightly related to arrays. See Kernighan p97.

Arrays may also be initialized at declaration.

      int i[4] = { 4, 3, 2, 1 };
      float x[2][3] = { { 8.8, 7.7, 6.6 }
                        { 5.5, 4.4, 3.3 } };

Order of reference can make a major difference in execution time. Vary right index fastest.

This program can be accessed at:
ftp://lt.tucson.az.us/pub/c/cache.c.

/* Louis Taber  
 *
 * Feb 10, 2001
 *
 * Program to demonstrate the effect 
 * of the cache memory system
 * and array addressing order.
 */

#include <stdio.h>
#include <time.h>


#define  LINE 512
#define  MAX_ARRAY_SIZE 64*1024*1024  /* 64 Mbytes */
#define  MAX_ROW ( MAX_ARRAY_SIZE / LINE )

char array[MAX_ROW][LINE];            /* Test array    */
int i,j;                              /* Index values  */
int size, row;                        /* Array indexes */
int sum, sum1, sum2;

clock_t start, filled_time, first_fetch, second_fetch; 
float f_t, t_1, t_2, ratio;

int
main()
{
printf("Execution Times           LINE= %d    \n\n",  LINE);
                                    
printf("     Array    Fill    Row     Column    C/R\n");
printf("      Size    Time    Fetch   Fetch     Ratio\n");

size=MAX_ARRAY_SIZE;

while( size >= 32 * 1024 )
  {
  row=size/LINE;
  sum=sum1=sum2=0;

  start= clock();

  /* Fill array */

  for( i=0; i<row; i++ )
    for( j=0; j<LINE; j++) 
      sum += (int)(array[i][j] = (char)((i+j)%127) ); 

  filled_time = clock();

  /* Access all of array right index fastest */

  for( i=0; i<row; i++ )  
    for( j=0; j<LINE; j++)
      sum1 += (int)array[i][j];

  first_fetch = clock();

  /* Access all of array left index fastest */

  for( j=0; j<LINE; j++)
    for( i=0; i<row; i++ )
      sum2 += (int)array[i][j];

  second_fetch = clock();

  f_t = (float)(filled_time-start)/CLOCKS_PER_SEC;
  t_1 = (float)(first_fetch-filled_time)/CLOCKS_PER_SEC;
  t_2 = (float)(second_fetch-first_fetch)/CLOCKS_PER_SEC; 
  ratio= t_2/t_1;

  printf("%10d  %6.2f   %6.2f   %6.2f  %6.2f\n", 
            size, f_t,t_1,t_2,  ratio);

  /* check to see of the sums are all the same */

  if( sum != sum1 || sum != sum2 )
    {
    printf(" Sums do not match\n");
    printf(" %d %d %d \n", sum, sum1, sum2);  
    }

  size >>=1;    /* Cut size of array in half. */
  }

return 0;
}

Intel Pentium, Dual 100MHz, 128 MBytes
Execution Times           LINE= 512    

     Array    Fill    Row     Column   C/R
      Size    Time    Fetch   Fetch    Ratio
  67108864   55.32(1) 14.03(1) 30.68    2.19(3)
  33554432   27.09     7.02    15.33    2.18
  16777216   13.67     3.51     7.67    2.19
   8388608    6.94     1.76     3.82    2.17
   4194304    3.59     0.88     1.92    2.18
   2097152    1.91     0.44     0.95    2.16
   1048576    1.06     0.22     0.48    2.18
    524288    0.64     0.11     0.21    1.91
    262144    0.45     0.06     0.09    1.50
    131072    0.34     0.02     0.04    2.00
     65536    0.20     0.01     0.12   12.00(4)
     32768    0.10     0.01     0.09    9.00


Intel Pentium II, 233 MHz, 386 Mbytes (gort)
Execution Times           LINE= 512    

     Array    Fill    Row     Column   C/R
      Size    Time    Fetch   Fetch    Ratio
  67108864   13.31     3.27    11.50    3.52
  33554432    6.34     1.64     5.73    3.49
  16777216    3.17     0.82     2.84    3.46
   8388608    1.59     0.41     1.41    3.44
   4194304    0.80     0.20     0.71    3.55
   2097152    0.40     0.10     0.36    3.60
   1048576    0.20     0.05     0.17    3.40
    524288    0.10     0.02     0.07    3.50
    262144    0.05     0.01     0.02    2.00
    131072    0.03     0.00     0.01     inf
     65536    0.01     0.00     0.01     inf
     32768    0.01     0.00     0.00     nan

AMD K6-2, 500MHz, 128MBytes (lt)
Execution Times           LINE= 512    

     Array    Fill    Row     Column   C/R
      Size    Time    Fetch   Fetch    Ratio
  67108864    7.56     1.97    19.54    9.92(3)
  33554432    3.34     0.98     9.77    9.97
  16777216    1.67     0.50     4.87    9.74
   8388608    0.84     0.24     2.44   10.17
   4194304    0.42     0.12     1.22   10.17
   2097152    0.21     0.06     0.60   10.00
   1048576    0.11     0.03     0.28    9.33
    524288    0.05     0.01     0.12   12.00
    262144    0.02     0.01     0.05    5.00
    131072    0.01     0.01     0.02    2.00
     65536    0.01     0.00     0.01     inf
     32768    0.00     0.00     0.00     nan


AMD K6-2, 233MHz, 64MBytes (amd)
Execution Times           LINE= 512    

     Array    Fill    Row     Column   C/R
      Size    Time    Fetch   Fetch    Ratio
  67108864   17.46     3.29   355.67  108.11(5)
  33554432    7.57     2.50    16.49    6.60
  16777216    3.94     1.30     8.24    6.34
   8388608    2.00     0.65     4.11    6.32
   4194304    0.98     0.33     2.04    6.18
   2097152    0.49     0.16     1.01    6.31
   1048576    0.24     0.08     0.48    6.00
    524288    0.13     0.04     0.17    4.25
    262144    0.06     0.02     0.08    4.00
    131072    0.03     0.01     0.03    3.00
     65536    0.01     0.00     0.02     inf
     32768    0.01     0.00     0.00     nan

This "benchmark" was using the FSF gcc compiler running Linux. Notes on cache.c program output:

Fill and row fetch times are mostly related to processor speed.
Column fetch times are MUCH slower.
On the AMD processor the ratios were higher.
I can't explain this one.
Performance is REALLY bad if you need to use virtual memory. Note the run using a 64MBytes array on a 64MBytes system. This time may have wrapped. I was off at the swap meet. It wraps every 72 min. Also note that the "row" sequence did not take much longer. Swapping does work.

Instructor: ltaber@pima.edu ** My new Home at GeoApps in Tucson ** The Pima College Site

5.11 Arrays