smalltalk-tng

annotate experiments/hashconsing/hashcons.c @ 321:c4a0718c2d3c

find changesets by author, revision, files, or words in the commit message
Sketch of dependencies
author Tony Garnock-Jones <tonygarnockjones@gmail.com>
date Sat Oct 08 15:36:03 2011 -0400 (7 months ago)
parents c8f794195b31
children
rev   line source
tonyg@109 1 #include <string.h>
tonyg@109 2 #include <stdlib.h>
tonyg@109 3 #include <stdio.h>
tonyg@109 4
tonyg@109 5 #include <assert.h>
tonyg@109 6
tonyg@109 7 #include <sys/time.h>
tonyg@109 8
tonyg@109 9 typedef struct Cons {
tonyg@109 10 struct Cons *next;
tonyg@109 11 struct Cons *car;
tonyg@109 12 struct Cons *cdr;
tonyg@109 13 } *CONS;
tonyg@109 14
tonyg@109 15 #define TAGBITS(x) (((int) (x)) & 3)
tonyg@109 16 #define DETAG(x) (((int) (x)) >> 2)
tonyg@109 17 #define ENTAG(x,t) ((CONS) (((x) << 2) | ((t) & 3)))
tonyg@109 18
tonyg@109 19 #define CONS_TAG 0
tonyg@109 20 #define INT_TAG 1
tonyg@109 21
tonyg@109 22 #define CONSP(x) (TAGBITS(x) == CONS_TAG)
tonyg@109 23 #define INTP(x) (TAGBITS(x) == INT_TAG)
tonyg@109 24
tonyg@109 25 #define ALLOC_TABLE_SIZE 1000003
tonyg@109 26
tonyg@109 27 static CONS alloc_table[ALLOC_TABLE_SIZE];
tonyg@109 28
tonyg@109 29 static struct Cons *heap;
tonyg@109 30 static CONS heap_next;
tonyg@109 31 static int heap_size;
tonyg@109 32
tonyg@109 33 typedef struct Root {
tonyg@109 34 CONS *root_pointer;
tonyg@109 35 struct Root *next;
tonyg@109 36 } *ROOT;
tonyg@109 37
tonyg@109 38 static ROOT roots = NULL;
tonyg@109 39
tonyg@109 40 static void add_root(CONS *pointer) {
tonyg@109 41 ROOT r = malloc(sizeof(struct Root));
tonyg@109 42 r->root_pointer = pointer;
tonyg@109 43 r->next = roots;
tonyg@109 44 roots = r;
tonyg@109 45 }
tonyg@109 46
tonyg@109 47 #define MARKIFY(x) (ENTAG(DETAG(x), INT_TAG))
tonyg@109 48 #define DEMARKIFY(x) (ENTAG(DETAG(x), CONS_TAG))
tonyg@109 49 #define SET_MARK(c) ((c)->next = MARKIFY((c)->next))
tonyg@109 50 #define CLEAR_MARK(c) ((c)->next = DEMARKIFY((c)->next))
tonyg@109 51 #define IS_MARKED(c) (INTP((c)->next))
tonyg@109 52
tonyg@109 53 static void sweep_alloc_table(void) {
tonyg@109 54 int i;
tonyg@109 55 for (i = 0; i < ALLOC_TABLE_SIZE; i++) {
tonyg@109 56 CONS bucket = alloc_table[i];
tonyg@109 57 CONS prev = NULL;
tonyg@109 58 while (bucket != NULL) {
tonyg@109 59 if (IS_MARKED(bucket)) {
tonyg@109 60 if (prev == NULL) {
tonyg@109 61 alloc_table[i] = bucket;
tonyg@109 62 } else {
tonyg@109 63 prev->next = MARKIFY(bucket);
tonyg@109 64 }
tonyg@109 65 prev = bucket;
tonyg@109 66 }
tonyg@109 67 bucket = DEMARKIFY(bucket->next);
tonyg@109 68 }
tonyg@109 69 if (prev == NULL) {
tonyg@109 70 alloc_table[i] = NULL;
tonyg@109 71 }
tonyg@109 72 }
tonyg@109 73 }
tonyg@109 74
tonyg@109 75 static void sweep_heap(void) {
tonyg@109 76 int i;
tonyg@109 77 heap_next = NULL;
tonyg@109 78 for (i = 0; i < heap_size; i++) {
tonyg@109 79 CONS c = &heap[i];
tonyg@109 80 if (IS_MARKED(c)) {
tonyg@109 81 CLEAR_MARK(c);
tonyg@109 82 } else {
tonyg@109 83 c->next = heap_next;
tonyg@109 84 heap_next = c;
tonyg@109 85 }
tonyg@109 86 }
tonyg@109 87 }
tonyg@109 88
tonyg@109 89 static void mark(CONS c) {
tonyg@109 90 tail_loop:
tonyg@109 91 if (CONSP(c) && !IS_MARKED(c)) {
tonyg@109 92 SET_MARK(c);
tonyg@109 93 mark(c->car);
tonyg@109 94 c = c->cdr;
tonyg@109 95 goto tail_loop;
tonyg@109 96 }
tonyg@109 97 }
tonyg@109 98
tonyg@109 99 static void init_gc(void) {
tonyg@109 100 int i;
tonyg@109 101
tonyg@109 102 for (i = 0; i < ALLOC_TABLE_SIZE; i++) {
tonyg@109 103 alloc_table[i] = NULL;
tonyg@109 104 }
tonyg@109 105
tonyg@109 106 heap_size = 2000000;
tonyg@109 107 heap = calloc(heap_size, sizeof(struct Cons));
tonyg@109 108 sweep_heap();
tonyg@109 109 }
tonyg@109 110
tonyg@109 111 static void gc(void) {
tonyg@109 112 ROOT r;
tonyg@109 113
tonyg@109 114 for (r = roots; r != NULL; r = r->next) {
tonyg@109 115 mark(*(r->root_pointer));
tonyg@109 116 }
tonyg@109 117
tonyg@109 118 sweep_alloc_table();
tonyg@109 119 sweep_heap();
tonyg@109 120 }
tonyg@109 121
tonyg@171 122 static CONS gc_alloc_pair(void) {
tonyg@171 123 gc();
tonyg@171 124 if (heap_next == NULL) {
tonyg@171 125 fprintf(stderr, "out of memory\n");
tonyg@171 126 exit(3);
tonyg@171 127 }
tonyg@171 128 {
tonyg@171 129 CONS result = heap_next;
tonyg@171 130 heap_next = heap_next->next;
tonyg@171 131 return result;
tonyg@171 132 }
tonyg@171 133 }
tonyg@171 134
tonyg@171 135 static inline CONS alloc_pair(void) {
tonyg@109 136 if (heap_next != NULL) {
tonyg@109 137 CONS result = heap_next;
tonyg@109 138 heap_next = heap_next->next;
tonyg@109 139 return result;
tonyg@109 140 } else {
tonyg@171 141 return gc_alloc_pair();
tonyg@109 142 }
tonyg@109 143 }
tonyg@109 144
tonyg@109 145 static CONS shared_cons(CONS car, CONS cdr) {
tonyg@109 146 int hash = (DETAG(car) + DETAG(cdr)) % ALLOC_TABLE_SIZE;
tonyg@109 147 CONS probe = alloc_table[hash];
tonyg@109 148 while (probe != NULL) {
tonyg@109 149 if (probe->car == car && probe->cdr == cdr) {
tonyg@109 150 return probe;
tonyg@109 151 }
tonyg@109 152 probe = probe->next;
tonyg@109 153 }
tonyg@109 154
tonyg@109 155 {
tonyg@109 156 CONS result = alloc_pair();
tonyg@109 157 result->next = alloc_table[hash];
tonyg@109 158 alloc_table[hash] = result;
tonyg@109 159 result->car = car;
tonyg@109 160 result->cdr = cdr;
tonyg@109 161 return result;
tonyg@109 162 }
tonyg@109 163 }
tonyg@109 164
tonyg@109 165 static CONS unshared_cons(CONS car, CONS cdr) {
tonyg@109 166 CONS result = alloc_pair();
tonyg@109 167 result->next = NULL;
tonyg@109 168 result->car = car;
tonyg@109 169 result->cdr = cdr;
tonyg@109 170 return result;
tonyg@109 171 }
tonyg@109 172
tonyg@109 173 #define NUM_ITERATIONS 10000000
tonyg@109 174
tonyg@109 175 int main(int argc, char *argv[]) {
tonyg@109 176 char *mode;
tonyg@109 177 struct timeval start;
tonyg@109 178 struct timeval stop;
tonyg@109 179
tonyg@109 180 if (argc < 2) {
tonyg@109 181 fprintf(stderr,
tonyg@109 182 "Usage: hashcons <mode>\n"
tonyg@109 183 " where <mode> in unshared, shared, uniform\n");
tonyg@109 184 exit(1);
tonyg@109 185 }
tonyg@109 186
tonyg@109 187 init_gc();
tonyg@109 188
tonyg@109 189 mode = argv[1];
tonyg@109 190 if (!strcmp(mode, "unshared")) {
tonyg@109 191 int i;
tonyg@109 192 CONS chain = NULL;
tonyg@109 193 gettimeofday(&start, NULL);
tonyg@109 194 for (i = 0; i < NUM_ITERATIONS; i++) {
tonyg@109 195 chain = unshared_cons(ENTAG(i, INT_TAG), NULL);
tonyg@109 196 }
tonyg@109 197 gettimeofday(&stop, NULL);
tonyg@109 198 } else if (!strcmp(mode, "shared")) {
tonyg@109 199 int i;
tonyg@109 200 CONS chain = NULL;
tonyg@109 201 gettimeofday(&start, NULL);
tonyg@109 202 for (i = 0; i < NUM_ITERATIONS; i++) {
tonyg@109 203 chain = shared_cons(ENTAG(i, INT_TAG), NULL);
tonyg@109 204 }
tonyg@109 205 gettimeofday(&stop, NULL);
tonyg@109 206 } else if (!strcmp(mode, "uniform")) {
tonyg@109 207 int i;
tonyg@109 208 CONS chain = NULL;
tonyg@109 209 gettimeofday(&start, NULL);
tonyg@109 210 for (i = 0; i < NUM_ITERATIONS; i++) {
tonyg@109 211 chain = shared_cons(ENTAG(12345, INT_TAG), NULL);
tonyg@109 212 }
tonyg@109 213 gettimeofday(&stop, NULL);
tonyg@109 214 }
tonyg@109 215
tonyg@109 216 double delta = (stop.tv_sec - start.tv_sec) + (stop.tv_usec - start.tv_usec) / 1000000.0;
tonyg@109 217 printf("Time delta: %6g seconds\n", delta);
tonyg@109 218 printf("Iterations: %d\n", NUM_ITERATIONS);
tonyg@109 219 printf("Rate: %6g Hz\n", NUM_ITERATIONS / delta);
tonyg@109 220 printf("Period: %6g microseconds\n", (delta * 1000000.0) / NUM_ITERATIONS);
tonyg@109 221 }