smalltalk-tng

view experiments/hashconsing/hashcons.c @ 109:c8f794195b31

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