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         printf("%zu words\n", num);
  63
  64         /* Append and prepend last char for miss testing. */
  65         misswords = talloc_array(words, char *, num);
  66         for (i = 0; i < num; i++) {
  67                 char lastc;
  68                 if (strlen(words[i]))
  69                         lastc = words[i][strlen(words[i])-1];
  70                 else
  71                         lastc = 'z';
  72                 misswords[i] = talloc_asprintf(misswords, "%c%s%c%c",
  73                                                lastc, words[i], lastc, lastc);
  74         }
  75
  76         printf("#01: Initial insert: ");
  77         fflush(stdout);
  78         start = time_now();
  79         for (i = 0; i < num; i++)
  80                 htable_str_add(&ht, words[i]);
  81         stop = time_now();
  82         printf(" %zu ns\n", normalize(&start, &stop, num));
  83
  84         printf("Bytes allocated: %zu\n",
  85                sizeof(ht.raw.table[0]) << ht.raw.bits);
  86
  87         printf("#02: Initial lookup (match): ");
  88         fflush(stdout);
  89         start = time_now();
  90         for (i = 0; i < num; i++)
  91                 if (htable_str_get(&ht, words[i]) != words[i])
  92                         abort();
  93         stop = time_now();
  94         printf(" %zu ns\n", normalize(&start, &stop, num));
  95
  96         printf("#03: Initial lookup (miss): ");
  97         fflush(stdout);
  98         start = time_now();
  99         for (i = 0; i < num; i++) {
 100                 if (htable_str_get(&ht, misswords[i]))
 101                         abort();
 102         }
 103         stop = time_now();
 104         printf(" %zu ns\n", normalize(&start, &stop, num));
 105
 106         /* Lookups in order are very cache-friendly for judy; try random */
 107         printf("#04: Initial lookup (random): ");
 108         fflush(stdout);
 109         start = time_now();
 110         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 111                 if (htable_str_get(&ht, words[j]) != words[j])
 112                         abort();
 113         stop = time_now();
 114         printf(" %zu ns\n", normalize(&start, &stop, num));
 115
 116         hashcount = 0;
 117         printf("#05: Initial delete all: ");
 118         fflush(stdout);
 119         start = time_now();
 120         for (i = 0; i < num; i++)
 121                 if (!htable_str_del(&ht, words[i]))
 122                         abort();
 123         stop = time_now();
 124         printf(" %zu ns\n", normalize(&start, &stop, num));
 125
 126         printf("#06: Initial re-inserting: ");
 127         fflush(stdout);
 128         start = time_now();
 129         for (i = 0; i < num; i++)
 130                 htable_str_add(&ht, words[i]);
 131         stop = time_now();
 132         printf(" %zu ns\n", normalize(&start, &stop, num));
 133
 134         hashcount = 0;
 135         printf("#07: Deleting first half: ");
 136         fflush(stdout);
 137         start = time_now();
 138         for (i = 0; i < num; i+=2)
 139                 if (!htable_str_del(&ht, words[i]))
 140                         abort();
 141         stop = time_now();
 142         printf(" %zu ns\n", normalize(&start, &stop, num));
 143
 144         printf("#08: Adding (a different) half: ");
 145         fflush(stdout);
 146
 147         start = time_now();
 148         for (i = 0; i < num; i+=2)
 149                 htable_str_add(&ht, misswords[i]);
 150         stop = time_now();
 151         printf(" %zu ns\n", normalize(&start, &stop, num));
 152
 153         printf("#09: Lookup after half-change (match): ");
 154         fflush(stdout);
 155         start = time_now();
 156         for (i = 1; i < num; i+=2)
 157                 if (htable_str_get(&ht, words[i]) != words[i])
 158                         abort();
 159         for (i = 0; i < num; i+=2) {
 160                 if (htable_str_get(&ht, misswords[i]) != misswords[i])
 161                         abort();
 162         }
 163         stop = time_now();
 164         printf(" %zu ns\n", normalize(&start, &stop, num));
 165
 166         printf("#10: Lookup after half-change (miss): ");
 167         fflush(stdout);
 168         start = time_now();
 169         for (i = 0; i < num; i+=2)
 170                 if (htable_str_get(&ht, words[i]))
 171                         abort();
 172         for (i = 1; i < num; i+=2) {
 173                 if (htable_str_get(&ht, misswords[i]))
 174                         abort();
 175         }
 176         stop = time_now();
 177         printf(" %zu ns\n", normalize(&start, &stop, num));
 178
 179         /* Hashtables with delete markers can fill with markers over time.
 180          * so do some changes to see how it operates in long-term. */
 181         printf("#11: Churn 1: ");
 182         start = time_now();
 183         for (j = 0; j < num; j+=2) {
 184                 if (!htable_str_del(&ht, misswords[j]))
 185                         abort();
 186                 if (!htable_str_add(&ht, words[j]))
 187                         abort();
 188         }
 189         stop = time_now();
 190         printf(" %zu ns\n", normalize(&start, &stop, num));
 191
 192         printf("#12: Churn 2: ");
 193         start = time_now();
 194         for (j = 1; j < num; j+=2) {
 195                 if (!htable_str_del(&ht, words[j]))
 196                         abort();
 197                 if (!htable_str_add(&ht, misswords[j]))
 198                         abort();
 199         }
 200         stop = time_now();
 201         printf(" %zu ns\n", normalize(&start, &stop, num));
 202
 203         printf("#13: Churn 3: ");
 204         start = time_now();
 205         for (j = 1; j < num; j+=2) {
 206                 if (!htable_str_del(&ht, misswords[j]))
 207                         abort();
 208                 if (!htable_str_add(&ht, words[j]))
 209                         abort();
 210         }
 211         stop = time_now();
 212         printf(" %zu ns\n", normalize(&start, &stop, num));
 213
 214         /* Now it's back to normal... */
 215         printf("#14: Post-Churn lookup (match): ");
 216         fflush(stdout);
 217         start = time_now();
 218         for (i = 0; i < num; i++)
 219                 if (htable_str_get(&ht, words[i]) != words[i])
 220                         abort();
 221         stop = time_now();
 222         printf(" %zu ns\n", normalize(&start, &stop, num));
 223
 224         printf("#15: Post-Churn lookup (miss): ");
 225         fflush(stdout);
 226         start = time_now();
 227         for (i = 0; i < num; i++) {
 228                 if (htable_str_get(&ht, misswords[i]))
 229                         abort();
 230         }
 231         stop = time_now();
 232         printf(" %zu ns\n", normalize(&start, &stop, num));
 233
 234         /* Lookups in order are very cache-friendly for judy; try random */
 235         printf("#16: Post-Churn lookup (random): ");
 236         fflush(stdout);
 237         start = time_now();
 238         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 239                 if (htable_str_get(&ht, words[j]) != words[j])
 240                         abort();
 241         stop = time_now();
 242         printf(" %zu ns\n", normalize(&start, &stop, num));
 243
 244         return 0;
 245 }