It seems that the cache miss penalty is quite severe on most motherboards
(it's 30-40 cycles on mine). The bottom line is that a motherboard that
handles cache misses quickly (like the Headland/Shasta chipset that was
mentioned some time ago) is extremely benificial in Linux.
To calculate the cache miss penalty, run the program a few times,
while running memory-intensive stuff in between. Use the slowest and
fastest run as follows:
cache miss penalty in seconds =
(Tslow - Tfast) / (SUMslow - SUMfast) / 25600
where
Tslow is the time taken in the slowest run,
SUMslow the value of sum in the slowest run,
and similarly for Tfast and SUMfast (sum is proportional to
the number of cache misses).
Compile with optimization (i.e. -O2). The constants are set for
a 256K cache.
I don't know much about cache design, this is just timing and math; there
may be some totally wrong assumptions.
I think it would be interesting to get some idea of how severe the cache
miss penalty actually is on different motherboards.
hhanemaa@cs.ruu.nl
-------------------------------------------------------------------------
/*
This is a program to test the effects of page-thrashing with a
direct-mapped external cache, which is what almost all current
motherboards seem to be equipped with. It can also be used to
calculate the cache miss penalty. It assumes that the core
memory as read from /proc/kcore or /dev/kmem is stored in the same
order in physical memory (which is the case).
How it works:
First, it allocates a 256K buffer using malloc(), and writes a
signature at the start of each of the 64 4K pages in the buffer.
It then scans all core memory looking for signatures, and records
where in (presumably) physical memory each of the 64 pages are mapped,
and writes an ASCII map to stdout.
Assuming a direct-mapped cache where pages at memory offset p map
into offset (p mod 256K) in the external cache, it counts and reports
how many pages of the buffer map into the same place ('cache page') in
the external cache. It also reports how contiguous the buffer is in
memory (linear contiguousness is defined as pages adjacent in virtual
memory that are also adjacent in physical memory).
Finally, a benchmark is run that linearly accesses the 256K buffer a
number of times.
On my machine with 5Mb of memory, right after rebooting Linux the
buffer seems to be allocated contiguously in physical memory (no
cache conflicts), and the benchmark takes about 0.5s. It quickly
becomes slower, and after having run some programs, the buffer is
usually heavily fragmented in physical memory, and about half of the
pages conflict in the external cache; the benchmark takes about 1.5s,
and the time seems to be directly related to the number of cache
conflicts. This is on a i486 running at 40 MHz in a motherboard
with a probably slow memory architecture. The internal cache probably
doesn't interfere too much (it may help to get the actual benchmark
code page out of the way). I think the dynamic buffer cache is the
major factor in memory fragmentation.
I think the benchmark does say something about how fast moderately
memory-intensive programs (and the kernel) run (although highly
CPU-dependent tasks rely mostly on the internal cache).
This means that most motherboards have a very bad cache/memory
architecture as far as a real virtual memory OS like Linux is
concerned, and that getting a motherboard with a good chipset (like
the Headland/Shasta chipset mentioned some time ago that can handle
cache misses quickly) is enormously benificial. If cache misses are
handled quickly, the external cache doesn't matter much. A very large
cache (like 1024K) should help a lot if cache misses are costly.
It also means that since a buffer stays at the same place in memory
during the life of a (long, memory intensive) process (ignoring
swapping), the theoretical possibility of making sure that buffers
are allocated so that cache conflicts are minimized is interesting.
This may be somewhat voodoo cachonomics, though. And I don't know
much about how the kernel allocates memory (other than that it quickly
produces fragmentation, which is reasonably unavoidable).
Here are some results from my machine. It seems that the time taken
is surprisingly predictable from the number of cache conflicts, which
also seems to be accurately predictable (sum).
For comparision purposes, the timing for sum = 0 and sum ~ 36 (in the
average range) are useful, as is the maximum observed value of sum.
p(n) = #'cache pages' into which n pages map:
n = 1 2 3 4 sum time
(1) 64 0 0.58
60 2 4 0.70
38 13 26 1.24
36 14 28 1.30
34 15 30 1.37
32 8 4 1 32 1.40
29 10 5 35 1.46
27 14 3 37 1.52
26 16 2 38 1.54
25 15 3 39 1.57
23 16 3 41 1.62
22 15 4 42 1.65
0 0 0 4 (worst case, theoretical) 64 ~2.18
(2) 50 7 14 0.86
46 9 18 0.94
32 16 32 1.22
28 18 36 1.30
24 14 4 40 1.39
21 20 1 43 1.44
(3) 0 0.50
28 1.22
sum = p(2) * 2 + p(3) * 3 + p(4) * 4 + ...
This is proportional to the expected number of cache conflicts.
Note that p(1) + p(2) * 2 + ... should be equal to 64 (NU_PAGES).
The optimal situation is p(1) = 64.
(1) i486 at 40 MHz, USAi chipset, 5M memory, 256K direct-mapped
write-back cache, 1/1/2 cache read/write/DRAM waitstates.
I now attempt to calculate the cache miss penalty:
Time seems to be approx. 0.58 + sum * 0.025.
Given 4096 / 16 = 256 cache lines in a page and 100 iterations,
100 * 256 = 25600 cache misses for each 'sum', the cache miss
penalty seems to be:
0.025 / 25600 = 980ns per 16-byte cache line, which is about
40 cycles at 40 MHz (ugh!).
(2) DRAM waitstates set to 1 (which seems stable as long as my
motherboard doesn't do DMA):
Time approx. base + sum * 0.020.
Cache miss penalty: 0.020 / 25600 = 780ns, about 31 cycles.
(3) Running at 33 Mhz, 0 cache read/write waitstates, 1 DRAM.
Cache miss penalty: 0.72 / 28 / 25600 = 1004ns (~30 cycles)
For NU_PAGES = 256 (1024K):
n = 1 2 3 4 5 6 7 8 9 10 sum time
4 7 15 15 12 4 1 3 2 252 8.77
2 8 17 18 7 4 2 4 0 1 254 8.82
0 0 0 64 (worst case, observed) 256 8.86
With a 1024K buffer, the cache miss penalty is about the only factor.
More useful is NU_PAGES = 16 (64K):
1 2 3
16 0 0.13
14 1 2 0.19
13 0 1 (average) 3 0.21
12 2 4 0.24
8 4 8 0.34
*/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <sys/stat.h>
#include <sys/time.h>
#define NU_PAGES 64 /* Number of 4K pages to test with. */
#define CACHE_PAGES 64 /* Number of pages in direct-mapped cache. */
/* 64 for 256K cache, 32 for 128K cache etc. */
#define USE_PROC /* USE_PROC: use /proc/kcore (pl14). */
/* USE_KMEM: use /dev/kmem (worse). */
#define SIGLENGTH 8
#define BENCHMARK_LOOPS 100
unsigned char *buf; /* Buffer used to test with. */
unsigned char sig[SIGLENGTH]; /* Signature string to detect pages. */
int count; /* Number of pages detected. */
int size; /* Size of /proc/kcore. */
int *map; /* Map of memory pages. */
void create_buffer() {
int i;
printf("Allocating %d pages.\n", NU_PAGES);
buf = malloc(NU_PAGES * 4096); /* Allocate 4K pages. */
printf("Writing %d signatures.\n", NU_PAGES);
/* Create signature. */
srand(clock());
for (i = 0; i < SIGLENGTH; i++)
sig[i] = random();
for (i = 0; i < NU_PAGES; i++) {
/* Write signature. */
memcpy(buf + i * 4096, sig, SIGLENGTH);
buf[i * 4096 + SIGLENGTH] = i; /* ID byte. */
}
}
void detect_pages() {
FILE *f;
struct stat st;
char *tmpbuf;
int i, n;
#ifdef USE_KMEM
f = fopen("/dev/kmem", "rb");
if (f == NULL) {
printf("Error: Cannot open /dev/kmem.\n");
exit(-1);
}
tmpbuf = alloca(16384);
size = 0;
while ((n = fread(tmpbuf, 1, 16384, f)) != 0) {
size += n;
if (size % (1024 * 1024) == 0)
printf("%d ", size / (1024 * 1024));
}
printf("\n/dev/kmem size is %d bytes.\n", size);
#endif
#ifdef USE_PROC
f = fopen("/proc/kcore", "rb");
if (f == NULL) {
printf("Error: /proc/kcore does not exist (need 0.99pl14).\n");
exit(-1);
}
fstat(fileno(f), &st);
size = st.st_size;
printf("/proc/kcore size is %d bytes.\n", size);
#endif
/* Build map. */
count = 0;
map = malloc(sizeof(int) * size / 4096);
for (i = 0; i < size / 4096; i++) {
unsigned char buf[64];
fseek(f, i * 4096, SEEK_SET);
fread(buf, 1, 64, f);
map[i] = 0x100;
if (memcmp(sig, buf, SIGLENGTH) == 0) {
/* This page belongs to the buffer. */
map[i] = buf[SIGLENGTH]; /* ID byte */
count++;
}
}
printf("Pages detected: %d (should be %d).\n", count, NU_PAGES);
fclose(f);
}
void print_map() {
int i;
int *cachepage;
int conflictcount[NU_PAGES + 1];
/* Allow for worst-case scenario. */
int contiguouscount, linearcontiguouscount, sum;
/* Count how many pages cache into each 'cache page', assuming a */
/* direct-mapped external cache. */
cachepage = malloc(sizeof(int) * CACHE_PAGES);
for (i = 0; i < CACHE_PAGES; i++)
cachepage[i] = 0;
printf("Map of physical address space (%d out of %d pages marked):\n",
NU_PAGES, size / 4096);
contiguouscount = 0;
linearcontiguouscount = 0;
for (i = 0; i < size / 4096; i++) {
if (map[i] == 0x100)
printf(".");
else { /* Page is in buffer. */
printf("#");
/* Increase count of 'cache page'. */
cachepage[i % CACHE_PAGES]++;
if (i > 0)
if (map[i - 1] != 0x100) {
contiguouscount++;
if (map[i - 1] == map[i] - 1)
linearcontiguouscount++;
if (map[i - 1] == map[i] + 1)
linearcontiguouscount++;
}
}
}
printf("\n");
printf("Contiguousness: %d%% (%d out of %d), linear contiguousness: "
"%d%%\n",
contiguouscount * 100 / (NU_PAGES - 1), contiguouscount,
NU_PAGES - 1, linearcontiguouscount * 100 / (NU_PAGES - 1));
for (i = 0; i < NU_PAGES; i++)
conflictcount[i] = 0;
for (i = 0; i < CACHE_PAGES; i++)
conflictcount[cachepage[i]]++;
printf("Cache 'pages' occupation histogram (assuming %dK "
"direct-mapped cache):\n", CACHE_PAGES * 4);
sum = 0;
for (i = 0; i < NU_PAGES; i++)
if (conflictcount[i] > 0) {
printf("%d: %d ", i, conflictcount[i]);
if (i > 1)
sum += i * conflictcount[i];
}
printf(" sum: %d (proportional to #cache misses)\n", sum);
}
void volatilize( int v ) {
static int val;
val = v;
}
void benchmark() {
struct timeval startclock, endclock;
int diffclock;
int i, j;
int page[NU_PAGES];
for (i = 0; i < NU_PAGES; i++)
page[i] = i; /* Access pages linearly. */
printf("Benchmarking...\n");
gettimeofday(&startclock,0);
for (i = 0; i < BENCHMARK_LOOPS; i++)
for (j = 0; j < NU_PAGES; j++) {
unsigned char *p;
int k, v;
v = 0;
p = buf + page[j] * 4096;
/* Read a byte in each 16-byte chunk of the page. */
/* (reading a 32-bit word would make more sense, */
/* but it doesn't really matter). */
for (k = 0; k < 4096 / 128; k++) {
v += *p;
v += *(p + 16);
v += *(p + 32);
v += *(p + 48);
v += *(p + 64);
v += *(p + 80);
v += *(p + 96);
v += *(p + 112);
p += 128;
}
volatilize(v);
}
gettimeofday(&endclock,0);
diffclock = (endclock.tv_sec -startclock.tv_sec)*1000000
+ (endclock.tv_usec-startclock.tv_usec);
printf("Time taken: %d.%03d\n"
, diffclock / 1000000, (diffclock % 1000000)/1000);
}
void main() {
create_buffer();
detect_pages();
print_map();
benchmark();
exit(0);
}
--+5n6rz5pIUxbDcmJ--