tracing/tracing/extras/chrome/estimated_input_latency.html - external/github.com/catapult-project/catapult - Git at Google

 <!DOCTYPE html>
 <!--
 Copyright 2016 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.
 -->

 <link rel="import" href="/tracing/metrics/system_health/loading_metric.html">
 <link rel="import" href="/tracing/value/histogram_set.html">

 <script>
 'use strict';
 tr.exportTo('tr.e.chrome', function() {
   // TODO(dproy): Because title and category are properties of TimedEvent
   // subclasses and not TimedEvent itself, we have to write our own "has title
   // and category" function rather than having it provided by TimedEvent.
   // This should be fixed.
   // https://github.com/catapult-project/catapult/issues/2784
   function hasTitleAndCategory(event, title, category) {
     return event.title === title && event.category &&
       tr.b.getCategoryParts(event.category).includes(category);
   }

   function getNavStartTimestamps(rendererHelper) {
     var navStartTimestamps = [];
     for (var e of rendererHelper.mainThread.sliceGroup.childEvents()) {
       if (hasTitleAndCategory(e, 'navigationStart', 'blink.user_timing')) {
         navStartTimestamps.push(e.start);
       }
     }
     return navStartTimestamps;
   }

   /**
    * Returns a map of renderer PIDs to array of timestamps at which the
    * renderer became interactive.
    */
   function getInteractiveTimestamps(model) {
     var interactiveTimestampsMap = new Map();
     var chromeHelper = model.getOrCreateHelper(
         tr.model.helpers.ChromeModelHelper);
     for (var rendererHelper of Object.values(chromeHelper.rendererHelpers)) {
       var timestamps = [];
       interactiveTimestampsMap.set(rendererHelper.pid, timestamps);
       var samples = tr.metrics.sh.collectLoadingMetricsForRenderer(
           rendererHelper).firstInteractiveSamples;
       for (var sample of samples) {
         timestamps.push(
             sample.diagnostics['Navigation infos'].value.interactive);
       }
     }
     return interactiveTimestampsMap;
   }

   /**
    * Returns an Array of task windows that start with the supplied interactive
    * timestamps.
    *
    * A task window is defined as the range of time from the time when the page
    * became interactive until either
    *
    *   1. The beginning of the next navigationStart event or
    *   2. The end of the trace
    *
    * This function only works when timestamps are from the same renderer. If
    * windows for multiple renderers need to be computed, the timestamps should
    * be separated for each renderer and this function should be called
    * separately for each.
    *
    * @param {!Array.<number>} interactiveTimestamps
    * @param {!Array.<number>} navStartTimestamps
    * @param {!number} traceEndTimestamp
    * @returns {!Array.<tr.b.math.Range>}
    */
   function getPostInteractiveTaskWindows(
       interactiveTimestamps, navStartTimestamps, traceEndTimestamp) {
     var navStartTsIndex = 0;
     var lastTaskWindowEndTs = undefined;
     var taskWindows = [];
     for (var currTTI of interactiveTimestamps) {
       // Find the first navigation start event after the interactive
       // timestamp.
       while (navStartTsIndex < navStartTimestamps.length &&
           navStartTimestamps[navStartTsIndex] < currTTI) {
         navStartTsIndex++;
       }

       var taskWindowEndTs = navStartTsIndex < navStartTimestamps.length ?
           navStartTimestamps[navStartTsIndex] : traceEndTimestamp;

       if (taskWindowEndTs === lastTaskWindowEndTs) {
         // This is the case where we have two different interactive timestamps
         // with no navigationStart event between them. This is only possible
         // when two different pages are sharing the same renderer process (and
         // therefore the same renderer scheduler). We cannot define a proper
         // task window in this case to calculate Estimated Input Latency.
         throw Error('Encountered two consecutive interactive timestamps ' +
             'with no navigationStart between them. ' +
             'PostInteractiveTaskWindow is not well defined in this case.');
       }

       taskWindows.push(tr.b.math.Range.fromExplicitRange(
           currTTI, taskWindowEndTs));
       lastTaskWindowEndTs = taskWindowEndTs;
     }
     return taskWindows;
   }

   /**
    * Returns the contribution of the given task to expected queueing time
    * in the given time window.
    *
    * The result is probabilityOf(task) * expectedQueueTimeDueTo(task),
    * where
    * - probabilityOf(task) = probability of input arriving while the given
    *   task is running.
    * - expectedQueueingTimeDueTo(task) = expected time until the end of the
    *   given task for input arriving while the task is running.
    *
    * We assume that input arrival time is uniformly distributed in the given
    * time window.
    *
    * @param {!tr.b.math.Range} A time window.
    * @param {!Array.<!{start: number, end: number, weight: number}>} A list of
    *        weighted tasks. The weight of a task must be between 0.0 and 1.0.
    * @returns {number}
    */
   function contributionToEQT(window, task) {
     var startInWindow = Math.max(window.min, task.start);
     var endInWindow = Math.min(window.max, task.end);
     var durationInWindow = endInWindow - startInWindow;
     if (durationInWindow <= 0) return 0;
     var probabilityOfTask = durationInWindow / (window.max - window.min);
     var minQueueingTime = task.end - endInWindow;
     var maxQueueingTime = task.end - startInWindow;
     var expectedQueueingTimeDueToTask =
         (maxQueueingTime + minQueueingTime) / 2;
     return probabilityOfTask * expectedQueueingTimeDueToTask;
   }

   /**
    * Returns weighted expected queueing time (EQT) for the given time window and
    * the given set of weighted tasks. The tasks must not overlap.
    *
    * The weighted EQT is computed as
    *   sum(contributionToEQT(window, task) * task.weight)
    * for all tasks in weightedTasks, where
    * - contributionToEQT is the function defined above.
    * - task.weight is an arbitrary number between 0.0 and 1.0. This is useful
    *   for computing contribution of chrome subcomponents (e.g. GC) to
    *   the expected queueing time for EQT diagnostics.
    *
    * We assume that input arrival time is uniformly distributed in the given
    * time window.
    *
    * @param {!tr.b.math.Range} A time window.
    * @param {!Array.<!{start: number, end: number, weight: number}>} A list of
    *        weighted tasks. The weight of a task must be between 0.0 and 1.0.
    * @returns {number}
    */
   function weightedExpectedQueueingTime(window, weightedTasks) {
     var result = 0;
     for (var task of weightedTasks) {
       result += contributionToEQT(window, task) * task.weight;
     }
     return result;
   }

   /**
    * Returns expected queueing time for the given time window and
    * the given set of tasks. The tasks must not overlap.
    *
    * @param {!tr.b.math.Range} A time window.
    * @param {!Array.<!{start: number, end: number}>} A list of tasks.
    * @returns {number}
    */
   function expectedQueueingTime(window, tasks) {
     return weightedExpectedQueueingTime(window, tasks.map(function(task) {
       return { start: task.start, end: task.end, weight: 1 };
     }));
   }

   /**
    * Object of this calss represents the sliding window and maintains its
    * main invariant: windowEQT = firstTaskEQT + innerEQT + lastTaskEQT.
    * It is intended to be used only in maxExpectedQueueingTimeInSlidingWindow().
    */
   class SlidingWindow {
     /**
      * @param {number} The starting time of the sliding window.
      * @param {number} The window size.
      * @param {!Array.<!{start: number, end: number}>} A list of tasks sorted by
      *     task start time.
      */
     constructor(startTime, windowSize, sortedTasks) {
       /**
        * @private @const {number} The window size.
        */
       this.windowSize_ = windowSize;
       /**
        * @private @const {!Array.<!{start: number, end: number}>} The tasks.
        */
       this.sortedTasks_ = sortedTasks;
       /**
        * @private {!tr.b.math.Range} The endpoints of the sliding window.
        */
       this.range_ = tr.b.math.Range.fromExplicitRange(
           startTime, startTime + windowSize);
       /**
        * @private {number} The index of the first task in the sortedTasks that
        *     ends after this window starts:
        *     this.range_.min < this.sortedTasks_[this.firstTaskIndex_].end.
        */
       this.firstTaskIndex_ =
           sortedTasks.findIndex(task => startTime < task.end);
       if (this.firstTaskIndex_ === -1)
         this.firstTaskIndex_ = sortedTasks.length;
       /**
        * @private {number} The index of the last task in the sortedTasks that
        *     starts before this window ends:
        *     this.range.max > this.sortedTasks_[lastTaskIndex_].start.
        */
       this.lastTaskIndex_ = -1;
       while (this.lastTaskIndex_ + 1 < sortedTasks.length &&
           sortedTasks[this.lastTaskIndex_ + 1].start < startTime + windowSize) {
         this.lastTaskIndex_++;
       }
       /**
        * @private {number} The sum of EQT contributions for all tasks between
        *     the first task and the last task (excluding the first and the last
        *     tasks). All such tasks are completely inside the window.
        */
       this.innerEQT_ = 0;
       for (var i = this.firstTaskIndex_ + 1; i < this.lastTaskIndex_; i++) {
         this.innerEQT_ += contributionToEQT(this.range_, sortedTasks[i]);
       }
     }

     /**
      * @returns the EQT for this window.
      */
     get getEQT() {
       var firstTaskEQT = 0;
       if (this.firstTaskIndex_ < this.sortedTasks_.length) {
         firstTaskEQT = contributionToEQT(this.range_,
             this.sortedTasks_[this.firstTaskIndex_]);
       }
       var lastTaskEQT = 0;
       if (this.firstTaskIndex_ < this.lastTaskIndex_) {
         lastTaskEQT = contributionToEQT(this.range_,
             this.sortedTasks_[this.lastTaskIndex_]);
       }
       return firstTaskEQT + this.innerEQT_ + lastTaskEQT;
     }

     /**
      * Moves the window to the given time t.
      * @param {number} The time.
      */
     slide(t) {
       this.range_ = tr.b.math.Range.fromExplicitRange(t, t + this.windowSize_);
       if (this.firstTaskIndex_ < this.sortedTasks_.length &&
           this.sortedTasks_[this.firstTaskIndex_].end <= t) {
         // The first task moved out of the window.
         this.firstTaskIndex_++;
         if (this.firstTaskIndex_ < this.lastTaskIndex_) {
           // The new first window was accounted in innerEQT. Undo that.
           this.innerEQT_ -= contributionToEQT(this.range_,
               this.sortedTasks_[this.firstTaskIndex_]);
         }
       }
       if (this.lastTaskIndex_ + 1 < this.sortedTasks_.length &&
           this.sortedTasks_[this.lastTaskIndex_ + 1].start <
               t + this.windowSize_) {
         // A new task moved in the window.
         if (this.firstTaskIndex_ < this.lastTaskIndex_) {
           // The old last task is completely inside the window.
           // Account it in innerEQT.
           this.innerEQT_ += contributionToEQT(this.range_,
               this.sortedTasks_[this.lastTaskIndex_]);
         }
         this.lastTaskIndex_++;
       }
     }
   }

   /**
    * Returns maximum expected queueing time for time window of the given size
    * that slides from the startTime to the endTime:
    *   max { expectedQueueingTime(window(t, t + windowSize), tasks),
    *         for all startTime <= t && t + w <= endTime }.
    * See https://goo.gl/jmWpMl for the description of the algorithm.
    *
    * @param {number} start time for the sliding window.
    * @param {number} end time for the sliding window.
    * @param {number} the size of the sliding window.
    * @param {!Array.<!{start: number, end: number}>} A list of tasks.
    *        The tasks must not overlap.
    * @returns {number}
    */
   function maxExpectedQueueingTimeInSlidingWindow(startTime, endTime,
       windowSize, tasks) {
     if (windowSize <= 0) {
       throw Error('The window size must be positive number');
     }
     if (startTime + windowSize > endTime) {
       throw Error('The sliding window must fit in the specified time range');
     }

     var sortedTasks = tasks.slice().sort((a, b) => a.start - b.start);

     for (var i = 1; i < sortedTasks.length; i++) {
       // Due to floating-point precision errors it might happen that the end
       // of the previous task is larger than the start of the current task.
       // Here is an example from a real trace of system-health benchmark:
       // Task 1: start=1932.0179090499878 end=1932.070909049988.
       // Task 2: start=1932.0709090232850 end=1932.118909023285.
       // To account for precision errors we consider tasks as overlapping
       // if the overlap is sufficiently large.
       if (sortedTasks[i - 1].end > sortedTasks[i].start + 1e-3) {
         throw Error('Tasks must not overlap');
       }
     }

     // Collect all time points that the sliding window needs to stop at.
     // See https://goo.gl/jmWpMl for justification.
     var endpoints = [];
     endpoints.push(startTime);
     endpoints.push(endTime - windowSize);
     for (var task of tasks) {
       endpoints.push(task.start - windowSize);
       endpoints.push(task.start);
       endpoints.push(task.end - windowSize);
       endpoints.push(task.end);
     }
     endpoints = endpoints.filter(
         x => (startTime <= x && x + windowSize <= endTime));
     endpoints.sort((a, b) => a - b);

     // Slide the window and compute maxEQT.
     var slidingWindow = new SlidingWindow(
         endpoints[0], windowSize, sortedTasks);
     var maxEQT = 0;
     for (var t of endpoints) {
       slidingWindow.slide(t);
       maxEQT = Math.max(maxEQT, slidingWindow.getEQT);
     }
     return maxEQT;
   }

   return {
     getPostInteractiveTaskWindows,
     getNavStartTimestamps,
     getInteractiveTimestamps,
     expectedQueueingTime,
     maxExpectedQueueingTimeInSlidingWindow,
     weightedExpectedQueueingTime
   };
 });
 </script>
	<!DOCTYPE html>
	<!--
	Copyright 2016 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.
	-->

	<link rel="import" href="/tracing/metrics/system_health/loading_metric.html">
	<link rel="import" href="/tracing/value/histogram_set.html">

	<script>
	'use strict';
	tr.exportTo('tr.e.chrome', function() {
	// TODO(dproy): Because title and category are properties of TimedEvent
	// subclasses and not TimedEvent itself, we have to write our own "has title
	// and category" function rather than having it provided by TimedEvent.
	// This should be fixed.
	// https://github.com/catapult-project/catapult/issues/2784
	function hasTitleAndCategory(event, title, category) {
	return event.title === title && event.category &&
	tr.b.getCategoryParts(event.category).includes(category);
	}

	function getNavStartTimestamps(rendererHelper) {
	var navStartTimestamps = [];
	for (var e of rendererHelper.mainThread.sliceGroup.childEvents()) {
	if (hasTitleAndCategory(e, 'navigationStart', 'blink.user_timing')) {
	navStartTimestamps.push(e.start);
	}
	}
	return navStartTimestamps;
	}

	/**
	* Returns a map of renderer PIDs to array of timestamps at which the
	* renderer became interactive.
	*/
	function getInteractiveTimestamps(model) {
	var interactiveTimestampsMap = new Map();
	var chromeHelper = model.getOrCreateHelper(
	tr.model.helpers.ChromeModelHelper);
	for (var rendererHelper of Object.values(chromeHelper.rendererHelpers)) {
	var timestamps = [];
	interactiveTimestampsMap.set(rendererHelper.pid, timestamps);
	var samples = tr.metrics.sh.collectLoadingMetricsForRenderer(
	rendererHelper).firstInteractiveSamples;
	for (var sample of samples) {
	timestamps.push(
	sample.diagnostics['Navigation infos'].value.interactive);
	}
	}
	return interactiveTimestampsMap;
	}

	/**
	* Returns an Array of task windows that start with the supplied interactive
	* timestamps.
	*
	* A task window is defined as the range of time from the time when the page
	* became interactive until either
	*
	* 1. The beginning of the next navigationStart event or
	* 2. The end of the trace
	*
	* This function only works when timestamps are from the same renderer. If
	* windows for multiple renderers need to be computed, the timestamps should
	* be separated for each renderer and this function should be called
	* separately for each.
	*
	* @param {!Array.<number>} interactiveTimestamps
	* @param {!Array.<number>} navStartTimestamps
	* @param {!number} traceEndTimestamp
	* @returns {!Array.<tr.b.math.Range>}
	*/
	function getPostInteractiveTaskWindows(
	interactiveTimestamps, navStartTimestamps, traceEndTimestamp) {
	var navStartTsIndex = 0;
	var lastTaskWindowEndTs = undefined;
	var taskWindows = [];
	for (var currTTI of interactiveTimestamps) {
	// Find the first navigation start event after the interactive
	// timestamp.
	while (navStartTsIndex < navStartTimestamps.length &&
	navStartTimestamps[navStartTsIndex] < currTTI) {
	navStartTsIndex++;
	}

	var taskWindowEndTs = navStartTsIndex < navStartTimestamps.length ?
	navStartTimestamps[navStartTsIndex] : traceEndTimestamp;

	if (taskWindowEndTs === lastTaskWindowEndTs) {
	// This is the case where we have two different interactive timestamps
	// with no navigationStart event between them. This is only possible
	// when two different pages are sharing the same renderer process (and
	// therefore the same renderer scheduler). We cannot define a proper
	// task window in this case to calculate Estimated Input Latency.
	throw Error('Encountered two consecutive interactive timestamps ' +
	'with no navigationStart between them. ' +
	'PostInteractiveTaskWindow is not well defined in this case.');
	}

	taskWindows.push(tr.b.math.Range.fromExplicitRange(
	currTTI, taskWindowEndTs));
	lastTaskWindowEndTs = taskWindowEndTs;
	}
	return taskWindows;
	}

	/**
	* Returns the contribution of the given task to expected queueing time
	* in the given time window.
	*
	* The result is probabilityOf(task) * expectedQueueTimeDueTo(task),
	* where
	* - probabilityOf(task) = probability of input arriving while the given
	* task is running.
	* - expectedQueueingTimeDueTo(task) = expected time until the end of the
	* given task for input arriving while the task is running.
	*
	* We assume that input arrival time is uniformly distributed in the given
	* time window.
	*
	* @param {!tr.b.math.Range} A time window.
	* @param {!Array.<!{start: number, end: number, weight: number}>} A list of
	* weighted tasks. The weight of a task must be between 0.0 and 1.0.
	* @returns {number}
	*/
	function contributionToEQT(window, task) {
	var startInWindow = Math.max(window.min, task.start);
	var endInWindow = Math.min(window.max, task.end);
	var durationInWindow = endInWindow - startInWindow;
	if (durationInWindow <= 0) return 0;
	var probabilityOfTask = durationInWindow / (window.max - window.min);
	var minQueueingTime = task.end - endInWindow;
	var maxQueueingTime = task.end - startInWindow;
	var expectedQueueingTimeDueToTask =
	(maxQueueingTime + minQueueingTime) / 2;
	return probabilityOfTask * expectedQueueingTimeDueToTask;
	}

	/**
	* Returns weighted expected queueing time (EQT) for the given time window and
	* the given set of weighted tasks. The tasks must not overlap.
	*
	* The weighted EQT is computed as
	* sum(contributionToEQT(window, task) * task.weight)
	* for all tasks in weightedTasks, where
	* - contributionToEQT is the function defined above.
	* - task.weight is an arbitrary number between 0.0 and 1.0. This is useful
	* for computing contribution of chrome subcomponents (e.g. GC) to
	* the expected queueing time for EQT diagnostics.
	*
	* We assume that input arrival time is uniformly distributed in the given
	* time window.
	*
	* @param {!tr.b.math.Range} A time window.
	* @param {!Array.<!{start: number, end: number, weight: number}>} A list of
	* weighted tasks. The weight of a task must be between 0.0 and 1.0.
	* @returns {number}
	*/
	function weightedExpectedQueueingTime(window, weightedTasks) {
	var result = 0;
	for (var task of weightedTasks) {
	result += contributionToEQT(window, task) * task.weight;
	}
	return result;
	}

	/**
	* Returns expected queueing time for the given time window and
	* the given set of tasks. The tasks must not overlap.
	*
	* @param {!tr.b.math.Range} A time window.
	* @param {!Array.<!{start: number, end: number}>} A list of tasks.
	* @returns {number}
	*/
	function expectedQueueingTime(window, tasks) {
	return weightedExpectedQueueingTime(window, tasks.map(function(task) {
	return { start: task.start, end: task.end, weight: 1 };
	}));
	}

	/**
	* Object of this calss represents the sliding window and maintains its
	* main invariant: windowEQT = firstTaskEQT + innerEQT + lastTaskEQT.
	* It is intended to be used only in maxExpectedQueueingTimeInSlidingWindow().
	*/
	class SlidingWindow {
	/**
	* @param {number} The starting time of the sliding window.
	* @param {number} The window size.
	* @param {!Array.<!{start: number, end: number}>} A list of tasks sorted by
	* task start time.
	*/
	constructor(startTime, windowSize, sortedTasks) {
	/**
	* @private @const {number} The window size.
	*/
	this.windowSize_ = windowSize;
	/**
	* @private @const {!Array.<!{start: number, end: number}>} The tasks.
	*/
	this.sortedTasks_ = sortedTasks;
	/**
	* @private {!tr.b.math.Range} The endpoints of the sliding window.
	*/
	this.range_ = tr.b.math.Range.fromExplicitRange(
	startTime, startTime + windowSize);
	/**
	* @private {number} The index of the first task in the sortedTasks that
	* ends after this window starts:
	* this.range_.min < this.sortedTasks_[this.firstTaskIndex_].end.
	*/
	this.firstTaskIndex_ =
	sortedTasks.findIndex(task => startTime < task.end);
	if (this.firstTaskIndex_ === -1)
	this.firstTaskIndex_ = sortedTasks.length;
	/**
	* @private {number} The index of the last task in the sortedTasks that
	* starts before this window ends:
	* this.range.max > this.sortedTasks_[lastTaskIndex_].start.
	*/
	this.lastTaskIndex_ = -1;
	while (this.lastTaskIndex_ + 1 < sortedTasks.length &&
	sortedTasks[this.lastTaskIndex_ + 1].start < startTime + windowSize) {
	this.lastTaskIndex_++;
	}
	/**
	* @private {number} The sum of EQT contributions for all tasks between
	* the first task and the last task (excluding the first and the last
	* tasks). All such tasks are completely inside the window.
	*/
	this.innerEQT_ = 0;
	for (var i = this.firstTaskIndex_ + 1; i < this.lastTaskIndex_; i++) {
	this.innerEQT_ += contributionToEQT(this.range_, sortedTasks[i]);
	}
	}

	/**
	* @returns the EQT for this window.
	*/
	get getEQT() {
	var firstTaskEQT = 0;
	if (this.firstTaskIndex_ < this.sortedTasks_.length) {
	firstTaskEQT = contributionToEQT(this.range_,
	this.sortedTasks_[this.firstTaskIndex_]);
	}
	var lastTaskEQT = 0;
	if (this.firstTaskIndex_ < this.lastTaskIndex_) {
	lastTaskEQT = contributionToEQT(this.range_,
	this.sortedTasks_[this.lastTaskIndex_]);
	}
	return firstTaskEQT + this.innerEQT_ + lastTaskEQT;
	}

	/**
	* Moves the window to the given time t.
	* @param {number} The time.
	*/
	slide(t) {
	this.range_ = tr.b.math.Range.fromExplicitRange(t, t + this.windowSize_);
	if (this.firstTaskIndex_ < this.sortedTasks_.length &&
	this.sortedTasks_[this.firstTaskIndex_].end <= t) {
	// The first task moved out of the window.
	this.firstTaskIndex_++;
	if (this.firstTaskIndex_ < this.lastTaskIndex_) {
	// The new first window was accounted in innerEQT. Undo that.
	this.innerEQT_ -= contributionToEQT(this.range_,
	this.sortedTasks_[this.firstTaskIndex_]);
	}
	}
	if (this.lastTaskIndex_ + 1 < this.sortedTasks_.length &&
	this.sortedTasks_[this.lastTaskIndex_ + 1].start <
	t + this.windowSize_) {
	// A new task moved in the window.
	if (this.firstTaskIndex_ < this.lastTaskIndex_) {
	// The old last task is completely inside the window.
	// Account it in innerEQT.
	this.innerEQT_ += contributionToEQT(this.range_,
	this.sortedTasks_[this.lastTaskIndex_]);
	}
	this.lastTaskIndex_++;
	}
	}
	}

	/**
	* Returns maximum expected queueing time for time window of the given size
	* that slides from the startTime to the endTime:
	* max { expectedQueueingTime(window(t, t + windowSize), tasks),
	* for all startTime <= t && t + w <= endTime }.
	* See https://goo.gl/jmWpMl for the description of the algorithm.
	*
	* @param {number} start time for the sliding window.
	* @param {number} end time for the sliding window.
	* @param {number} the size of the sliding window.
	* @param {!Array.<!{start: number, end: number}>} A list of tasks.
	* The tasks must not overlap.
	* @returns {number}
	*/
	function maxExpectedQueueingTimeInSlidingWindow(startTime, endTime,
	windowSize, tasks) {
	if (windowSize <= 0) {
	throw Error('The window size must be positive number');
	}
	if (startTime + windowSize > endTime) {
	throw Error('The sliding window must fit in the specified time range');
	}

	var sortedTasks = tasks.slice().sort((a, b) => a.start - b.start);

	for (var i = 1; i < sortedTasks.length; i++) {
	// Due to floating-point precision errors it might happen that the end
	// of the previous task is larger than the start of the current task.
	// Here is an example from a real trace of system-health benchmark:
	// Task 1: start=1932.0179090499878 end=1932.070909049988.
	// Task 2: start=1932.0709090232850 end=1932.118909023285.
	// To account for precision errors we consider tasks as overlapping
	// if the overlap is sufficiently large.
	if (sortedTasks[i - 1].end > sortedTasks[i].start + 1e-3) {
	throw Error('Tasks must not overlap');
	}
	}

	// Collect all time points that the sliding window needs to stop at.
	// See https://goo.gl/jmWpMl for justification.
	var endpoints = [];
	endpoints.push(startTime);
	endpoints.push(endTime - windowSize);
	for (var task of tasks) {
	endpoints.push(task.start - windowSize);
	endpoints.push(task.start);
	endpoints.push(task.end - windowSize);
	endpoints.push(task.end);
	}
	endpoints = endpoints.filter(
	x => (startTime <= x && x + windowSize <= endTime));
	endpoints.sort((a, b) => a - b);

	// Slide the window and compute maxEQT.
	var slidingWindow = new SlidingWindow(
	endpoints[0], windowSize, sortedTasks);
	var maxEQT = 0;
	for (var t of endpoints) {
	slidingWindow.slide(t);
	maxEQT = Math.max(maxEQT, slidingWindow.getEQT);
	}
	return maxEQT;
	}

	return {
	getPostInteractiveTaskWindows,
	getNavStartTimestamps,
	getInteractiveTimestamps,
	expectedQueueingTime,
	maxExpectedQueueingTimeInSlidingWindow,
	weightedExpectedQueueingTime
	};
	});
	</script>