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>
11 static size_t hashcount;
16 /* Some contents. Doubles as consistency check. */
20 static const unsigned int *objkey(const struct object *obj)
25 static size_t hash_obj(const unsigned int *key)
28 return hashl(key, 1, 0);
31 static bool cmp(const unsigned int *key1, const unsigned int *key2)
33 return *key1 == *key2;
36 HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, obj);
38 static unsigned int popcount(unsigned long val)
40 #if HAVE_BUILTIN_POPCOUNTL
41 return __builtin_popcountl(val);
43 if (sizeof(long) == sizeof(u64)) {
45 v = (v & 0x5555555555555555ULL)
46 + ((v >> 1) & 0x5555555555555555ULL);
47 v = (v & 0x3333333333333333ULL)
48 + ((v >> 1) & 0x3333333333333333ULL);
49 v = (v & 0x0F0F0F0F0F0F0F0FULL)
50 + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL);
51 v = (v & 0x00FF00FF00FF00FFULL)
52 + ((v >> 1) & 0x00FF00FF00FF00FFULL);
53 v = (v & 0x0000FFFF0000FFFFULL)
54 + ((v >> 1) & 0x0000FFFF0000FFFFULL);
55 v = (v & 0x00000000FFFFFFFFULL)
56 + ((v >> 1) & 0x00000000FFFFFFFFULL);
59 val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL);
60 val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL);
61 val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL);
62 val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL);
63 val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL);
68 static size_t perfect(const struct htable *ht)
70 size_t i, placed_perfect = 0;
72 for (i = 0; i < ((size_t)1 << ht->bits); i++) {
73 if (!entry_is_valid(ht->table[i]))
75 if (hash_bucket(ht, ht->rehash(get_raw_ptr(ht, ht->table[i]),
77 assert((ht->table[i] & ht->perfect_bit)
82 return placed_perfect;
85 static size_t count_deleted(const struct htable *ht)
87 size_t i, delete_markers = 0;
89 for (i = 0; i < ((size_t)1 << ht->bits); i++) {
90 if (ht->table[i] == HTABLE_DELETED)
93 return delete_markers;
96 /* Nanoseconds per operation */
97 static size_t normalize(const struct timeval *start,
98 const struct timeval *stop,
103 timersub(stop, start, &diff);
105 /* Floating point is more accurate here. */
106 return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
110 static size_t worst_run(struct htable *ht, size_t *deleted)
112 size_t longest = 0, len = 0, this_del = 0, i;
115 /* This doesn't take into account end-wrap, but gives an idea. */
116 for (i = 0; i < ((size_t)1 << ht->bits); i++) {
119 if (ht->table[i] == HTABLE_DELETED)
133 int main(int argc, char *argv[])
136 size_t i, j, num, deleted;
137 struct timeval start, stop;
138 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 ht = htable_obj_new();
157 printf("Initial insert: ");
159 gettimeofday(&start, NULL);
160 for (i = 0; i < num; i++)
161 htable_obj_add(ht, objs[i].self);
162 gettimeofday(&stop, NULL);
163 printf(" %zu ns\n", normalize(&start, &stop, num));
164 printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
165 1U << htr->bits, popcount(htr->common_mask),
166 perfect(htr) * 100.0 / htr->elems);
169 /* Screw with mask, to hobble us. */
170 update_common(htr, (void *)~htr->common_bits);
171 printf("Details: DUMB MODE: mask bits %u\n",
172 popcount(htr->common_mask));
175 printf("Initial lookup (match): ");
177 gettimeofday(&start, NULL);
178 for (i = 0; i < num; i++)
179 if (htable_obj_get(ht, &i)->self != objs[i].self)
181 gettimeofday(&stop, NULL);
182 printf(" %zu ns\n", normalize(&start, &stop, num));
184 printf("Initial lookup (miss): ");
186 gettimeofday(&start, NULL);
187 for (i = 0; i < num; i++) {
188 unsigned int n = i + num;
189 if (htable_obj_get(ht, &n))
192 gettimeofday(&stop, NULL);
193 printf(" %zu ns\n", normalize(&start, &stop, num));
195 /* Lookups in order are very cache-friendly for judy; try random */
196 printf("Initial lookup (random): ");
198 gettimeofday(&start, NULL);
199 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
200 if (htable_obj_get(ht, &j)->self != &objs[j])
202 gettimeofday(&stop, NULL);
203 printf(" %zu ns\n", normalize(&start, &stop, num));
206 printf("Initial delete all: ");
208 gettimeofday(&start, NULL);
209 for (i = 0; i < num; i++)
210 if (!htable_obj_del(ht, objs[i].self))
212 gettimeofday(&stop, NULL);
213 printf(" %zu ns\n", normalize(&start, &stop, num));
214 printf("Details: rehashes %zu\n", hashcount);
216 printf("Initial re-inserting: ");
218 gettimeofday(&start, NULL);
219 for (i = 0; i < num; i++)
220 htable_obj_add(ht, objs[i].self);
221 gettimeofday(&stop, NULL);
222 printf(" %zu ns\n", normalize(&start, &stop, num));
225 printf("Deleting first half: ");
227 gettimeofday(&start, NULL);
228 for (i = 0; i < num; i+=2)
229 if (!htable_obj_del(ht, objs[i].self))
231 gettimeofday(&stop, NULL);
232 printf(" %zu ns\n", normalize(&start, &stop, num));
234 printf("Details: rehashes %zu, delete markers %zu\n",
235 hashcount, count_deleted(htr));
237 printf("Adding (a different) half: ");
240 for (i = 0; i < num; i+=2)
243 gettimeofday(&start, NULL);
244 for (i = 0; i < num; i+=2)
245 htable_obj_add(ht, objs[i].self);
246 gettimeofday(&stop, NULL);
247 printf(" %zu ns\n", normalize(&start, &stop, num));
249 printf("Details: delete markers %zu, perfect %.0f%%\n",
250 count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
252 printf("Lookup after half-change (match): ");
254 gettimeofday(&start, NULL);
255 for (i = 1; i < num; i+=2)
256 if (htable_obj_get(ht, &i)->self != objs[i].self)
258 for (i = 0; i < num; i+=2) {
259 unsigned int n = i + num;
260 if (htable_obj_get(ht, &n)->self != objs[i].self)
263 gettimeofday(&stop, NULL);
264 printf(" %zu ns\n", normalize(&start, &stop, num));
266 printf("Lookup after half-change (miss): ");
268 gettimeofday(&start, NULL);
269 for (i = 0; i < num; i++) {
270 unsigned int n = i + num * 2;
271 if (htable_obj_get(ht, &n))
274 gettimeofday(&stop, NULL);
275 printf(" %zu ns\n", normalize(&start, &stop, num));
277 /* Hashtables with delete markers can fill with markers over time.
278 * so do some changes to see how it operates in long-term. */
279 for (i = 0; i < 5; i++) {
281 /* We don't measure this: jmap is different. */
282 printf("Details: initial churn\n");
284 printf("Churning %s time: ",
291 gettimeofday(&start, NULL);
292 for (j = 0; j < num; j++) {
293 if (!htable_obj_del(ht, &objs[j]))
295 objs[j].key = num*i+j;
296 if (!htable_obj_add(ht, &objs[j]))
299 gettimeofday(&stop, NULL);
301 printf(" %zu ns\n", normalize(&start, &stop, num));
304 /* Spread out the keys more to try to make it harder. */
305 printf("Details: reinserting with spread\n");
306 for (i = 0; i < num; i++) {
307 if (!htable_obj_del(ht, objs[i].self))
309 objs[i].key = num * 5 + i * 9;
310 if (!htable_obj_add(ht, objs[i].self))
313 printf("Details: delete markers %zu, perfect %.0f%%\n",
314 count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
315 i = worst_run(htr, &deleted);
316 printf("Details: worst run %zu (%zu deleted)\n", i, deleted);
318 printf("Lookup after churn & spread (match): ");
320 gettimeofday(&start, NULL);
321 for (i = 0; i < num; i++) {
322 unsigned int n = num * 5 + i * 9;
323 if (htable_obj_get(ht, &n)->self != objs[i].self)
326 gettimeofday(&stop, NULL);
327 printf(" %zu ns\n", normalize(&start, &stop, num));
329 printf("Lookup after churn & spread (miss): ");
331 gettimeofday(&start, NULL);
332 for (i = 0; i < num; i++) {
333 unsigned int n = num * (5 + 9) + i * 9;
334 if (htable_obj_get(ht, &n))
337 gettimeofday(&stop, NULL);
338 printf(" %zu ns\n", normalize(&start, &stop, num));
340 printf("Lookup after churn & spread (random): ");
342 gettimeofday(&start, NULL);
343 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
344 unsigned int n = num * 5 + j * 9;
345 if (htable_obj_get(ht, &n)->self != &objs[j])
348 gettimeofday(&stop, NULL);
349 printf(" %zu ns\n", normalize(&start, &stop, num));
352 printf("Deleting half after churn & spread: ");
354 gettimeofday(&start, NULL);
355 for (i = 0; i < num; i+=2)
356 if (!htable_obj_del(ht, objs[i].self))
358 gettimeofday(&stop, NULL);
359 printf(" %zu ns\n", normalize(&start, &stop, num));
361 printf("Adding (a different) half after churn & spread: ");
364 for (i = 0; i < num; i+=2)
365 objs[i].key = num*6+i*9;
367 gettimeofday(&start, NULL);
368 for (i = 0; i < num; i+=2)
369 htable_obj_add(ht, objs[i].self);
370 gettimeofday(&stop, NULL);
371 printf(" %zu ns\n", normalize(&start, &stop, num));
373 printf("Details: delete markers %zu, perfect %.0f%%\n",
374 count_deleted(htr), perfect(htr) * 100.0 / htr->elems);