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

   1 /* Simple speed tests for a hash of strings using hsearch */
   2 #include <ccan/htable/htable_type.h>
   3 #include <ccan/htable/htable.c>
   4 #include <ccan/tal/str/str.h>
   5 #include <ccan/tal/grab_file/grab_file.h>
   6 #include <ccan/tal/tal.h>
   7 #include <ccan/hash/hash.h>
   8 #include <ccan/time/time.h>
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <time.h>
  13 #include <unistd.h>
  14 #include <sys/time.h>
  15 #include <search.h>
  16
  17 /* Nanoseconds per operation */
  18 static size_t normalize(const struct timeabs *start,
  19                         const struct timeabs *stop,
  20                         unsigned int num)
  21 {
  22         return time_to_nsec(time_divide(time_between(*stop, *start), num));
  23 }
  24
  25 int main(int argc, char *argv[])
  26 {
  27         size_t i, j, num;
  28         struct timeabs start, stop;
  29         char **w;
  30         ENTRY *words, *misswords;
  31
  32         w = tal_strsplit(NULL, grab_file(NULL,
  33                                          argv[1] ? argv[1] : "/usr/share/dict/words"), "\n", STR_NO_EMPTY);
  34         num = tal_count(w) - 1;
  35         printf("%zu words\n", num);
  36
  37         hcreate(num+num/3);
  38
  39         words = tal_arr(w, ENTRY, num);
  40         for (i = 0; i < num; i++) {
  41                 words[i].key = w[i];
  42                 words[i].data = words[i].key;
  43         }
  44
  45         /* Append and prepend last char for miss testing. */
  46         misswords = tal_arr(w, ENTRY, num);
  47         for (i = 0; i < num; i++) {
  48                 char lastc;
  49                 if (strlen(w[i]))
  50                         lastc = w[i][strlen(w[i])-1];
  51                 else
  52                         lastc = 'z';
  53                 misswords[i].key = tal_fmt(misswords, "%c%s%c%c",
  54                                            lastc, w[i], lastc, lastc);
  55         }
  56
  57         printf("#01: Initial insert: ");
  58         fflush(stdout);
  59         start = time_now();
  60         for (i = 0; i < num; i++)
  61                 hsearch(words[i], ENTER);
  62         stop = time_now();
  63         printf(" %zu ns\n", normalize(&start, &stop, num));
  64
  65         printf("#02: Initial lookup (match): ");
  66         fflush(stdout);
  67         start = time_now();
  68         for (i = 0; i < num; i++)
  69                 if (hsearch(words[i], FIND)->data != words[i].data)
  70                         abort();
  71         stop = time_now();
  72         printf(" %zu ns\n", normalize(&start, &stop, num));
  73
  74         printf("#03: Initial lookup (miss): ");
  75         fflush(stdout);
  76         start = time_now();
  77         for (i = 0; i < num; i++) {
  78                 if (hsearch(misswords[i], FIND))
  79                         abort();
  80         }
  81         stop = time_now();
  82         printf(" %zu ns\n", normalize(&start, &stop, num));
  83
  84         /* Lookups in order are very cache-friendly for judy; try random */
  85         printf("#04: Initial lookup (random): ");
  86         fflush(stdout);
  87         start = time_now();
  88         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
  89                 if (hsearch(words[i], FIND)->data != words[i].data)
  90                         abort();
  91         stop = time_now();
  92         printf(" %zu ns\n", normalize(&start, &stop, num));
  93
  94         return 0;
  95 }