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

   1 /* Simple speed tests for a hash of strings. */
   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
  16 static size_t hashcount;
  17
  18 static const char *strkey(const char *str)
  19 {
  20         return str;
  21 }
  22
  23 static size_t hash_str(const char *key)
  24 {
  25         hashcount++;
  26         return hash(key, strlen(key), 0);
  27 }
  28
  29 static bool cmp(const char *obj, const char *key)
  30 {
  31         return strcmp(obj, key) == 0;
  32 }
  33
  34 HTABLE_DEFINE_TYPE(char, strkey, hash_str, cmp, htable_str);
  35
  36 /* Nanoseconds per operation */
  37 static size_t normalize(const struct timeval *start,
  38                         const struct timeval *stop,
  39                         unsigned int num)
  40 {
  41         struct timeval diff;
  42
  43         timersub(stop, start, &diff);
  44
  45         /* Floating point is more accurate here. */
  46         return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
  47                 / num * 1000;
  48 }
  49
  50 int main(int argc, char *argv[])
  51 {
  52         size_t i, j, num;
  53         struct timeval start, stop;
  54         struct htable_str ht;
  55         char **words, **misswords;
  56
  57         words = strsplit(NULL, grab_file(NULL,
  58                                          argv[1] ? argv[1] : "/usr/share/dict/words",
  59                                          NULL), "\n");
  60         htable_str_init(&ht);
  61         num = talloc_array_length(words) - 1;
  62         /* Note that on my system, num is just > 98304, where we double! */
  63         printf("%zu words\n", num);
  64
  65         /* Append and prepend last char for miss testing. */
  66         misswords = talloc_array(words, char *, num);
  67         for (i = 0; i < num; i++) {
  68                 char lastc;
  69                 if (strlen(words[i]))
  70                         lastc = words[i][strlen(words[i])-1];
  71                 else
  72                         lastc = 'z';
  73                 misswords[i] = talloc_asprintf(misswords, "%c%s%c%c",
  74                                                lastc, words[i], lastc, lastc);
  75         }
  76
  77         printf("#01: Initial insert: ");
  78         fflush(stdout);
  79         start = time_now();
  80         for (i = 0; i < num; i++)
  81                 htable_str_add(&ht, words[i]);
  82         stop = time_now();
  83         printf(" %zu ns\n", normalize(&start, &stop, num));
  84
  85         printf("Bytes allocated: %zu\n",
  86                sizeof(ht.raw.table[0]) << ht.raw.bits);
  87
  88         printf("#02: Initial lookup (match): ");
  89         fflush(stdout);
  90         start = time_now();
  91         for (i = 0; i < num; i++)
  92                 if (htable_str_get(&ht, words[i]) != words[i])
  93                         abort();
  94         stop = time_now();
  95         printf(" %zu ns\n", normalize(&start, &stop, num));
  96
  97         printf("#03: Initial lookup (miss): ");
  98         fflush(stdout);
  99         start = time_now();
 100         for (i = 0; i < num; i++) {
 101                 if (htable_str_get(&ht, misswords[i]))
 102                         abort();
 103         }
 104         stop = time_now();
 105         printf(" %zu ns\n", normalize(&start, &stop, num));
 106
 107         /* Lookups in order are very cache-friendly for judy; try random */
 108         printf("#04: Initial lookup (random): ");
 109         fflush(stdout);
 110         start = time_now();
 111         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 112                 if (htable_str_get(&ht, words[j]) != words[j])
 113                         abort();
 114         stop = time_now();
 115         printf(" %zu ns\n", normalize(&start, &stop, num));
 116
 117         hashcount = 0;
 118         printf("#05: Initial delete all: ");
 119         fflush(stdout);
 120         start = time_now();
 121         for (i = 0; i < num; i++)
 122                 if (!htable_str_del(&ht, words[i]))
 123                         abort();
 124         stop = time_now();
 125         printf(" %zu ns\n", normalize(&start, &stop, num));
 126
 127         printf("#06: Initial re-inserting: ");
 128         fflush(stdout);
 129         start = time_now();
 130         for (i = 0; i < num; i++)
 131                 htable_str_add(&ht, words[i]);
 132         stop = time_now();
 133         printf(" %zu ns\n", normalize(&start, &stop, num));
 134
 135         hashcount = 0;
 136         printf("#07: Deleting first half: ");
 137         fflush(stdout);
 138         start = time_now();
 139         for (i = 0; i < num; i+=2)
 140                 if (!htable_str_del(&ht, words[i]))
 141                         abort();
 142         stop = time_now();
 143         printf(" %zu ns\n", normalize(&start, &stop, num));
 144
 145         printf("#08: Adding (a different) half: ");
 146         fflush(stdout);
 147
 148         start = time_now();
 149         for (i = 0; i < num; i+=2)
 150                 htable_str_add(&ht, misswords[i]);
 151         stop = time_now();
 152         printf(" %zu ns\n", normalize(&start, &stop, num));
 153
 154         printf("#09: Lookup after half-change (match): ");
 155         fflush(stdout);
 156         start = time_now();
 157         for (i = 1; i < num; i+=2)
 158                 if (htable_str_get(&ht, words[i]) != words[i])
 159                         abort();
 160         for (i = 0; i < num; i+=2) {
 161                 if (htable_str_get(&ht, misswords[i]) != misswords[i])
 162                         abort();
 163         }
 164         stop = time_now();
 165         printf(" %zu ns\n", normalize(&start, &stop, num));
 166
 167         printf("#10: Lookup after half-change (miss): ");
 168         fflush(stdout);
 169         start = time_now();
 170         for (i = 0; i < num; i+=2)
 171                 if (htable_str_get(&ht, words[i]))
 172                         abort();
 173         for (i = 1; i < num; i+=2) {
 174                 if (htable_str_get(&ht, misswords[i]))
 175                         abort();
 176         }
 177         stop = time_now();
 178         printf(" %zu ns\n", normalize(&start, &stop, num));
 179
 180         /* Hashtables with delete markers can fill with markers over time.
 181          * so do some changes to see how it operates in long-term. */
 182         printf("#11: Churn 1: ");
 183         start = time_now();
 184         for (j = 0; j < num; j+=2) {
 185                 if (!htable_str_del(&ht, misswords[j]))
 186                         abort();
 187                 if (!htable_str_add(&ht, words[j]))
 188                         abort();
 189         }
 190         stop = time_now();
 191         printf(" %zu ns\n", normalize(&start, &stop, num));
 192
 193         printf("#12: Churn 2: ");
 194         start = time_now();
 195         for (j = 1; j < num; j+=2) {
 196                 if (!htable_str_del(&ht, words[j]))
 197                         abort();
 198                 if (!htable_str_add(&ht, misswords[j]))
 199                         abort();
 200         }
 201         stop = time_now();
 202         printf(" %zu ns\n", normalize(&start, &stop, num));
 203
 204         printf("#13: Churn 3: ");
 205         start = time_now();
 206         for (j = 1; j < num; j+=2) {
 207                 if (!htable_str_del(&ht, misswords[j]))
 208                         abort();
 209                 if (!htable_str_add(&ht, words[j]))
 210                         abort();
 211         }
 212         stop = time_now();
 213         printf(" %zu ns\n", normalize(&start, &stop, num));
 214
 215         /* Now it's back to normal... */
 216         printf("#14: Post-Churn lookup (match): ");
 217         fflush(stdout);
 218         start = time_now();
 219         for (i = 0; i < num; i++)
 220                 if (htable_str_get(&ht, words[i]) != words[i])
 221                         abort();
 222         stop = time_now();
 223         printf(" %zu ns\n", normalize(&start, &stop, num));
 224
 225         printf("#15: Post-Churn lookup (miss): ");
 226         fflush(stdout);
 227         start = time_now();
 228         for (i = 0; i < num; i++) {
 229                 if (htable_str_get(&ht, misswords[i]))
 230                         abort();
 231         }
 232         stop = time_now();
 233         printf(" %zu ns\n", normalize(&start, &stop, num));
 234
 235         /* Lookups in order are very cache-friendly for judy; try random */
 236         printf("#16: Post-Churn lookup (random): ");
 237         fflush(stdout);
 238         start = time_now();
 239         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 240                 if (htable_str_get(&ht, words[j]) != words[j])
 241                         abort();
 242         stop = time_now();
 243         printf(" %zu ns\n", normalize(&start, &stop, num));
 244
 245         return 0;
 246 }