testing/radix-tree/benchmark.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * benchmark.c:
0004  * Author: Konstantin Khlebnikov <koct9i@gmail.com>
0005  */
0006 #include <linux/radix-tree.h>
0007 #include <linux/slab.h>
0008 #include <linux/errno.h>
0009 #include <time.h>
0010 #include "test.h"
0011
0012 #define NSEC_PER_SEC    1000000000L
0013
0014 static long long benchmark_iter(struct radix_tree_root *root, bool tagged)
0015 {
0016     volatile unsigned long sink = 0;
0017     struct radix_tree_iter iter;
0018     struct timespec start, finish;
0019     long long nsec;
0020     int l, loops = 1;
0021     void **slot;
0022
0023 #ifdef BENCHMARK
0024 again:
0025 #endif
0026     clock_gettime(CLOCK_MONOTONIC, &start);
0027     for (l = 0; l < loops; l++) {
0028         if (tagged) {
0029             radix_tree_for_each_tagged(slot, root, &iter, 0, 0)
0030                 sink ^= (unsigned long)slot;
0031         } else {
0032             radix_tree_for_each_slot(slot, root, &iter, 0)
0033                 sink ^= (unsigned long)slot;
0034         }
0035     }
0036     clock_gettime(CLOCK_MONOTONIC, &finish);
0037
0038     nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
0039            (finish.tv_nsec - start.tv_nsec);
0040
0041 #ifdef BENCHMARK
0042     if (loops == 1 && nsec * 5 < NSEC_PER_SEC) {
0043         loops = NSEC_PER_SEC / nsec / 4 + 1;
0044         goto again;
0045     }
0046 #endif
0047
0048     nsec /= loops;
0049     return nsec;
0050 }
0051
0052 static void benchmark_insert(struct radix_tree_root *root,
0053                  unsigned long size, unsigned long step)
0054 {
0055     struct timespec start, finish;
0056     unsigned long index;
0057     long long nsec;
0058
0059     clock_gettime(CLOCK_MONOTONIC, &start);
0060
0061     for (index = 0 ; index < size ; index += step)
0062         item_insert(root, index);
0063
0064     clock_gettime(CLOCK_MONOTONIC, &finish);
0065
0066     nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
0067            (finish.tv_nsec - start.tv_nsec);
0068
0069     printv(2, "Size: %8ld, step: %8ld, insertion: %15lld ns\n",
0070         size, step, nsec);
0071 }
0072
0073 static void benchmark_tagging(struct radix_tree_root *root,
0074                  unsigned long size, unsigned long step)
0075 {
0076     struct timespec start, finish;
0077     unsigned long index;
0078     long long nsec;
0079
0080     clock_gettime(CLOCK_MONOTONIC, &start);
0081
0082     for (index = 0 ; index < size ; index += step)
0083         radix_tree_tag_set(root, index, 0);
0084
0085     clock_gettime(CLOCK_MONOTONIC, &finish);
0086
0087     nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
0088            (finish.tv_nsec - start.tv_nsec);
0089
0090     printv(2, "Size: %8ld, step: %8ld, tagging: %17lld ns\n",
0091         size, step, nsec);
0092 }
0093
0094 static void benchmark_delete(struct radix_tree_root *root,
0095                  unsigned long size, unsigned long step)
0096 {
0097     struct timespec start, finish;
0098     unsigned long index;
0099     long long nsec;
0100
0101     clock_gettime(CLOCK_MONOTONIC, &start);
0102
0103     for (index = 0 ; index < size ; index += step)
0104         item_delete(root, index);
0105
0106     clock_gettime(CLOCK_MONOTONIC, &finish);
0107
0108     nsec = (finish.tv_sec - start.tv_sec) * NSEC_PER_SEC +
0109            (finish.tv_nsec - start.tv_nsec);
0110
0111     printv(2, "Size: %8ld, step: %8ld, deletion: %16lld ns\n",
0112         size, step, nsec);
0113 }
0114
0115 static void benchmark_size(unsigned long size, unsigned long step)
0116 {
0117     RADIX_TREE(tree, GFP_KERNEL);
0118     long long normal, tagged;
0119
0120     benchmark_insert(&tree, size, step);
0121     benchmark_tagging(&tree, size, step);
0122
0123     tagged = benchmark_iter(&tree, true);
0124     normal = benchmark_iter(&tree, false);
0125
0126     printv(2, "Size: %8ld, step: %8ld, tagged iteration: %8lld ns\n",
0127         size, step, tagged);
0128     printv(2, "Size: %8ld, step: %8ld, normal iteration: %8lld ns\n",
0129         size, step, normal);
0130
0131     benchmark_delete(&tree, size, step);
0132
0133     item_kill_tree(&tree);
0134     rcu_barrier();
0135 }
0136
0137 void benchmark(void)
0138 {
0139     unsigned long size[] = {1 << 10, 1 << 20, 0};
0140     unsigned long step[] = {1, 2, 7, 15, 63, 64, 65,
0141                 128, 256, 512, 12345, 0};
0142     int c, s;
0143
0144     printv(1, "starting benchmarks\n");
0145     printv(1, "RADIX_TREE_MAP_SHIFT = %d\n", RADIX_TREE_MAP_SHIFT);
0146
0147     for (c = 0; size[c]; c++)
0148         for (s = 0; step[s]; s++)
0149             benchmark_size(size[c], step[s]);
0150 }