]>
Commit | Line | Data |
---|---|---|
cfa40bcf KK |
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 | ||
0d4a41c1 RS |
20 | #define for_each_index(i, base, order) \ |
21 | for (i = base; i < base + (1 << order); i++) | |
22 | ||
cfa40bcf KK |
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 | ||
0d4a41c1 RS |
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 | ||
cfa40bcf KK |
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; | |
cfa40bcf | 131 | |
0d4a41c1 RS |
132 | benchmark_insert(&tree, size, step, order); |
133 | benchmark_tagging(&tree, size, step, order); | |
cfa40bcf KK |
134 | |
135 | tagged = benchmark_iter(&tree, true); | |
136 | normal = benchmark_iter(&tree, false); | |
137 | ||
0d4a41c1 RS |
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); | |
cfa40bcf KK |
144 | |
145 | item_kill_tree(&tree); | |
146 | rcu_barrier(); | |
147 | } | |
148 | ||
6478581c RS |
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 | ||
54f4d334 RS |
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 | ||
cfa40bcf KK |
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 | ||
73bc029b RS |
240 | printv(1, "starting benchmarks\n"); |
241 | printv(1, "RADIX_TREE_MAP_SHIFT = %d\n", RADIX_TREE_MAP_SHIFT); | |
cfa40bcf KK |
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); | |
6478581c RS |
250 | |
251 | for (c = 0; size[c]; c++) | |
252 | for (s = 0; step[s]; s++) | |
253 | benchmark_split(size[c], step[s]); | |
54f4d334 RS |
254 | |
255 | for (s = 0; step[s]; s++) | |
256 | benchmark_join(step[s]); | |
cfa40bcf | 257 | } |