8c815699012208a3ac7d3bad146a10e88c7238c9
[ccan] / 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 timespec *start,
36                         const struct timespec *stop,
37                         unsigned int num)
38 {
39         return time_to_nsec(time_divide(time_sub(*stop, *start), num));
40 }
41
42 int main(int argc, char *argv[])
43 {
44         size_t i, j, num;
45         struct timespec start, stop;
46         struct strset set;
47         char **words, **misswords;
48
49         words = strsplit(NULL, grab_file(NULL,
50                                          argv[1] ? argv[1] : "/usr/share/dict/words",
51                                          NULL), "\n");
52         strset_init(&set);
53         num = talloc_array_length(words) - 1;
54         printf("%zu words\n", num);
55
56         /* Append and prepend last char for miss testing. */
57         misswords = talloc_array(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] = talloc_asprintf(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_set(&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_test(&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_test(&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_test(&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_clear(&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_set(&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_clear(&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_set(&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_test(&set, words[i]))
150                         abort();
151         for (i = 0; i < num; i+=2) {
152                 if (!strset_test(&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_test(&set, words[i]))
163                         abort();
164         for (i = 1; i < num; i+=2) {
165                 if (strset_test(&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_clear(&set, misswords[j]))
177                         abort();
178                 if (!strset_set(&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_clear(&set, words[j]))
188                         abort();
189                 if (!strset_set(&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_clear(&set, misswords[j]))
199                         abort();
200                 if (!strset_set(&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_test(&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_test(&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_test(&set, words[j]))
232                         abort();
233         stop = time_now();
234         printf(" %zu ns\n", normalize(&start, &stop, num));
235
236         return 0;
237 }