/*
    caching.c

    Bridger Herman <bridger at carleton.edu> for CS208.02, Fall 2024
    Updated lightly by Tanya Amert, Fall 2024

    Demonstrates the effects that caching has on performance. Some code from
    https://diveintosystems.org/book/C11-MemHierarchy/locality.html

    usage:

        ./caching <matrix size>

    compile with (-g is debugging symbols for gdb)

        gcc -g -Og -o caching caching.c
*/

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

/////////////////////////////////////////////////////////////
// Generate random matrices                                //
/////////////////////////////////////////////////////////////

int* get_random_matrix_1d(int n, int max)
{
    int *mat = (int *)malloc(n * n * sizeof(int *));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            mat[i * n + j] = 1 + rand() % max;
        }
    }

    return mat;
}

/////////////////////////////////////////////////////////////
// Compute average matrix value                            //
/////////////////////////////////////////////////////////////

float average_mat_1d_byrow(int *mat, int n)
{
    int total = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // Note indexing: i * n + j
            total += mat[i * n + j];
        }
    }

    return (float) total / (n * n);
}

float average_mat_1d_bycol(int *mat, int n)
{
    int total = 0;

    for (int j = 0; j < n; j++) // Note loop ordering
    {
        for (int i = 0; i < n; i++)
        {
            // Note indexing: i * n + j
            total += mat[i * n + j];
        }
    }

    return (float) total / (n * n);
}

/////////////////////////////////////////////////////////////
// main function                                           //
/////////////////////////////////////////////////////////////

int main(int argc, char **argv)
{
    if (argc != 2)
    {
        printf("usage: ./caching <matrix size>\n");
        return 1;
    }

    int matrix_size;
    int matches = sscanf(argv[1], "%8d", &matrix_size);
    if (matches != 1)
    {
        exit(1);
    }
    printf("Matrix size: %d\n", matrix_size);

    // Setup timer
    double timer;
    float result;
    struct timeval tstart, tend;

    // Build the matrix
    srand(208); // random seed
    int* matrix1d = get_random_matrix_1d(matrix_size, 10);

    // Row-major traversal
    gettimeofday(&tstart, NULL);
    result = average_mat_1d_byrow(matrix1d, matrix_size);
    gettimeofday(&tend, NULL);

    timer = tend.tv_sec - tstart.tv_sec + (tend.tv_usec - tstart.tv_usec)/1.e6;
    printf("by row:    result: %.2f -- time %6.8f sec\n", result, timer);

    // Column-major traversal
    gettimeofday(&tstart, NULL);
    result = average_mat_1d_bycol(matrix1d, matrix_size);
    gettimeofday(&tend, NULL);

    timer = tend.tv_sec - tstart.tv_sec + (tend.tv_usec - tstart.tv_usec)/1.e6;
    printf("by column: result: %.2f -- time %6.8f sec\n", result, timer);

    // Clean up after ourselves
    free(matrix1d);

    return 0;
}