clovis: Identify prefetchable resources from dependencies and tracing.

tools/android/loading/prefetch_view.py

+# 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.
+
+"""Models the effect of NoState Prefetch from a loading trace.
+
+When executed as a script, takes a trace as a command-line arguments and shows
+how many requests were prefetched.
+"""
+
+import operator
+
+import loading_trace
+import request_dependencies_lens
+
+
+class PrefetchSimulationView(object):
+  """Simulates the effect of prefetching resources discoverable by the preload
+  scanner.
+  """
+  def __init__(self, trace, dependencies_lens):
+    """Initializes an instance of PrefetchSimulationView.
+
+    Args:
+      trace: (LoadingTrace) a loading trace.
+      dependencies_lens: (RequestDependencyLens) request dependencies.
+    """
+    self.trace = trace
+    self.dependencies_lens = dependencies_lens
+    self._resource_events = self.trace.tracing_track.Filter(
+        categories=set([u'blink.net']))
+    assert len(self._resource_events.GetEvents()) > 0,\
+            'Was the "blink.net" category enabled at trace collection time?"'
+
+  def ParserDiscoverableRequests(self, request, recurse=False):
+    """Returns a list of requests discovered by the parser from a given request.
+
+    Args:
+      request: (Request) Root request.
+
+    Returns:
+      [Request]
+    """
+    # TODO(lizeb): handle the recursive case.
+    assert not recurse
+    discoverable_requests = [request]
+    first_request = self.dependencies_lens.GetRedirectChain(request)[-1]
+    deps = self.dependencies_lens.GetRequestDependencies()
+    for (first, second, reason) in deps:
+      if first.request_id == first_request.request_id and reason == 'parser':
+        discoverable_requests.append(second)
+    return discoverable_requests
+
+  def ExpandRedirectChains(self, requests):
+    return reduce(
+        operator.add,
+        [self.dependencies_lens.GetRedirectChain(r) for r in requests], [])

[mattcary, 2016/03/18 15:58:25]

Isn't this an n^2 operation? Each add has to copy the initial part of the
expanded chain.

Indeed, this seems to be the case in practice. The following runs instantly:

x = [r for r in itertools.chain.from_iterable([i] for i in xrange(1000000))]

But I got bored and ^C'd the following:

x = reduce(operator.add, ([i] for i in xrange(100000)), [])

[Benoit L, 2016/03/21 09:52:10]

/facepalm.
Done.

+
+  def PreloadedRequests(self, request):
+    """Returns the requests that have been preloaded from a given request.
+
+    This list is the set of request that are:
+    - Discoverable by the parser
+    - Found in the trace log.
+
+    Before looking for dependencies, this follows the redirect chain.
+
+    Args:
+      request: (Request) Root request.
+
+    Returns:
+      A list of Request. Does not include the root request. This list is a
+      subset of the one returned by ParserDiscoverableRequests().
+    """
+    preload_step_events = filter(
+        lambda e:  e.args.get('step') == 'Preload',

[mattcary, 2016/03/18 15:58:25]

Can you gloss what the Preload event is? I presume the idea here that we only
look at resources that appear during the preload time of the page load but it
would be nice to elucidate. In particular, it's not clear to me if this is being
conservative, that is, if there are resources that could be preloaded but happen
to not currently be.

[Benoit L, 2016/03/21 09:52:10]

Done.

+        self._resource_events.GetEvents())
+    preloaded_urls = set()
+    for preload_step_event in preload_step_events:
+      preload_event = self._resource_events.EventFromStep(preload_step_event)
+      if preload_event:
+        preloaded_urls.add(preload_event.args['url'])
+    parser_requests = self.ParserDiscoverableRequests(request)
+    preloaded_root_requests = filter(
+        lambda r: r.url in preloaded_urls, parser_requests)
+    # We can actually fetch the whole redirect chain.
+    return reduce(operator.add,

[mattcary, 2016/03/18 15:58:25]

Ditto about n^2 here.

[Benoit L, 2016/03/21 09:52:10]

Done.

+                  [self.dependencies_lens.GetRedirectChain(r)
+                   for r in preloaded_root_requests], [request])
+
+
+def _PrintSummary(prefetch_view):
+  requests = prefetch_view.trace.request_track.GetEvents()
+  first_request = prefetch_view.trace.request_track.GetEvents()[0]
+  parser_requests = prefetch_view.ExpandRedirectChains(
+      prefetch_view.ParserDiscoverableRequests(first_request))
+  preloaded_requests = prefetch_view.ExpandRedirectChains(
+      prefetch_view.PreloadedRequests(first_request))
+  print '%d requests, %d parser from the main request, %d preloaded' % (
+      len(requests), len(parser_requests), len(preloaded_requests))
+
+
+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)
+
+
+if __name__ == '__main__':
+  import sys
+  main(sys.argv[1])