third_party/highway/hwy/auto_tune_test.cc

// Copyright 2025 Google LLC
// SPDX-License-Identifier: Apache-2.0
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "third_party/highway/hwy/auto_tune.h"

#include <stddef.h>
#include <stdint.h>

#include <algorithm>
#include <random>
#include <vector>

#include "third_party/highway/hwy/base.h"           // HWY_ASSERT
#include "third_party/highway/hwy/nanobenchmark.h"  // Unpredictable1
#include "third_party/highway/hwy/tests/hwy_gtest.h"
#include "third_party/highway/hwy/tests/test_util-inl.h"

namespace hwy {
namespace {

// Returns random floating-point number in [-8, 8).
static double Random(RandomState& rng) {
  const int32_t bits = static_cast<int32_t>(Random32(&rng)) & 1023;
  return (bits - 512) / 64.0;
}

TEST(AutoTuneTest, TestCostDistribution) {
  // All equal exercises the MAD=0 trimming case.
  const size_t kMaxValues = CostDistribution::kMaxValues;
  for (size_t num : {size_t{3}, kMaxValues - 1, kMaxValues, kMaxValues + 1}) {
    const double kVal = 6.5;
    for (double outlier : {0.0, 1000.0}) {
      CostDistribution cd;
      const size_t num_outliers = HWY_MAX(num / 4, size_t{1});
      for (size_t i = 0; i < num - num_outliers; ++i) cd.Notify(kVal);
      for (size_t i = 0; i < num_outliers; ++i) cd.Notify(outlier);
      HWY_ASSERT_EQ(kVal, cd.EstimateCost());
    }
  }

  // Gaussian distribution with salt and pepper noise.
  RandomState rng;
  for (size_t rep = 0; rep < AdjustedReps(1000); ++rep) {
    CostDistribution cd;
    const size_t num = 1000;  // enough for stable variance
    for (size_t i = 0; i < num; ++i) {
      // Central limit theorem: sum of independent random is Gaussian.
      double sum = 500.0;
      for (size_t sum_idx = 0; sum_idx < 100; ++sum_idx) sum += Random(rng);

      // 16% salt and pepper noise
      const uint32_t r = Random32(&rng);
      if (r < (1u << 28)) sum = (r & 3) ? 1E5 : 1;
      cd.Notify(sum);
    }
    const double cost = cd.EstimateCost();
    if (!(300.0 <= cost && cost <= 510.0)) {
      HWY_ABORT("Cost %f outside expected range.", cost);
    }
  }
}

TEST(AutoTuneTest, TestNextEdges) {
  NextWithSkip list(123);
  HWY_ASSERT_EQ(0, list.Next(122));  // Check wrap-around
  HWY_ASSERT_EQ(1, list.Next(0));
  list.Skip(1);
  HWY_ASSERT_EQ(2, list.Next(0));
  list.Skip(2);
  HWY_ASSERT_EQ(3, list.Next(0));

  // Skip last
  list.Skip(122);
  HWY_ASSERT_EQ(0, list.Next(121));

  // Skip first
  list.Skip(0);
  HWY_ASSERT_EQ(3, list.Next(121));
}

TEST(AutoTuneTest, TestNextSkipAllButOne) {
  // Prime, pow2 +/- 1
  for (size_t num : {size_t{37}, size_t{63}, size_t{513}}) {
    NextWithSkip list(num);
    std::vector<uint32_t> pos;
    pos.reserve(num);
    for (size_t i = 0; i < num; ++i) {
      pos.push_back(static_cast<uint32_t>(i));
    }
    std::mt19937 rng(static_cast<uint_fast32_t>(129 * Unpredictable1()));
    std::shuffle(pos.begin(), pos.end(), rng);
    for (size_t i = 0; i < num - 1; ++i) {
      list.Skip(pos[i]);
    }
    HWY_ASSERT_EQ(pos.back(), list.Next(pos.back()));  // only one left
  }
}

}  // namespace
}  // namespace hwy

HWY_TEST_MAIN();