tdb2: more stats
[ccan] / ccan / btree / test / run-benchmark.c
1 /* Include the main header first, to test it works */
2 #include <ccan/btree/btree.h>
3 /* Include the C files directly. */
4 #include <ccan/btree/btree.c>
5 #include <ccan/tap/tap.h>
6
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10
11 uint32_t rand32_state = 0;
12
13 /*
14  * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
15  * Uses the BCPL linear congruential generator method.
16  */
17 static uint32_t rand32(void)
18 {
19         rand32_state *= (uint32_t)0x7FF8A3ED;
20         rand32_state += (uint32_t)0x2AA01D31;
21         return rand32_state;
22 }
23
24 static void scramble(void *base, size_t nmemb, size_t size)
25 {
26         char *i = base;
27         char *o;
28         size_t sd;
29         for (;nmemb>1;nmemb--) {
30                 o = i + size*(rand32()%nmemb);
31                 for (sd=size;sd--;) {
32                         char tmp = *o;
33                         *o++ = *i;
34                         *i++ = tmp;
35                 }
36         }
37 }
38
39 struct test_item {
40         size_t key;
41         uint32_t value;
42 };
43
44 /* For ordering a btree of test_item pointers. */
45 static btree_search_implement (
46         order_by_key,
47         const struct test_item *,
48         ,
49         a == b,
50         a < b
51 )
52
53 /* For qsorting an array of test_item pointers. */
54 static int compare_test_item(const void *ap, const void *bp)
55 {
56         const struct test_item *a = *(const struct test_item * const*)ap;
57         const struct test_item *b = *(const struct test_item * const*)bp;
58         if (a == b)
59                 return 0;
60         if (a < b)
61                 return -1;
62         return 1;
63 }
64
65 /*
66  * If lr == 0, make sure iter points to the item given.
67  * If lr == 1, make sure iter points to after the item given.
68  */
69 static int check_iter(btree_iterator iter_orig, const void *item, int lr)
70 {
71         btree_iterator iter = {*iter_orig};
72         if (iter->item != item)
73                 return 0;
74         if (lr) {
75                 if (!btree_prev(iter))
76                         return 0;
77         } else {
78                 if (!btree_deref(iter))
79                         return 0;
80         }
81         if (iter->item != item)
82                 return 0;
83         if (iter->node->item[iter->k] != iter->item)
84                 return 0;
85         
86         return 1;
87 }
88
89 /*
90  * Returns 1 on insert, 0 on duplicate,
91  * -1 on bad iterator returned by find, and
92  * -2 on bad iterator returned by insert.
93  */
94 static int insert_test_item(struct btree *btree, struct test_item *item)
95 {
96         btree_iterator iter;
97         int lr;
98         
99         /* Find the first or last matching item, randomly choosing between the two. */
100         lr = rand32() & 1;
101         if (btree_find_lr(btree, item, iter, lr)) {
102                 if (!check_iter(iter, item, lr))
103                         return -1;
104                 return 0;
105         }
106         
107         btree_insert_at(iter, item);
108         
109         if (iter->item != item)
110                 return -2;
111         
112         return 1;
113 }
114
115 /*
116  * Returns 1 on remove, 0 on missing,
117  * -1 on bad iterator returned by find, and
118  * -2 on bad iterator returned by remove.
119  */
120 static int remove_test_item(struct btree *btree, struct test_item *item)
121 {
122         btree_iterator iter;
123         
124         if (!btree_find(btree, item, iter))
125                 return 0;
126         
127         if (!check_iter(iter, item, 0))
128                 return -1;
129         
130         btree_remove_at(iter);
131         
132         if (iter->item != item)
133                 return -2;
134         
135         return 1;
136 }
137
138 static struct {
139         size_t success;
140         
141         size_t excess;
142         size_t duplicate;
143         size_t missing;
144         size_t incorrect;
145         size_t failed;
146         
147         size_t bad_iter_find;
148         size_t bad_iter_insert;
149         size_t bad_iter_remove;
150         size_t bad_iter_next;
151 } stats;
152
153 static void clear_stats(void) {
154         memset(&stats, 0, sizeof(stats));
155 }
156
157 static int print_stats(const char *success_label, size_t expected_success) {
158         int failed = 0;
159         
160         printf("      %s:  \t%zu\n", success_label, stats.success);
161         if (stats.success != expected_success)
162                 failed = 1;
163         
164         if (stats.excess)
165                 failed = 1, printf("      Excess:     \t%zu\n", stats.excess);
166         if (stats.duplicate)
167                 failed = 1, printf("      Duplicate:  \t%zu\n", stats.duplicate);
168         if (stats.missing)
169                 failed = 1, printf("      Missing:    \t%zu\n", stats.missing);
170         if (stats.incorrect)
171                 failed = 1, printf("      Incorrect:  \t%zu\n", stats.incorrect);
172         if (stats.failed)
173                 failed = 1, printf("      Failed:     \t%zu\n", stats.failed);
174         
175         if (stats.bad_iter_find || stats.bad_iter_insert ||
176             stats.bad_iter_remove || stats.bad_iter_next) {
177                 failed = 1;
178                 printf("      Bad iterators yielded by:\n");
179                 if (stats.bad_iter_find)
180                         printf("          btree_find_lr(): %zu\n", stats.bad_iter_find);
181                 if (stats.bad_iter_insert)
182                         printf("          btree_insert_at(): %zu\n", stats.bad_iter_insert);
183                 if (stats.bad_iter_remove)
184                         printf("          btree_remove_at(): %zu\n", stats.bad_iter_remove);
185                 if (stats.bad_iter_next)
186                         printf("          btree_next(): %zu\n", stats.bad_iter_next);
187         }
188         
189         return !failed;
190 }
191
192 static void benchmark(size_t max_per_trial, size_t round_count, int random_counts)
193 {
194         struct test_item **test_item;
195         struct test_item *test_item_array;
196         size_t i, count;
197         size_t round = 0;
198         
199         test_item = malloc(max_per_trial * sizeof(*test_item));
200         test_item_array = malloc(max_per_trial * sizeof(*test_item_array));
201         
202         if (!test_item || !test_item_array) {
203                 fail("Not enough memory for %zu keys per trial\n",
204                         max_per_trial);
205                 return;
206         }
207         
208         /* Initialize test_item pointers. */
209         for (i=0; i<max_per_trial; i++)
210                 test_item[i] = &test_item_array[i];
211         
212         /*
213          * If round_count is not zero, run round_count trials.
214          * Otherwise, run forever.
215          */
216         for (round = 1; round_count==0 || round <= round_count; round++) {
217                 struct btree *btree;
218                 btree_iterator iter;
219                 
220                 printf("Round %zu\n", round);
221                 
222                 if (random_counts)
223                         count = rand32() % (max_per_trial+1);
224                 else
225                         count = max_per_trial;
226                 
227                 /*
228                  * Initialize test items by giving them sequential keys and
229                  * random values. Scramble them so the order of insertion
230                  * will be random.
231                  */
232                 for (i=0; i<count; i++) {
233                         test_item[i]->key = i;
234                         test_item[i]->value = rand32();
235                 }
236                 scramble(test_item, count, sizeof(*test_item));
237                 
238                 btree = btree_new(order_by_key);
239                 
240                 clear_stats();
241                 printf("   Inserting %zu items...\n", count);
242                 for (i=0; i<count; i++) {
243                         switch (insert_test_item(btree, test_item[i])) {
244                                 case 1: stats.success++; break;
245                                 case 0: stats.duplicate++; break;
246                                 case -1: stats.bad_iter_find++; break;
247                                 case -2: stats.bad_iter_insert++; break;
248                                 default: stats.failed++; break;
249                         }
250                 }
251                 ok1(print_stats("Inserted", count));
252                 
253                 scramble(test_item, count, sizeof(*test_item));
254                 
255                 printf("   Finding %zu items...\n", count);
256                 clear_stats();
257                 for (i=0; i<count; i++) {
258                         int lr = rand32() & 1;
259                         
260                         if (!btree_find_lr(btree, test_item[i], iter, lr)) {
261                                 stats.missing++;
262                                 continue;
263                         }
264                         
265                         if (!check_iter(iter, test_item[i], lr)) {
266                                 stats.bad_iter_find++;
267                                 continue;
268                         }
269                         
270                         stats.success++;
271                 }
272                 ok1(print_stats("Retrieved", count));
273                 
274                 qsort(test_item, count, sizeof(*test_item), compare_test_item);
275                 
276                 printf("   Traversing forward through %zu items...\n", count);
277                 clear_stats();
278                 i = 0;
279                 for (btree_begin(btree, iter); btree_next(iter);) {
280                         if (i >= count) {
281                                 stats.excess++;
282                                 continue;
283                         }
284                         
285                         if (iter->item == test_item[i])
286                                 stats.success++;
287                         else
288                                 stats.incorrect++;
289                         
290                         i++;
291                 }
292                 ok1(print_stats("Retrieved", count));
293                 
294                 printf("   Traversing backward through %zu items...\n", count);
295                 clear_stats();
296                 i = count;
297                 for (btree_end(btree, iter); btree_prev(iter);) {
298                         if (!i) {
299                                 stats.excess++;
300                                 continue;
301                         }
302                         i--;
303                         
304                         if (iter->item == test_item[i])
305                                 stats.success++;
306                         else
307                                 stats.incorrect++;
308                 }
309                 ok1(print_stats("Retrieved", count));
310                 
311                 ok1(btree->count == count);
312                 
313                 //static int remove_test_item(struct btree *btree, struct test_item *item);
314                 scramble(test_item, count, sizeof(*test_item));
315                 
316                 printf("   Deleting %zu items...\n", count);
317                 clear_stats();
318                 for (i=0; i<count; i++) {
319                         int s = remove_test_item(btree, test_item[i]);
320                         if (s != 1)
321                                 printf("remove_test_item failed\n");
322                         switch (s) {
323                                 case 1: stats.success++; break;
324                                 case 0: stats.missing++; break;
325                                 case -1: stats.bad_iter_find++; break;
326                                 case -2: stats.bad_iter_remove++; break;
327                                 default: stats.failed++; break;
328                         }
329                 }
330                 ok1(btree->count == 0);
331                 ok1(print_stats("Deleted", count));
332                 ok1(btree->root->depth == 0 && btree->root->count == 0);
333                 
334                 btree_delete(btree);
335         }
336         
337         free(test_item);
338         free(test_item_array);
339 }
340
341 int main(void)
342 {
343         plan_tests(32);
344         
345         benchmark(300000, 4, 0);
346         
347         return exit_status();
348 }