1/*
 2 * benchmark.c:
 3 * Author: Konstantin Khlebnikov <koct9i@gmail.com>
 4 *
 5 * This program is free software; you can redistribute it and/or modify it
 6 * under the terms and conditions of the GNU General Public License,
 7 * version 2, as published by the Free Software Foundation.
 8 *
 9 * This program is distributed in the hope it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
12 * more details.
13 */
14#include <linux/radix-tree.h>
15#include <linux/slab.h>
16#include <linux/errno.h>
17#include <time.h>
18#include "test.h"
19
20#define NSEC_PER_SEC	1000000000L
21
22static long long benchmark_iter(struct radix_tree_root *root, bool tagged)
23{
24	volatile unsigned long sink = 0;
25	struct radix_tree_iter iter;
26	struct timespec start, finish;
27	long long nsec;
28	int l, loops = 1;
29	void **slot;
30
31#ifdef BENCHMARK
32again:
33#endif
34	clock_gettime(CLOCK_MONOTONIC, &start);
35	for (l = 0; l < loops; l++) {
36		if (tagged) {
37			radix_tree_for_each_tagged(slot, root, &iter, 0, 0)
38				sink ^= (unsigned long)slot;
39		} else {
40			radix_tree_for_each_slot(slot, root, &iter, 0)
41				sink ^= (unsigned long)slot;
42		}
43	}
44	clock_gettime(CLOCK_MONOTONIC, &finish);
45
46	nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
47	       (finish.tv_nsec - start.tv_nsec);
48
49#ifdef BENCHMARK
50	if (loops == 1 && nsec * 5 < NSEC_PER_SEC) {
51		loops = NSEC_PER_SEC / nsec / 4 + 1;
52		goto again;
53	}
54#endif
55
56	nsec /= loops;
57	return nsec;
58}
59
60static void benchmark_size(unsigned long size, unsigned long step, int order)
61{
62	RADIX_TREE(tree, GFP_KERNEL);
63	long long normal, tagged;
64	unsigned long index;
65
66	for (index = 0 ; index < size ; index += step) {
67		item_insert_order(&tree, index, order);
68		radix_tree_tag_set(&tree, index, 0);
69	}
70
71	tagged = benchmark_iter(&tree, true);
72	normal = benchmark_iter(&tree, false);
73
74	printf("Size %ld, step %6ld, order %d tagged %10lld ns, normal %10lld ns\n",
75		size, step, order, tagged, normal);
76
77	item_kill_tree(&tree);
78	rcu_barrier();
79}
80
81void benchmark(void)
82{
83	unsigned long size[] = {1 << 10, 1 << 20, 0};
84	unsigned long step[] = {1, 2, 7, 15, 63, 64, 65,
85				128, 256, 512, 12345, 0};
86	int c, s;
87
88	printf("starting benchmarks\n");
89	printf("RADIX_TREE_MAP_SHIFT = %d\n", RADIX_TREE_MAP_SHIFT);
90
91	for (c = 0; size[c]; c++)
92		for (s = 0; step[s]; s++)
93			benchmark_size(size[c], step[s], 0);
94
95	for (c = 0; size[c]; c++)
96		for (s = 0; step[s]; s++)
97			benchmark_size(size[c], step[s] << 9, 9);
98}