1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Benchmark find_next_bit and related bit operations. 4 * 5 * Copyright 2020 Google LLC. 6 */ 7 #include <stdlib.h> 8 #include "bench.h" 9 #include "../util/stat.h" 10 #include <linux/bitmap.h> 11 #include <linux/bitops.h> 12 #include <linux/time64.h> 13 #include <subcmd/parse-options.h> 14 15 static unsigned int outer_iterations = 5; 16 static unsigned int inner_iterations = 100000; 17 18 static const struct option options[] = { 19 OPT_UINTEGER('i', "outer-iterations", &outer_iterations, 20 "Number of outer iterations used"), 21 OPT_UINTEGER('j', "inner-iterations", &inner_iterations, 22 "Number of inner iterations used"), 23 OPT_END() 24 }; 25 26 static const char *const bench_usage[] = { 27 "perf bench mem find_bit <options>", 28 NULL 29 }; 30 31 static unsigned int accumulator; 32 static unsigned int use_of_val; 33 34 static noinline void workload(int val) 35 { 36 use_of_val += val; 37 accumulator++; 38 } 39 40 #if (defined(__i386__) || defined(__x86_64__)) && defined(__GCC_ASM_FLAG_OUTPUTS__) 41 static bool asm_test_bit(long nr, const unsigned long *addr) 42 { 43 bool oldbit; 44 45 asm volatile("bt %2,%1" 46 : "=@ccc" (oldbit) 47 : "m" (*(unsigned long *)addr), "Ir" (nr) : "memory"); 48 49 return oldbit; 50 } 51 #else 52 #define asm_test_bit test_bit 53 #endif 54 55 static int do_for_each_set_bit(unsigned int num_bits) 56 { 57 unsigned long *to_test = bitmap_zalloc(num_bits); 58 struct timeval start, end, diff; 59 u64 runtime_us; 60 struct stats fb_time_stats, tb_time_stats; 61 double time_average, time_stddev; 62 unsigned int bit, i, j; 63 unsigned int set_bits, skip; 64 65 init_stats(&fb_time_stats); 66 init_stats(&tb_time_stats); 67 68 for (set_bits = 1; set_bits <= num_bits; set_bits <<= 1) { 69 bitmap_zero(to_test, num_bits); 70 skip = num_bits / set_bits; 71 for (i = 0; i < num_bits; i += skip) 72 __set_bit(i, to_test); 73 74 for (i = 0; i < outer_iterations; i++) { 75 #ifndef NDEBUG 76 unsigned int old = accumulator; 77 #endif 78 79 gettimeofday(&start, NULL); 80 for (j = 0; j < inner_iterations; j++) { 81 for_each_set_bit(bit, to_test, num_bits) 82 workload(bit); 83 } 84 gettimeofday(&end, NULL); 85 assert(old + (inner_iterations * set_bits) == accumulator); 86 timersub(&end, &start, &diff); 87 runtime_us = diff.tv_sec * USEC_PER_SEC + diff.tv_usec; 88 update_stats(&fb_time_stats, runtime_us); 89 90 #ifndef NDEBUG 91 old = accumulator; 92 #endif 93 gettimeofday(&start, NULL); 94 for (j = 0; j < inner_iterations; j++) { 95 for (bit = 0; bit < num_bits; bit++) { 96 if (asm_test_bit(bit, to_test)) 97 workload(bit); 98 } 99 } 100 gettimeofday(&end, NULL); 101 assert(old + (inner_iterations * set_bits) == accumulator); 102 timersub(&end, &start, &diff); 103 runtime_us = diff.tv_sec * USEC_PER_SEC + diff.tv_usec; 104 update_stats(&tb_time_stats, runtime_us); 105 } 106 107 printf("%d operations %d bits set of %d bits\n", 108 inner_iterations, set_bits, num_bits); 109 time_average = avg_stats(&fb_time_stats); 110 time_stddev = stddev_stats(&fb_time_stats); 111 printf(" Average for_each_set_bit took: %.3f usec (+- %.3f usec)\n", 112 time_average, time_stddev); 113 time_average = avg_stats(&tb_time_stats); 114 time_stddev = stddev_stats(&tb_time_stats); 115 printf(" Average test_bit loop took: %.3f usec (+- %.3f usec)\n", 116 time_average, time_stddev); 117 118 if (use_of_val == accumulator) /* Try to avoid compiler tricks. */ 119 printf("\n"); 120 } 121 bitmap_free(to_test); 122 return 0; 123 } 124 125 int bench_mem_find_bit(int argc, const char **argv) 126 { 127 int err = 0, i; 128 129 argc = parse_options(argc, argv, options, bench_usage, 0); 130 if (argc) { 131 usage_with_options(bench_usage, options); 132 exit(EXIT_FAILURE); 133 } 134 135 for (i = 1; i <= 2048; i <<= 1) 136 do_for_each_set_bit(i); 137 138 return err; 139 } 140