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