//===================================================== file = alloc4.c =====
//=  Times indexing into one-time allocated memory                          =
//=   - Sequential and random reads to study caching effects                =
//===========================================================================
//=  Notes:                                                                 =
//=    1) Must manually set #define for WIN or UNIX compile                 =
//=    2) Must manually set #define NUM                                     =
//=    3) Note that an index value is computed within the sequential loop   =
//=       so that overhead is same as in random loop.  The non-use of index =
//=       in the first loop results in a compiler warning. Ignore it.       =
//=    4) NUM memory locations are malloc'ed at the start.                  =
//=-------------------------------------------------------------------------=
//= Example execution:                                                      =
//=                                                                         =
//=   ----------------------------------------------- alloc3.c -----        =
//=     It took   1.362 sec to do 10000000 sequential indexes into memory   =
//=     It took   1.933 sec to do 10000000 random indexes into memory       =
//=   ---------------------------------------------------------------       =
//=-------------------------------------------------------------------------=
//=  Build: bcc32 alloc3.c, gcc alloc3.c                                    =
//=-------------------------------------------------------------------------=
//=  Execute: alloc3                                                        =
//=-------------------------------------------------------------------------=
//=  Author: Kenneth J. Christensen                                         =
//=          University of South Florida                                    =
//=          WWW: http://www.csee.usf.edu/~christen                         =
//=          Email: christen@csee.usf.edu                                   =
//=-------------------------------------------------------------------------=
//=  History: KJC (12/17/00) - Genesis (from timeit.c)                      =
//===========================================================================
#define  WIN                // WIN for Windows and UNIX for Unix

//----- Include files -------------------------------------------------------
#include <stdio.h>          // Needed for printf()
#include <stdlib.h>         // Needed for malloc(), rand(), and exit()
#ifdef WIN
#include <sys\timeb.h>      // Needed for ftime() and timeb structure
#endif
#ifdef UNIX
#include <sys/timeb.h>      // Needed for ftime() and timeb structure
#endif

//----- Defines -------------------------------------------------------------
#define NUM    10000000     // Number of allocations to perform

//===========================================================================
//=  Main program                                                           =
//===========================================================================
void main(void)
{
  unsigned int *val;        // Unsigned int value
  unsigned int temp;        // Temporary unsigned int value
  struct timeb start, stop; // Start and stop times structures
  double       elapsed1;    // Elapsed time in seconds for sequential
  double       elapsed2;    // Elapsed time in seconds for random
  unsigned int i;           // Loop counter
  unsigned int index;       // Array index

  // Output a banner
  printf("----------------------------------------------- alloc4.c -----\n");

  // Do the malloc all at once (outside of the timing loop) and assign values
  val = malloc(NUM * sizeof(unsigned int));
  if (val == NULL)
  {
    printf("ERROR - malloc failed with NULL pointer (NUM = %d) \n", NUM);
    exit(1);
  }
  for (i=0; i<NUM; i++)
    val[i] = i;

  // Start timing
  ftime(&start);

  // Perform NUM reads in sequential order
  for (i=0; i<NUM; i++)
  {
    index = rand() % NUM;
    temp = val[i];
  }

  // Stop timing and compute elapsed time for elapsed1
  ftime(&stop);
  elapsed1 = ((double) stop.time + ((double) stop.millitm * 0.001)) -
             ((double) start.time + ((double) start.millitm * 0.001));

  // Start timing
  ftime(&start);

  // Perform NUM reads in random order
  for (i=0; i<NUM; i++)
  {
    index = rand() % NUM;
    temp = val[index];
  }

  // Stop timing and compute elapsed time for elapsed2
  ftime(&stop);
  elapsed2 = ((double) stop.time + ((double) stop.millitm * 0.001)) -
             ((double) start.time + ((double) start.millitm * 0.001));

  // Output elapsed times
  printf("  It took %7.3f sec to do %d sequential reads from memory \n",
    elapsed1, NUM);
  printf("  It took %7.3f sec to do %d random reads from memory \n",
    elapsed2, NUM);
  printf("---------------------------------------------------------------\n");
}