Memory Cache and Performance

Cache Pitfall #1: Random accesses

enum {n=1024/4};
int arr[n];

int inc_arr(void) {
	for (int i=0;i<n;i++)
		arr[i]++;
	return 0;
}

int foo(void) {
	double t=time_function(inc_arr);
	printf("%.3f ns/element\n",t/n*1.0e9);
	return 0;
}

(Try this in NetRun now!)

enum {n=1024/4};
int arr[n];

int inc_arr(void) {
	unsigned int loc=0;
	for (int i=0;i<n;i++) {
		arr[loc%n]++;
		loc+=12345;
	}
	return 0;
}

int foo(void) {
	double t=time_function(inc_arr);
	printf("%.3f ns/element\n",t/n*1.0e9);
	return 0;
}

(Try this in NetRun now!)

Application: Linked List

class linked_listnode {
public:
	linked_listnode *next;
	int data;
	linked_listnode(linked_listnode *next_,int data_) {next=next_; data=data_;}
};

linked_listnode *make_list(void) { /* build a million-node list */
	linked_listnode *head=0;
	for (int i=0;i<1000000;i++) {
		char *padding=new char[rand()%40];
		head=new linked_listnode(head,rand()%7);
	}
	return head;
}
linked_listnode *list=make_list(); /*<- build list once, so it's not timed with foo */

int foo(void) { /* walk through the linked list */
	int sum=0;
	for (linked_listnode *cur=list; cur!=NULL; cur=cur->next) 
		sum+=cur->data;
	return sum;
}

(Try this in NetRun now!)

linked_listnode *make_list(void) { /* build a million-node list */
	linked_listnode *head=0;
	for (int i=0;i<1000000;i++) {
		head=new linked_listnode(head,rand()%7);
	}
	return head;
}

(Try this in NetRun now!)

#include <new>
class linked_listnode {
public:
	linked_listnode *next;
	int data;
	linked_listnode(linked_listnode *next_,int data_) {next=next_; data=data_;}
	linked_listnode() {}
};

linked_listnode *make_list(void) { /* build a million-node list */
	linked_listnode *head=0;
	linked_listnode *arr=new linked_listnode[1000000];
	for (int i=0;i<1000000;i++) {
		head=new(&arr[i]) linked_listnode(head,rand()%7);
	}
	return head;
}
linked_listnode *list=make_list(); /*<- build list once, so it's not timed with foo */

int foo(void) { /* walk through the linked list */
	int sum=0;
	for (linked_listnode *cur=list; cur!=NULL; cur=cur->next) 
		sum+=cur->data;
	return sum;
}

(Try this in NetRun now!)

Hardware: Levels of Cache

	for (i=0;i<max;i++) { /* jump around in buffer, incrementing as we go */
		sum+=buf[loc&mask]++;
		loc+=1234567;
	}

• "L1" cache is the fastest (like 5ns) but tiny (100KB or less).
• "L2" cache is slower (7-10ns) but much bigger (up to a meg)
• RAM is painfully slow (100ns or more) but huge (gigs)
  

Hardware: DRAM Hardware

Software: Memory Speed

• Good *if* you're accessing a small amount of memory--small enough to stay in cache.  The pieces of memory you use often automatically get copied into fast cache memory.  For example, the top of the stack, recent stuff from the heap, and commonly used globals are almost always in cache, and hence really fast.  Machines only have on the order of 1 meg of cache nowdays.
  
• Good *if* you're accessing memory sequentially--if you access a[i], you then access a[i+1].  This "streaming" access is fast because memory chips don't have to change rows.  See Ars Technica for piles of details on the mechanics of RAM access.
  
• Terrible *if* you're accessing a big buffer (too big to fit in cache) in a nonsequential way.  Cached accesses are on the order of 1ns.  Streaming access is also a few ns.  Random access that isn't in the cache is on the order of 100ns!
  

• Make things smaller, or re-use them more often, to take advantage of the cache.
  
• Make your accesses more regular, to get streaming access.
  

• Change your algorithm to improve locality.  Think about how your loops access memory.  Often it's trivial to reorganize your loops so you touch the same data 5 times before hitting the next piece of data (temporal locality); or so you access arrays sequentially (spatial locality).  Sometimes an algorithm that's theoretically more efficient will be slower than another algorithm with more instructions but better locality!
  
