74 lines
1.8 KiB
C
74 lines
1.8 KiB
C
/*
|
|
* GOOD: Row-Major Matrix Traversal
|
|
* =================================
|
|
* This program traverses a 2D matrix in row-major order,
|
|
* matching how C stores 2D arrays in memory for excellent cache utilization.
|
|
*
|
|
* Compile: make matrix_row_major
|
|
* Run: ./matrix_row_major
|
|
* Profile: perf stat -e cache-misses,cache-references,L1-dcache-load-misses ./matrix_row_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;
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Row-major traversal: access sequential memory addresses
|
|
* Memory layout: [0][0], [0][1], [0][2], ... [0][COLS-1], [1][0], ...
|
|
* This matches how C stores 2D arrays - CACHE FRIENDLY
|
|
*/
|
|
long sum_row_major(void) {
|
|
long sum = 0;
|
|
for (int i = 0; i < ROWS; i++) {
|
|
for (int j = 0; j < COLS; j++) {
|
|
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 (sequential!)\n\n",
|
|
sizeof(int));
|
|
|
|
init_matrix();
|
|
|
|
/* Warm up */
|
|
sum_row_major();
|
|
|
|
double start = get_time();
|
|
long result = sum_row_major();
|
|
double elapsed = get_time() - start;
|
|
|
|
printf("Row-major sum: %ld in %.3f seconds\n\n", result, elapsed);
|
|
|
|
printf("To see cache behavior, run:\n");
|
|
printf(" perf stat -e cache-misses,cache-references,L1-dcache-load-misses ./matrix_row_major\n");
|
|
|
|
return 0;
|
|
}
|