lib/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/str_talloc/str_talloc.h>
   5 #include <ccan/grab_file/grab_file.h>
   6 #include <ccan/talloc/talloc.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 timeval *start,
  19                         const struct timeval *stop,
  20                         unsigned int num)
  21 {
  22         struct timeval diff;
  23
  24         timersub(stop, start, &diff);
  25
  26         /* Floating point is more accurate here. */
  27         return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
  28                 / num * 1000;
  29 }
  30
  31 int main(int argc, char *argv[])
  32 {
  33         size_t i, j, num;
  34         struct timeval start, stop;
  35         char **w;
  36         ENTRY *words, *misswords;
  37
  38         w = strsplit(NULL, grab_file(NULL,
  39                                      argv[1] ? argv[1] : "/usr/share/dict/words",
  40                                      NULL), "\n");
  41         num = talloc_array_length(w) - 1;
  42         printf("%zu words\n", num);
  43
  44         hcreate(num+num/3);
  45
  46         words = talloc_array(w, ENTRY, num);
  47         for (i = 0; i < num; i++) {
  48                 words[i].key = w[i];
  49                 words[i].data = words[i].key;
  50         }
  51
  52         /* Append and prepend last char for miss testing. */
  53         misswords = talloc_array(w, ENTRY, num);
  54         for (i = 0; i < num; i++) {
  55                 char lastc;
  56                 if (strlen(w[i]))
  57                         lastc = w[i][strlen(w[i])-1];
  58                 else
  59                         lastc = 'z';
  60                 misswords[i].key = talloc_asprintf(misswords, "%c%s%c%c",
  61                                                    lastc, w[i],
  62                                                    lastc, lastc);
  63         }
  64
  65         printf("#01: Initial insert: ");
  66         fflush(stdout);
  67         start = time_now();
  68         for (i = 0; i < num; i++)
  69                 hsearch(words[i], ENTER);
  70         stop = time_now();
  71         printf(" %zu ns\n", normalize(&start, &stop, num));
  72
  73         printf("#02: Initial lookup (match): ");
  74         fflush(stdout);
  75         start = time_now();
  76         for (i = 0; i < num; i++)
  77                 if (hsearch(words[i], FIND)->data != words[i].data)
  78                         abort();
  79         stop = time_now();
  80         printf(" %zu ns\n", normalize(&start, &stop, num));
  81
  82         printf("#03: Initial lookup (miss): ");
  83         fflush(stdout);
  84         start = time_now();
  85         for (i = 0; i < num; i++) {
  86                 if (hsearch(misswords[i], FIND))
  87                         abort();
  88         }
  89         stop = time_now();
  90         printf(" %zu ns\n", normalize(&start, &stop, num));
  91
  92         /* Lookups in order are very cache-friendly for judy; try random */
  93         printf("#04: Initial lookup (random): ");
  94         fflush(stdout);
  95         start = time_now();
  96         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
  97                 if (hsearch(words[i], FIND)->data != words[i].data)
  98                         abort();
  99         stop = time_now();
 100         printf(" %zu ns\n", normalize(&start, &stop, num));
 101
 102         return 0;
 103 }