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 for_each_index(i, base, order) \
21 	        for (i = base; i < base + (1 << order); i++)
22 
23 #define NSEC_PER_SEC	1000000000L
24 
25 static long long benchmark_iter(struct radix_tree_root *root, bool tagged)
26 {
27 	volatile unsigned long sink = 0;
28 	struct radix_tree_iter iter;
29 	struct timespec start, finish;
30 	long long nsec;
31 	int l, loops = 1;
32 	void **slot;
33 
34 #ifdef BENCHMARK
35 again:
36 #endif
37 	clock_gettime(CLOCK_MONOTONIC, &start);
38 	for (l = 0; l < loops; l++) {
39 		if (tagged) {
40 			radix_tree_for_each_tagged(slot, root, &iter, 0, 0)
41 				sink ^= (unsigned long)slot;
42 		} else {
43 			radix_tree_for_each_slot(slot, root, &iter, 0)
44 				sink ^= (unsigned long)slot;
45 		}
46 	}
47 	clock_gettime(CLOCK_MONOTONIC, &finish);
48 
49 	nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
50 	       (finish.tv_nsec - start.tv_nsec);
51 
52 #ifdef BENCHMARK
53 	if (loops == 1 && nsec * 5 < NSEC_PER_SEC) {
54 		loops = NSEC_PER_SEC / nsec / 4 + 1;
55 		goto again;
56 	}
57 #endif
58 
59 	nsec /= loops;
60 	return nsec;
61 }
62 
63 static void benchmark_insert(struct radix_tree_root *root,
64 			     unsigned long size, unsigned long step, int order)
65 {
66 	struct timespec start, finish;
67 	unsigned long index;
68 	long long nsec;
69 
70 	clock_gettime(CLOCK_MONOTONIC, &start);
71 
72 	for (index = 0 ; index < size ; index += step)
73 		item_insert_order(root, index, order);
74 
75 	clock_gettime(CLOCK_MONOTONIC, &finish);
76 
77 	nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
78 	       (finish.tv_nsec - start.tv_nsec);
79 
80 	printv(2, "Size: %8ld, step: %8ld, order: %d, insertion: %15lld ns\n",
81 		size, step, order, nsec);
82 }
83 
84 static void benchmark_tagging(struct radix_tree_root *root,
85 			     unsigned long size, unsigned long step, int order)
86 {
87 	struct timespec start, finish;
88 	unsigned long index;
89 	long long nsec;
90 
91 	clock_gettime(CLOCK_MONOTONIC, &start);
92 
93 	for (index = 0 ; index < size ; index += step)
94 		radix_tree_tag_set(root, index, 0);
95 
96 	clock_gettime(CLOCK_MONOTONIC, &finish);
97 
98 	nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
99 	       (finish.tv_nsec - start.tv_nsec);
100 
101 	printv(2, "Size: %8ld, step: %8ld, order: %d, tagging: %17lld ns\n",
102 		size, step, order, nsec);
103 }
104 
105 static void benchmark_delete(struct radix_tree_root *root,
106 			     unsigned long size, unsigned long step, int order)
107 {
108 	struct timespec start, finish;
109 	unsigned long index, i;
110 	long long nsec;
111 
112 	clock_gettime(CLOCK_MONOTONIC, &start);
113 
114 	for (index = 0 ; index < size ; index += step)
115 		for_each_index(i, index, order)
116 			item_delete(root, i);
117 
118 	clock_gettime(CLOCK_MONOTONIC, &finish);
119 
120 	nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
121 	       (finish.tv_nsec - start.tv_nsec);
122 
123 	printv(2, "Size: %8ld, step: %8ld, order: %d, deletion: %16lld ns\n",
124 		size, step, order, nsec);
125 }
126 
127 static void benchmark_size(unsigned long size, unsigned long step, int order)
128 {
129 	RADIX_TREE(tree, GFP_KERNEL);
130 	long long normal, tagged;
131 
132 	benchmark_insert(&tree, size, step, order);
133 	benchmark_tagging(&tree, size, step, order);
134 
135 	tagged = benchmark_iter(&tree, true);
136 	normal = benchmark_iter(&tree, false);
137 
138 	printv(2, "Size: %8ld, step: %8ld, order: %d, tagged iteration: %8lld ns\n",
139 		size, step, order, tagged);
140 	printv(2, "Size: %8ld, step: %8ld, order: %d, normal iteration: %8lld ns\n",
141 		size, step, order, normal);
142 
143 	benchmark_delete(&tree, size, step, order);
144 
145 	item_kill_tree(&tree);
146 	rcu_barrier();
147 }
148 
149 static long long  __benchmark_split(unsigned long index,
150 				    int old_order, int new_order)
151 {
152 	struct timespec start, finish;
153 	long long nsec;
154 	RADIX_TREE(tree, GFP_ATOMIC);
155 
156 	item_insert_order(&tree, index, old_order);
157 
158 	clock_gettime(CLOCK_MONOTONIC, &start);
159 	radix_tree_split(&tree, index, new_order);
160 	clock_gettime(CLOCK_MONOTONIC, &finish);
161 	nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
162 	       (finish.tv_nsec - start.tv_nsec);
163 
164 	item_kill_tree(&tree);
165 
166 	return nsec;
167 
168 }
169 
170 static void benchmark_split(unsigned long size, unsigned long step)
171 {
172 	int i, j, idx;
173 	long long nsec = 0;
174 
175 
176 	for (idx = 0; idx < size; idx += step) {
177 		for (i = 3; i < 11; i++) {
178 			for (j = 0; j < i; j++) {
179 				nsec += __benchmark_split(idx, i, j);
180 			}
181 		}
182 	}
183 
184 	printv(2, "Size %8ld, step %8ld, split time %10lld ns\n",
185 			size, step, nsec);
186 
187 }
188 
189 static long long  __benchmark_join(unsigned long index,
190 			     unsigned order1, unsigned order2)
191 {
192 	unsigned long loc;
193 	struct timespec start, finish;
194 	long long nsec;
195 	void *item, *item2 = item_create(index + 1, order1);
196 	RADIX_TREE(tree, GFP_KERNEL);
197 
198 	item_insert_order(&tree, index, order2);
199 	item = radix_tree_lookup(&tree, index);
200 
201 	clock_gettime(CLOCK_MONOTONIC, &start);
202 	radix_tree_join(&tree, index + 1, order1, item2);
203 	clock_gettime(CLOCK_MONOTONIC, &finish);
204 	nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
205 		(finish.tv_nsec - start.tv_nsec);
206 
207 	loc = find_item(&tree, item);
208 	if (loc == -1)
209 		free(item);
210 
211 	item_kill_tree(&tree);
212 
213 	return nsec;
214 }
215 
216 static void benchmark_join(unsigned long step)
217 {
218 	int i, j, idx;
219 	long long nsec = 0;
220 
221 	for (idx = 0; idx < 1 << 10; idx += step) {
222 		for (i = 1; i < 15; i++) {
223 			for (j = 0; j < i; j++) {
224 				nsec += __benchmark_join(idx, i, j);
225 			}
226 		}
227 	}
228 
229 	printv(2, "Size %8d, step %8ld, join time %10lld ns\n",
230 			1 << 10, step, nsec);
231 }
232 
233 void benchmark(void)
234 {
235 	unsigned long size[] = {1 << 10, 1 << 20, 0};
236 	unsigned long step[] = {1, 2, 7, 15, 63, 64, 65,
237 				128, 256, 512, 12345, 0};
238 	int c, s;
239 
240 	printv(1, "starting benchmarks\n");
241 	printv(1, "RADIX_TREE_MAP_SHIFT = %d\n", RADIX_TREE_MAP_SHIFT);
242 
243 	for (c = 0; size[c]; c++)
244 		for (s = 0; step[s]; s++)
245 			benchmark_size(size[c], step[s], 0);
246 
247 	for (c = 0; size[c]; c++)
248 		for (s = 0; step[s]; s++)
249 			benchmark_size(size[c], step[s] << 9, 9);
250 
251 	for (c = 0; size[c]; c++)
252 		for (s = 0; step[s]; s++)
253 			benchmark_split(size[c], step[s]);
254 
255 	for (s = 0; step[s]; s++)
256 		benchmark_join(step[s]);
257 }
258