140 lines · c
1// SPDX-License-Identifier: GPL-2.02/*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 15static unsigned int outer_iterations = 5;16static unsigned int inner_iterations = 100000;17 18static 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 26static const char *const bench_usage[] = {27 "perf bench mem find_bit <options>",28 NULL29};30 31static unsigned int accumulator;32static unsigned int use_of_val;33 34static 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__)41static 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#else52#define asm_test_bit test_bit53#endif54 55static 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 NDEBUG76 unsigned int old = accumulator;77#endif78 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 NDEBUG91 old = accumulator;92#endif93 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 125int 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