1 /* Simple speed tests for hashtables. */
2 #include <ccan/htable/htable_type.h>
3 #include <ccan/htable/htable.c>
4 #include <ccan/hash/hash.h>
12 static size_t hashcount;
17 /* Some contents. Doubles as consistency check. */
21 static const unsigned int *objkey(const struct object *obj)
26 static size_t hash_obj(const unsigned int *key)
29 return hashl(key, 1, 0);
32 static bool cmp(const struct object *object, const unsigned int *key)
34 return object->key == *key;
37 HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, htable_obj);
39 static unsigned int popcount(unsigned long val)
41 #if HAVE_BUILTIN_POPCOUNTL
42 return __builtin_popcountl(val);
44 if (sizeof(long) == sizeof(u64)) {
46 v = (v & 0x5555555555555555ULL)
47 + ((v >> 1) & 0x5555555555555555ULL);
48 v = (v & 0x3333333333333333ULL)
49 + ((v >> 1) & 0x3333333333333333ULL);
50 v = (v & 0x0F0F0F0F0F0F0F0FULL)
51 + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL);
52 v = (v & 0x00FF00FF00FF00FFULL)
53 + ((v >> 1) & 0x00FF00FF00FF00FFULL);
54 v = (v & 0x0000FFFF0000FFFFULL)
55 + ((v >> 1) & 0x0000FFFF0000FFFFULL);
56 v = (v & 0x00000000FFFFFFFFULL)
57 + ((v >> 1) & 0x00000000FFFFFFFFULL);
60 val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL);
61 val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL);
62 val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL);
63 val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL);
64 val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL);
69 static size_t perfect(const struct htable *ht)
71 size_t i, placed_perfect = 0;
73 for (i = 0; i < ((size_t)1 << ht->bits); i++) {
74 if (!entry_is_valid(ht->table[i]))
76 if (hash_bucket(ht, ht->rehash(get_raw_ptr(ht, ht->table[i]),
78 assert((ht->table[i] & ht->perfect_bit)
83 return placed_perfect;
86 static size_t count_deleted(const struct htable *ht)
88 size_t i, delete_markers = 0;
90 for (i = 0; i < ((size_t)1 << ht->bits); i++) {
91 if (ht->table[i] == HTABLE_DELETED)
94 return delete_markers;
97 /* Nanoseconds per operation */
98 static size_t normalize(const struct timeval *start,
99 const struct timeval *stop,
104 timersub(stop, start, &diff);
106 /* Floating point is more accurate here. */
107 return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
111 static size_t worst_run(struct htable *ht, size_t *deleted)
113 size_t longest = 0, len = 0, this_del = 0, i;
116 /* This doesn't take into account end-wrap, but gives an idea. */
117 for (i = 0; i < ((size_t)1 << ht->bits); i++) {
120 if (ht->table[i] == HTABLE_DELETED)
134 int main(int argc, char *argv[])
137 size_t i, j, num, deleted;
138 struct timeval start, stop;
139 struct htable_obj ht;
140 bool make_dumb = false;
142 if (argv[1] && strcmp(argv[1], "--dumb") == 0) {
146 num = argv[1] ? atoi(argv[1]) : 1000000;
147 objs = calloc(num, sizeof(objs[0]));
149 for (i = 0; i < num; i++) {
151 objs[i].self = &objs[i];
154 htable_obj_init(&ht);
156 printf("Initial insert: ");
158 gettimeofday(&start, NULL);
159 for (i = 0; i < num; i++)
160 htable_obj_add(&ht, objs[i].self);
161 gettimeofday(&stop, NULL);
162 printf(" %zu ns\n", normalize(&start, &stop, num));
163 printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
164 1U << ht.raw.bits, popcount(ht.raw.common_mask),
165 perfect(&ht.raw) * 100.0 / ht.raw.elems);
168 /* Screw with mask, to hobble us. */
169 update_common(&ht.raw, (void *)~ht.raw.common_bits);
170 printf("Details: DUMB MODE: mask bits %u\n",
171 popcount(ht.raw.common_mask));
174 printf("Initial lookup (match): ");
176 gettimeofday(&start, NULL);
177 for (i = 0; i < num; i++)
178 if (htable_obj_get(&ht, &i)->self != objs[i].self)
180 gettimeofday(&stop, NULL);
181 printf(" %zu ns\n", normalize(&start, &stop, num));
183 printf("Initial lookup (miss): ");
185 gettimeofday(&start, NULL);
186 for (i = 0; i < num; i++) {
187 unsigned int n = i + num;
188 if (htable_obj_get(&ht, &n))
191 gettimeofday(&stop, NULL);
192 printf(" %zu ns\n", normalize(&start, &stop, num));
194 /* Lookups in order are very cache-friendly for judy; try random */
195 printf("Initial lookup (random): ");
197 gettimeofday(&start, NULL);
198 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
199 if (htable_obj_get(&ht, &j)->self != &objs[j])
201 gettimeofday(&stop, NULL);
202 printf(" %zu ns\n", normalize(&start, &stop, num));
205 printf("Initial delete all: ");
207 gettimeofday(&start, NULL);
208 for (i = 0; i < num; i++)
209 if (!htable_obj_del(&ht, objs[i].self))
211 gettimeofday(&stop, NULL);
212 printf(" %zu ns\n", normalize(&start, &stop, num));
213 printf("Details: rehashes %zu\n", hashcount);
215 printf("Initial re-inserting: ");
217 gettimeofday(&start, NULL);
218 for (i = 0; i < num; i++)
219 htable_obj_add(&ht, objs[i].self);
220 gettimeofday(&stop, NULL);
221 printf(" %zu ns\n", normalize(&start, &stop, num));
224 printf("Deleting first half: ");
226 gettimeofday(&start, NULL);
227 for (i = 0; i < num; i+=2)
228 if (!htable_obj_del(&ht, objs[i].self))
230 gettimeofday(&stop, NULL);
231 printf(" %zu ns\n", normalize(&start, &stop, num));
233 printf("Details: rehashes %zu, delete markers %zu\n",
234 hashcount, count_deleted(&ht.raw));
236 printf("Adding (a different) half: ");
239 for (i = 0; i < num; i+=2)
242 gettimeofday(&start, NULL);
243 for (i = 0; i < num; i+=2)
244 htable_obj_add(&ht, objs[i].self);
245 gettimeofday(&stop, NULL);
246 printf(" %zu ns\n", normalize(&start, &stop, num));
248 printf("Details: delete markers %zu, perfect %.0f%%\n",
249 count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
251 printf("Lookup after half-change (match): ");
253 gettimeofday(&start, NULL);
254 for (i = 1; i < num; i+=2)
255 if (htable_obj_get(&ht, &i)->self != objs[i].self)
257 for (i = 0; i < num; i+=2) {
258 unsigned int n = i + num;
259 if (htable_obj_get(&ht, &n)->self != objs[i].self)
262 gettimeofday(&stop, NULL);
263 printf(" %zu ns\n", normalize(&start, &stop, num));
265 printf("Lookup after half-change (miss): ");
267 gettimeofday(&start, NULL);
268 for (i = 0; i < num; i++) {
269 unsigned int n = i + num * 2;
270 if (htable_obj_get(&ht, &n))
273 gettimeofday(&stop, NULL);
274 printf(" %zu ns\n", normalize(&start, &stop, num));
276 /* Hashtables with delete markers can fill with markers over time.
277 * so do some changes to see how it operates in long-term. */
278 for (i = 0; i < 5; i++) {
280 /* We don't measure this: jmap is different. */
281 printf("Details: initial churn\n");
283 printf("Churning %s time: ",
290 gettimeofday(&start, NULL);
291 for (j = 0; j < num; j++) {
292 if (!htable_obj_del(&ht, &objs[j]))
294 objs[j].key = num*i+j;
295 if (!htable_obj_add(&ht, &objs[j]))
298 gettimeofday(&stop, NULL);
300 printf(" %zu ns\n", normalize(&start, &stop, num));
303 /* Spread out the keys more to try to make it harder. */
304 printf("Details: reinserting with spread\n");
305 for (i = 0; i < num; i++) {
306 if (!htable_obj_del(&ht, objs[i].self))
308 objs[i].key = num * 5 + i * 9;
309 if (!htable_obj_add(&ht, objs[i].self))
312 printf("Details: delete markers %zu, perfect %.0f%%\n",
313 count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
314 i = worst_run(&ht.raw, &deleted);
315 printf("Details: worst run %zu (%zu deleted)\n", i, deleted);
317 printf("Lookup after churn & spread (match): ");
319 gettimeofday(&start, NULL);
320 for (i = 0; i < num; i++) {
321 unsigned int n = num * 5 + i * 9;
322 if (htable_obj_get(&ht, &n)->self != objs[i].self)
325 gettimeofday(&stop, NULL);
326 printf(" %zu ns\n", normalize(&start, &stop, num));
328 printf("Lookup after churn & spread (miss): ");
330 gettimeofday(&start, NULL);
331 for (i = 0; i < num; i++) {
332 unsigned int n = num * (5 + 9) + i * 9;
333 if (htable_obj_get(&ht, &n))
336 gettimeofday(&stop, NULL);
337 printf(" %zu ns\n", normalize(&start, &stop, num));
339 printf("Lookup after churn & spread (random): ");
341 gettimeofday(&start, NULL);
342 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
343 unsigned int n = num * 5 + j * 9;
344 if (htable_obj_get(&ht, &n)->self != &objs[j])
347 gettimeofday(&stop, NULL);
348 printf(" %zu ns\n", normalize(&start, &stop, num));
351 printf("Deleting half after churn & spread: ");
353 gettimeofday(&start, NULL);
354 for (i = 0; i < num; i+=2)
355 if (!htable_obj_del(&ht, objs[i].self))
357 gettimeofday(&stop, NULL);
358 printf(" %zu ns\n", normalize(&start, &stop, num));
360 printf("Adding (a different) half after churn & spread: ");
363 for (i = 0; i < num; i+=2)
364 objs[i].key = num*6+i*9;
366 gettimeofday(&start, NULL);
367 for (i = 0; i < num; i+=2)
368 htable_obj_add(&ht, objs[i].self);
369 gettimeofday(&stop, NULL);
370 printf(" %zu ns\n", normalize(&start, &stop, num));
372 printf("Details: delete markers %zu, perfect %.0f%%\n",
373 count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);