clovis: Estimate cost of a load, until a given point.

Review URL: https://codereview.chromium.org/1827813005

Cr-Commit-Position: refs/heads/master@{#383318}

8 files changed, 514 insertions, 5 deletions

diff --git a/tools/android/loading/dependency_graph.py b/tools/android/loading/dependency_graph.py
new file mode 100644
index 0000000..23285cc
--- /dev/null
+++ b/tools/android/loading/dependency_graph.py
@@ -0,0 +1,72 @@
+# 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.
+
+"""Request dependency graph."""
+
+import graph
+import request_track
+
+
+class _RequestNode(graph.Node):
+  def __init__(self, request):
+    super(_RequestNode, self).__init__()
+    self.request = request
+    self.cost = request.Cost()
+
+
+class _Edge(graph.Edge):
+  def __init__(self, from_node, to_node, reason):
+    super(_Edge, self).__init__(from_node, to_node)
+    self.reason = reason
+    self.cost = request_track.TimeBetween(
+        self.from_node.request, self.to_node.request, self.reason)
+
+
+class RequestDependencyGraph(object):
+  """Request dependency graph."""
+  def __init__(self, requests, dependencies_lens):
+    """Creates a request dependency graph.
+
+    Args:
+      requests: ([Request]) a list of requests.
+      dependencies_lens: (RequestDependencyLens)
+    """
+    self._requests = requests
+    deps = dependencies_lens.GetRequestDependencies()
+    self._nodes_by_id = {r.request_id : _RequestNode(r) for r in self._requests}
+    edges = []
+    for (parent_request, child_request, reason) in deps:
+      if (parent_request.request_id not in self._nodes_by_id
+          or child_request.request_id not in self._nodes_by_id):
+        continue
+      parent_node = self._nodes_by_id[parent_request.request_id]
+      child_node = self._nodes_by_id[child_request.request_id]
+      edges.append(_Edge(parent_node, child_node, reason))
+    self._first_request_node = self._nodes_by_id[self._requests[0].request_id]
+    self._deps_graph = graph.DirectedGraph(self._nodes_by_id.values(), edges)
+
+  def UpdateRequestsCost(self, request_id_to_cost):
+    """Updates the cost of the nodes identified by their request ID.
+
+    Args:
+      request_id_to_cost: {request_id: new_cost} Can be a superset of the
+                          requests actually present in the graph.
+
+    """
+    for node in self._deps_graph.Nodes():
+      request_id = node.request.request_id
+      if request_id in request_id_to_cost:
+        node.cost = request_id_to_cost[request_id]
+
+  def Cost(self, from_first_request=True):
+    """Returns the cost of the graph, that is the costliest path.
+
+    Args:
+      from_first_request: (boolean) If True, only considers paths that originate
+                          from the first request node.
+    """
+    if from_first_request:
+      return self._deps_graph.Cost([self._first_request_node])
+    else:
+      return self._deps_graph.Cost()
diff --git a/tools/android/loading/dependency_graph_unittest.py b/tools/android/loading/dependency_graph_unittest.py
new file mode 100644
index 0000000..448a234
--- /dev/null
+++ b/tools/android/loading/dependency_graph_unittest.py
@@ -0,0 +1,54 @@
+# 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.
+
+import unittest
+
+import dependency_graph
+import request_dependencies_lens
+from request_dependencies_lens_unittest import TestRequests
+import request_track
+
+
+class RequestDependencyGraphTestCase(unittest.TestCase):
+  def setUp(self):
+    super(RequestDependencyGraphTestCase, self).setUp()
+    self.trace = TestRequests.CreateLoadingTrace()
+
+  def testUpdateRequestCost(self):
+    requests = self.trace.request_track.GetEvents()
+    requests[0].timing = request_track.TimingFromDict(
+        {'requestTime': 12, 'loadingFinished': 10})
+    dependencies_lens = request_dependencies_lens.RequestDependencyLens(
+        self.trace)
+    g = dependency_graph.RequestDependencyGraph(requests, dependencies_lens)
+    self.assertEqual(10, g.Cost())
+    request_id = requests[0].request_id
+    g.UpdateRequestsCost({request_id: 100})
+    self.assertEqual(100, g.Cost())
+    g.UpdateRequestsCost({'unrelated_id': 1000})
+    self.assertEqual(100, g.Cost())
+
+  def testCost(self):
+    requests = self.trace.request_track.GetEvents()
+    for (index, request) in enumerate(requests):
+      request.timing = request_track.TimingFromDict(
+          {'requestTime': index, 'receiveHeadersEnd': 10,
+           'loadingFinished': 10})
+    dependencies_lens = request_dependencies_lens.RequestDependencyLens(
+        self.trace)
+    g = dependency_graph.RequestDependencyGraph(requests, dependencies_lens)
+    # First redirect -> Second redirect -> Redirected Request -> Request ->
+    # JS Request 2
+    self.assertEqual(7010, g.Cost())
+    # Not on the critical path
+    g.UpdateRequestsCost({TestRequests.JS_REQUEST.request_id: 0})
+    self.assertEqual(7010, g.Cost())
+    g.UpdateRequestsCost({TestRequests.FIRST_REDIRECT_REQUEST.request_id: 0})
+    self.assertEqual(7000, g.Cost())
+    g.UpdateRequestsCost({TestRequests.SECOND_REDIRECT_REQUEST.request_id: 0})
+    self.assertEqual(6990, g.Cost())
+
+
+if __name__ == '__main__':
+  unittest.main()
diff --git a/tools/android/loading/graph.py b/tools/android/loading/graph.py
new file mode 100644
index 0000000..a665439
--- /dev/null
+++ b/tools/android/loading/graph.py
@@ -0,0 +1,175 @@
+# 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.
+
+"""Support for graphs."""
+
+import collections
+
+
+class Node(object):
+  """A node in a Graph.
+
+  Nodes are identified within a graph using object identity.
+  """
+  def __init__(self):
+    """Create a new node."""
+    self.cost = 0
+
+
+class Edge(object):
+  """Represents an edge in a graph."""
+  def __init__(self, from_node, to_node):
+    """Creates an Edge.
+
+    Args:
+      from_node: (Node) Start node.
+      to_node: (Node) End node.
+    """
+    self.from_node = from_node
+    self.to_node = to_node
+    self.cost = 0
+
+
+class DirectedGraph(object):
+  """Directed graph.
+
+  A graph is identified by a list of nodes and a list of edges. It does not need
+  to be acyclic, but then some methods will fail.
+  """
+  def __init__(self, nodes, edges):
+    """Builds a graph from a set of node and edges.
+
+    Note that the edges referencing a node not in the provided list are dropped.
+
+    Args:
+      nodes: ([Node]) List of nodes.
+      edges: ([Edge]) List of Edges.
+    """
+    assert all(isinstance(node, Node) for node in nodes)
+    assert all(isinstance(edge, Edge) for edge in edges)
+    self._nodes = set(nodes)
+    self._edges = set(filter(
+        lambda e: e.from_node in self._nodes and e.to_node in self._nodes,
+        edges))
+    self._in_edges = {n: [] for n in self._nodes}
+    self._out_edges = {n: [] for n in self._nodes}
+    for edge in self._edges:
+      self._out_edges[edge.from_node].append(edge)
+      self._in_edges[edge.to_node].append(edge)
+
+  def OutEdges(self, node):
+    """Returns a list of edges starting from a node.
+    """
+    return self._out_edges[node]
+
+  def InEdges(self, node):
+    """Returns a list of edges ending at a node."""
+    return self._in_edges[node]
+
+  def Nodes(self):
+    """Returns the set of nodes of this graph."""
+    return self._nodes
+
+  def Edges(self):
+    """Returns the set of edges of this graph."""
+    return self._edges
+
+  def UpdateEdge(self, edge, new_from_node, new_to_node):
+    """Updates an edge.
+
+    Args:
+      edge:
+      new_from_node:
+      new_to_node:
+    """
+    assert edge in self._edges
+    assert new_from_node in self._nodes
+    assert new_to_node in self._nodes
+    self._in_edges[edge.to_node].remove(edge)
+    self._out_edges[edge.from_node].remove(edge)
+    edge.from_node = new_from_node
+    edge.to_node = new_to_node
+    # TODO(lizeb): Check for duplicate edges?
+    self._in_edges[edge.to_node].append(edge)
+    self._out_edges[edge.from_node].append(edge)
+
+  def TopologicalSort(self, roots=None):
+    """Returns a list of nodes, in topological order.
+
+      Args:
+        roots: ([Node]) If set, the topological sort will only consider nodes
+                        reachable from this list of sources.
+    """
+    sorted_nodes = []
+    if roots is None:
+      nodes_subset = self._nodes
+    else:
+      nodes_subset = self.ReachableNodes(roots)
+    remaining_in_edges = {n: 0 for n in nodes_subset}
+    for edge in self._edges:
+      if edge.from_node in nodes_subset and edge.to_node in nodes_subset:
+        remaining_in_edges[edge.to_node] += 1
+    sources = [node for (node, count) in remaining_in_edges.items()
+               if count == 0]
+    while sources:
+      node = sources.pop(0)
+      sorted_nodes.append(node)
+      for e in self.OutEdges(node):
+        successor = e.to_node
+        if successor not in nodes_subset:
+          continue
+        assert remaining_in_edges[successor] > 0
+        remaining_in_edges[successor] -= 1
+        if remaining_in_edges[successor] == 0:
+          sources.append(successor)
+    return sorted_nodes
+
+  def ReachableNodes(self, roots):
+    """Returns a list of nodes from a set of root nodes."""
+    visited = set()
+    fifo = collections.deque(roots)
+    while len(fifo) != 0:
+      node = fifo.pop()
+      visited.add(node)
+      for e in self.OutEdges(node):
+        if e.to_node not in visited:
+          visited.add(e.to_node)
+        fifo.appendleft(e.to_node)
+    return list(visited)
+
+  def Cost(self, roots=None, path_list=None, costs_out=None):
+    """Compute the cost of the graph.
+
+    Args:
+      roots: ([Node]) If set, only compute the cost of the paths reachable
+             from this list of nodes.
+      path_list: if not None, gets a list of nodes in the longest path.
+      costs_out: if not None, gets a vector of node costs by node.
+
+    Returns:
+      Cost of the longest path.
+    """
+    costs = {n: 0 for n in self._nodes}
+    for node in self.TopologicalSort(roots):
+      cost = 0
+      if self.InEdges(node):
+        cost = max([costs[e.from_node] + e.cost for e in self.InEdges(node)])
+      costs[node] = cost + node.cost
+    max_cost = max(costs.values())
+    if costs_out is not None:
+      del costs_out[:]
+      costs_out.extend(costs)
+    assert max_cost > 0
+    if path_list is not None:
+      del path_list[:]
+      node = (i for i in self._nodes if costs[i] == max_cost).next()
+      path_list.append(node)
+      while self.InEdges(node):
+        predecessors = [e.from_node for e in self.InEdges(node)]
+        node = reduce(
+            lambda costliest_node, next_node:
+            next_node if costs[next_node] > costs[costliest_node]
+            else costliest_node, predecessors)
+        path_list.insert(0, node)
+    return max_cost
diff --git a/tools/android/loading/graph_unittest.py b/tools/android/loading/graph_unittest.py
new file mode 100644
index 0000000..e8ef761
--- /dev/null
+++ b/tools/android/loading/graph_unittest.py
@@ -0,0 +1,170 @@
+# 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.
+
+import operator
+import os
+import sys
+import unittest
+
+import graph
+
+
+class _IndexedNode(graph.Node):
+  def __init__(self, index):
+    super(_IndexedNode, self).__init__()
+    self.index = index
+
+
+class GraphTestCase(unittest.TestCase):
+  @classmethod
+  def MakeGraph(cls, count, edge_tuples):
+    """Makes a graph from a list of edges.
+
+    Args:
+      count: Number of nodes.
+      edge_tuples: (from_index, to_index). Both indices must be in [0, count),
+                   and uniquely identify a node.
+    """
+    nodes = [_IndexedNode(i) for i in xrange(count)]
+    edges = [graph.Edge(nodes[from_index], nodes[to_index])
+             for (from_index, to_index) in edge_tuples]
+    return (nodes, edges, graph.DirectedGraph(nodes, edges))
+
+  @classmethod
+  def _NodesIndices(cls, g):
+    return map(operator.attrgetter('index'), g.Nodes())
+
+  def testBuildGraph(self):
+    (nodes, edges, g) = self.MakeGraph(
+        7,
+        [(0, 1),
+         (0, 2),
+         (1, 3),
+         (3, 4),
+         (5, 6)])
+    self.assertListEqual(range(7), sorted(self._NodesIndices(g)))
+    self.assertSetEqual(set(edges), set(g.Edges()))
+
+    self.assertSetEqual(set([edges[0], edges[1]]), set(g.OutEdges(nodes[0])))
+    self.assertFalse(g.InEdges(nodes[0]))
+    self.assertSetEqual(set([edges[2]]), set(g.OutEdges(nodes[1])))
+    self.assertSetEqual(set([edges[0]]), set(g.InEdges(nodes[1])))
+    self.assertFalse(g.OutEdges(nodes[2]))
+    self.assertSetEqual(set([edges[1]]), set(g.InEdges(nodes[2])))
+    self.assertSetEqual(set([edges[3]]), set(g.OutEdges(nodes[3])))
+    self.assertSetEqual(set([edges[2]]), set(g.InEdges(nodes[3])))
+    self.assertFalse(g.OutEdges(nodes[4]))
+    self.assertSetEqual(set([edges[3]]), set(g.InEdges(nodes[4])))
+    self.assertSetEqual(set([edges[4]]), set(g.OutEdges(nodes[5])))
+    self.assertFalse(g.InEdges(nodes[5]))
+    self.assertFalse(g.OutEdges(nodes[6]))
+    self.assertSetEqual(set([edges[4]]), set(g.InEdges(nodes[6])))
+
+  def testIgnoresUnknownEdges(self):
+    nodes = [_IndexedNode(i) for i in xrange(7)]
+    edges = [graph.Edge(nodes[from_index], nodes[to_index])
+             for (from_index, to_index) in [
+                 (0, 1), (0, 2), (1, 3), (3, 4), (5, 6)]]
+    edges.append(graph.Edge(nodes[4], _IndexedNode(42)))
+    edges.append(graph.Edge(_IndexedNode(42), nodes[5]))
+    g = graph.DirectedGraph(nodes, edges)
+    self.assertListEqual(range(7), sorted(self._NodesIndices(g)))
+    self.assertEqual(5, len(g.Edges()))
+
+  def testUpdateEdge(self):
+    (nodes, edges, g) = self.MakeGraph(
+        7,
+        [(0, 1),
+         (0, 2),
+         (1, 3),
+         (3, 4),
+         (5, 6)])
+    edge = edges[1]
+    self.assertTrue(edge in g.OutEdges(nodes[0]))
+    self.assertTrue(edge in g.InEdges(nodes[2]))
+    g.UpdateEdge(edge, nodes[2], nodes[3])
+    self.assertFalse(edge in g.OutEdges(nodes[0]))
+    self.assertFalse(edge in g.InEdges(nodes[2]))
+    self.assertTrue(edge in g.OutEdges(nodes[2]))
+    self.assertTrue(edge in g.InEdges(nodes[3]))
+
+  def testTopologicalSort(self):
+    (_, edges, g) = self.MakeGraph(
+        7,
+        [(0, 1),
+         (0, 2),
+         (1, 3),
+         (3, 4),
+         (5, 6)])
+    sorted_nodes = g.TopologicalSort()
+    node_to_sorted_index = dict(zip(sorted_nodes, xrange(len(sorted_nodes))))
+    for e in edges:
+      self.assertTrue(
+          node_to_sorted_index[e.from_node] < node_to_sorted_index[e.to_node])
+
+  def testReachableNodes(self):
+    (nodes, _, g) = self.MakeGraph(
+        7,
+        [(0, 1),
+         (0, 2),
+         (1, 3),
+         (3, 4),
+         (5, 6)])
+    self.assertSetEqual(
+        set([0, 1, 2, 3, 4]),
+        set(n.index for n in g.ReachableNodes([nodes[0]])))
+    self.assertSetEqual(
+        set([0, 1, 2, 3, 4]),
+        set(n.index for n in g.ReachableNodes([nodes[0], nodes[1]])))
+    self.assertSetEqual(
+        set([5, 6]),
+        set(n.index for n in g.ReachableNodes([nodes[5]])))
+    self.assertSetEqual(
+        set([6]),
+        set(n.index for n in g.ReachableNodes([nodes[6]])))
+
+  def testCost(self):
+    (nodes, edges, g) = self.MakeGraph(
+        7,
+        [(0, 1),
+         (0, 2),
+         (1, 3),
+         (3, 4),
+         (5, 6)])
+    for (i, node) in enumerate(nodes):
+      node.cost = i + 1
+    nodes[6].cost = 6
+    for edge in edges:
+      edge.cost = 1
+    self.assertEqual(15, g.Cost())
+    path_list = []
+    g.Cost(path_list=path_list)
+    self.assertListEqual([nodes[i] for i in (0, 1, 3, 4)], path_list)
+    nodes[6].cost = 9
+    self.assertEqual(16, g.Cost())
+    g.Cost(path_list=path_list)
+    self.assertListEqual([nodes[i] for i in (5, 6)], path_list)
+
+  def testCostWithRoots(self):
+    (nodes, edges, g) = self.MakeGraph(
+        7,
+        [(0, 1),
+         (0, 2),
+         (1, 3),
+         (3, 4),
+         (5, 6)])
+    for (i, node) in enumerate(nodes):
+      node.cost = i + 1
+    nodes[6].cost = 9
+    for edge in edges:
+      edge.cost = 1
+    path_list = []
+    self.assertEqual(16, g.Cost(path_list=path_list))
+    self.assertListEqual([nodes[i] for i in (5, 6)], path_list)
+    self.assertEqual(15, g.Cost(roots=[nodes[0]], path_list=path_list))
+    self.assertListEqual([nodes[i] for i in (0, 1, 3, 4)], path_list)
+
+
+if __name__ == '__main__':
+  unittest.main()
diff --git a/tools/android/loading/prefetch_view.py b/tools/android/loading/prefetch_view.py
index 76f7723..8a172bd 100644
--- a/tools/android/loading/prefetch_view.py
+++ b/tools/android/loading/prefetch_view.py
@@ -14,20 +14,24 @@ how many requests were prefetched.
 import itertools
 import operator
 
+import dependency_graph
 import loading_trace
+import user_satisfied_lens
 import request_dependencies_lens
+import request_track
 
 
 class PrefetchSimulationView(object):
   """Simulates the effect of prefetching resources discoverable by the preload
   scanner.
   """
-  def __init__(self, trace, dependencies_lens):
+  def __init__(self, trace, dependencies_lens, user_lens):
     """Initializes an instance of PrefetchSimulationView.
 
     Args:
       trace: (LoadingTrace) a loading trace.
       dependencies_lens: (RequestDependencyLens) request dependencies.
+      user_lens: (UserSatisfiedLens) Lens used to compute costs.
     """
     self.trace = trace
     self.dependencies_lens = dependencies_lens
@@ -35,6 +39,13 @@ class PrefetchSimulationView(object):
         categories=set([u'blink.net']))
     assert len(self._resource_events.GetEvents()) > 0,\
             'Was the "blink.net" category enabled at trace collection time?"'
