git.ozlabs.org Git - ccan/blob - 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/tal/str/str.h>
  23 #include <ccan/tal/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 timeabs *start,
  36                         const struct timeabs *stop,
  37                         unsigned int num)
  38 {
  39         return time_to_nsec(time_divide(time_between(*stop, *start), num));
  40 }
  41
  42 int main(int argc, char *argv[])
  43 {
  44         size_t i, j, num;
  45         struct timeabs start, stop;
  46         struct strset set;
  47         char **words, **misswords;
  48
  49         words = tal_strsplit(NULL, grab_file(NULL,
  50                                              argv[1] ? argv[1] : "/usr/share/dict/words"),
  51                              "\n", STR_NO_EMPTY);
  52         strset_init(&set);
  53         num = tal_count(words) - 1;
  54         printf("%zu words\n", num);
  55
  56         /* Append and prepend last char for miss testing. */
  57         misswords = tal_arr(words, char *, num);
  58         for (i = 0; i < num; i++) {
  59                 char lastc;
  60                 if (strlen(words[i]))
  61                         lastc = words[i][strlen(words[i])-1];
  62                 else
  63                         lastc = 'z';
  64                 misswords[i] = tal_fmt(misswords, "%c%s%c%c",
  65                                        lastc, words[i], lastc, lastc);
  66         }
  67
  68         printf("#01: Initial insert: ");
  69         fflush(stdout);
  70         start = time_now();
  71         for (i = 0; i < num; i++)
  72                 strset_add(&set, words[i]);
  73         stop = time_now();
  74         printf(" %zu ns\n", normalize(&start, &stop, num));
  75
  76 #if 0
  77         printf("Nodes allocated: %zu (%zu bytes)\n",
  78                allocated, allocated * sizeof(critbit0_node));
  79 #endif
  80
  81         printf("#02: Initial lookup (match): ");
  82         fflush(stdout);
  83         start = time_now();
  84         for (i = 0; i < num; i++)
  85                 if (!strset_get(&set, words[i]))
  86                         abort();
  87         stop = time_now();
  88         printf(" %zu ns\n", normalize(&start, &stop, num));
  89
  90         printf("#03: Initial lookup (miss): ");
  91         fflush(stdout);
  92         start = time_now();
  93         for (i = 0; i < num; i++) {
  94                 if (strset_get(&set, misswords[i]))
  95                         abort();
  96         }
  97         stop = time_now();
  98         printf(" %zu ns\n", normalize(&start, &stop, num));
  99
 100         /* Lookups in order are very cache-friendly for judy; try random */
 101         printf("#04: Initial lookup (random): ");
 102         fflush(stdout);
 103         start = time_now();
 104         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 105                 if (!strset_get(&set, words[j]))
 106                         abort();
 107         stop = time_now();
 108         printf(" %zu ns\n", normalize(&start, &stop, num));
 109
 110         printf("#05: Initial delete all: ");
 111         fflush(stdout);
 112         start = time_now();
 113         for (i = 0; i < num; i++)
 114                 if (!strset_del(&set, words[i]))
 115                         abort();
 116         stop = time_now();
 117         printf(" %zu ns\n", normalize(&start, &stop, num));
 118
 119         printf("#06: Initial re-inserting: ");
 120         fflush(stdout);
 121         start = time_now();
 122         for (i = 0; i < num; i++)
 123                 strset_add(&set, words[i]);
 124         stop = time_now();
 125         printf(" %zu ns\n", normalize(&start, &stop, num));
 126
 127         printf("#07: Deleting first half: ");
 128         fflush(stdout);
 129         start = time_now();
 130         for (i = 0; i < num; i+=2)
 131                 if (!strset_del(&set, words[i]))
 132                         abort();
 133         stop = time_now();
 134         printf(" %zu ns\n", normalize(&start, &stop, num));
 135
 136         printf("#08: Adding (a different) half: ");
 137         fflush(stdout);
 138
 139         start = time_now();
 140         for (i = 0; i < num; i+=2)
 141                 strset_add(&set, misswords[i]);
 142         stop = time_now();
 143         printf(" %zu ns\n", normalize(&start, &stop, num));
 144
 145         printf("#09: Lookup after half-change (match): ");
 146         fflush(stdout);
 147         start = time_now();
 148         for (i = 1; i < num; i+=2)
 149                 if (!strset_get(&set, words[i]))
 150                         abort();
 151         for (i = 0; i < num; i+=2) {
 152                 if (!strset_get(&set, misswords[i]))
 153                         abort();
 154         }
 155         stop = time_now();
 156         printf(" %zu ns\n", normalize(&start, &stop, num));
 157
 158         printf("#10: Lookup after half-change (miss): ");
 159         fflush(stdout);
 160         start = time_now();
 161         for (i = 0; i < num; i+=2)
 162                 if (strset_get(&set, words[i]))
 163                         abort();
 164         for (i = 1; i < num; i+=2) {
 165                 if (strset_get(&set, misswords[i]))
 166                         abort();
 167         }
 168         stop = time_now();
 169         printf(" %zu ns\n", normalize(&start, &stop, num));
 170
 171         /* Hashtables with delete markers can fill with markers over time.
 172          * so do some changes to see how it operates in long-term. */
 173         printf("#11: Churn 1: ");
 174         start = time_now();
 175         for (j = 0; j < num; j+=2) {
 176                 if (!strset_del(&set, misswords[j]))
 177                         abort();
 178                 if (!strset_add(&set, words[j]))
 179                         abort();
 180         }
 181         stop = time_now();
 182         printf(" %zu ns\n", normalize(&start, &stop, num));
 183
 184         printf("#12: Churn 2: ");
 185         start = time_now();
 186         for (j = 1; j < num; j+=2) {
 187                 if (!strset_del(&set, words[j]))
 188                         abort();
 189                 if (!strset_add(&set, misswords[j]))
 190                         abort();
 191         }
 192         stop = time_now();
 193         printf(" %zu ns\n", normalize(&start, &stop, num));
 194
 195         printf("#13: Churn 3: ");
 196         start = time_now();
 197         for (j = 1; j < num; j+=2) {
 198                 if (!strset_del(&set, misswords[j]))
 199                         abort();
 200                 if (!strset_add(&set, words[j]))
 201                         abort();
 202         }
 203         stop = time_now();
 204         printf(" %zu ns\n", normalize(&start, &stop, num));
 205
 206         /* Now it's back to normal... */
 207         printf("#14: Post-Churn lookup (match): ");
 208         fflush(stdout);
 209         start = time_now();
 210         for (i = 0; i < num; i++)
 211                 if (!strset_get(&set, words[i]))
 212                         abort();
 213         stop = time_now();
 214         printf(" %zu ns\n", normalize(&start, &stop, num));
 215
 216         printf("#15: Post-Churn lookup (miss): ");
 217         fflush(stdout);
 218         start = time_now();
 219         for (i = 0; i < num; i++) {
 220                 if (strset_get(&set, misswords[i]))
 221                         abort();
 222         }
 223         stop = time_now();
 224         printf(" %zu ns\n", normalize(&start, &stop, num));
 225
 226         /* Lookups in order are very cache-friendly for judy; try random */
 227         printf("#16: Post-Churn lookup (random): ");
 228         fflush(stdout);
 229         start = time_now();
 230         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 231                 if (!strset_get(&set, words[j]))
 232                         abort();
 233         stop = time_now();
 234         printf(" %zu ns\n", normalize(&start, &stop, num));
 235
 236         return 0;
 237 }