auto_tune_test.cc (4010B)
1 // Copyright 2025 Google LLC 2 // SPDX-License-Identifier: Apache-2.0 3 // 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at 7 // 8 // http://www.apache.org/licenses/LICENSE-2.0 9 // 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 16 #include "hwy/auto_tune.h" 17 18 #include <stddef.h> 19 #include <stdint.h> 20 21 #include <algorithm> 22 #include <random> 23 #include <vector> 24 25 #include "hwy/base.h" // HWY_ASSERT 26 #include "hwy/nanobenchmark.h" // Unpredictable1 27 #include "hwy/tests/hwy_gtest.h" 28 #include "hwy/tests/test_util-inl.h" 29 30 namespace hwy { 31 namespace { 32 33 // Returns random floating-point number in [-8, 8). 34 static double Random(RandomState& rng) { 35 const int32_t bits = static_cast<int32_t>(Random32(&rng)) & 1023; 36 return (bits - 512) / 64.0; 37 } 38 39 TEST(AutoTuneTest, TestCostDistribution) { 40 // All equal exercises the MAD=0 trimming case. 41 const size_t kMaxValues = CostDistribution::kMaxValues; 42 for (size_t num : {size_t{3}, kMaxValues - 1, kMaxValues, kMaxValues + 1}) { 43 const double kVal = 6.5; 44 for (double outlier : {0.0, 1000.0}) { 45 CostDistribution cd; 46 const size_t num_outliers = HWY_MAX(num / 4, size_t{1}); 47 for (size_t i = 0; i < num - num_outliers; ++i) cd.Notify(kVal); 48 for (size_t i = 0; i < num_outliers; ++i) cd.Notify(outlier); 49 const double cost = cd.EstimateCost(); 50 // Winsorization allows outliers to shift the central tendency a bit. 51 HWY_ASSERT(cost >= kVal - 0.25); 52 HWY_ASSERT(cost <= kVal + 0.25); 53 } 54 } 55 56 // Gaussian distribution with additive+multiplicative noise. 57 RandomState rng; 58 for (size_t rep = 0; rep < AdjustedReps(1000); ++rep) { 59 CostDistribution cd; 60 const size_t num = 1000; // enough for stable variance 61 for (size_t i = 0; i < num; ++i) { 62 // Central limit theorem: sum of independent random is Gaussian. 63 double sum = 500.0; 64 for (size_t sum_idx = 0; sum_idx < 100; ++sum_idx) sum += Random(rng); 65 66 // 16% noise: mostly additive, some lucky shots. 67 const uint32_t r = Random32(&rng); 68 if (r < (1u << 28)) { 69 static constexpr double kPowers[4] = {0.0, 1E3, 1E4, 1E5}; 70 static constexpr double kMul[4] = {0.50, 0.75, 0.85, 0.90}; 71 if (r & 3) { // 75% chance of large additive noise 72 sum += kPowers[r & 3]; 73 } else { // 25% chance of small multiplicative reduction 74 sum *= kMul[(r >> 2) & 3]; 75 } 76 } 77 cd.Notify(sum); 78 } 79 const double cost = cd.EstimateCost(); 80 if (!(490.0 <= cost && cost <= 540.0)) { 81 HWY_ABORT("Cost %f outside expected range.", cost); 82 } 83 } 84 } 85 86 TEST(AutoTuneTest, TestNextEdges) { 87 NextWithSkip list(123); 88 HWY_ASSERT_EQ(0, list.Next(122)); // Check wrap-around 89 HWY_ASSERT_EQ(1, list.Next(0)); 90 list.Skip(1); 91 HWY_ASSERT_EQ(2, list.Next(0)); 92 list.Skip(2); 93 HWY_ASSERT_EQ(3, list.Next(0)); 94 95 // Skip last 96 list.Skip(122); 97 HWY_ASSERT_EQ(0, list.Next(121)); 98 99 // Skip first 100 list.Skip(0); 101 HWY_ASSERT_EQ(3, list.Next(121)); 102 } 103 104 TEST(AutoTuneTest, TestNextSkipAllButOne) { 105 // Prime, pow2 +/- 1 106 for (size_t num : {size_t{37}, size_t{63}, size_t{513}}) { 107 NextWithSkip list(num); 108 std::vector<uint32_t> pos; 109 pos.reserve(num); 110 for (size_t i = 0; i < num; ++i) { 111 pos.push_back(static_cast<uint32_t>(i)); 112 } 113 std::mt19937 rng(static_cast<uint_fast32_t>(129 * Unpredictable1())); 114 std::shuffle(pos.begin(), pos.end(), rng); 115 for (size_t i = 0; i < num - 1; ++i) { 116 list.Skip(pos[i]); 117 } 118 HWY_ASSERT_EQ(pos.back(), list.Next(pos.back())); // only one left 119 } 120 } 121 122 } // namespace 123 } // namespace hwy 124 125 HWY_TEST_MAIN();