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
 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	NULL
 29};
 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#else
 52#define asm_test_bit test_bit
 53#endif
 54
 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 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
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}