+    self._user_lens = user_lens
+    request_ids = self._user_lens.CriticalRequests()
+    all_requests = self.trace.request_track.GetEvents()
+    self._first_request_node = all_requests[0].request_id
+    requests = [r for r in all_requests if r.request_id in request_ids]
+    self.graph = dependency_graph.RequestDependencyGraph(
+        requests, self.dependencies_lens)
 
   def ParserDiscoverableRequests(self, request, recurse=False):
     """Returns a list of requests discovered by the parser from a given request.
@@ -93,7 +104,7 @@ class PrefetchSimulationView(object):
          for r in preloaded_root_requests]))
 
 
-def _PrintSummary(prefetch_view):
+def _PrintSummary(prefetch_view, user_lens):
   requests = prefetch_view.trace.request_track.GetEvents()
   first_request = prefetch_view.trace.request_track.GetEvents()[0]
   parser_requests = prefetch_view.ExpandRedirectChains(
@@ -102,13 +113,22 @@ def _PrintSummary(prefetch_view):
       prefetch_view.PreloadedRequests(first_request))
   print '%d requests, %d parser from the main request, %d preloaded' % (
       len(requests), len(parser_requests), len(preloaded_requests))
+  print 'Time to user satisfaction: %.02fms' % (
+      prefetch_view.graph.Cost() + user_lens.PostloadTimeMsec())
+
+  print 'With 0-cost prefetched resources...'
+  new_costs = {r.request_id: 0. for r in preloaded_requests}
+  prefetch_view.graph.UpdateRequestsCost(new_costs)
+  print 'Time to user satisfaction: %.02fms' % (
+      prefetch_view.graph.Cost() + user_lens.PostloadTimeMsec())
 
 
 def main(filename):
   trace = loading_trace.LoadingTrace.FromJsonFile(filename)
   dependencies_lens = request_dependencies_lens.RequestDependencyLens(trace)
-  prefetch_view = PrefetchSimulationView(trace, dependencies_lens)
-  _PrintSummary(prefetch_view)
+  user_lens = user_satisfied_lens.FirstContentfulPaintLens(trace)
+  prefetch_view = PrefetchSimulationView(trace, dependencies_lens, user_lens)
+  _PrintSummary(prefetch_view, user_lens)
 
 
 if __name__ == '__main__':
diff --git a/tools/android/loading/prefetch_view_unittest.py b/tools/android/loading/prefetch_view_unittest.py
index f7210bc..ca8897d2 100644
--- a/tools/android/loading/prefetch_view_unittest.py
+++ b/tools/android/loading/prefetch_view_unittest.py
@@ -7,6 +7,8 @@ import unittest
 import prefetch_view
 import request_dependencies_lens
 from request_dependencies_lens_unittest import TestRequests
+import request_track
+import test_utils
 
 
 class PrefetchSimulationViewTestCase(unittest.TestCase):
@@ -54,8 +56,9 @@ class PrefetchSimulationViewTestCase(unittest.TestCase):
     self.trace = TestRequests.CreateLoadingTrace(trace_events)
     dependencies_lens = request_dependencies_lens.RequestDependencyLens(
         self.trace)
+    self.user_satisfied_lens = test_utils.MockUserSatisfiedLens(self.trace)
     self.prefetch_view = prefetch_view.PrefetchSimulationView(
-        self.trace, dependencies_lens)
+        self.trace, dependencies_lens, self.user_satisfied_lens)
 
 
 if __name__ == '__main__':
diff --git a/tools/android/loading/request_track.py b/tools/android/loading/request_track.py
index bba015d..2c083c7 100644
--- a/tools/android/loading/request_track.py
+++ b/tools/android/loading/request_track.py
@@ -244,6 +244,14 @@ class Request(object):
       return int(age_match.group(1))
     return -1
 
+  def Cost(self):
+    """Returns the cost of this request in ms, defined as time between
+    request_time and the latest timing event.
+    """
+    # All fields in timing are millis relative to request_time.
+    return max([0] + [t for f, t in self.timing._asdict().iteritems()
+                      if f != 'request_time'])
+
   def __eq__(self, o):
     return self.__dict__ == o.__dict__
 
diff --git a/tools/android/loading/test_utils.py b/tools/android/loading/test_utils.py
index 38737c0..a221385 100644
--- a/tools/android/loading/test_utils.py
+++ b/tools/android/loading/test_utils.py
@@ -10,6 +10,7 @@ import loading_trace
 import page_track
 import request_track
 import tracing
+import user_satisfied_lens
 
 
 class FakeRequestTrack(devtools_monitor.Track):
@@ -207,3 +208,9 @@ class MockConnection(object):
       del self._expected_responses[method]
     self._test_case.assertEqual(expected_params, params)
     return response
+
+
+class MockUserSatisfiedLens(user_satisfied_lens._UserSatisfiedLens):
+  def _CalculateTimes(self, _):
+    self._satisfied_msec = float('inf')
+    self._event_msec = float('inf')