lib/ccan/strset/tools/speed.c

   1 /* Simple speed tests using strset code.
   2  *
   3  * Results on my 32 bit Intel(R) Core(TM) i5 CPU M 560  @ 2.67GHz, gcc 4.5.2:
   4  * Run 100 times: Min-Max(Avg)
   5  #01: Initial insert:   212-219(214)
   6  #02: Initial lookup (match):   161-169(162)
   7  #03: Initial lookup (miss):   157-163(158)
   8  #04: Initial lookup (random):   450-479(453)
   9  #05: Initial delete all:   126-137(128)
  10  #06: Initial re-inserting:   193-198(194)
  11  #07: Deleting first half:   99-102(99)
  12  #08: Adding (a different) half:   143-154(144)
  13  #09: Lookup after half-change (match):   183-189(184)
  14  #10: Lookup after half-change (miss):   198-212(199)
  15  #11: Churn 1:   274-282(276)
  16  #12: Churn 2:   279-296(282)
  17  #13: Churn 3:   278-294(280)
  18  #14: Post-Churn lookup (match):   170-180(171)
  19  #15: Post-Churn lookup (miss):   175-186(176)
  20  #16: Post-Churn lookup (random):   522-534(525)
  21  */
  22 #include <ccan/str_talloc/str_talloc.h>
  23 #include <ccan/grab_file/grab_file.h>
  24 #include <ccan/talloc/talloc.h>
  25 #include <ccan/time/time.h>
  26 #include <ccan/strset/strset.c>
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <time.h>
  31 #include <unistd.h>
  32 #include <sys/time.h>
  33
  34 /* Nanoseconds per operation */
  35 static size_t normalize(const struct timeval *start,
  36                         const struct timeval *stop,
  37                         unsigned int num)
  38 {
  39         struct timeval diff;
  40
  41         timersub(stop, start, &diff);
  42
  43         /* Floating point is more accurate here. */
  44         return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
  45                 / num * 1000;
  46 }
  47
  48 int main(int argc, char *argv[])
  49 {
  50         size_t i, j, num;
  51         struct timeval start, stop;
  52         struct strset set;
  53         char **words, **misswords;
  54
  55         words = strsplit(NULL, grab_file(NULL,
  56                                          argv[1] ? argv[1] : "/usr/share/dict/words",
  57                                          NULL), "\n");
  58         strset_init(&set);
  59         num = talloc_array_length(words) - 1;
  60         printf("%zu words\n", num);
  61
  62         /* Append and prepend last char for miss testing. */
  63         misswords = talloc_array(words, char *, num);
  64         for (i = 0; i < num; i++) {
  65                 char lastc;
  66                 if (strlen(words[i]))
  67                         lastc = words[i][strlen(words[i])-1];
  68                 else
  69                         lastc = 'z';
  70                 misswords[i] = talloc_asprintf(misswords, "%c%s%c%c",
  71                                                lastc, words[i], lastc, lastc);
  72         }
  73
  74         printf("#01: Initial insert: ");
  75         fflush(stdout);
  76         start = time_now();
  77         for (i = 0; i < num; i++)
  78                 strset_set(&set, words[i]);
  79         stop = time_now();
  80         printf(" %zu ns\n", normalize(&start, &stop, num));
  81
  82 #if 0
  83         printf("Nodes allocated: %zu (%zu bytes)\n",
  84                allocated, allocated * sizeof(critbit0_node));
  85 #endif
  86
  87         printf("#02: Initial lookup (match): ");
  88         fflush(stdout);
  89         start = time_now();
  90         for (i = 0; i < num; i++)
  91                 if (!strset_test(&set, 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 (strset_test(&set, 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 (!strset_test(&set, words[j]))
 112                         abort();
 113         stop = time_now();
 114         printf(" %zu ns\n", normalize(&start, &stop, num));
 115
 116         printf("#05: Initial delete all: ");
 117         fflush(stdout);
 118         start = time_now();
 119         for (i = 0; i < num; i++)
 120                 if (!strset_clear(&set, words[i]))
 121                         abort();
 122         stop = time_now();
 123         printf(" %zu ns\n", normalize(&start, &stop, num));
 124
 125         printf("#06: Initial re-inserting: ");
 126         fflush(stdout);
 127         start = time_now();
 128         for (i = 0; i < num; i++)
 129                 strset_set(&set, words[i]);
 130         stop = time_now();
 131         printf(" %zu ns\n", normalize(&start, &stop, num));
 132
 133         printf("#07: Deleting first half: ");
 134         fflush(stdout);
 135         start = time_now();
 136         for (i = 0; i < num; i+=2)
 137                 if (!strset_clear(&set, words[i]))
 138                         abort();
 139         stop = time_now();
 140         printf(" %zu ns\n", normalize(&start, &stop, num));
 141
 142         printf("#08: Adding (a different) half: ");
 143         fflush(stdout);
 144
 145         start = time_now();
 146         for (i = 0; i < num; i+=2)
 147                 strset_set(&set, misswords[i]);
 148         stop = time_now();
 149         printf(" %zu ns\n", normalize(&start, &stop, num));
 150
 151         printf("#09: Lookup after half-change (match): ");
 152         fflush(stdout);
 153         start = time_now();
 154         for (i = 1; i < num; i+=2)
 155                 if (!strset_test(&set, words[i]))
 156                         abort();
 157         for (i = 0; i < num; i+=2) {
 158                 if (!strset_test(&set, misswords[i]))
 159                         abort();
 160         }
 161         stop = time_now();
 162         printf(" %zu ns\n", normalize(&start, &stop, num));
 163
 164         printf("#10: Lookup after half-change (miss): ");
 165         fflush(stdout);
 166         start = time_now();
 167         for (i = 0; i < num; i+=2)
 168                 if (strset_test(&set, words[i]))
 169                         abort();
 170         for (i = 1; i < num; i+=2) {
 171                 if (strset_test(&set, misswords[i]))
 172                         abort();
 173         }
 174         stop = time_now();
 175         printf(" %zu ns\n", normalize(&start, &stop, num));
 176
 177         /* Hashtables with delete markers can fill with markers over time.
 178          * so do some changes to see how it operates in long-term. */
 179         printf("#11: Churn 1: ");
 180         start = time_now();
 181         for (j = 0; j < num; j+=2) {
 182                 if (!strset_clear(&set, misswords[j]))
 183                         abort();
 184                 if (!strset_set(&set, words[j]))
 185                         abort();
 186         }
 187         stop = time_now();
 188         printf(" %zu ns\n", normalize(&start, &stop, num));
 189
 190         printf("#12: Churn 2: ");
 191         start = time_now();
 192         for (j = 1; j < num; j+=2) {
 193                 if (!strset_clear(&set, words[j]))
 194                         abort();
 195                 if (!strset_set(&set, misswords[j]))
 196                         abort();
 197         }
 198         stop = time_now();
 199         printf(" %zu ns\n", normalize(&start, &stop, num));
 200
 201         printf("#13: Churn 3: ");
 202         start = time_now();
 203         for (j = 1; j < num; j+=2) {
 204                 if (!strset_clear(&set, misswords[j]))
 205                         abort();
 206                 if (!strset_set(&set, words[j]))
 207                         abort();
 208         }
 209         stop = time_now();
 210         printf(" %zu ns\n", normalize(&start, &stop, num));
 211
 212         /* Now it's back to normal... */
 213         printf("#14: Post-Churn lookup (match): ");
 214         fflush(stdout);
 215         start = time_now();
 216         for (i = 0; i < num; i++)
 217                 if (!strset_test(&set, words[i]))
 218                         abort();
 219         stop = time_now();
 220         printf(" %zu ns\n", normalize(&start, &stop, num));
 221
 222         printf("#15: Post-Churn lookup (miss): ");
 223         fflush(stdout);
 224         start = time_now();
 225         for (i = 0; i < num; i++) {
 226                 if (strset_test(&set, misswords[i]))
 227                         abort();
 228         }
 229         stop = time_now();
 230         printf(" %zu ns\n", normalize(&start, &stop, num));
 231
 232         /* Lookups in order are very cache-friendly for judy; try random */
 233         printf("#16: Post-Churn lookup (random): ");
 234         fflush(stdout);
 235         start = time_now();
 236         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 237                 if (!strset_test(&set, words[j]))
 238                         abort();
 239         stop = time_now();
 240         printf(" %zu ns\n", normalize(&start, &stop, num));
 241
 242         return 0;
 243 }