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