tools/testing/radix-tree/benchmark.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * benchmark.c:
   4  * Author: Konstantin Khlebnikov <koct9i@gmail.com>
   5  */
   6 #include <linux/radix-tree.h>
   7 #include <linux/slab.h>
   8 #include <linux/errno.h>
   9 #include <time.h>
  10 #include "test.h"
  11
  12 #define NSEC_PER_SEC    1000000000L
  13
  14 static long long benchmark_iter(struct radix_tree_root *root, bool tagged)
  15 {
  16         volatile unsigned long sink = 0;
  17         struct radix_tree_iter iter;
  18         struct timespec start, finish;
  19         long long nsec;
  20         int l, loops = 1;
  21         void **slot;
  22
  23 #ifdef BENCHMARK
  24 again:
  25 #endif
  26         clock_gettime(CLOCK_MONOTONIC, &start);
  27         for (l = 0; l < loops; l++) {
  28                 if (tagged) {
  29                         radix_tree_for_each_tagged(slot, root, &iter, 0, 0)
  30                                 sink ^= (unsigned long)slot;
  31                 } else {
  32                         radix_tree_for_each_slot(slot, root, &iter, 0)
  33                                 sink ^= (unsigned long)slot;
  34                 }
  35         }
  36         clock_gettime(CLOCK_MONOTONIC, &finish);
  37
  38         nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
  39                (finish.tv_nsec - start.tv_nsec);
  40
  41 #ifdef BENCHMARK
  42         if (loops == 1 && nsec * 5 < NSEC_PER_SEC) {
  43                 loops = NSEC_PER_SEC / nsec / 4 + 1;
  44                 goto again;
  45         }
  46 #endif
  47
  48         nsec /= loops;
  49         return nsec;
  50 }
  51
  52 static void benchmark_insert(struct radix_tree_root *root,
  53                              unsigned long size, unsigned long step)
  54 {
  55         struct timespec start, finish;
  56         unsigned long index;
  57         long long nsec;
  58
  59         clock_gettime(CLOCK_MONOTONIC, &start);
  60
  61         for (index = 0 ; index < size ; index += step)
  62                 item_insert(root, index);
  63
  64         clock_gettime(CLOCK_MONOTONIC, &finish);
  65
  66         nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
  67                (finish.tv_nsec - start.tv_nsec);
  68
  69         printv(2, "Size: %8ld, step: %8ld, insertion: %15lld ns\n",
  70                 size, step, nsec);
  71 }
  72
  73 static void benchmark_tagging(struct radix_tree_root *root,
  74                              unsigned long size, unsigned long step)
  75 {
  76         struct timespec start, finish;
  77         unsigned long index;
  78         long long nsec;
  79
  80         clock_gettime(CLOCK_MONOTONIC, &start);
  81
  82         for (index = 0 ; index < size ; index += step)
  83                 radix_tree_tag_set(root, index, 0);
  84
  85         clock_gettime(CLOCK_MONOTONIC, &finish);
  86
  87         nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
  88                (finish.tv_nsec - start.tv_nsec);
  89
  90         printv(2, "Size: %8ld, step: %8ld, tagging: %17lld ns\n",
  91                 size, step, nsec);
  92 }
  93
  94 static void benchmark_delete(struct radix_tree_root *root,
  95                              unsigned long size, unsigned long step)
  96 {
  97         struct timespec start, finish;
  98         unsigned long index;
  99         long long nsec;
 100
 101         clock_gettime(CLOCK_MONOTONIC, &start);
 102
 103         for (index = 0 ; index < size ; index += step)
 104                 item_delete(root, index);
 105
 106         clock_gettime(CLOCK_MONOTONIC, &finish);
 107
 108         nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
 109                (finish.tv_nsec - start.tv_nsec);
 110
 111         printv(2, "Size: %8ld, step: %8ld, deletion: %16lld ns\n",
 112                 size, step, nsec);
 113 }
 114
 115 static void benchmark_size(unsigned long size, unsigned long step)
 116 {
 117         RADIX_TREE(tree, GFP_KERNEL);
 118         long long normal, tagged;
 119
 120         benchmark_insert(&tree, size, step);
 121         benchmark_tagging(&tree, size, step);
 122
 123         tagged = benchmark_iter(&tree, true);
 124         normal = benchmark_iter(&tree, false);
 125
 126         printv(2, "Size: %8ld, step: %8ld, tagged iteration: %8lld ns\n",
 127                 size, step, tagged);
 128         printv(2, "Size: %8ld, step: %8ld, normal iteration: %8lld ns\n",
 129                 size, step, normal);
 130
 131         benchmark_delete(&tree, size, step);
 132
 133         item_kill_tree(&tree);
 134         rcu_barrier();
 135 }
 136
 137 void benchmark(void)
 138 {
 139         unsigned long size[] = {1 << 10, 1 << 20, 0};
 140         unsigned long step[] = {1, 2, 7, 15, 63, 64, 65,
 141                                 128, 256, 512, 12345, 0};
 142         int c, s;
 143
 144         printv(1, "starting benchmarks\n");
 145         printv(1, "RADIX_TREE_MAP_SHIFT = %d\n", RADIX_TREE_MAP_SHIFT);
 146
 147         for (c = 0; size[c]; c++)
 148                 for (s = 0; step[s]; s++)
 149                         benchmark_size(size[c], step[s]);
 150 }