~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/tools/testing/radix-tree/benchmark.c

Version: ~ [ linux-5.5-rc7 ] ~ [ linux-5.4.13 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.97 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.166 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.210 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.210 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.81 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 
 22 static 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
 32 again:
 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 
 60 static void benchmark_insert(struct radix_tree_root *root,
 61                              unsigned long size, unsigned long step)
 62 {
 63         struct timespec start, finish;
 64         unsigned long index;
 65         long long nsec;
 66 
 67         clock_gettime(CLOCK_MONOTONIC, &start);
 68 
 69         for (index = 0 ; index < size ; index += step)
 70                 item_insert(root, index);
 71 
 72         clock_gettime(CLOCK_MONOTONIC, &finish);
 73 
 74         nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
 75                (finish.tv_nsec - start.tv_nsec);
 76 
 77         printv(2, "Size: %8ld, step: %8ld, insertion: %15lld ns\n",
 78                 size, step, nsec);
 79 }
 80 
 81 static void benchmark_tagging(struct radix_tree_root *root,
 82                              unsigned long size, unsigned long step)
 83 {
 84         struct timespec start, finish;
 85         unsigned long index;
 86         long long nsec;
 87 
 88         clock_gettime(CLOCK_MONOTONIC, &start);
 89 
 90         for (index = 0 ; index < size ; index += step)
 91                 radix_tree_tag_set(root, index, 0);
 92 
 93         clock_gettime(CLOCK_MONOTONIC, &finish);
 94 
 95         nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
 96                (finish.tv_nsec - start.tv_nsec);
 97 
 98         printv(2, "Size: %8ld, step: %8ld, tagging: %17lld ns\n",
 99                 size, step, nsec);
100 }
101 
102 static void benchmark_delete(struct radix_tree_root *root,
103                              unsigned long size, unsigned long step)
104 {
105         struct timespec start, finish;
106         unsigned long index;
107         long long nsec;
108 
109         clock_gettime(CLOCK_MONOTONIC, &start);
110 
111         for (index = 0 ; index < size ; index += step)
112                 item_delete(root, index);
113 
114         clock_gettime(CLOCK_MONOTONIC, &finish);
115 
116         nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
117                (finish.tv_nsec - start.tv_nsec);
118 
119         printv(2, "Size: %8ld, step: %8ld, deletion: %16lld ns\n",
120                 size, step, nsec);
121 }
122 
123 static void benchmark_size(unsigned long size, unsigned long step)
124 {
125         RADIX_TREE(tree, GFP_KERNEL);
126         long long normal, tagged;
127 
128         benchmark_insert(&tree, size, step);
129         benchmark_tagging(&tree, size, step);
130 
131         tagged = benchmark_iter(&tree, true);
132         normal = benchmark_iter(&tree, false);
133 
134         printv(2, "Size: %8ld, step: %8ld, tagged iteration: %8lld ns\n",
135                 size, step, tagged);
136         printv(2, "Size: %8ld, step: %8ld, normal iteration: %8lld ns\n",
137                 size, step, normal);
138 
139         benchmark_delete(&tree, size, step);
140 
141         item_kill_tree(&tree);
142         rcu_barrier();
143 }
144 
145 void benchmark(void)
146 {
147         unsigned long size[] = {1 << 10, 1 << 20, 0};
148         unsigned long step[] = {1, 2, 7, 15, 63, 64, 65,
149                                 128, 256, 512, 12345, 0};
150         int c, s;
151 
152         printv(1, "starting benchmarks\n");
153         printv(1, "RADIX_TREE_MAP_SHIFT = %d\n", RADIX_TREE_MAP_SHIFT);
154 
155         for (c = 0; size[c]; c++)
156                 for (s = 0; step[s]; s++)
157                         benchmark_size(size[c], step[s]);
158 }
159 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp