/*
 * BAD: Column-Major Matrix Traversal
 * ===================================
 * This program traverses a 2D matrix in column-major order,
 * which causes poor cache utilization because C stores arrays in row-major order.
 *
 * Compile: make matrix_col_major
 * Run:     ./matrix_col_major
 * Profile: perf stat -e cache-misses,cache-references,L1-dcache-load-misses ./matrix_col_major
 */

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

#define ROWS 8192
#define COLS 8192

/* Using static to avoid stack overflow */
static int matrix[ROWS][COLS];

double get_time(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec / 1e9;
}

void init_matrix(void) {
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            matrix[i][j] = (i + j) % 100;
        }
    }
}

/*
 * Column-major traversal: jump around in memory
 * Access pattern: [0][0], [1][0], [2][0], ... [ROWS-1][0], [0][1], ...
 * Each access is COLS * sizeof(int) bytes apart - CACHE HOSTILE
 */
long sum_col_major(void) {
    long sum = 0;
    for (int j = 0; j < COLS; j++) {
        for (int i = 0; i < ROWS; i++) {
            sum += matrix[i][j];
        }
    }
    return sum;
}

int main(void) {
    printf("Matrix size: %d x %d = %zu bytes\n",
           ROWS, COLS, sizeof(matrix));
    printf("Cache line size (typical): 64 bytes\n");
    printf("Stride per access: %zu bytes (jumps over entire row!)\n\n",
           COLS * sizeof(int));

    init_matrix();

    /* Warm up */
    sum_col_major();

    double start = get_time();
    long result = sum_col_major();
    double elapsed = get_time() - start;

    printf("Column-major sum: %ld in %.3f seconds\n\n", result, elapsed);

    printf("To see cache misses, run:\n");
    printf("  perf stat -e cache-misses,cache-references,L1-dcache-load-misses ./matrix_col_major\n");

    return 0;
}