Content-Length: 3652 | pFad | https://www.infradead.org/~willy/linux/scan.c
// gcc -W -Wall -O2 -g scan.c -o scan
/*
* scan.c - Demonstrate costs of physical vs logical scanning
* Copyright (c) 2023 Oracle Corporation
* Author: Matthew Wilcox
* Version: 1.1
*/
#include
#include
#include
#include
unsigned int verbose;
#define printv(level, fmt, ...) \
if (level <= verbose) { printf(fmt, ##__VA_ARGS__); }
/* time2 - time1 */
double diff_time(struct timespec *time1, struct timespec *time2)
{
double result = time2->tv_nsec - time1->tv_nsec;
return time2->tv_sec - time1->tv_sec + result / 1000 / 1000 / 1000;
}
int usage(char opt)
{
fprintf(stderr, "Option %c not known\n", opt);
return 1;
}
/* Number of pages in memmap */
unsigned long count = 1000 * 1000;
/*
* struct page is about this big. technically the linked list points
* to the linked list, not to the struct page, but it's close enough for
* cricket.
*/
struct page {
unsigned long flags;
struct page *next;
struct page *prev;
unsigned long age;
unsigned long padding[4];
};
void shuffle(struct page **array, unsigned long seed)
{
unsigned long i;
printv(2, "random seed %lu\n", seed);
srand48(seed);
/* Knuth shuffle. O(n) time */
for (i = 1; i < count; i++) {
struct page *page;
unsigned long j = (unsigned long)mrand48() % (i + 1);
page = array[j];
array[j] = array[i];
array[i] = page;
}
for (i = 0; i < count; i++) {
struct page *page = array[i];
page->next = array[(i + 1) % count];
page->prev = array[(i - 1) % count];
page->age = i;
}
}
int main(int argc, char **argv)
{
int opt;
unsigned long seed = time(NULL);
struct page *memmap, **lru_array, *page;
unsigned long total, i;
struct timespec start, finish;
double phys_scan, listlru, arraylru;
while ((opt = getopt(argc, argv, "c:s:v")) != -1) {
if (opt == 'c')
count *= strtoul(optarg, NULL, 0);
else if (opt == 's')
seed = strtoul(optarg, NULL, 0);
else if (opt == 'v')
verbose++;
else
return usage(opt);
}
clock_gettime(CLOCK_MONOTONIC, &start);
memmap = calloc(count, sizeof(struct page));
if (!memmap) {
perror("Allocating memmap");
return 1;
}
clock_gettime(CLOCK_MONOTONIC, &finish);
printv(3, "Allocated memmap for %lu pages in %fs\n", count,
diff_time(&start, &finish));
lru_array = malloc(count * sizeof(struct page *));
for (i = 0; i < count; i++)
lru_array[i] = memmap + i;
clock_gettime(CLOCK_MONOTONIC, &start);
shuffle(lru_array, seed);
clock_gettime(CLOCK_MONOTONIC, &finish);
printv(3, "Created shuffled list in %fs\n", diff_time(&start, &finish));
total = 0;
clock_gettime(CLOCK_MONOTONIC, &start);
for (i = 0; i < count; i++)
total += memmap[i].age;
clock_gettime(CLOCK_MONOTONIC, &finish);
printv(3, "total = %lu\n", total);
phys_scan = diff_time(&start, &finish);
printv(1, "Physical scan in %fs\n", phys_scan);
total = 0;
page = memmap;
clock_gettime(CLOCK_MONOTONIC, &start);
for (i = 0; i < count; i++)
total += lru_array[i]->age;
clock_gettime(CLOCK_MONOTONIC, &finish);
printv(3, "total = %lu\n", total);
arraylru = diff_time(&start, &finish);
printv(1, "Array scan in %fs\n", arraylru);
total = 0;
page = memmap;
clock_gettime(CLOCK_MONOTONIC, &start);
do {
total += page->age;
page = page->next;
} while (page != memmap);
clock_gettime(CLOCK_MONOTONIC, &finish);
printv(3, "total = %lu\n", total);
listlru = diff_time(&start, &finish);
printv(1, "ListLRU scan in %fs\n", listlru);
printf("Physical scan is %f faster than ListLRU\n",
listlru / phys_scan);
printf("Physical scan is %f faster than ArrayLRU\n",
arraylru / phys_scan);
return 0;
}
--- a PPN by Garber Painting Akron. With Image Size Reduction included!Fetched URL: https://www.infradead.org/~willy/linux/scan.c
Alternative Proxies:
Alternative Proxy
pFad Proxy
pFad v3 Proxy
pFad v4 Proxy