xref: /aosp_15_r20/external/libcxx/utils/google-benchmark/test/complexity_test.cc (revision 58b9f456b02922dfdb1fad8a988d5fd8765ecb80)
1*58b9f456SAndroid Build Coastguard Worker #undef NDEBUG
2*58b9f456SAndroid Build Coastguard Worker #include <algorithm>
3*58b9f456SAndroid Build Coastguard Worker #include <cassert>
4*58b9f456SAndroid Build Coastguard Worker #include <cmath>
5*58b9f456SAndroid Build Coastguard Worker #include <cstdlib>
6*58b9f456SAndroid Build Coastguard Worker #include <vector>
7*58b9f456SAndroid Build Coastguard Worker #include "benchmark/benchmark.h"
8*58b9f456SAndroid Build Coastguard Worker #include "output_test.h"
9*58b9f456SAndroid Build Coastguard Worker 
10*58b9f456SAndroid Build Coastguard Worker namespace {
11*58b9f456SAndroid Build Coastguard Worker 
12*58b9f456SAndroid Build Coastguard Worker #define ADD_COMPLEXITY_CASES(...) \
13*58b9f456SAndroid Build Coastguard Worker   int CONCAT(dummy, __LINE__) = AddComplexityTest(__VA_ARGS__)
14*58b9f456SAndroid Build Coastguard Worker 
AddComplexityTest(std::string test_name,std::string big_o_test_name,std::string rms_test_name,std::string big_o)15*58b9f456SAndroid Build Coastguard Worker int AddComplexityTest(std::string test_name, std::string big_o_test_name,
16*58b9f456SAndroid Build Coastguard Worker                       std::string rms_test_name, std::string big_o) {
17*58b9f456SAndroid Build Coastguard Worker   SetSubstitutions({{"%name", test_name},
18*58b9f456SAndroid Build Coastguard Worker                     {"%bigo_name", big_o_test_name},
19*58b9f456SAndroid Build Coastguard Worker                     {"%rms_name", rms_test_name},
20*58b9f456SAndroid Build Coastguard Worker                     {"%bigo_str", "[ ]* %float " + big_o},
21*58b9f456SAndroid Build Coastguard Worker                     {"%bigo", big_o},
22*58b9f456SAndroid Build Coastguard Worker                     {"%rms", "[ ]*[0-9]+ %"}});
23*58b9f456SAndroid Build Coastguard Worker   AddCases(
24*58b9f456SAndroid Build Coastguard Worker       TC_ConsoleOut,
25*58b9f456SAndroid Build Coastguard Worker       {{"^%bigo_name %bigo_str %bigo_str[ ]*$"},
26*58b9f456SAndroid Build Coastguard Worker        {"^%bigo_name", MR_Not},  // Assert we we didn't only matched a name.
27*58b9f456SAndroid Build Coastguard Worker        {"^%rms_name %rms %rms[ ]*$", MR_Next}});
28*58b9f456SAndroid Build Coastguard Worker   AddCases(TC_JSONOut, {{"\"name\": \"%bigo_name\",$"},
29*58b9f456SAndroid Build Coastguard Worker                         {"\"run_name\": \"%name\",$", MR_Next},
30*58b9f456SAndroid Build Coastguard Worker                         {"\"run_type\": \"aggregate\",$", MR_Next},
31*58b9f456SAndroid Build Coastguard Worker                         {"\"aggregate_name\": \"BigO\",$", MR_Next},
32*58b9f456SAndroid Build Coastguard Worker                         {"\"cpu_coefficient\": %float,$", MR_Next},
33*58b9f456SAndroid Build Coastguard Worker                         {"\"real_coefficient\": %float,$", MR_Next},
34*58b9f456SAndroid Build Coastguard Worker                         {"\"big_o\": \"%bigo\",$", MR_Next},
35*58b9f456SAndroid Build Coastguard Worker                         {"\"time_unit\": \"ns\"$", MR_Next},
36*58b9f456SAndroid Build Coastguard Worker                         {"}", MR_Next},
37*58b9f456SAndroid Build Coastguard Worker                         {"\"name\": \"%rms_name\",$"},
38*58b9f456SAndroid Build Coastguard Worker                         {"\"run_name\": \"%name\",$", MR_Next},
39*58b9f456SAndroid Build Coastguard Worker                         {"\"run_type\": \"aggregate\",$", MR_Next},
40*58b9f456SAndroid Build Coastguard Worker                         {"\"aggregate_name\": \"RMS\",$", MR_Next},
41*58b9f456SAndroid Build Coastguard Worker                         {"\"rms\": %float$", MR_Next},
42*58b9f456SAndroid Build Coastguard Worker                         {"}", MR_Next}});
43*58b9f456SAndroid Build Coastguard Worker   AddCases(TC_CSVOut, {{"^\"%bigo_name\",,%float,%float,%bigo,,,,,$"},
44*58b9f456SAndroid Build Coastguard Worker                        {"^\"%bigo_name\"", MR_Not},
45*58b9f456SAndroid Build Coastguard Worker                        {"^\"%rms_name\",,%float,%float,,,,,,$", MR_Next}});
46*58b9f456SAndroid Build Coastguard Worker   return 0;
47*58b9f456SAndroid Build Coastguard Worker }
48*58b9f456SAndroid Build Coastguard Worker 
49*58b9f456SAndroid Build Coastguard Worker }  // end namespace
50*58b9f456SAndroid Build Coastguard Worker 
51*58b9f456SAndroid Build Coastguard Worker // ========================================================================= //
52*58b9f456SAndroid Build Coastguard Worker // --------------------------- Testing BigO O(1) --------------------------- //
53*58b9f456SAndroid Build Coastguard Worker // ========================================================================= //
54*58b9f456SAndroid Build Coastguard Worker 
BM_Complexity_O1(benchmark::State & state)55*58b9f456SAndroid Build Coastguard Worker void BM_Complexity_O1(benchmark::State& state) {
56*58b9f456SAndroid Build Coastguard Worker   for (auto _ : state) {
57*58b9f456SAndroid Build Coastguard Worker     for (int i = 0; i < 1024; ++i) {
58*58b9f456SAndroid Build Coastguard Worker       benchmark::DoNotOptimize(&i);
59*58b9f456SAndroid Build Coastguard Worker     }
60*58b9f456SAndroid Build Coastguard Worker   }
61*58b9f456SAndroid Build Coastguard Worker   state.SetComplexityN(state.range(0));
62*58b9f456SAndroid Build Coastguard Worker }
63*58b9f456SAndroid Build Coastguard Worker BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity(benchmark::o1);
64*58b9f456SAndroid Build Coastguard Worker BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity();
__anon16f5e7d40202(int64_t) 65*58b9f456SAndroid Build Coastguard Worker BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity([](int64_t) {
66*58b9f456SAndroid Build Coastguard Worker   return 1.0;
67*58b9f456SAndroid Build Coastguard Worker });
68*58b9f456SAndroid Build Coastguard Worker 
69*58b9f456SAndroid Build Coastguard Worker const char *one_test_name = "BM_Complexity_O1";
70*58b9f456SAndroid Build Coastguard Worker const char *big_o_1_test_name = "BM_Complexity_O1_BigO";
71*58b9f456SAndroid Build Coastguard Worker const char *rms_o_1_test_name = "BM_Complexity_O1_RMS";
72*58b9f456SAndroid Build Coastguard Worker const char *enum_big_o_1 = "\\([0-9]+\\)";
73*58b9f456SAndroid Build Coastguard Worker // FIXME: Tolerate both '(1)' and 'lgN' as output when the complexity is auto
74*58b9f456SAndroid Build Coastguard Worker // deduced.
75*58b9f456SAndroid Build Coastguard Worker // See https://github.com/google/benchmark/issues/272
76*58b9f456SAndroid Build Coastguard Worker const char *auto_big_o_1 = "(\\([0-9]+\\))|(lgN)";
77*58b9f456SAndroid Build Coastguard Worker const char *lambda_big_o_1 = "f\\(N\\)";
78*58b9f456SAndroid Build Coastguard Worker 
79*58b9f456SAndroid Build Coastguard Worker // Add enum tests
80*58b9f456SAndroid Build Coastguard Worker ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
81*58b9f456SAndroid Build Coastguard Worker                      enum_big_o_1);
82*58b9f456SAndroid Build Coastguard Worker 
83*58b9f456SAndroid Build Coastguard Worker // Add auto enum tests
84*58b9f456SAndroid Build Coastguard Worker ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
85*58b9f456SAndroid Build Coastguard Worker                      auto_big_o_1);
86*58b9f456SAndroid Build Coastguard Worker 
87*58b9f456SAndroid Build Coastguard Worker // Add lambda tests
88*58b9f456SAndroid Build Coastguard Worker ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
89*58b9f456SAndroid Build Coastguard Worker                      lambda_big_o_1);
90*58b9f456SAndroid Build Coastguard Worker 
91*58b9f456SAndroid Build Coastguard Worker // ========================================================================= //
92*58b9f456SAndroid Build Coastguard Worker // --------------------------- Testing BigO O(N) --------------------------- //
93*58b9f456SAndroid Build Coastguard Worker // ========================================================================= //
94*58b9f456SAndroid Build Coastguard Worker 
ConstructRandomVector(int64_t size)95*58b9f456SAndroid Build Coastguard Worker std::vector<int> ConstructRandomVector(int64_t size) {
96*58b9f456SAndroid Build Coastguard Worker   std::vector<int> v;
97*58b9f456SAndroid Build Coastguard Worker   v.reserve(static_cast<int>(size));
98*58b9f456SAndroid Build Coastguard Worker   for (int i = 0; i < size; ++i) {
99*58b9f456SAndroid Build Coastguard Worker     v.push_back(static_cast<int>(std::rand() % size));
100*58b9f456SAndroid Build Coastguard Worker   }
101*58b9f456SAndroid Build Coastguard Worker   return v;
102*58b9f456SAndroid Build Coastguard Worker }
103*58b9f456SAndroid Build Coastguard Worker 
BM_Complexity_O_N(benchmark::State & state)104*58b9f456SAndroid Build Coastguard Worker void BM_Complexity_O_N(benchmark::State& state) {
105*58b9f456SAndroid Build Coastguard Worker   auto v = ConstructRandomVector(state.range(0));
106*58b9f456SAndroid Build Coastguard Worker   // Test worst case scenario (item not in vector)
107*58b9f456SAndroid Build Coastguard Worker   const int64_t item_not_in_vector = state.range(0) * 2;
108*58b9f456SAndroid Build Coastguard Worker   for (auto _ : state) {
109*58b9f456SAndroid Build Coastguard Worker     benchmark::DoNotOptimize(std::find(v.begin(), v.end(), item_not_in_vector));
110*58b9f456SAndroid Build Coastguard Worker   }
111*58b9f456SAndroid Build Coastguard Worker   state.SetComplexityN(state.range(0));
112*58b9f456SAndroid Build Coastguard Worker }
113*58b9f456SAndroid Build Coastguard Worker BENCHMARK(BM_Complexity_O_N)
114*58b9f456SAndroid Build Coastguard Worker     ->RangeMultiplier(2)
115*58b9f456SAndroid Build Coastguard Worker     ->Range(1 << 10, 1 << 16)
116*58b9f456SAndroid Build Coastguard Worker     ->Complexity(benchmark::oN);
117*58b9f456SAndroid Build Coastguard Worker BENCHMARK(BM_Complexity_O_N)
118*58b9f456SAndroid Build Coastguard Worker     ->RangeMultiplier(2)
119*58b9f456SAndroid Build Coastguard Worker     ->Range(1 << 10, 1 << 16)
__anon16f5e7d40302(int64_t n) 120*58b9f456SAndroid Build Coastguard Worker     ->Complexity([](int64_t n) -> double { return static_cast<double>(n); });
121*58b9f456SAndroid Build Coastguard Worker BENCHMARK(BM_Complexity_O_N)
122*58b9f456SAndroid Build Coastguard Worker     ->RangeMultiplier(2)
123*58b9f456SAndroid Build Coastguard Worker     ->Range(1 << 10, 1 << 16)
124*58b9f456SAndroid Build Coastguard Worker     ->Complexity();
125*58b9f456SAndroid Build Coastguard Worker 
126*58b9f456SAndroid Build Coastguard Worker const char *n_test_name = "BM_Complexity_O_N";
127*58b9f456SAndroid Build Coastguard Worker const char *big_o_n_test_name = "BM_Complexity_O_N_BigO";
128*58b9f456SAndroid Build Coastguard Worker const char *rms_o_n_test_name = "BM_Complexity_O_N_RMS";
129*58b9f456SAndroid Build Coastguard Worker const char *enum_auto_big_o_n = "N";
130*58b9f456SAndroid Build Coastguard Worker const char *lambda_big_o_n = "f\\(N\\)";
131*58b9f456SAndroid Build Coastguard Worker 
132*58b9f456SAndroid Build Coastguard Worker // Add enum tests
133*58b9f456SAndroid Build Coastguard Worker ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
134*58b9f456SAndroid Build Coastguard Worker                      enum_auto_big_o_n);
135*58b9f456SAndroid Build Coastguard Worker 
136*58b9f456SAndroid Build Coastguard Worker // Add lambda tests
137*58b9f456SAndroid Build Coastguard Worker ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
138*58b9f456SAndroid Build Coastguard Worker                      lambda_big_o_n);
139*58b9f456SAndroid Build Coastguard Worker 
140*58b9f456SAndroid Build Coastguard Worker // ========================================================================= //
141*58b9f456SAndroid Build Coastguard Worker // ------------------------- Testing BigO O(N*lgN) ------------------------- //
142*58b9f456SAndroid Build Coastguard Worker // ========================================================================= //
143*58b9f456SAndroid Build Coastguard Worker 
BM_Complexity_O_N_log_N(benchmark::State & state)144*58b9f456SAndroid Build Coastguard Worker static void BM_Complexity_O_N_log_N(benchmark::State& state) {
145*58b9f456SAndroid Build Coastguard Worker   auto v = ConstructRandomVector(state.range(0));
146*58b9f456SAndroid Build Coastguard Worker   for (auto _ : state) {
147*58b9f456SAndroid Build Coastguard Worker     std::sort(v.begin(), v.end());
148*58b9f456SAndroid Build Coastguard Worker   }
149*58b9f456SAndroid Build Coastguard Worker   state.SetComplexityN(state.range(0));
150*58b9f456SAndroid Build Coastguard Worker }
151*58b9f456SAndroid Build Coastguard Worker static const double kLog2E = 1.44269504088896340736;
152*58b9f456SAndroid Build Coastguard Worker BENCHMARK(BM_Complexity_O_N_log_N)
153*58b9f456SAndroid Build Coastguard Worker     ->RangeMultiplier(2)
154*58b9f456SAndroid Build Coastguard Worker     ->Range(1 << 10, 1 << 16)
155*58b9f456SAndroid Build Coastguard Worker     ->Complexity(benchmark::oNLogN);
156*58b9f456SAndroid Build Coastguard Worker BENCHMARK(BM_Complexity_O_N_log_N)
157*58b9f456SAndroid Build Coastguard Worker     ->RangeMultiplier(2)
158*58b9f456SAndroid Build Coastguard Worker     ->Range(1 << 10, 1 << 16)
__anon16f5e7d40402(int64_t n) 159*58b9f456SAndroid Build Coastguard Worker     ->Complexity([](int64_t n) { return kLog2E * n * log(static_cast<double>(n)); });
160*58b9f456SAndroid Build Coastguard Worker BENCHMARK(BM_Complexity_O_N_log_N)
161*58b9f456SAndroid Build Coastguard Worker     ->RangeMultiplier(2)
162*58b9f456SAndroid Build Coastguard Worker     ->Range(1 << 10, 1 << 16)
163*58b9f456SAndroid Build Coastguard Worker     ->Complexity();
164*58b9f456SAndroid Build Coastguard Worker 
165*58b9f456SAndroid Build Coastguard Worker const char *n_lg_n_test_name = "BM_Complexity_O_N_log_N";
166*58b9f456SAndroid Build Coastguard Worker const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_BigO";
167*58b9f456SAndroid Build Coastguard Worker const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_RMS";
168*58b9f456SAndroid Build Coastguard Worker const char *enum_auto_big_o_n_lg_n = "NlgN";
169*58b9f456SAndroid Build Coastguard Worker const char *lambda_big_o_n_lg_n = "f\\(N\\)";
170*58b9f456SAndroid Build Coastguard Worker 
171*58b9f456SAndroid Build Coastguard Worker // Add enum tests
172*58b9f456SAndroid Build Coastguard Worker ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
173*58b9f456SAndroid Build Coastguard Worker                      rms_o_n_lg_n_test_name, enum_auto_big_o_n_lg_n);
174*58b9f456SAndroid Build Coastguard Worker 
175*58b9f456SAndroid Build Coastguard Worker // Add lambda tests
176*58b9f456SAndroid Build Coastguard Worker ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
177*58b9f456SAndroid Build Coastguard Worker                      rms_o_n_lg_n_test_name, lambda_big_o_n_lg_n);
178*58b9f456SAndroid Build Coastguard Worker 
179*58b9f456SAndroid Build Coastguard Worker // ========================================================================= //
180*58b9f456SAndroid Build Coastguard Worker // --------------------------- TEST CASES END ------------------------------ //
181*58b9f456SAndroid Build Coastguard Worker // ========================================================================= //
182*58b9f456SAndroid Build Coastguard Worker 
main(int argc,char * argv[])183*58b9f456SAndroid Build Coastguard Worker int main(int argc, char *argv[]) { RunOutputTests(argc, argv); }
184