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

   1 /* Density measurements for hashtables. */
   2 #include <ccan/err/err.h>
   3 #include <ccan/htable/htable_type.h>
   4 #include <ccan/htable/htable.c>
   5 #include <ccan/hash/hash.h>
   6 #include <ccan/ptrint/ptrint.h>
   7 #include <ccan/time/time.h>
   8 #include <stdio.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11 #include <unistd.h>
  12
  13 /* We don't actually hash objects: we put values in as if they were ptrs */
  14 static uintptr_t key(const ptrint_t *obj)
  15 {
  16         return ptr2int(obj);
  17 }
  18
  19 static size_t hash_uintptr(uintptr_t key)
  20 {
  21         return hashl(&key, 1, 0);
  22 }
  23
  24 static bool cmp(const ptrint_t *p, uintptr_t k)
  25 {
  26         return key(p) == k;
  27 }
  28
  29 HTABLE_DEFINE_TYPE(ptrint_t, key, hash_uintptr, cmp, htable_ptrint);
  30
  31 /* Nanoseconds per operation */
  32 static size_t normalize(const struct timeabs *start,
  33                         const struct timeabs *stop,
  34                         unsigned int num)
  35 {
  36         return time_to_nsec(time_divide(time_between(*stop, *start), num));
  37 }
  38
  39 static size_t average_run(const struct htable_ptrint *ht, size_t count, size_t *longest)
  40 {
  41         size_t i, total = 0;
  42
  43         *longest = 0;
  44         for (i = 0; i < count; i++) {
  45                 size_t h = hash_uintptr(i + 2);
  46                 size_t run = 1;
  47
  48                 while (get_raw_ptr(&ht->raw, ht->raw.table[h % ((size_t)1 << ht->raw.bits)]) != int2ptr(i + 2)) {
  49                         h++;
  50                         run++;
  51                 }
  52                 total += run;
  53                 if (run > *longest)
  54                         *longest = run;
  55         }
  56         return total / count;
  57 }
  58
  59 int main(int argc, char *argv[])
  60 {
  61         unsigned int i;
  62         size_t num;
  63         struct timeabs start, stop;
  64         struct htable_ptrint ht;
  65
  66         if (argc != 2)
  67                 errx(1, "Usage: density <power-of-2-tablesize>");
  68
  69         num = atoi(argv[1]);
  70
  71         printf("Total buckets, buckets used, nanoseconds search time per element, avg run, longest run\n");
  72         for (i = 1; i <= 99; i++) {
  73                 uintptr_t j;
  74                 struct htable_ptrint_iter it;
  75                 size_t count, avg_run, longest_run;
  76                 ptrint_t *p;
  77
  78                 htable_ptrint_init_sized(&ht, num * 3 / 4);
  79                 assert((1 << ht.raw.bits) == num);
  80
  81                 /* Can't put 0 or 1 in the hash table: multiply by a prime. */
  82                 for (j = 0; j < num * i / 100; j++) {
  83                         htable_ptrint_add(&ht, int2ptr(j + 2));
  84                         /* stop it from doubling! */
  85                         ht.raw.elems = num / 2;
  86                 }
  87                 /* Must not have changed! */
  88                 assert((1 << ht.raw.bits) == num);
  89
  90                 /* Clean cache */
  91                 count = 0;
  92                 for (p = htable_ptrint_first(&ht, &it); p; p = htable_ptrint_next(&ht, &it))
  93                         count++;
  94                 assert(count == num * i / 100);
  95                 start = time_now();
  96                 for (j = 0; j < count; j++)
  97                         assert(htable_ptrint_get(&ht, j + 2));
  98                 stop = time_now();
  99                 avg_run = average_run(&ht, count, &longest_run);
 100                 printf("%zu,%zu,%zu,%zu,%zu\n",
 101                        num, count, normalize(&start, &stop, count), avg_run, longest_run);
 102                 fflush(stdout);
 103                 htable_ptrint_clear(&ht);
 104         }
 105
 106         return 0;
 107 }