git.ozlabs.org Git - ccan/blob - ccan/htable/tools/speed.c

   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>
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <time.h>
   8 #include <unistd.h>
   9 #include <sys/time.h>
  10
  11 static size_t hashcount;
  12 struct object {
  13         /* The key. */
  14         unsigned int key;
  15
  16         /* Some contents. Doubles as consistency check. */
  17         struct object *self;
  18 };
  19
  20 static const unsigned int *objkey(const struct object *obj)
  21 {
  22         return &obj->key;
  23 }
  24
  25 static size_t hash_obj(const unsigned int *key)
  26 {
  27         hashcount++;
  28         return hashl(key, 1, 0);
  29 }
  30
  31 static bool cmp(const unsigned int *key1, const unsigned int *key2)
  32 {
  33         return *key1 == *key2;
  34 }
  35
  36 HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, obj);
  37
  38 static unsigned int popcount(unsigned long val)
  39 {
  40 #if HAVE_BUILTIN_POPCOUNTL
  41         return __builtin_popcountl(val);
  42 #else
  43         if (sizeof(long) == sizeof(u64)) {
  44                 u64 v = val;
  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);
  57                 return v;
  58         }
  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);
  64         return val;
  65 #endif
  66 }
  67
  68 static size_t perfect(const struct htable *ht)
  69 {
  70         size_t i, placed_perfect = 0;
  71
  72         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
  73                 if (!entry_is_valid(ht->table[i]))
  74                         continue;
  75                 if (hash_bucket(ht, ht->rehash(get_raw_ptr(ht, ht->table[i]),
  76                                                ht->priv)) == i)
  77                         placed_perfect++;
  78         }
  79         return placed_perfect;
  80 }
  81
  82 static size_t count_deleted(const struct htable *ht)
  83 {
  84         size_t i, delete_markers = 0;
  85
  86         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
  87                 if (ht->table[i] == HTABLE_DELETED)
  88                         delete_markers++;
  89         }
  90         return delete_markers;
  91 }
  92
  93 /* Nanoseconds per operation */
  94 static size_t normalize(const struct timeval *start,
  95                         const struct timeval *stop,
  96                         unsigned int num)
  97 {
  98         struct timeval diff;
  99
 100         timersub(stop, start, &diff);
 101
 102         /* Floating point is more accurate here. */
 103         return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
 104                 / num * 1000;
 105 }
 106
 107 static size_t worst_run(struct htable *ht, size_t *deleted)
 108 {
 109         size_t longest = 0, len = 0, this_del = 0, i;
 110
 111         *deleted = 0;
 112         /* This doesn't take into account end-wrap, but gives an idea. */
 113         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
 114                 if (ht->table[i]) {
 115                         len++;
 116                         if (ht->table[i] == HTABLE_DELETED)
 117                                 this_del++;
 118                 } else {
 119                         if (len > longest) {
 120                                 longest = len;
 121                                 *deleted = this_del;
 122                         }
 123                         len = 0;
 124                         this_del = 0;
 125                 }
 126         }
 127         return longest;
 128 }
 129
 130 int main(int argc, char *argv[])
 131 {
 132         struct object *objs;
 133         size_t i, j, num, deleted;
 134         struct timeval start, stop;
 135         struct htable_obj *ht;
 136         struct htable *htr;
 137         bool make_dumb = false;
 138
 139         if (argv[1] && strcmp(argv[1], "--dumb") == 0) {
 140                 argv++;
 141                 make_dumb = true;
 142         }
 143         num = argv[1] ? atoi(argv[1]) : 1000000;
 144         objs = calloc(num, sizeof(objs[0]));
 145
 146         for (i = 0; i < num; i++) {
 147                 objs[i].key = i;
 148                 objs[i].self = &objs[i];
 149         }
 150
 151         ht = htable_obj_new();
 152         htr = (void *)ht;
 153
 154         printf("Initial insert: ");
 155         fflush(stdout);
 156         gettimeofday(&start, NULL);
 157         for (i = 0; i < num; i++)
 158                 htable_obj_add(ht, objs[i].self);
 159         gettimeofday(&stop, NULL);
 160         printf(" %zu ns\n", normalize(&start, &stop, num));
 161         printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
 162                1U << htr->bits, popcount(htr->common_mask),
 163                perfect(htr) * 100.0 / htr->elems);
 164
 165         if (make_dumb) {
 166                 /* Screw with mask, to hobble us. */
 167                 update_common(htr, (void *)~htr->common_bits);
 168                 printf("Details: DUMB MODE: mask bits %u\n",
 169                        popcount(htr->common_mask));
 170         }
 171
 172         printf("Initial lookup (match): ");
 173         fflush(stdout);
 174         gettimeofday(&start, NULL);
 175         for (i = 0; i < num; i++)
 176                 if (htable_obj_get(ht, &i)->self != objs[i].self)
 177                         abort();
 178         gettimeofday(&stop, NULL);
 179         printf(" %zu ns\n", normalize(&start, &stop, num));
 180
 181         printf("Initial lookup (miss): ");
 182         fflush(stdout);
 183         gettimeofday(&start, NULL);
 184         for (i = 0; i < num; i++) {
 185                 unsigned int n = i + num;
 186                 if (htable_obj_get(ht, &n))
 187                         abort();
 188         }
 189         gettimeofday(&stop, NULL);
 190         printf(" %zu ns\n", normalize(&start, &stop, num));
 191
 192         /* Lookups in order are very cache-friendly for judy; try random */
 193         printf("Initial lookup (random): ");
 194         fflush(stdout);
 195         gettimeofday(&start, NULL);
 196         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 197                 if (htable_obj_get(ht, &j)->self != &objs[j])
 198                         abort();
 199         gettimeofday(&stop, NULL);
 200         printf(" %zu ns\n", normalize(&start, &stop, num));
 201
 202         hashcount = 0;
 203         printf("Initial delete all: ");
 204         fflush(stdout);
 205         gettimeofday(&start, NULL);
 206         for (i = 0; i < num; i++)
 207                 if (!htable_obj_del(ht, objs[i].self))
 208                         abort();
 209         gettimeofday(&stop, NULL);
 210         printf(" %zu ns\n", normalize(&start, &stop, num));
 211         printf("Details: rehashes %zu\n", hashcount);
 212
 213         printf("Initial re-inserting: ");
 214         fflush(stdout);
 215         gettimeofday(&start, NULL);
 216         for (i = 0; i < num; i++)
 217                 htable_obj_add(ht, objs[i].self);
 218         gettimeofday(&stop, NULL);
 219         printf(" %zu ns\n", normalize(&start, &stop, num));
 220
 221         hashcount = 0;
 222         printf("Deleting first half: ");
 223         fflush(stdout);
 224         gettimeofday(&start, NULL);
 225         for (i = 0; i < num; i+=2)
 226                 if (!htable_obj_del(ht, objs[i].self))
 227                         abort();
 228         gettimeofday(&stop, NULL);
 229         printf(" %zu ns\n", normalize(&start, &stop, num));
 230
 231         printf("Details: rehashes %zu, delete markers %zu\n",
 232                hashcount, count_deleted(htr));
 233
 234         printf("Adding (a different) half: ");
 235         fflush(stdout);
 236
 237         for (i = 0; i < num; i+=2)
 238                 objs[i].key = num+i;
 239
 240         gettimeofday(&start, NULL);
 241         for (i = 0; i < num; i+=2)
 242                 htable_obj_add(ht, objs[i].self);
 243         gettimeofday(&stop, NULL);
 244         printf(" %zu ns\n", normalize(&start, &stop, num));
 245
 246         printf("Details: delete markers %zu, perfect %.0f%%\n",
 247                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
 248
 249         printf("Lookup after half-change (match): ");
 250         fflush(stdout);
 251         gettimeofday(&start, NULL);
 252         for (i = 1; i < num; i+=2)
 253                 if (htable_obj_get(ht, &i)->self != objs[i].self)
 254                         abort();
 255         for (i = 0; i < num; i+=2) {
 256                 unsigned int n = i + num;
 257                 if (htable_obj_get(ht, &n)->self != objs[i].self)
 258                         abort();
 259         }
 260         gettimeofday(&stop, NULL);
 261         printf(" %zu ns\n", normalize(&start, &stop, num));
 262
 263         printf("Lookup after half-change (miss): ");
 264         fflush(stdout);
 265         gettimeofday(&start, NULL);
 266         for (i = 0; i < num; i++) {
 267                 unsigned int n = i + num * 2;
 268                 if (htable_obj_get(ht, &n))
 269                         abort();
 270         }
 271         gettimeofday(&stop, NULL);
 272         printf(" %zu ns\n", normalize(&start, &stop, num));
 273
 274         /* Hashtables with delete markers can fill with markers over time.
 275          * so do some changes to see how it operates in long-term. */
 276         for (i = 0; i < 5; i++) {
 277                 if (i == 0) {
 278                         /* We don't measure this: jmap is different. */
 279                         printf("Details: initial churn\n");
 280                 } else {
 281                         printf("Churning %s time: ",
 282                                i == 1 ? "second"
 283                                : i == 2 ? "third"
 284                                : i == 3 ? "fourth"
 285                                : "fifth");
 286                         fflush(stdout);
 287                 }
 288                 gettimeofday(&start, NULL);
 289                 for (j = 0; j < num; j++) {
 290                         if (!htable_obj_del(ht, &objs[j]))
 291                                 abort();
 292                         objs[j].key = num*i+j;
 293                         if (!htable_obj_add(ht, &objs[j]))
 294                                 abort();
 295                 }
 296                 gettimeofday(&stop, NULL);
 297                 if (i != 0)
 298                         printf(" %zu ns\n", normalize(&start, &stop, num));
 299         }
 300
 301         /* Spread out the keys more to try to make it harder. */
 302         printf("Details: reinserting with spread\n");
 303         for (i = 0; i < num; i++) {
 304                 if (!htable_obj_del(ht, objs[i].self))
 305                         abort();
 306                 objs[i].key = num * 5 + i * 9;
 307                 if (!htable_obj_add(ht, objs[i].self))
 308                         abort();
 309         }
 310         printf("Details: delete markers %zu, perfect %.0f%%\n",
 311                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
 312         i = worst_run(htr, &deleted);
 313         printf("Details: worst run %zu (%zu deleted)\n", i, deleted);
 314
 315         printf("Lookup after churn & spread (match): ");
 316         fflush(stdout);
 317         gettimeofday(&start, NULL);
 318         for (i = 0; i < num; i++) {
 319                 unsigned int n = num * 5 + i * 9;
 320                 if (htable_obj_get(ht, &n)->self != objs[i].self)
 321                         abort();
 322         }
 323         gettimeofday(&stop, NULL);
 324         printf(" %zu ns\n", normalize(&start, &stop, num));
 325
 326         printf("Lookup after churn & spread (miss): ");
 327         fflush(stdout);
 328         gettimeofday(&start, NULL);
 329         for (i = 0; i < num; i++) {
 330                 unsigned int n = num * 6 + i * 9;
 331                 if (htable_obj_get(ht, &n))
 332                         abort();
 333         }
 334         gettimeofday(&stop, NULL);
 335         printf(" %zu ns\n", normalize(&start, &stop, num));
 336
 337         printf("Lookup after churn & spread (random): ");
 338         fflush(stdout);
 339         gettimeofday(&start, NULL);
 340         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
 341                 unsigned int n = num * 5 + j * 9;
 342                 if (htable_obj_get(ht, &n)->self != &objs[j])
 343                         abort();
 344         }
 345         gettimeofday(&stop, NULL);
 346         printf(" %zu ns\n", normalize(&start, &stop, num));
 347
 348         hashcount = 0;
 349         printf("Deleting half after churn & spread: ");
 350         fflush(stdout);
 351         gettimeofday(&start, NULL);
 352         for (i = 0; i < num; i+=2)
 353                 if (!htable_obj_del(ht, objs[i].self))
 354                         abort();
 355         gettimeofday(&stop, NULL);
 356         printf(" %zu ns\n", normalize(&start, &stop, num));
 357
 358         printf("Adding (a different) half after churn & spread: ");
 359         fflush(stdout);
 360
 361         for (i = 0; i < num; i+=2)
 362                 objs[i].key = num*6+i*9;
 363
 364         gettimeofday(&start, NULL);
 365         for (i = 0; i < num; i+=2)
 366                 htable_obj_add(ht, objs[i].self);
 367         gettimeofday(&stop, NULL);
 368         printf(" %zu ns\n", normalize(&start, &stop, num));
 369
 370         printf("Details: delete markers %zu, perfect %.0f%%\n",
 371                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
 372
 373         return 0;
 374 }