// Copyright 2018 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "ui/latency/windowed_analyzer.h" #include "base/time/time.h" #include "testing/gtest/include/gtest/gtest.h" #include "ui/latency/frame_metrics_test_common.h" namespace ui { namespace frame_metrics { namespace { // Verify that the worst values for Mean, SMR, and RMS are all the same if // every value added is the same. Makes for a nice sanity check. TEST(FrameMetricsWindowedAnalyzerTest, AllResultsTheSame) { // For this test, we don't care about the timeline, so just keep it constant. TestWindowedAnalyzerClient client; SharedWindowedAnalyzerClient shared_client( 60, base::TimeTicks(), base::TimeTicks() + base::TimeDelta::FromSeconds(1)); // Try adding a single sample vs. multiple samples. for (size_t samples : {1u, 100u}) { // A power of 2 sweep for both the value and weight dimensions. for (uint64_t value = 1; value < 0x100000000ULL; value *= 2) { // Adding too many samples can result in overflow when multiplied by the // weight. Divide by samples to avoid overflow. for (uint64_t weight = 1; weight < 0x100000000ULL / samples; weight *= 2) { WindowedAnalyzer analyzer(&client, &shared_client); AddSamplesHelper(&analyzer, value, weight, samples); uint64_t expected_value = value * TestWindowedAnalyzerClient::result_scale; EXPECT_EQ(analyzer.ComputeWorstMean().value, expected_value) << value << " x " << weight; EXPECT_EQ(analyzer.ComputeWorstRMS().value, expected_value) << value << " x " << weight; EXPECT_NEAR_SMR(analyzer.ComputeWorstSMR().value, expected_value, weight) << value << " x " << weight; } } } // All min/max combinations of value and weight. for (uint64_t value : {0u, 0xFFFFFFFFu}) { for (uint64_t weight : {1u, 0xFFFFFFFFu}) { const size_t kSamplesToAdd = weight == 1 ? 100 : 1; WindowedAnalyzer analyzer(&client, &shared_client); AddSamplesHelper(&analyzer, value, weight, kSamplesToAdd); // TestWindowedAnalyzerClient scales the result by 2. uint64_t expected_value = value * TestWindowedAnalyzerClient::result_scale; // Makes sure our precision is good enough. EXPECT_EQ(analyzer.ComputeWorstMean().value, expected_value) << value << " x " << weight; EXPECT_EQ(analyzer.ComputeWorstRMS().value, expected_value) << value << " x " << weight; EXPECT_NEAR_SMR(analyzer.ComputeWorstSMR().value, expected_value, weight) << value << " x " << weight; } } } // Verify that the worst values and their time regions are properly tracked // seperately for mean, SMR, and RMS. TEST(FrameMetricsWindowedAnalyzerTest, AllResultsDifferent) { const size_t kMaxWindowSize = 6; // Same as the pattern length. const uint32_t kSampleWeight = 100; TestWindowedAnalyzerClient client; SharedWindowedAnalyzerClient shared_client( kMaxWindowSize, base::TimeTicks(), base::TimeTicks() + base::TimeDelta::FromSeconds(1)); WindowedAnalyzer analyzer(&client, &shared_client); // Used to "clear" all the windowed accumulators. const std::vector pattern_clear = {0, 0, 0, 0, 0, 0}; // Worst mean pattern: mean of 3, smr of 1.5, rms of ~4.2. const std::vector pattern_max_mean = {0, 6, 0, 6, 0, 6}; double expected_worst_mean = 3 * kFixedPointMultiplier * TestWindowedAnalyzerClient::result_scale; // Lots of small janks maximizes the SMR. // Worst SMR pattern: mean of 2, smr of 2, rms of 2. const std::vector pattern_max_smr = {2, 2, 2, 2, 2, 2}; double expected_worst_smr = 2 * kFixedPointMultiplier * TestWindowedAnalyzerClient::result_scale; // A few big janks dominate RMS. // Worst RMS pattern: Mean of 2, smr of ~.3, rms of ~4.9 const std::vector pattern_max_rms = {0, 0, 0, 0, 0, 12}; double expected_worst_rms = std::sqrt((12 * 12) / 6) * kFixedPointMultiplier * TestWindowedAnalyzerClient::result_scale; AddPatternHelper(&shared_client, &analyzer, pattern_clear, kSampleWeight); AddPatternHelper(&shared_client, &analyzer, pattern_max_mean, kSampleWeight); SharedWindowedAnalyzerClient worst_mean_client(shared_client); AddPatternHelper(&shared_client, &analyzer, pattern_clear, kSampleWeight); AddPatternHelper(&shared_client, &analyzer, pattern_max_smr, kSampleWeight); SharedWindowedAnalyzerClient worst_smr_client(shared_client); AddPatternHelper(&shared_client, &analyzer, pattern_clear, kSampleWeight); AddPatternHelper(&shared_client, &analyzer, pattern_max_rms, kSampleWeight); SharedWindowedAnalyzerClient worst_rms_client(shared_client); // If there is a tie, the first window detected wins. // This can go wrong if there's any accumulation of error because the // values added aren't exactly the same as the values removed. // This only catches accumulation of error in one direction, so isn't // thorough, but it does help improve coverage. AddPatternHelper(&shared_client, &analyzer, pattern_clear, kSampleWeight); AddPatternHelper(&shared_client, &analyzer, pattern_max_mean, kSampleWeight); AddPatternHelper(&shared_client, &analyzer, pattern_clear, kSampleWeight); AddPatternHelper(&shared_client, &analyzer, pattern_max_smr, kSampleWeight); AddPatternHelper(&shared_client, &analyzer, pattern_clear, kSampleWeight); AddPatternHelper(&shared_client, &analyzer, pattern_max_rms, kSampleWeight); AddPatternHelper(&shared_client, &analyzer, pattern_clear, kSampleWeight); FrameRegionResult worst_mean = analyzer.ComputeWorstMean(); EXPECT_DOUBLE_EQ(expected_worst_mean, worst_mean.value); EXPECT_EQ(worst_mean_client.window_begin, worst_mean.window_begin); EXPECT_EQ(worst_mean_client.window_end, worst_mean.window_end); FrameRegionResult worst_smr = analyzer.ComputeWorstSMR(); EXPECT_NEAR_SMR(expected_worst_smr, worst_smr.value, kSampleWeight); EXPECT_EQ(worst_smr_client.window_begin, worst_smr.window_begin); EXPECT_EQ(worst_smr_client.window_end, worst_smr.window_end); FrameRegionResult worst_rms = analyzer.ComputeWorstRMS(); EXPECT_DOUBLE_EQ(expected_worst_rms, worst_rms.value); EXPECT_EQ(worst_rms_client.window_begin, worst_rms.window_begin); EXPECT_EQ(worst_rms_client.window_end, worst_rms.window_end); } // Verify that the worst values and their time regions are properly tracked // even before a full window's worth is available. TEST(FrameMetricsWindowedAnalyzerTest, SmallSampleSize) { const size_t kMaxWindowSize = 6; // Bigger than the pattern length. const uint32_t kSampleWeight = 100; TestWindowedAnalyzerClient client; SharedWindowedAnalyzerClient shared_client( kMaxWindowSize, base::TimeTicks(), base::TimeTicks() + base::TimeDelta::FromSeconds(1)); WindowedAnalyzer analyzer(&client, &shared_client); const std::vector pattern_short = {2, 2, 2}; double expected_initial_value = 2 * kFixedPointMultiplier * TestWindowedAnalyzerClient::result_scale; AddPatternHelper(&shared_client, &analyzer, pattern_short, kSampleWeight); SharedWindowedAnalyzerClient short_client(shared_client); FrameRegionResult worst_mean = analyzer.ComputeWorstMean(); EXPECT_DOUBLE_EQ(expected_initial_value, worst_mean.value); EXPECT_EQ(short_client.window_begin, worst_mean.window_begin); EXPECT_EQ(short_client.window_end, worst_mean.window_end); FrameRegionResult worst_smr = analyzer.ComputeWorstSMR(); EXPECT_NEAR_SMR(expected_initial_value, worst_smr.value, kSampleWeight); EXPECT_EQ(short_client.window_begin, worst_smr.window_begin); EXPECT_EQ(short_client.window_end, worst_smr.window_end); FrameRegionResult worst_rms = analyzer.ComputeWorstRMS(); EXPECT_DOUBLE_EQ(expected_initial_value, worst_rms.value); EXPECT_EQ(short_client.window_begin, worst_rms.window_begin); EXPECT_EQ(short_client.window_end, worst_rms.window_end); } // Verify that a few bad values at the start don't dominate the result. TEST(FrameMetricsWindowedAnalyzerTest, BadFirstSamples) { const size_t kMaxWindowSize = 6; const uint32_t kSampleWeight = 100; FrameRegionResult worst_mean, worst_smr, worst_rms; TestWindowedAnalyzerClient client; SharedWindowedAnalyzerClient shared_client( kMaxWindowSize, base::TimeTicks(), base::TimeTicks() + base::TimeDelta::FromSeconds(1)); WindowedAnalyzer analyzer(&client, &shared_client); // The 7's at the start will dominate the result if the implemenationd // doesn't only start remembering the worst values after receiving at least // a window's worth of samples. const std::vector pattern_short = {7, 7}; double expected_initial_value = 7 * kFixedPointMultiplier * TestWindowedAnalyzerClient::result_scale; AddPatternHelper(&shared_client, &analyzer, pattern_short, kSampleWeight); SharedWindowedAnalyzerClient short_client(shared_client); worst_mean = analyzer.ComputeWorstMean(); EXPECT_DOUBLE_EQ(expected_initial_value, worst_mean.value); EXPECT_EQ(short_client.window_begin, worst_mean.window_begin); EXPECT_EQ(short_client.window_end, worst_mean.window_end); worst_smr = analyzer.ComputeWorstSMR(); EXPECT_NEAR_SMR(expected_initial_value, worst_smr.value, kSampleWeight); EXPECT_EQ(short_client.window_begin, worst_smr.window_begin); EXPECT_EQ(short_client.window_end, worst_smr.window_end); worst_rms = analyzer.ComputeWorstRMS(); EXPECT_DOUBLE_EQ(expected_initial_value, worst_rms.value); EXPECT_EQ(short_client.window_begin, worst_rms.window_begin); EXPECT_EQ(short_client.window_end, worst_rms.window_end); // Clear the window. const std::vector pattern_clear = {0, 0, 0, 0, 0, 0}; AddPatternHelper(&shared_client, &analyzer, pattern_clear, kSampleWeight); // Make sure a new worst window with results less than 7 is detected. const std::vector pattern_long = {6, 6, 6, 6, 6, 6}; double expected_final_value = 6 * kFixedPointMultiplier * TestWindowedAnalyzerClient::result_scale; AddPatternHelper(&shared_client, &analyzer, pattern_long, kSampleWeight); SharedWindowedAnalyzerClient long_client(shared_client); worst_mean = analyzer.ComputeWorstMean(); EXPECT_DOUBLE_EQ(expected_final_value, worst_mean.value); EXPECT_EQ(long_client.window_begin, worst_mean.window_begin); EXPECT_EQ(long_client.window_end, worst_mean.window_end); worst_smr = analyzer.ComputeWorstSMR(); EXPECT_NEAR_SMR(expected_final_value, worst_smr.value, kSampleWeight); EXPECT_EQ(long_client.window_begin, worst_smr.window_begin); EXPECT_EQ(long_client.window_end, worst_smr.window_end); worst_rms = analyzer.ComputeWorstRMS(); EXPECT_DOUBLE_EQ(expected_final_value, worst_rms.value); EXPECT_EQ(long_client.window_begin, worst_rms.window_begin); EXPECT_EQ(long_client.window_end, worst_rms.window_end); } // Verify ResetAccumulators is continuous across the reset boundary. TEST(FrameMetricsWindowedAnalyzerTest, ResetWorstValues) { const size_t kMaxWindowSize = 6; // Same as the pattern length. const uint32_t kSampleWeight = 100; FrameRegionResult worst_mean, worst_smr, worst_rms; TestWindowedAnalyzerClient client; SharedWindowedAnalyzerClient shared_client( kMaxWindowSize, base::TimeTicks(), base::TimeTicks() + base::TimeDelta::FromSeconds(1)); WindowedAnalyzer analyzer(&client, &shared_client); // Start off with the worst pattern. const std::vector pattern1 = {9, 9, 9, 9, 9, 9}; double expected_initial_value = 9 * kFixedPointMultiplier * TestWindowedAnalyzerClient::result_scale; AddPatternHelper(&shared_client, &analyzer, pattern1, kSampleWeight); SharedWindowedAnalyzerClient initial_client(shared_client); worst_mean = analyzer.ComputeWorstMean(); EXPECT_DOUBLE_EQ(expected_initial_value, worst_mean.value); EXPECT_EQ(initial_client.window_begin, worst_mean.window_begin); EXPECT_EQ(initial_client.window_end, worst_mean.window_end); worst_smr = analyzer.ComputeWorstSMR(); EXPECT_NEAR_SMR(expected_initial_value, worst_smr.value, kSampleWeight); EXPECT_EQ(initial_client.window_begin, worst_smr.window_begin); EXPECT_EQ(initial_client.window_end, worst_smr.window_end); worst_rms = analyzer.ComputeWorstRMS(); EXPECT_DOUBLE_EQ(expected_initial_value, worst_rms.value); EXPECT_EQ(initial_client.window_begin, worst_rms.window_begin); EXPECT_EQ(initial_client.window_end, worst_rms.window_end); // The 4's below will affect the window, even after a reset, but // won't affect the current worst values. const std::vector pattern2 = {4, 4, 4, 4, 4, 4}; AddPatternHelper(&shared_client, &analyzer, pattern2, kSampleWeight); worst_mean = analyzer.ComputeWorstMean(); EXPECT_DOUBLE_EQ(expected_initial_value, worst_mean.value); EXPECT_EQ(initial_client.window_begin, worst_mean.window_begin); EXPECT_EQ(initial_client.window_end, worst_mean.window_end); worst_smr = analyzer.ComputeWorstSMR(); EXPECT_NEAR_SMR(expected_initial_value, worst_smr.value, kSampleWeight); EXPECT_EQ(initial_client.window_begin, worst_smr.window_begin); EXPECT_EQ(initial_client.window_end, worst_smr.window_end); worst_rms = analyzer.ComputeWorstRMS(); EXPECT_DOUBLE_EQ(expected_initial_value, worst_rms.value); EXPECT_EQ(initial_client.window_begin, worst_rms.window_begin); EXPECT_EQ(initial_client.window_end, worst_rms.window_end); // Reset the worst value. This should not destroy sample history or // any accumulators. analyzer.ResetWorstValues(); // The first 4 below will be included with the previous 4's to detect an // entire window of results, even though we've reset the worst values. const std::vector pattern3 = {4}; double expected_final_value = 4 * kFixedPointMultiplier * TestWindowedAnalyzerClient::result_scale; AddPatternHelper(&shared_client, &analyzer, pattern3, kSampleWeight); SharedWindowedAnalyzerClient final_client(shared_client); // Add a window of 1's here to verify it does not affect the window of 4's. const std::vector pattern4 = {1, 1, 1, 1, 1, 1}; AddPatternHelper(&shared_client, &analyzer, pattern4, kSampleWeight); worst_mean = analyzer.ComputeWorstMean(); EXPECT_DOUBLE_EQ(expected_final_value, worst_mean.value); EXPECT_EQ(final_client.window_begin, worst_mean.window_begin); EXPECT_EQ(final_client.window_end, worst_mean.window_end); worst_smr = analyzer.ComputeWorstSMR(); EXPECT_NEAR_SMR(expected_final_value, worst_smr.value, kSampleWeight); EXPECT_EQ(final_client.window_begin, worst_smr.window_begin); EXPECT_EQ(final_client.window_end, worst_smr.window_end); worst_rms = analyzer.ComputeWorstRMS(); EXPECT_DOUBLE_EQ(expected_final_value, worst_rms.value); EXPECT_EQ(final_client.window_begin, worst_rms.window_begin); EXPECT_EQ(final_client.window_end, worst_rms.window_end); } // WindowedAnalyzerNaive is a version of WindowedAnalyzer that doesn't use // fixed point math and can accumulate error, even with double precision // accumulators. This is used to verify patterns that accumulate error without // fixed point math, so we can then verify those patterns don't result in // acculated error in the actual implementation. class WindowedAnalyzerNaive { public: WindowedAnalyzerNaive(size_t max_window_size) : max_window_size_(max_window_size) {} void AddSample(uint32_t value, uint32_t weight, uint64_t weighted_value, uint64_t weighted_root, const Accumulator96b& weighted_square) { if (history_.size() >= max_window_size_) { Sample old = history_.front(); history_.pop_front(); naive_accumulator_ -= static_cast(old.weight) * old.value; naive_root_accumulator_ -= static_cast(old.weight) * std::sqrt(old.value); naive_square_accumulator_ -= static_cast(old.weight) * old.value * old.value; naive_total_weight_ -= old.weight; } history_.push_back({value, weight}); naive_accumulator_ += static_cast(weight) * value; naive_root_accumulator_ += static_cast(weight) * std::sqrt(value); naive_square_accumulator_ += static_cast(weight) * value * value; naive_total_weight_ += weight; } struct Sample { uint32_t value; uint32_t weight; }; const size_t max_window_size_; double naive_accumulator_ = 0; double naive_root_accumulator_ = 0; double naive_square_accumulator_ = 0; double naive_total_weight_ = 0; base::circular_deque history_; }; // A version of the WindowedAnalyzer that allows us to inspect the internal // state for testing purposes. class TestWindowedAnalyzer : public WindowedAnalyzer { public: TestWindowedAnalyzer(const WindowedAnalyzerClient* client, const SharedWindowedAnalyzerClient* shared_client) : WindowedAnalyzer(client, shared_client) {} ~TestWindowedAnalyzer() override {} double CurrentAccumulator() { return accumulator_; } double CurrentRootAccumulator() { return root_accumulator_; } double CurrentSquareAccumulator() { return square_accumulator_.ToDouble(); } }; // This test verifies that it's easy to blow the dynamic range of a floating // point accumulator with a particular pattern. Then it verifies that same // pattern does not result in error in the actual implementation. void TestNoAccumulatedPrecisionError(uint32_t big_value, uint32_t small_value, double naive_root_error_floor, double naive_square_error_floor) { const size_t kRuns = 1000; const size_t kMaxWindowSize = 6; // Same as the pattern length. const std::vector pattern_clear = {0, 0, 0, 0, 0, 0}; const std::vector pattern_bad = {big_value, small_value, small_value, small_value, small_value, small_value}; // Set up the actual WindowedAnalyzer implementation. TestWindowedAnalyzerClient client_impl; SharedWindowedAnalyzerClient shared_client_impl( kMaxWindowSize, base::TimeTicks(), base::TimeTicks() + base::TimeDelta::FromSeconds(1)); TestWindowedAnalyzer analyzer_impl(&client_impl, &shared_client_impl); // Set up the naive WindowedAnalyzer implementation. SharedWindowedAnalyzerClient shared_client_naive( kMaxWindowSize, base::TimeTicks(), base::TimeTicks() + base::TimeDelta::FromSeconds(1)); WindowedAnalyzerNaive analyzer_naive(kMaxWindowSize); // Verify error keeps accumulating each time the bad pattern is applied. // Note: We don't expect error in the mean accumulator since the values added // are already truncated to whole integers before being passed in via // AddSamples(). double naive_root_accumulator_prev = 0; double naive_square_accumulator_prev = 0; for (size_t i = 1; i <= kRuns; i++) { AddCubedPatternHelper(&shared_client_naive, &analyzer_naive, pattern_bad); AddCubedPatternHelper(&shared_client_naive, &analyzer_naive, pattern_clear); EXPECT_EQ(0, analyzer_naive.naive_accumulator_); EXPECT_ABS_LT(naive_root_accumulator_prev, analyzer_naive.naive_root_accumulator_); EXPECT_ABS_LT(naive_square_accumulator_prev, analyzer_naive.naive_square_accumulator_); naive_root_accumulator_prev = analyzer_naive.naive_root_accumulator_; naive_square_accumulator_prev = analyzer_naive.naive_square_accumulator_; } // Verify naive error is bigger than some threshold after kRuns. EXPECT_ABS_LE(naive_root_error_floor * kRuns, analyzer_naive.naive_root_accumulator_); EXPECT_ABS_LE(naive_square_error_floor * kRuns, analyzer_naive.naive_square_accumulator_); // Verify actual implementation has no error. for (size_t i = 1; i <= kRuns; i++) { AddCubedPatternHelper(&shared_client_impl, &analyzer_impl, pattern_bad); AddCubedPatternHelper(&shared_client_impl, &analyzer_impl, pattern_clear); EXPECT_EQ(0, analyzer_impl.CurrentAccumulator()); EXPECT_EQ(0, analyzer_impl.CurrentRootAccumulator()); EXPECT_EQ(0, analyzer_impl.CurrentSquareAccumulator()); } } // This is a synthetic example that is just outside the dynamic range of a // double accumulator. Doubles have 53 significand bits. When cubed, the // difference between the small and big values below require just over 53 bits. TEST(FrameMetricsWindowedAnalyzerTest, NoAccumulatedPrecisionErrorBasic) { constexpr uint32_t big = 1 << 19; constexpr uint32_t small = 2; TestNoAccumulatedPrecisionError(big, small, 5e-8, 60); } // This is a more realistic scenario with orders of magnitude we are likely // to see in actual data. The error is small, but can become significant over // time. TEST(FrameMetricsWindowedAnalyzerTest, NoAccumulatedPrecisionErrorBig) { constexpr uint32_t big = 1 * base::TimeTicks::kMicrosecondsPerSecond; constexpr uint32_t small = 1 * base::TimeTicks::kMicrosecondsPerMillisecond; TestNoAccumulatedPrecisionError(big, small, 7e-8, 256); } // This is a scenario with orders of magnitude that we can see in our data, // but that will be rare. Even after a single bad pattern, the error is // significant. TEST(FrameMetricsWindowedAnalyzerTest, NoAccumulatedPrecisionErrorBigger) { constexpr uint32_t big = 20 * base::TimeTicks::kMicrosecondsPerSecond; constexpr uint32_t small = 1 * base::TimeTicks::kMicrosecondsPerMillisecond; TestNoAccumulatedPrecisionError(big, small, 2e-5, 1e6); } } // namespace } // namespace frame_metrics } // namespace ui