1 /* Simple speed tests for jmap. */
2 #include <ccan/jmap/jmap.c>
3 #include <ccan/time/time.c>
9 /* Some contents. Doubles as consistency check. */
14 JMAP_MEMBERS(unsigned int, struct object *);
17 /* Nanoseconds per operation */
18 static size_t normalize(const struct timeabs *start,
19 const struct timeabs *stop,
22 return time_to_nsec(time_divide(time_between(*stop, *start), num));
25 int main(int argc, char *argv[])
30 struct timeabs start, stop;
31 struct jmap_obj *jmap;
33 num = argv[1] ? atoi(argv[1]) : 1000000;
34 objs = calloc(num, sizeof(objs[0]));
36 for (i = 0; i < num; i++) {
37 objs[i].self = &objs[i];
40 jmap = jmap_new(struct jmap_obj);
42 printf("Initial insert: ");
45 for (i = 0; i < num; i++)
46 jmap_add(jmap, i, objs[i].self);
48 printf(" %zu ns\n", normalize(&start, &stop, num));
50 printf("Initial lookup (match): ");
53 for (i = 0; i < num; i++)
54 if (jmap_get(jmap, i)->self != objs[i].self)
57 printf(" %zu ns\n", normalize(&start, &stop, num));
59 printf("Initial lookup (miss): ");
62 for (i = 0; i < num; i++)
63 if (jmap_get(jmap, i+num))
66 printf(" %zu ns\n", normalize(&start, &stop, num));
68 /* Lookups in order are very cache-friendly for judy; try random */
69 printf("Initial lookup (random): ");
72 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
73 if (jmap_get(jmap, j)->self != &objs[j])
76 printf(" %zu ns\n", normalize(&start, &stop, num));
78 printf("Initial delete all: ");
81 for (i = 0; i < num; i++)
84 printf(" %zu ns\n", normalize(&start, &stop, num));
86 printf("Initial re-inserting: ");
89 for (i = 0; i < num; i++)
90 jmap_add(jmap, i, objs[i].self);
92 printf(" %zu ns\n", normalize(&start, &stop, num));
94 printf("Deleting first half: ");
97 for (i = 0; i < num; i+=2)
100 printf(" %zu ns\n", normalize(&start, &stop, num));
102 printf("Adding (a different) half: ");
106 for (i = 0; i < num; i+=2)
107 jmap_add(jmap, num+i, objs[i].self);
109 printf(" %zu ns\n", normalize(&start, &stop, num));
111 printf("Lookup after half-change (match): ");
114 for (i = 1; i < num; i+=2)
115 if (jmap_get(jmap, i)->self != objs[i].self)
117 for (i = 0; i < num; i+=2)
118 if (jmap_get(jmap, i+num)->self != objs[i].self)
121 printf(" %zu ns\n", normalize(&start, &stop, num));
123 printf("Lookup after half-change(miss): ");
126 for (i = 0; i < num; i++)
127 if (jmap_get(jmap, i+num*2))
130 printf(" %zu ns\n", normalize(&start, &stop, num));
132 /* Hashtables with delete markers can fill with markers over time.
133 * so do some changes to see how it operates in long-term. */
134 printf("Details: churning first time\n");
135 for (i = 1; i < num; i+=2) {
136 if (!jmap_del(jmap, i))
138 jmap_add(jmap, i, objs[i].self);
140 for (i = 0; i < num; i+=2) {
141 if (!jmap_del(jmap, i+num))
143 jmap_add(jmap, i, objs[i].self);
145 for (i = 1; i < 5; i++) {
146 printf("Churning %s time: ",
154 for (j = 0; j < num; j++) {
155 if (!jmap_del(jmap, num*(i-1)+j))
157 jmap_add(jmap, num*i+j, &objs[j]);
160 printf(" %zu ns\n", normalize(&start, &stop, num));
163 /* Spread out the keys more to try to make it harder. */
164 printf("Details: reinserting with spread\n");
165 for (i = 0; i < num; i++) {
166 if (!jmap_del(jmap, num*4 + i))
168 jmap_add(jmap, num * 5 + i * 9, objs[i].self);
171 if (jmap_popcount(jmap, 0, -1) != num)
174 printf("Lookup after churn & spread (match): ");
177 for (i = 0; i < num; i++)
178 if (jmap_get(jmap, num * 5 + i * 9)->self != objs[i].self) {
179 printf("i =%u\n", i);
183 printf(" %zu ns\n", normalize(&start, &stop, num));
185 printf("Lookup after churn & spread (miss): ");
188 for (i = 0; i < num; i++)
189 if (jmap_get(jmap, num * 6 + i * 9))
192 printf(" %zu ns\n", normalize(&start, &stop, num));
194 printf("Lookup after churn & spread (random): ");
197 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
198 if (jmap_get(jmap, num * 5 + j * 9)->self != &objs[j])
201 printf(" %zu ns\n", normalize(&start, &stop, num));
203 printf("Lookup after churn & spread (half-random): ");
206 for (i = 0, j = 0; i < num/2; i++, j = (j + 10007) % num) {
207 if (jmap_get(jmap, num * 5 + j * 9)->self != &objs[j])
209 if (jmap_get(jmap, num * 5 + (j + 1) * 9)->self != &objs[j+1])
213 printf(" %zu ns\n", normalize(&start, &stop, num));
215 printf("Deleting half after churn & spread: ");
218 for (i = 0; i < num; i+=2)
219 jmap_del(jmap, num * 5 + i * 9);
221 printf(" %zu ns\n", normalize(&start, &stop, num));
223 printf("Adding (a different) half after churn & spread: ");
227 for (i = 0; i < num; i+=2)
228 jmap_add(jmap, num * 6 + i * 9, objs[i].self);
230 printf(" %zu ns\n", normalize(&start, &stop, num));