tools/testing/radix-tree/benchmark.c

   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 }