• Change your data structure to improve locality.  For example, you might change linked lists into arrays.  The trouble with linked lists is that links are allocated at random separate locations; but an array will be contiguous in memory (spatial locality).
• Change your input data to improve locality.  For example, processing data in small pieces (1KB) will usually have better temporal locality than huge chunks (1GB).  Of course, if your pieces are too small, sometimes your program will slow down because of the per-piece overhead!

Application: 2D Arrays implemented as 1D Arrays

int arr[4][3];
int foo(void) {
	arr[0][0]=0xA0B0;
	arr[0][1]=0xA0B1;
	arr[0][2]=0xA0B2;
	arr[1][0]=0xA1B0;
	arr[2][0]=0xA2B0;
	arr[3][0]=0xA3B0;
	return 0;
}

• "j is the fast index", since as you walk through the 1D array, the 2D value of j changes fast (every step), but i changes more slowly.
• "the array is column-major" (if i is the column number, like I've drawn the table above, a whole row is contiguous in memory), *or* "the array is row-major" (if i is the row number, like the transpose of my figure, a whole row is contiguous in memory).  Note that whether you call an array row- or column-major depends on what you *define* as the rows or columns!

enum {sx=512};
enum {sy=512};
double img[sx*sy];

int inc_img(void) {
        for (int x=0;x<sx;x++)
	for (int y=0;y<sy;y++)
		img[x+y*sx]++;
	return 0;
}

int foo(void) {
	double t=time_function(inc_img);
	printf("%.3f ns/pixel\n",t/(sx*sy)*1.0e9);
	return 0;
}

• Avoiding the power-of-two-jumps that screw up a set-associative cache (see below), by changing "sx" to 512+4.  This alone speeds the program up to 15ns/pixel.

• Making "img" smaller, by changing it to a "char" (1 byte) instead of "double" (8 bytes).  This speeds the program up to 6ns/pixel (try it!).
• Making the access more regular, by either interchanging the x and y loops, or by changing how the array is indexed (so it's "img[x*sy+y]").  This speeds the program up to 4ns/pixel.
  
• Doing both--small data with regular access.  This speeds the program up to about 1ns/pixel--a 70x improvement!

Cache Pitfall #2: Set-associative Cache Mapping

enum {n=1024*1024};
char arr[n]; 

int foo(void) {
	arr[0]++;
	arr[12345]++;
	return 0;
}

(Try this in NetRun now!)

enum {n=1024*1024};
char arr[n]; 

int foo(void) {
	arr[0]++;
	arr[65536]++;
	return 0;
}

(Try this in NetRun now!)

Cache Pitfall #3: Cache Coherence and Cache Thrashing

enum {n=2}; /* number of threads */
enum {m=1000*1000}; /* number of times to access the int */
int offset=1; /* distance, in ints, between threads' accesses */
volatile int arr[1025];
void hammer_on_int(volatile int *ptr) {
	for (int i=0;i<m;i++)
		(*ptr)++;
}
int multi_hammer(void) {
#pragma omp parallel for
        for (int thread=0;thread<n;thread++) {
        	hammer_on_int(&arr[thread*offset]);
        }
	return 0;
}
int foo(void) {
	for (offset=1;offset<=1024;offset*=2)
		printf("%d-byte offset took %.3f ns/++\n",
			sizeof(int)*offset,time_function(multi_hammer)*1.0e9/m);
	return 0;
}

(Try this in NetRun now!)

4-byte offset took 19.437 ns/++
8-byte offset took 19.304 ns/++
16-byte offset took 20.442 ns/++
32-byte offset took 22.939 ns/++
64-byte offset took 2.615 ns/++
128-byte offset took 2.601 ns/++
256-byte offset took 2.598 ns/++
512-byte offset took 2.572 ns/++
1024-byte offset took 2.857 ns/++
2048-byte offset took 2.664 ns/++
4096-byte offset took 2.571 ns/++
Program complete.  Return 0 (0x0)

Hardware: Snoopy Cache Coherence Protocol