components/page_load_metrics/browser/layout_shift_normalization.cc - chromium/src - Git at Google

 // Copyright 2020 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 "components/page_load_metrics/browser/layout_shift_normalization.h"

 namespace page_load_metrics {
 constexpr auto NEW_SHIFT_BUFFER_WINDOW_DURATION =
     base::TimeDelta::FromSeconds(5);
 constexpr auto MAX_SHIFT_BUFFER_SIZE = 300;

 LayoutShiftNormalization::LayoutShiftNormalization() = default;
 LayoutShiftNormalization::~LayoutShiftNormalization() = default;

 void LayoutShiftNormalization::AddNewLayoutShifts(
     const std::vector<page_load_metrics::mojom::LayoutShiftPtr>& new_shifts,
     base::TimeTicks current_time,
     float cumulative_layout_shift_score) {
   if (new_shifts.empty() || normalized_cls_data_.data_tainted)
     return;

   if ((current_time - new_shifts[0]->layout_shift_time >
        NEW_SHIFT_BUFFER_WINDOW_DURATION) ||
       (recent_layout_shifts_.size() + new_shifts.size() >
        MAX_SHIFT_BUFFER_SIZE)) {
     // We can't keep all layout shifts all the time especially for long lived
     // pages. So we allow a layout shift to be delivered to the browser
     // process within 5 seconds and set a limit for the number of shifts we can
     // store in the browser process. If the delivery latency of a layout shift
     // is bigger than 5s, we can't process this layout shift and get the correct
     // normalization results, which means we should not report the results in
     // UKM.
     normalized_cls_data_.data_tainted = true;
     return;
   }

   // Append all shift data.
   for (const auto& layout_shift : new_shifts) {
     recent_layout_shifts_.emplace_back(layout_shift->layout_shift_time,
                                        layout_shift->layout_shift_score);
   }

   // At this point, the vector contains two sorted subvectors, and we can do an
   // in-place merge to create a sorted vector.
   std::inplace_merge(recent_layout_shifts_.begin(),
                      recent_layout_shifts_.end() - new_shifts.size(),
                      recent_layout_shifts_.end());

   // Now that we have a single sorted list of shifts, we can find the partition
   // point for old shifts which we are ready to delete
   auto first_non_stale = std::upper_bound(
       recent_layout_shifts_.begin(), recent_layout_shifts_.end(),
       current_time - NEW_SHIFT_BUFFER_WINDOW_DURATION,
       [](auto time, auto const& shift) { return time < shift.first; });

   // Update sliding and session window CLS.
   UpdateWindowCLS(current_time, recent_layout_shifts_.begin(), first_non_stale,
                   recent_layout_shifts_.end(), cumulative_layout_shift_score);

   // Finally, remove the stale shifts at this point.
   recent_layout_shifts_.erase(recent_layout_shifts_.begin(), first_non_stale);
 }

 void LayoutShiftNormalization::ClearAllLayoutShifts() {
   normalized_cls_data_ = NormalizedCLSData();
   recent_layout_shifts_.clear();
   sliding_300ms_.clear();
   sliding_1000ms_.clear();
   session_gap1000ms_max5000ms_ = SessionWindow();
   session_gap1000ms_ = SessionWindow();
   session_gap5000ms_ = SessionWindow();
   session_gap5000ms_count_ = 0;
 }

 void LayoutShiftNormalization::UpdateSlidingWindow(
     std::vector<SlidingWindow>* sliding_windows,
     base::TimeDelta duration,
     base::TimeTicks current_time,
     std::vector<std::pair<base::TimeTicks, double>>::const_iterator begin,
     std::vector<std::pair<base::TimeTicks, double>>::const_iterator end,
     double& max_score) {
   for (auto it = begin; it != end; ++it) {
     for (SlidingWindow& window : *sliding_windows) {
       if (it->first - window.start_time <= duration) {
         window.layout_shift_score += it->second;
         max_score = std::max(max_score, window.layout_shift_score);
       }
     }
     sliding_windows->emplace_back(SlidingWindow{it->first, it->second});
     max_score = std::max(max_score, it->second);
   }
   // Erase stale sliding windows.
   auto first_non_stale_window = std::upper_bound(
       sliding_windows->begin(), sliding_windows->end(),
       current_time - NEW_SHIFT_BUFFER_WINDOW_DURATION - duration,
       [](auto time, auto const& window) { return time < window.start_time; });
   sliding_windows->erase(sliding_windows->begin(), first_non_stale_window);
 }

 void LayoutShiftNormalization::UpdateSessionWindow(
     SessionWindow* session_window,
     base::TimeDelta gap,
     base::TimeDelta max_duration,
     std::vector<std::pair<base::TimeTicks, double>>::const_iterator begin,
     std::vector<std::pair<base::TimeTicks, double>>::const_iterator end,
     float& max_score,
     uint32_t& count) {
   for (auto it = begin; it != end; ++it) {
     if ((it->first - session_window->last_time > gap) ||
         (it->first - session_window->start_time > max_duration)) {
       session_window->start_time = it->first;
       session_window->layout_shift_score = 0;
       ++count;
     }
     session_window->last_time = it->first;
     session_window->layout_shift_score += it->second;
     max_score = std::max(max_score, session_window->layout_shift_score);
   }
 }

 // This function will update layout shift normalization results for sliding
 // windows and session windows twice. The first update is processing stale
 // layout shifts (current_time - layout_shift_time >= 5s) in
 // recent_layout_shifts_. The second update is continuing the first update by
 // processing remaining layout shifts in recent_layout_shifts_. Processing
 // layout shifts in order is very important to our algorithm or we may
 // miscalculate the number of windows or layout shift score for a window.
 // We assume the browser process can receive any layout shift within 5 seconds,
 // so there might be some non-stale layout shifts on the way and a newer layout
 // shift can be received earlier than an old one. This is one reason why we
 // update layout shift normalization twice. Another reason is we can't updating
 // normalization on demand when we record UKM because of constant class objects.
 // The first update is for updating the normalization for all stale layout shift
 // we received. The second update is for all layout shifts we received so far in
 // case we need to record UKM right away.
 void LayoutShiftNormalization::UpdateWindowCLS(
     base::TimeTicks current_time,
     std::vector<std::pair<base::TimeTicks, double>>::const_iterator first,
     std::vector<std::pair<base::TimeTicks, double>>::const_iterator
         first_non_stale,
     std::vector<std::pair<base::TimeTicks, double>>::const_iterator last,
     float cumulative_layout_shift_score) {
   float dummy_max = 0.0;
   uint32_t dummy_count = 0;
   // Update Sliding Windows.
   UpdateSlidingWindow(
       &sliding_300ms_, base::TimeDelta::FromMilliseconds(300), current_time,
       first, first_non_stale,
       normalized_cls_data_.sliding_windows_duration300ms_max_cls);
   UpdateSlidingWindow(
       &sliding_1000ms_, base::TimeDelta::FromMilliseconds(1000), current_time,
       first, first_non_stale,
       normalized_cls_data_.sliding_windows_duration1000ms_max_cls);
   auto tmp_sliding_300ms = sliding_300ms_;
   auto tmp_sliding_1000ms = sliding_1000ms_;

   // Update Session Windows.
   UpdateSessionWindow(
       &session_gap1000ms_max5000ms_, base::TimeDelta::FromMilliseconds(1000),
       base::TimeDelta::FromMilliseconds(5000), first, first_non_stale,
       normalized_cls_data_.session_windows_gap1000ms_max5000ms_max_cls,
       dummy_count);
   UpdateSessionWindow(
       &session_gap1000ms_, base::TimeDelta::FromMilliseconds(1000),
       base::TimeDelta::Max(), first, first_non_stale,
       normalized_cls_data_.session_windows_gap1000ms_maxMax_max_cls,
       dummy_count);
   UpdateSessionWindow(&session_gap5000ms_,
                       base::TimeDelta::FromMilliseconds(5000),
                       base::TimeDelta::Max(), first, first_non_stale, dummy_max,
                       session_gap5000ms_count_);

   auto tmp_session_gap1000ms_max5000ms = session_gap1000ms_max5000ms_;
   auto tmp_session_gap1000ms_ = session_gap1000ms_;
   auto tmp_session_gap5000ms_ = session_gap5000ms_;
   auto tmp_session_gap5000ms_count_ = session_gap5000ms_count_;

   UpdateSlidingWindow(
       &tmp_sliding_300ms, base::TimeDelta::FromMilliseconds(300), current_time,
       first_non_stale, last,
       normalized_cls_data_.sliding_windows_duration300ms_max_cls);
   UpdateSlidingWindow(
       &tmp_sliding_1000ms, base::TimeDelta::FromMilliseconds(1000),
       current_time, first_non_stale, last,
       normalized_cls_data_.sliding_windows_duration1000ms_max_cls);
   UpdateSessionWindow(
       &tmp_session_gap1000ms_max5000ms, base::TimeDelta::FromMilliseconds(1000),
       base::TimeDelta::FromMilliseconds(5000), first_non_stale, last,
       normalized_cls_data_.session_windows_gap1000ms_max5000ms_max_cls,
       dummy_count);
   UpdateSessionWindow(
       &tmp_session_gap1000ms_, base::TimeDelta::FromMilliseconds(1000),
       base::TimeDelta::Max(), first_non_stale, last,
       normalized_cls_data_.session_windows_gap1000ms_maxMax_max_cls,
       dummy_count);
   UpdateSessionWindow(&tmp_session_gap5000ms_,
                       base::TimeDelta::FromMilliseconds(5000),
                       base::TimeDelta::Max(), first_non_stale, last, dummy_max,
                       tmp_session_gap5000ms_count_);
   normalized_cls_data_.session_windows_gap5000ms_maxMax_average_cls =
       cumulative_layout_shift_score / tmp_session_gap5000ms_count_;
 }
 }  // namespace page_load_metrics
	// Copyright 2020 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 "components/page_load_metrics/browser/layout_shift_normalization.h"

	namespace page_load_metrics {
	constexpr auto NEW_SHIFT_BUFFER_WINDOW_DURATION =
	base::TimeDelta::FromSeconds(5);
	constexpr auto MAX_SHIFT_BUFFER_SIZE = 300;

	LayoutShiftNormalization::LayoutShiftNormalization() = default;
	LayoutShiftNormalization::~LayoutShiftNormalization() = default;

	void LayoutShiftNormalization::AddNewLayoutShifts(
	const std::vector<page_load_metrics::mojom::LayoutShiftPtr>& new_shifts,
	base::TimeTicks current_time,
	float cumulative_layout_shift_score) {
	if (new_shifts.empty() \|\| normalized_cls_data_.data_tainted)
	return;

	if ((current_time - new_shifts[0]->layout_shift_time >
	NEW_SHIFT_BUFFER_WINDOW_DURATION) \|\|
	(recent_layout_shifts_.size() + new_shifts.size() >
	MAX_SHIFT_BUFFER_SIZE)) {
	// We can't keep all layout shifts all the time especially for long lived
	// pages. So we allow a layout shift to be delivered to the browser
	// process within 5 seconds and set a limit for the number of shifts we can
	// store in the browser process. If the delivery latency of a layout shift
	// is bigger than 5s, we can't process this layout shift and get the correct
	// normalization results, which means we should not report the results in
	// UKM.
	normalized_cls_data_.data_tainted = true;
	return;
	}

	// Append all shift data.
	for (const auto& layout_shift : new_shifts) {
	recent_layout_shifts_.emplace_back(layout_shift->layout_shift_time,
	layout_shift->layout_shift_score);
	}

	// At this point, the vector contains two sorted subvectors, and we can do an
	// in-place merge to create a sorted vector.
	std::inplace_merge(recent_layout_shifts_.begin(),
	recent_layout_shifts_.end() - new_shifts.size(),
	recent_layout_shifts_.end());

	// Now that we have a single sorted list of shifts, we can find the partition
	// point for old shifts which we are ready to delete
	auto first_non_stale = std::upper_bound(
	recent_layout_shifts_.begin(), recent_layout_shifts_.end(),
	current_time - NEW_SHIFT_BUFFER_WINDOW_DURATION,
	[](auto time, auto const& shift) { return time < shift.first; });

	// Update sliding and session window CLS.
	UpdateWindowCLS(current_time, recent_layout_shifts_.begin(), first_non_stale,
	recent_layout_shifts_.end(), cumulative_layout_shift_score);

	// Finally, remove the stale shifts at this point.
	recent_layout_shifts_.erase(recent_layout_shifts_.begin(), first_non_stale);
	}

	void LayoutShiftNormalization::ClearAllLayoutShifts() {
	normalized_cls_data_ = NormalizedCLSData();
	recent_layout_shifts_.clear();
	sliding_300ms_.clear();
	sliding_1000ms_.clear();
	session_gap1000ms_max5000ms_ = SessionWindow();
	session_gap1000ms_ = SessionWindow();
	session_gap5000ms_ = SessionWindow();
	session_gap5000ms_count_ = 0;
	}

	void LayoutShiftNormalization::UpdateSlidingWindow(
	std::vector<SlidingWindow>* sliding_windows,
	base::TimeDelta duration,
	base::TimeTicks current_time,
	std::vector<std::pair<base::TimeTicks, double>>::const_iterator begin,
	std::vector<std::pair<base::TimeTicks, double>>::const_iterator end,
	double& max_score) {
	for (auto it = begin; it != end; ++it) {
	for (SlidingWindow& window : *sliding_windows) {
	if (it->first - window.start_time <= duration) {
	window.layout_shift_score += it->second;
	max_score = std::max(max_score, window.layout_shift_score);
	}
	}
	sliding_windows->emplace_back(SlidingWindow{it->first, it->second});
	max_score = std::max(max_score, it->second);
	}
	// Erase stale sliding windows.
	auto first_non_stale_window = std::upper_bound(
	sliding_windows->begin(), sliding_windows->end(),
	current_time - NEW_SHIFT_BUFFER_WINDOW_DURATION - duration,
	[](auto time, auto const& window) { return time < window.start_time; });
	sliding_windows->erase(sliding_windows->begin(), first_non_stale_window);
	}

	void LayoutShiftNormalization::UpdateSessionWindow(
	SessionWindow* session_window,
	base::TimeDelta gap,
	base::TimeDelta max_duration,
	std::vector<std::pair<base::TimeTicks, double>>::const_iterator begin,
	std::vector<std::pair<base::TimeTicks, double>>::const_iterator end,
	float& max_score,
	uint32_t& count) {
	for (auto it = begin; it != end; ++it) {
	if ((it->first - session_window->last_time > gap) \|\|
	(it->first - session_window->start_time > max_duration)) {
	session_window->start_time = it->first;
	session_window->layout_shift_score = 0;
	++count;
	}
	session_window->last_time = it->first;
	session_window->layout_shift_score += it->second;
	max_score = std::max(max_score, session_window->layout_shift_score);
	}
	}

	// This function will update layout shift normalization results for sliding
	// windows and session windows twice. The first update is processing stale
	// layout shifts (current_time - layout_shift_time >= 5s) in
	// recent_layout_shifts_. The second update is continuing the first update by
	// processing remaining layout shifts in recent_layout_shifts_. Processing
	// layout shifts in order is very important to our algorithm or we may
	// miscalculate the number of windows or layout shift score for a window.
	// We assume the browser process can receive any layout shift within 5 seconds,
	// so there might be some non-stale layout shifts on the way and a newer layout
	// shift can be received earlier than an old one. This is one reason why we
	// update layout shift normalization twice. Another reason is we can't updating
	// normalization on demand when we record UKM because of constant class objects.
	// The first update is for updating the normalization for all stale layout shift
	// we received. The second update is for all layout shifts we received so far in
	// case we need to record UKM right away.
	void LayoutShiftNormalization::UpdateWindowCLS(
	base::TimeTicks current_time,
	std::vector<std::pair<base::TimeTicks, double>>::const_iterator first,
	std::vector<std::pair<base::TimeTicks, double>>::const_iterator
	first_non_stale,
	std::vector<std::pair<base::TimeTicks, double>>::const_iterator last,
	float cumulative_layout_shift_score) {
	float dummy_max = 0.0;
	uint32_t dummy_count = 0;
	// Update Sliding Windows.
	UpdateSlidingWindow(
	&sliding_300ms_, base::TimeDelta::FromMilliseconds(300), current_time,
	first, first_non_stale,
	normalized_cls_data_.sliding_windows_duration300ms_max_cls);
	UpdateSlidingWindow(
	&sliding_1000ms_, base::TimeDelta::FromMilliseconds(1000), current_time,
	first, first_non_stale,
	normalized_cls_data_.sliding_windows_duration1000ms_max_cls);
	auto tmp_sliding_300ms = sliding_300ms_;
	auto tmp_sliding_1000ms = sliding_1000ms_;

	// Update Session Windows.
	UpdateSessionWindow(
	&session_gap1000ms_max5000ms_, base::TimeDelta::FromMilliseconds(1000),
	base::TimeDelta::FromMilliseconds(5000), first, first_non_stale,
	normalized_cls_data_.session_windows_gap1000ms_max5000ms_max_cls,
	dummy_count);
	UpdateSessionWindow(
	&session_gap1000ms_, base::TimeDelta::FromMilliseconds(1000),
	base::TimeDelta::Max(), first, first_non_stale,
	normalized_cls_data_.session_windows_gap1000ms_maxMax_max_cls,
	dummy_count);
	UpdateSessionWindow(&session_gap5000ms_,
	base::TimeDelta::FromMilliseconds(5000),
	base::TimeDelta::Max(), first, first_non_stale, dummy_max,
	session_gap5000ms_count_);

	auto tmp_session_gap1000ms_max5000ms = session_gap1000ms_max5000ms_;
	auto tmp_session_gap1000ms_ = session_gap1000ms_;
	auto tmp_session_gap5000ms_ = session_gap5000ms_;
	auto tmp_session_gap5000ms_count_ = session_gap5000ms_count_;

	UpdateSlidingWindow(
	&tmp_sliding_300ms, base::TimeDelta::FromMilliseconds(300), current_time,
	first_non_stale, last,
	normalized_cls_data_.sliding_windows_duration300ms_max_cls);
	UpdateSlidingWindow(
	&tmp_sliding_1000ms, base::TimeDelta::FromMilliseconds(1000),
	current_time, first_non_stale, last,
	normalized_cls_data_.sliding_windows_duration1000ms_max_cls);
	UpdateSessionWindow(
	&tmp_session_gap1000ms_max5000ms, base::TimeDelta::FromMilliseconds(1000),
	base::TimeDelta::FromMilliseconds(5000), first_non_stale, last,
	normalized_cls_data_.session_windows_gap1000ms_max5000ms_max_cls,
	dummy_count);
	UpdateSessionWindow(
	&tmp_session_gap1000ms_, base::TimeDelta::FromMilliseconds(1000),
	base::TimeDelta::Max(), first_non_stale, last,
	normalized_cls_data_.session_windows_gap1000ms_maxMax_max_cls,
	dummy_count);
	UpdateSessionWindow(&tmp_session_gap5000ms_,
	base::TimeDelta::FromMilliseconds(5000),
	base::TimeDelta::Max(), first_non_stale, last, dummy_max,
	tmp_session_gap5000ms_count_);
	normalized_cls_data_.session_windows_gap5000ms_maxMax_average_cls =
	cumulative_layout_shift_score / tmp_session_gap5000ms_count_;
	}
	} // namespace page_load_metrics