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