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