]> git.ozlabs.org Git - ccan/blob - ccan/jmap/tools/speed.c
htable: push capacity limit from 66 to 75%
[ccan] / ccan / jmap / tools / speed.c
1 /* Simple speed tests for jmap. */
2 #include <ccan/jmap/jmap_type.h>
3 #include <ccan/jmap/jmap.c>
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <time.h>
7 #include <unistd.h>
8 #include <sys/time.h>
9
10 struct object {
11         /* Some contents. Doubles as consistency check. */
12         struct object *self;
13 };
14
15 /* Nanoseconds per operation */
16 static size_t normalize(const struct timeval *start,
17                         const struct timeval *stop,
18                         unsigned int num)
19 {
20         struct timeval diff;
21
22         timersub(stop, start, &diff);
23
24         /* Floating point is more accurate here. */
25         return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
26                 / num * 1000;
27 }
28
29 JMAP_DEFINE_UINTIDX_TYPE(struct object, obj);
30
31 int main(int argc, char *argv[])
32 {
33         struct object *objs;
34         size_t i, j, num;
35         struct timeval start, stop;
36         struct jmap_obj *jmap;
37
38         num = argv[1] ? atoi(argv[1]) : 1000000;
39         objs = calloc(num, sizeof(objs[0]));
40
41         for (i = 0; i < num; i++) {
42                 objs[i].self = &objs[i];
43         }
44
45         jmap = jmap_obj_new();
46
47         printf("Initial insert: ");
48         fflush(stdout);
49         gettimeofday(&start, NULL);
50         for (i = 0; i < num; i++)
51                 jmap_obj_add(jmap, i, objs[i].self);
52         gettimeofday(&stop, NULL);
53         printf(" %zu ns\n", normalize(&start, &stop, num));
54
55         printf("Initial lookup (match): ");
56         fflush(stdout);
57         gettimeofday(&start, NULL);
58         for (i = 0; i < num; i++)
59                 if (jmap_obj_get(jmap, i)->self != objs[i].self)
60                         abort();
61         gettimeofday(&stop, NULL);
62         printf(" %zu ns\n", normalize(&start, &stop, num));
63
64         printf("Initial lookup (miss): ");
65         fflush(stdout);
66         gettimeofday(&start, NULL);
67         for (i = 0; i < num; i++)
68                 if (jmap_obj_get(jmap, i+num))
69                         abort();
70         gettimeofday(&stop, NULL);
71         printf(" %zu ns\n", normalize(&start, &stop, num));
72
73         /* Lookups in order are very cache-friendly for judy; try random */
74         printf("Initial lookup (random): ");
75         fflush(stdout);
76         gettimeofday(&start, NULL);
77         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
78                 if (jmap_obj_get(jmap, j)->self != &objs[j])
79                         abort();
80         gettimeofday(&stop, NULL);
81         printf(" %zu ns\n", normalize(&start, &stop, num));
82
83         printf("Initial delete all: ");
84         fflush(stdout);
85         gettimeofday(&start, NULL);
86         for (i = 0; i < num; i++)
87                 jmap_obj_del(jmap, i);
88         gettimeofday(&stop, NULL);
89         printf(" %zu ns\n", normalize(&start, &stop, num));
90
91         printf("Initial re-inserting: ");
92         fflush(stdout);
93         gettimeofday(&start, NULL);
94         for (i = 0; i < num; i++)
95                 jmap_obj_add(jmap, i, objs[i].self);
96         gettimeofday(&stop, NULL);
97         printf(" %zu ns\n", normalize(&start, &stop, num));
98
99         printf("Deleting first half: ");
100         fflush(stdout);
101         gettimeofday(&start, NULL);
102         for (i = 0; i < num; i+=2)
103                 jmap_obj_del(jmap, i);
104         gettimeofday(&stop, NULL);
105         printf(" %zu ns\n", normalize(&start, &stop, num));
106
107         printf("Adding (a different) half: ");
108         fflush(stdout);
109
110         gettimeofday(&start, NULL);
111         for (i = 0; i < num; i+=2)
112                 jmap_obj_add(jmap, num+i, objs[i].self);
113         gettimeofday(&stop, NULL);
114         printf(" %zu ns\n", normalize(&start, &stop, num));
115
116         printf("Lookup after half-change (match): ");
117         fflush(stdout);
118         gettimeofday(&start, NULL);
119         for (i = 1; i < num; i+=2)
120                 if (jmap_obj_get(jmap, i)->self != objs[i].self)
121                         abort();
122         for (i = 0; i < num; i+=2)
123                 if (jmap_obj_get(jmap, i+num)->self != objs[i].self)
124                         abort();
125         gettimeofday(&stop, NULL);
126         printf(" %zu ns\n", normalize(&start, &stop, num));
127
128         printf("Lookup after half-change(miss): ");
129         fflush(stdout);
130         gettimeofday(&start, NULL);
131         for (i = 0; i < num; i++)
132                 if (jmap_obj_get(jmap, i+num*2))
133                         abort();
134         gettimeofday(&stop, NULL);
135         printf(" %zu ns\n", normalize(&start, &stop, num));
136
137         /* Hashtables with delete markers can fill with markers over time.
138          * so do some changes to see how it operates in long-term. */
139         printf("Details: churning first time\n");
140         for (i = 1; i < num; i+=2) {
141                 if (!jmap_obj_del(jmap, i))
142                         abort();
143                 jmap_obj_add(jmap, i, objs[i].self);
144         }
145         for (i = 0; i < num; i+=2) {
146                 if (!jmap_obj_del(jmap, i+num))
147                         abort();
148                 jmap_obj_add(jmap, i, objs[i].self);
149         }
150         for (i = 1; i < 5; i++) {
151                 printf("Churning %s time: ",
152                        i == 1 ? "second"
153                        : i == 2 ? "third"
154                        : i == 3 ? "fourth"
155                        : "fifth");
156                 fflush(stdout);
157                 gettimeofday(&start, NULL);
158                 for (j = 0; j < num; j++) {
159                         if (!jmap_obj_del(jmap, num*(i-1)+j))
160                                 abort();
161                         jmap_obj_add(jmap, num*i+j, &objs[j]);
162                 }
163                 gettimeofday(&stop, NULL);
164                 printf(" %zu ns\n", normalize(&start, &stop, num));
165         }
166
167         /* Spread out the keys more to try to make it harder. */
168         printf("Details: reinserting with spread\n");
169         for (i = 0; i < num; i++) {
170                 if (!jmap_obj_del(jmap, num*4 + i))
171                         abort();
172                 jmap_obj_add(jmap, num * 5 + i * 9, objs[i].self);
173         }
174
175         if (jmap_obj_popcount(jmap, 0, -1) != num)
176                 abort();
177
178         printf("Lookup after churn & spread (match): ");
179         fflush(stdout);
180         gettimeofday(&start, NULL);
181         for (i = 0; i < num; i++)
182                 if (jmap_obj_get(jmap, num * 5 + i * 9)->self != objs[i].self) {
183                         printf("i  =%u\n", i);
184                         abort();
185                 }
186         gettimeofday(&stop, NULL);
187         printf(" %zu ns\n", normalize(&start, &stop, num));
188
189         printf("Lookup after churn & spread (miss): ");
190         fflush(stdout);
191         gettimeofday(&start, NULL);
192         for (i = 0; i < num; i++)
193                 if (jmap_obj_get(jmap, num * 6 + i * 9))
194                         abort();
195         gettimeofday(&stop, NULL);
196         printf(" %zu ns\n", normalize(&start, &stop, num));
197
198         printf("Lookup after churn & spread (random): ");
199         fflush(stdout);
200         gettimeofday(&start, NULL);
201         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
202                 if (jmap_obj_get(jmap, num * 5 + j * 9)->self != &objs[j])
203                         abort();
204         gettimeofday(&stop, NULL);
205         printf(" %zu ns\n", normalize(&start, &stop, num));
206
207         printf("Lookup after churn & spread (half-random): ");
208         fflush(stdout);
209         gettimeofday(&start, NULL);
210         for (i = 0, j = 0; i < num/2; i++, j = (j + 10007) % num) {
211                 if (jmap_obj_get(jmap, num * 5 + j * 9)->self != &objs[j])
212                         abort();
213                 if (jmap_obj_get(jmap, num * 5 + (j + 1) * 9)->self != &objs[j+1])
214                         abort();
215         }
216         gettimeofday(&stop, NULL);
217         printf(" %zu ns\n", normalize(&start, &stop, num));
218
219         printf("Deleting half after churn & spread: ");
220         fflush(stdout);
221         gettimeofday(&start, NULL);
222         for (i = 0; i < num; i+=2)
223                 jmap_obj_del(jmap, num * 5 + i * 9);
224         gettimeofday(&stop, NULL);
225         printf(" %zu ns\n", normalize(&start, &stop, num));
226
227         printf("Adding (a different) half after churn & spread: ");
228         fflush(stdout);
229
230         gettimeofday(&start, NULL);
231         for (i = 0; i < num; i+=2)
232                 jmap_obj_add(jmap, num * 6 + i * 9, objs[i].self);
233         gettimeofday(&stop, NULL);
234         printf(" %zu ns\n", normalize(&start, &stop, num));
235
236         return 0;
237 }