1 /* Simple speed tests for jmap. */
2 #include <ccan/jmap/jmap_type.h>
3 #include <ccan/jmap/jmap.c>
11 /* Some contents. Doubles as consistency check. */
15 /* Nanoseconds per operation */
16 static size_t normalize(const struct timeval *start,
17 const struct timeval *stop,
22 timersub(stop, start, &diff);
24 /* Floating point is more accurate here. */
25 return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
29 JMAP_DEFINE_UINTIDX_TYPE(struct object, obj);
31 int main(int argc, char *argv[])
35 struct timeval start, stop;
36 struct jmap_obj *jmap;
38 num = argv[1] ? atoi(argv[1]) : 1000000;
39 objs = calloc(num, sizeof(objs[0]));
41 for (i = 0; i < num; i++) {
42 objs[i].self = &objs[i];
45 jmap = jmap_obj_new();
47 printf("Initial insert: ");
49 gettimeofday(&start, NULL);
50 for (i = 0; i < num; i++)
51 jmap_obj_add(jmap, i, objs[i].self);
52 gettimeofday(&stop, NULL);
53 printf(" %zu ns\n", normalize(&start, &stop, num));
55 printf("Initial lookup (match): ");
57 gettimeofday(&start, NULL);
58 for (i = 0; i < num; i++)
59 if (jmap_obj_get(jmap, i)->self != objs[i].self)
61 gettimeofday(&stop, NULL);
62 printf(" %zu ns\n", normalize(&start, &stop, num));
64 printf("Initial lookup (miss): ");
66 gettimeofday(&start, NULL);
67 for (i = 0; i < num; i++)
68 if (jmap_obj_get(jmap, i+num))
70 gettimeofday(&stop, NULL);
71 printf(" %zu ns\n", normalize(&start, &stop, num));
73 /* Lookups in order are very cache-friendly for judy; try random */
74 printf("Initial lookup (random): ");
76 gettimeofday(&start, NULL);
77 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
78 if (jmap_obj_get(jmap, j)->self != &objs[j])
80 gettimeofday(&stop, NULL);
81 printf(" %zu ns\n", normalize(&start, &stop, num));
83 printf("Initial delete all: ");
85 gettimeofday(&start, NULL);
86 for (i = 0; i < num; i++)
87 jmap_obj_del(jmap, i);
88 gettimeofday(&stop, NULL);
89 printf(" %zu ns\n", normalize(&start, &stop, num));
91 printf("Initial re-inserting: ");
93 gettimeofday(&start, NULL);
94 for (i = 0; i < num; i++)
95 jmap_obj_add(jmap, i, objs[i].self);
96 gettimeofday(&stop, NULL);
97 printf(" %zu ns\n", normalize(&start, &stop, num));
99 printf("Deleting first half: ");
101 gettimeofday(&start, NULL);
102 for (i = 0; i < num; i+=2)
103 jmap_obj_del(jmap, i);
104 gettimeofday(&stop, NULL);
105 printf(" %zu ns\n", normalize(&start, &stop, num));
107 printf("Adding (a different) half: ");
110 gettimeofday(&start, NULL);
111 for (i = 0; i < num; i+=2)
112 jmap_obj_add(jmap, num+i, objs[i].self);
113 gettimeofday(&stop, NULL);
114 printf(" %zu ns\n", normalize(&start, &stop, num));
116 printf("Lookup after half-change (match): ");
118 gettimeofday(&start, NULL);
119 for (i = 1; i < num; i+=2)
120 if (jmap_obj_get(jmap, i)->self != objs[i].self)
122 for (i = 0; i < num; i+=2)
123 if (jmap_obj_get(jmap, i+num)->self != objs[i].self)
125 gettimeofday(&stop, NULL);
126 printf(" %zu ns\n", normalize(&start, &stop, num));
128 printf("Lookup after half-change(miss): ");
130 gettimeofday(&start, NULL);
131 for (i = 0; i < num; i++)
132 if (jmap_obj_get(jmap, i+num*2))
134 gettimeofday(&stop, NULL);
135 printf(" %zu ns\n", normalize(&start, &stop, num));
137 /* Hashtables with delete markers can fill with markers over time.
138 * so do some changes to see how it operates in long-term. */
139 printf("Details: churning first time\n");
140 for (i = 1; i < num; i+=2) {
141 if (!jmap_obj_del(jmap, i))
143 jmap_obj_add(jmap, i, objs[i].self);
145 for (i = 0; i < num; i+=2) {
146 if (!jmap_obj_del(jmap, i+num))
148 jmap_obj_add(jmap, i, objs[i].self);
150 for (i = 1; i < 5; i++) {
151 printf("Churning %s time: ",
157 gettimeofday(&start, NULL);
158 for (j = 0; j < num; j++) {
159 if (!jmap_obj_del(jmap, num*(i-1)+j))
161 jmap_obj_add(jmap, num*i+j, &objs[j]);
163 gettimeofday(&stop, NULL);
164 printf(" %zu ns\n", normalize(&start, &stop, num));
167 /* Spread out the keys more to try to make it harder. */
168 printf("Details: reinserting with spread\n");
169 for (i = 0; i < num; i++) {
170 if (!jmap_obj_del(jmap, num*4 + i))
172 jmap_obj_add(jmap, num * 5 + i * 9, objs[i].self);
175 if (jmap_obj_popcount(jmap, 0, -1) != num)
178 printf("Lookup after churn & spread (match): ");
180 gettimeofday(&start, NULL);
181 for (i = 0; i < num; i++)
182 if (jmap_obj_get(jmap, num * 5 + i * 9)->self != objs[i].self) {
183 printf("i =%u\n", i);
186 gettimeofday(&stop, NULL);
187 printf(" %zu ns\n", normalize(&start, &stop, num));
189 printf("Lookup after churn & spread (miss): ");
191 gettimeofday(&start, NULL);
192 for (i = 0; i < num; i++)
193 if (jmap_obj_get(jmap, num * 6 + i * 9))
195 gettimeofday(&stop, NULL);
196 printf(" %zu ns\n", normalize(&start, &stop, num));
198 printf("Lookup after churn & spread (random): ");
200 gettimeofday(&start, NULL);
201 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
202 if (jmap_obj_get(jmap, num * 5 + j * 9)->self != &objs[j])
204 gettimeofday(&stop, NULL);
205 printf(" %zu ns\n", normalize(&start, &stop, num));
207 printf("Lookup after churn & spread (half-random): ");
209 gettimeofday(&start, NULL);
210 for (i = 0, j = 0; i < num/2; i++, j = (j + 10007) % num) {
211 if (jmap_obj_get(jmap, num * 5 + j * 9)->self != &objs[j])
213 if (jmap_obj_get(jmap, num * 5 + (j + 1) * 9)->self != &objs[j+1])
216 gettimeofday(&stop, NULL);
217 printf(" %zu ns\n", normalize(&start, &stop, num));
219 printf("Deleting half after churn & spread: ");
221 gettimeofday(&start, NULL);
222 for (i = 0; i < num; i+=2)
223 jmap_obj_del(jmap, num * 5 + i * 9);
224 gettimeofday(&stop, NULL);
225 printf(" %zu ns\n", normalize(&start, &stop, num));
227 printf("Adding (a different) half after churn & spread: ");
230 gettimeofday(&start, NULL);
231 for (i = 0; i < num; i+=2)
232 jmap_obj_add(jmap, num * 6 + i * 9, objs[i].self);
233 gettimeofday(&stop, NULL);
234 printf(" %zu ns\n", normalize(&start, &stop, num));