/*++

    This simple program allocates a multi-megabyte sized array of integers, then times
    how long it takes to write to every array location.  The program varies the pattern
    it uses to write each array location based on a stride that changes between each
    pass through the array.

    For example a stride of 1 makes one pass through the array accessing locations
    0,1,2,... until the end of the array is reached.  A stride of 2 makes two passes
    through the array, first accessing locations 0,2,4... and then accessing locations
    1,3,5,... until the end of the array is reached.  The program starts with an initial
    stride value and each pass increases the stride until the stride is equal to half
    the size of the array.  The program measures in seconds on long it takes for each
    new stride through the array.

    The program takes four arguments, first is the number of megabytes to allocate to the
    array, second is an initial stride value, the third and fourth parameters are the
    multiplicative and additive factors used to compute each new stride.  For example,
    the parameters "4 1 2 0" allocates a array of 4MB, with an initial stride value of 1,
    then with each new pass the stride is doubled in size 1,2,4,8,16,32...  With input
    values "4 1 1 1" the stride values increase by 1 each time 1,2,3,4,5,6,...

    Your assignment is to compile and run this program on a computer of your choice using
    a fairly large array, but not large enough to force the system to page to the disk.
    For most systems a good size is about 512MB.

    If 512MB is your array size try running the program with the following two sets of
    parameters "512 1 2 0" and "512 1000 1 1".  You might observe some unusual timing
    patterns that you will need to be ready to discuss.  Note that the second set of
    parameters will take a long time to finish, however any anomalies should be noticable
    within 20 minutes.  Save your output because that is what we will be discussing.

--*/

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

void main (int argc, char *argv[])
{
    clock_t StartTime, EndTime;
    unsigned long *Array;
    unsigned long Size, StartStride, StrideTimes, StridePlus;
    unsigned long i,j,k;

    sscanf(argv[1], "%lu", &Size);
    sscanf(argv[2], "%lu", &StartStride);
    sscanf(argv[3], "%lu", &StrideTimes);
    sscanf(argv[4], "%lu", &StridePlus);

    printf("Size = %luMB\n", Size);

    // Allocate a test array

    Size = 1024 * 1024 * Size;
    if ((Array = malloc(Size)) == NULL) {
        printf("malloc failed\n");
        return;
    }
    Size /= sizeof(unsigned long);

    // Now test it for strides from StartStride to Size/2

    printf("  Stride   Seconds\n");
    for (i = StartStride; i <= Size/2; i = (i*StrideTimes)+StridePlus) {
        printf("%8lu", i);
        StartTime = clock();
        for (j = 0; j < i; j++) {
            for (k = j; k < Size; k += i) {
                Array[k] = k;
            }
        }
        EndTime = clock();
        printf(", %8.3f\n", ((double)(EndTime - StartTime)/CLOCKS_PER_SEC));
    }
}