smalltalk-tng

view experiments/hashconsing/hashcons.c @ 323:454c18798969

find changesets by author, revision, files, or words in the commit message
merger
author Tony Garnock-Jones <tonygarnockjones@gmail.com>
date Tue Feb 07 11:34:20 2012 -0500 (3 months ago)
parents c8f794195b31
children
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 gc_alloc_pair(void) {
123 gc();
124 if (heap_next == NULL) {
125 fprintf(stderr, "out of memory\n");
126 exit(3);
127 }
128 {
129 CONS result = heap_next;
130 heap_next = heap_next->next;
131 return result;
132 }
133 }
134
135 static inline CONS alloc_pair(void) {
136 if (heap_next != NULL) {
137 CONS result = heap_next;
138 heap_next = heap_next->next;
139 return result;
140 } else {
141 return gc_alloc_pair();
142 }
143 }
144
145 static CONS shared_cons(CONS car, CONS cdr) {
146 int hash = (DETAG(car) + DETAG(cdr)) % ALLOC_TABLE_SIZE;
147 CONS probe = alloc_table[hash];
148 while (probe != NULL) {
149 if (probe->car == car && probe->cdr == cdr) {
150 return probe;
151 }
152 probe = probe->next;
153 }
154
155 {
156 CONS result = alloc_pair();
157 result->next = alloc_table[hash];
158 alloc_table[hash] = result;
159 result->car = car;
160 result->cdr = cdr;
161 return result;
162 }
163 }
164
165 static CONS unshared_cons(CONS car, CONS cdr) {
166 CONS result = alloc_pair();
167 result->next = NULL;
168 result->car = car;
169 result->cdr = cdr;
170 return result;
171 }
172
173 #define NUM_ITERATIONS 10000000
174
175 int main(int argc, char *argv[]) {
176 char *mode;
177 struct timeval start;
178 struct timeval stop;
179
180 if (argc < 2) {
181 fprintf(stderr,
182 "Usage: hashcons <mode>\n"
183 " where <mode> in unshared, shared, uniform\n");
184 exit(1);
185 }
186
187 init_gc();
188
189 mode = argv[1];
190 if (!strcmp(mode, "unshared")) {
191 int i;
192 CONS chain = NULL;
193 gettimeofday(&start, NULL);
194 for (i = 0; i < NUM_ITERATIONS; i++) {
195 chain = unshared_cons(ENTAG(i, INT_TAG), NULL);
196 }
197 gettimeofday(&stop, NULL);
198 } else if (!strcmp(mode, "shared")) {
199 int i;
200 CONS chain = NULL;
201 gettimeofday(&start, NULL);
202 for (i = 0; i < NUM_ITERATIONS; i++) {
203 chain = shared_cons(ENTAG(i, INT_TAG), NULL);
204 }
205 gettimeofday(&stop, NULL);
206 } else if (!strcmp(mode, "uniform")) {
207 int i;
208 CONS chain = NULL;
209 gettimeofday(&start, NULL);
210 for (i = 0; i < NUM_ITERATIONS; i++) {
211 chain = shared_cons(ENTAG(12345, INT_TAG), NULL);
212 }
213 gettimeofday(&stop, NULL);
214 }
215
216 double delta = (stop.tv_sec - start.tv_sec) + (stop.tv_usec - start.tv_usec) / 1000000.0;
217 printf("Time delta: %6g seconds\n", delta);
218 printf("Iterations: %d\n", NUM_ITERATIONS);
219 printf("Rate: %6g Hz\n", NUM_ITERATIONS / delta);
220 printf("Period: %6g microseconds\n", (delta * 1000000.0) / NUM_ITERATIONS);
221 }