]>
git.proxmox.com Git - mirror_ubuntu-zesty-kernel.git/blob - tools/testing/radix-tree/benchmark.c
3 * Author: Konstantin Khlebnikov <koct9i@gmail.com>
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.
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
14 #include <linux/radix-tree.h>
15 #include <linux/slab.h>
16 #include <linux/errno.h>
20 #define NSEC_PER_SEC 1000000000L
22 static long long benchmark_iter(struct radix_tree_root
*root
, bool tagged
)
24 volatile unsigned long sink
= 0;
25 struct radix_tree_iter iter
;
26 struct timespec start
, finish
;
34 clock_gettime(CLOCK_MONOTONIC
, &start
);
35 for (l
= 0; l
< loops
; l
++) {
37 radix_tree_for_each_tagged(slot
, root
, &iter
, 0, 0)
38 sink
^= (unsigned long)slot
;
40 radix_tree_for_each_slot(slot
, root
, &iter
, 0)
41 sink
^= (unsigned long)slot
;
44 clock_gettime(CLOCK_MONOTONIC
, &finish
);
46 nsec
= (finish
.tv_sec
- start
.tv_sec
) * NSEC_PER_SEC
+
47 (finish
.tv_nsec
- start
.tv_nsec
);
50 if (loops
== 1 && nsec
* 5 < NSEC_PER_SEC
) {
51 loops
= NSEC_PER_SEC
/ nsec
/ 4 + 1;
60 static void benchmark_size(unsigned long size
, unsigned long step
, int order
)
62 RADIX_TREE(tree
, GFP_KERNEL
);
63 long long normal
, tagged
;
66 for (index
= 0 ; index
< size
; index
+= step
) {
67 item_insert_order(&tree
, index
, order
);
68 radix_tree_tag_set(&tree
, index
, 0);
71 tagged
= benchmark_iter(&tree
, true);
72 normal
= benchmark_iter(&tree
, false);
74 printf("Size %ld, step %6ld, order %d tagged %10lld ns, normal %10lld ns\n",
75 size
, step
, order
, tagged
, normal
);
77 item_kill_tree(&tree
);
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};
88 printf("starting benchmarks\n");
89 printf("RADIX_TREE_MAP_SHIFT = %d\n", RADIX_TREE_MAP_SHIFT
);
91 for (c
= 0; size
[c
]; c
++)
92 for (s
= 0; step
[s
]; s
++)
93 benchmark_size(size
[c
], step
[s
], 0);
95 for (c
= 0; size
[c
]; c
++)
96 for (s
= 0; step
[s
]; s
++)
97 benchmark_size(size
[c
], step
[s
] << 9, 9);