The memory hierarchy
Most of the time, programmers will assume that memory is flat, meaning that all memory references are equally expensive.
Typical CPUs implement several layers of caching backed by system memory and then virtual memory. The cache layers are very fast memory (typically on the same die as the CPU); system memory is slower; virtual memory is slower by 6 orders of magnitude. Typically data is moved to the fastest available level of the cache when it is accessed; data that hasn't been accessed in a while is pushed out to slower levels to make room. To amortize the overhead costs of this process, data is managed in blocks, which may range from as little as 64bytes for the on-chip caches to as much as 4096 bytes or more for the virtual memory system.
The effect of storing data in caches is that it's cheaper - sometime much cheaper - to access data at an address close to other addresses you've looked at recently than to access data far away.
Caching and data structures
The structure of the cache system means that a data structure will run faster if it has good locality, which means that pieces of the data structure accessed around the same time tend to be in about the same place.
💡For Example, given the choice between searching through an unsorted array and unsorted linked list, you are better off searching the array: each position you look at in the array comes right after the previous pistion, so it is likely to be stored in the same block.
💡In contrast, the elements of the linked list will be wherever malloc managed to scrounge up애써 찾아보다 space : in the worst case, one element per virtual memory block, each of which needs to be paged in from disk if you are running low on space.
The disadvantage of the array over the linked list is that calling realloc may be expensive; one way to avoid this to build a linked list of large nodes each of which holds an array, as done in this sample code : stackBlockList.c. This is actually slightly slower than just building a stack as an array : stackArray.c but much faster than the simple linked-list approach : stackList.c.
stackList.c
#include <stdlib.h>
#include <assert.h>
// #include "stack.h"
typedef struct __node {
struct __node *next;
int value;
} Node;
// typedef struct __node node;
typedef Node node;
typedef struct __stack {
node *head;
} stack;
// struct __stack stack;
// typedef StackList stack;
stack * stackCreate(void) {
stack * s = (stack*) malloc(sizeof(stack));
// assert() : Exception과 비슷한 용도
// param이 True : pass
// param이 False : assert error
assert(s);
s->head = 0;
return s;
}
void stackDestroy(stack *s) {
node *rnode;
// struct node *next;
for(rnode = s->head ; rnode != NULL ; rnode = rnode->next) {
// next = rnode->next;
free(rnode);
}
free(s);
}
int isStackEmpty(stack s) {
return (s.head == NULL);
}
void stackPush(stack *s, int v) {
node *n;
n = (node*)malloc(sizeof(node));
assert(n);
n->next = s->head->next;
n->value = v;
s->head = n;
}
//void stackPop(stack s, int v) {
int stackPop(stack *s, int v) {
node *rnode;
int rvalue;
rnode = (node*)malloc(sizeof(node));
assert(rnode);
rnode = s->head;
rvalue = s->head->value;
s->head = rnode->next;
free(rnode);
// pop한 값 return
return rvalue;
}stackBlock.c
#include <stdlib.h>
#include <assert.h>
// #include "stack.h"
#define BLOCK_SIZE 1024
typedef struct __block {
struct __block *next;
int top;
int values[BLOCK_SIZE];
} block;
typedef struct __stack {
block *head;
} stack;
stack *stackCreate(void) {
stack *s;
s = (stack*)malloc(sizeof(stack));
assert(s);
s->head = NULL;
return s;
}
void stackDestroy(stack *s) {
block *b;
block *next;
for(b = s->head ; b != NULL ; b = b->next) {
free(b);
}
free(s);
}
int isStackEmpty(stack s) {
return (s.head == NULL);
}
void stackPush(stack *s, int v) {
block *b;
if(s->head == NULL || s->head->top == BLOCK_SIZE) {
// need a new block
b = (block*)malloc(sizeof(block));
assert(b);
b->next = s->head;
b->top = 0;
s->head = b;
}
// first block exists and is not full
s->head->values[s->head->top++] = v;
}
int stackPop(stack * s) {
block *rblock;
int rvalue;
rblock = s->head;
assert(rblock);
// rvalue = s->value[(rblock->top)--];
rvalue = s->value[--(rblock->top)];
if(b->top == 0) {
s->head = rblock->next;
free(rblock);
}
return rvalue;
}
stackArray.c
#include <stdlib.h>
#include <assert.h>
// #include "stack.h"
typedef struct __stack {
// number of spaces in values
int size;
// first unused space
int top;
// data
int *values;
} stack;
#define INITIAL_SIZE 512
// stack *stackCreate(void) {
// stack *s;
// s = (stack*)malloc(sizeof(stack));
// assert(s);
// s->size = INITIAL_SIZE;
// s->top = 0;
// s->values = (int*)malloc(sizeof(*s->values) * s->size);
// return s;
// }
void stackCreate(stack * s) {
s->size = INITIAL_SIZE;
s->top = 0;
s->values = malloc(sizeof(*s->values) * s->size);
}
void stackDestroy(stack * s) {
free(s->values);
free(s);
}
int isStackEmpty(stack s) {
return (s.top == 0);
}
void stackPush(stack *s, int v) {
if(s->top >= s->size) {
s->size *= 2;
s->values = realloc(s->values, sizeof(*s->values) * s->size);
assert(s->values);
}
s->values[(s->top)++] = v;
}
int stackPop(stack *s){
assert(s);
return (s->values[--(s->top)]);
}Ref)
cs.yale.edu/homes/aspnes/pinewiki/BTrees.html
