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