perf/bench/find-bit-bench.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Benchmark find_next_bit and related bit operations.
0004  *
0005  * Copyright 2020 Google LLC.
0006  */
0007 #include <stdlib.h>
0008 #include "bench.h"
0009 #include "../util/stat.h"
0010 #include <linux/bitmap.h>
0011 #include <linux/bitops.h>
0012 #include <linux/time64.h>
0013 #include <subcmd/parse-options.h>
0014
0015 static unsigned int outer_iterations = 5;
0016 static unsigned int inner_iterations = 100000;
0017
0018 static const struct option options[] = {
0019     OPT_UINTEGER('i', "outer-iterations", &outer_iterations,
0020         "Number of outer iterations used"),
0021     OPT_UINTEGER('j', "inner-iterations", &inner_iterations,
0022         "Number of inner iterations used"),
0023     OPT_END()
0024 };
0025
0026 static const char *const bench_usage[] = {
0027     "perf bench mem find_bit <options>",
0028     NULL
0029 };
0030
0031 static unsigned int accumulator;
0032 static unsigned int use_of_val;
0033
0034 static noinline void workload(int val)
0035 {
0036     use_of_val += val;
0037     accumulator++;
0038 }
0039
0040 #if (defined(__i386__) || defined(__x86_64__)) && defined(__GCC_ASM_FLAG_OUTPUTS__)
0041 static bool asm_test_bit(long nr, const unsigned long *addr)
0042 {
0043     bool oldbit;
0044
0045     asm volatile("bt %2,%1"
0046              : "=@ccc" (oldbit)
0047              : "m" (*(unsigned long *)addr), "Ir" (nr) : "memory");
0048
0049     return oldbit;
0050 }
0051 #else
0052 #define asm_test_bit test_bit
0053 #endif
0054
0055 static int do_for_each_set_bit(unsigned int num_bits)
0056 {
0057     unsigned long *to_test = bitmap_zalloc(num_bits);
0058     struct timeval start, end, diff;
0059     u64 runtime_us;
0060     struct stats fb_time_stats, tb_time_stats;
0061     double time_average, time_stddev;
0062     unsigned int bit, i, j;
0063     unsigned int set_bits, skip;
0064     unsigned int old;
0065
0066     init_stats(&fb_time_stats);
0067     init_stats(&tb_time_stats);
0068
0069     for (set_bits = 1; set_bits <= num_bits; set_bits <<= 1) {
0070         bitmap_zero(to_test, num_bits);
0071         skip = num_bits / set_bits;
0072         for (i = 0; i < num_bits; i += skip)
0073             set_bit(i, to_test);
0074
0075         for (i = 0; i < outer_iterations; i++) {
0076             old = accumulator;
0077             gettimeofday(&start, NULL);
0078             for (j = 0; j < inner_iterations; j++) {
0079                 for_each_set_bit(bit, to_test, num_bits)
0080                     workload(bit);
0081             }
0082             gettimeofday(&end, NULL);
0083             assert(old + (inner_iterations * set_bits) == accumulator);
0084             timersub(&end, &start, &diff);
0085             runtime_us = diff.tv_sec * USEC_PER_SEC + diff.tv_usec;
0086             update_stats(&fb_time_stats, runtime_us);
0087
0088             old = accumulator;
0089             gettimeofday(&start, NULL);
0090             for (j = 0; j < inner_iterations; j++) {
0091                 for (bit = 0; bit < num_bits; bit++) {
0092                     if (asm_test_bit(bit, to_test))
0093                         workload(bit);
0094                 }
0095             }
0096             gettimeofday(&end, NULL);
0097             assert(old + (inner_iterations * set_bits) == accumulator);
0098             timersub(&end, &start, &diff);
0099             runtime_us = diff.tv_sec * USEC_PER_SEC + diff.tv_usec;
0100             update_stats(&tb_time_stats, runtime_us);
0101         }
0102
0103         printf("%d operations %d bits set of %d bits\n",
0104             inner_iterations, set_bits, num_bits);
0105         time_average = avg_stats(&fb_time_stats);
0106         time_stddev = stddev_stats(&fb_time_stats);
0107         printf("  Average for_each_set_bit took: %.3f usec (+- %.3f usec)\n",
0108             time_average, time_stddev);
0109         time_average = avg_stats(&tb_time_stats);
0110         time_stddev = stddev_stats(&tb_time_stats);
0111         printf("  Average test_bit loop took:    %.3f usec (+- %.3f usec)\n",
0112             time_average, time_stddev);
0113
0114         if (use_of_val == accumulator)  /* Try to avoid compiler tricks. */
0115             printf("\n");
0116     }
0117     bitmap_free(to_test);
0118     return 0;
0119 }
0120
0121 int bench_mem_find_bit(int argc, const char **argv)
0122 {
0123     int err = 0, i;
0124
0125     argc = parse_options(argc, argv, options, bench_usage, 0);
0126     if (argc) {
0127         usage_with_options(bench_usage, options);
0128         exit(EXIT_FAILURE);
0129     }
0130
0131     for (i = 1; i <= 2048; i <<= 1)
0132         do_for_each_set_bit(i);
0133
0134     return err;
0135 }