124 lines
3.2 KiB
C
124 lines
3.2 KiB
C
/*
|
|
* BAD: Scattered Linked List Traversal
|
|
* =====================================
|
|
* This program creates a linked list with nodes scattered randomly in memory,
|
|
* simulating real-world fragmented allocation patterns.
|
|
* This causes terrible cache behavior due to random memory access.
|
|
*
|
|
* Compile: make list_scattered
|
|
* Run: ./list_scattered
|
|
* Profile: perf stat -e cache-misses,cache-references ./list_scattered
|
|
*/
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdint.h>
|
|
#include <time.h>
|
|
|
|
#define N 10000000 /* 10 million elements */
|
|
|
|
struct node {
|
|
int value;
|
|
struct node *next;
|
|
};
|
|
|
|
double get_time(void) {
|
|
struct timespec ts;
|
|
clock_gettime(CLOCK_MONOTONIC, &ts);
|
|
return ts.tv_sec + ts.tv_nsec / 1e9;
|
|
}
|
|
|
|
/* Fast deterministic PRNG - much faster than rand() */
|
|
static uint64_t xorshift64_state = 42;
|
|
|
|
static inline uint64_t xorshift64(void) {
|
|
uint64_t x = xorshift64_state;
|
|
x ^= x << 13;
|
|
x ^= x >> 7;
|
|
x ^= x << 17;
|
|
xorshift64_state = x;
|
|
return x;
|
|
}
|
|
|
|
long sum_list(struct node *head) {
|
|
long sum = 0;
|
|
struct node *curr = head;
|
|
while (curr != NULL) {
|
|
sum += curr->value;
|
|
curr = curr->next;
|
|
}
|
|
return sum;
|
|
}
|
|
|
|
/*
|
|
* Create linked list with nodes scattered in memory (worst case for cache)
|
|
* Each node is allocated individually, then shuffled and linked randomly.
|
|
*/
|
|
struct node *create_list_scattered(int n) {
|
|
struct node **nodes = malloc(n * sizeof(struct node *));
|
|
if (!nodes) {
|
|
perror("malloc");
|
|
exit(1);
|
|
}
|
|
|
|
/* Allocate each node separately - they end up scattered in heap */
|
|
for (int i = 0; i < n; i++) {
|
|
nodes[i] = malloc(sizeof(struct node));
|
|
if (!nodes[i]) {
|
|
perror("malloc node");
|
|
exit(1);
|
|
}
|
|
nodes[i]->value = i % 100;
|
|
}
|
|
|
|
/* Shuffle the order (Fisher-Yates) to ensure random access pattern */
|
|
for (int i = n - 1; i > 0; i--) {
|
|
int j = xorshift64() % (i + 1);
|
|
struct node *tmp = nodes[i];
|
|
nodes[i] = nodes[j];
|
|
nodes[j] = tmp;
|
|
}
|
|
|
|
/* Link them in shuffled order */
|
|
for (int i = 0; i < n - 1; i++) {
|
|
nodes[i]->next = nodes[i + 1];
|
|
}
|
|
nodes[n - 1]->next = NULL;
|
|
|
|
struct node *head = nodes[0];
|
|
free(nodes); /* Free the pointer array, not the nodes */
|
|
return head;
|
|
}
|
|
|
|
void free_scattered_list(struct node *head) {
|
|
while (head != NULL) {
|
|
struct node *next = head->next;
|
|
free(head);
|
|
head = next;
|
|
}
|
|
}
|
|
|
|
int main(void) {
|
|
printf("Scattered Linked List Traversal (%d elements)\n", N);
|
|
printf("Each node allocated individually, then linked in random order.\n");
|
|
printf("This causes maximum cache thrashing.\n\n");
|
|
|
|
printf("Creating scattered linked list (this takes a while)...\n");
|
|
struct node *list = create_list_scattered(N);
|
|
|
|
/* Warm up */
|
|
sum_list(list);
|
|
|
|
double start = get_time();
|
|
long result = sum_list(list);
|
|
double elapsed = get_time() - start;
|
|
|
|
printf("Scattered list sum: %ld in %.4f seconds\n\n", result, elapsed);
|
|
|
|
printf("To see cache behavior, run:\n");
|
|
printf(" perf stat -e cache-misses,cache-references ./list_scattered\n");
|
|
|
|
free_scattered_list(list);
|
|
return 0;
|
|
}
|