clovis: Identify prefetchable resources from dependencies and tracing.

clovis: Identify prefetchable resources from dependencies and tracing.

Resources that are discoverable by the preload scanner are behind a
"parser" dependency. However, this is a superset of the actual
discoverable resources. Use tracing to find the actual resources, that
are then matched to requests.

Committed: https://crrev.com/7f2bd1dc11f2e24416a0c0380bf4d908d4e82b62
Cr-Commit-Position: refs/heads/master@{#382542}

[Benoit L, 2016-03-17 16:50:08]

lizeb@chromium.org changed reviewers:
+ blundell@chromium.org, mattcary@chromium.org

[mattcary, 2016-03-18 15:58:26]

lgtm

https://codereview.chromium.org/1813723002/diff/20001/tools/android/loading/p...
File tools/android/loading/prefetch_view.py (right):

https://codereview.chromium.org/1813723002/diff/20001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:57:
[self.dependencies_lens.GetRedirectChain(r) for r in requests], [])
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)), [])

https://codereview.chromium.org/1813723002/diff/20001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:76: lambda e:  e.args.get('step') ==
'Preload',
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.

https://codereview.chromium.org/1813723002/diff/20001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:87: return reduce(operator.add,
Ditto about n^2 here.

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

Thanks for the review!

https://codereview.chromium.org/1813723002/diff/20001/tools/android/loading/p...
File tools/android/loading/prefetch_view.py (right):

https://codereview.chromium.org/1813723002/diff/20001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:57:
[self.dependencies_lens.GetRedirectChain(r) for r in requests], [])
On 2016/03/18 15:58:25, mattcary wrote:
> 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)), [])

/facepalm.
Done.

https://codereview.chromium.org/1813723002/diff/20001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:76: lambda e:  e.args.get('step') ==
'Preload',
On 2016/03/18 15:58:25, mattcary wrote:
> 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.

Done.

https://codereview.chromium.org/1813723002/diff/20001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:87: return reduce(operator.add,
On 2016/03/18 15:58:25, mattcary wrote:
> Ditto about n^2 here.

Done.

[blundell, 2016-03-21 10:07:18]

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
File tools/android/loading/prefetch_view.py (right):

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:5: """Models the effect of NoState
Prefetch from a loading trace.
Nit: prefetch_view is a quite generic name. Maybe no_state_prefetch_view?

[blundell, 2016-03-21 10:22:04]

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
File tools/android/loading/prefetch_view.py (right):

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:5: """Models the effect of NoState
Prefetch from a loading trace.
On 2016/03/21 10:07:18, blundell wrote:
> Nit: prefetch_view is a quite generic name. Maybe no_state_prefetch_view?

Also, let's provide a one-sentence description of nostate prefetch here and link
to this doc:

https://docs.google.com/document/d/16VCYGGWau483IMSxODpg5faZny1FJ6vNK2v-BuM5E...

[blundell, 2016-03-21 10:47:16]

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
File tools/android/loading/prefetch_view.py (right):

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:36: def ParserDiscoverableRequests(self,
request, recurse=False):
Should/could this eventually be the same code that's used by sandwich to
determine which resources to stuff into the cache when doing its evaluation of
nostate prefetch?

[mattcary, 2016-03-21 10:54:44]

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
File tools/android/loading/prefetch_view.py (right):

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:36: def ParserDiscoverableRequests(self,
request, recurse=False):
On 2016/03/21 10:47:16, blundell wrote:
> Should/could this eventually be the same code that's used by sandwich to
> determine which resources to stuff into the cache when doing its evaluation of
> nostate prefetch?

That's an interesting general question: should our model be based on the same
code, to maximize fidelity, or independent, to reduce the chance of making the
same implementation mistake twice?

For the immediate Q1 goals, though, I think we can keep them separate to
minimize thrashing and move quickly. The general question may take a while to
resolve.

[blundell, 2016-03-21 10:58:06]

On 2016/03/21 10:54:44, mattcary wrote:
>
https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
> File tools/android/loading/prefetch_view.py (right):
> 
>
https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
> tools/android/loading/prefetch_view.py:36: def
ParserDiscoverableRequests(self,
> request, recurse=False):
> On 2016/03/21 10:47:16, blundell wrote:
> > Should/could this eventually be the same code that's used by sandwich to
> > determine which resources to stuff into the cache when doing its evaluation
of
> > nostate prefetch?
> 
> That's an interesting general question: should our model be based on the same
> code, to maximize fidelity, or independent, to reduce the chance of making the
> same implementation mistake twice?
> 
> For the immediate Q1 goals, though, I think we can keep them separate to
> minimize thrashing and move quickly. The general question may take a while to
> resolve.

To me it seems clear that Clovis and Sandwich should be making the same decision
on whether a given resource is prefetchable via Technique X, and having them
call the same routines to make that decision is the best way to achieve that.
Agree that we don't have cross-validation of that code itself in that case.

Is having them use the same code more effort than putting the code in a library?
I agree that it doesn't need to block anything now, but trying to get a feel for
why/whether this will be challenging.

[mattcary, 2016-03-21 11:59:26]

On 2016/03/21 10:58:06, blundell wrote:
> On 2016/03/21 10:54:44, mattcary wrote:
> >
>
https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
> > File tools/android/loading/prefetch_view.py (right):
> > 
> >
>
https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
> > tools/android/loading/prefetch_view.py:36: def
> ParserDiscoverableRequests(self,
> > request, recurse=False):
> > On 2016/03/21 10:47:16, blundell wrote:
> > > Should/could this eventually be the same code that's used by sandwich to
> > > determine which resources to stuff into the cache when doing its
evaluation
> of
> > > nostate prefetch?
> > 
> > That's an interesting general question: should our model be based on the
same
> > code, to maximize fidelity, or independent, to reduce the chance of making
the
> > same implementation mistake twice?
> > 
> > For the immediate Q1 goals, though, I think we can keep them separate to
> > minimize thrashing and move quickly. The general question may take a while
to
> > resolve.
> 
> To me it seems clear that Clovis and Sandwich should be making the same
decision
> on whether a given resource is prefetchable via Technique X, and having them
> call the same routines to make that decision is the best way to achieve that.
> Agree that we don't have cross-validation of that code itself in that case.
> 
> Is having them use the same code more effort than putting the code in a
library?
> I agree that it doesn't need to block anything now, but trying to get a feel
for
> why/whether this will be challenging.

Sandwich is using the traces directly and not as much of the track
postprocessing that we do in clovis. So we'll have to dig into when everything
settles down.

[gabadie, 2016-03-21 12:55:44]

gabadie@chromium.org changed reviewers:
+ gabadie@chromium.org

[gabadie, 2016-03-21 12:55:45]

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
File tools/android/loading/prefetch_view.py (right):

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:36: def ParserDiscoverableRequests(self,
request, recurse=False):
On 2016/03/21 10:54:44, mattcary wrote:
> On 2016/03/21 10:47:16, blundell wrote:
> > Should/could this eventually be the same code that's used by sandwich to
> > determine which resources to stuff into the cache when doing its evaluation
of
> > nostate prefetch?
> 
> That's an interesting general question: should our model be based on the same
> code, to maximize fidelity, or independent, to reduce the chance of making the
> same implementation mistake twice?
> 
> For the immediate Q1 goals, though, I think we can keep them separate to
> minimize thrashing and move quickly. The general question may take a while to
> resolve.

Fly by comment: Sandwich is currently simulating the HTMLPreloadScanner using
the exact same API, is taking care of the data protocol, but not the
GetRequestDependencies: 

https://code.google.com/p/chromium/codesearch#chromium/src/tools/android/load...

After having compared both implementation (that sadly looks both incomplete),
making them common could very much increase interests from both parties. I would
be happy to discuss a design of an extensible API that would let us write
different resources prefetching policies, and reuse them everywhere at will.

Basically, sandwich's need is to get a white-list of requests to keep their
resources into the cache.

[Benoit L, 2016-03-22 09:32:23]

Thanks for the comments.
Added a link to the NoState prefetch design doc.

As for the other concerns, since there is no clear consensus, can we land this
CL, then iterate?

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
File tools/android/loading/prefetch_view.py (right):

https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
tools/android/loading/prefetch_view.py:5: """Models the effect of NoState
Prefetch from a loading trace.
On 2016/03/21 10:07:18, blundell wrote:
> Nit: prefetch_view is a quite generic name. Maybe no_state_prefetch_view?

This is intended to simulate prefetch in a generic way, not especially NoState
prefetch. So, what about:
- Keeping the name as is
- Adding the link to the design doc, citing it as an example?

[mattcary, 2016-03-22 09:34:51]

On 2016/03/22 09:32:23, Benoit L wrote:
> Thanks for the comments.
> Added a link to the NoState prefetch design doc.
> 
> As for the other concerns, since there is no clear consensus, can we land this
> CL, then iterate?
> 
sgtm

[mattcary, 2016-03-22 09:34:52]

On 2016/03/22 09:32:23, Benoit L wrote:
> Thanks for the comments.
> Added a link to the NoState prefetch design doc.
> 
> As for the other concerns, since there is no clear consensus, can we land this
> CL, then iterate?
> 
sgtm

[blundell, 2016-03-22 09:35:06]

On 2016/03/22 09:32:23, Benoit L wrote:
> Thanks for the comments.
> Added a link to the NoState prefetch design doc.
> 
> As for the other concerns, since there is no clear consensus, can we land this
> CL, then iterate?
> 
>
https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
> File tools/android/loading/prefetch_view.py (right):
> 
>
https://codereview.chromium.org/1813723002/diff/40001/tools/android/loading/p...
> tools/android/loading/prefetch_view.py:5: """Models the effect of NoState
> Prefetch from a loading trace.
> On 2016/03/21 10:07:18, blundell wrote:
> > Nit: prefetch_view is a quite generic name. Maybe no_state_prefetch_view?
> 
> This is intended to simulate prefetch in a generic way, not especially NoState
> prefetch. So, what about:
> - Keeping the name as is
> - Adding the link to the design doc, citing it as an example?

LGTM

Yep, I'm fine with having a generic prefetch_view.py, was just bothered by the
incongruence between the generic name and the seemingly-specific purpose.

I'm fine with unifying offline. I do think that unification makes sense.

[Benoit L, 2016-03-22 09:36:04]

The CQ bit was checked by lizeb@chromium.org

[Benoit L, 2016-03-22 09:36:04]

The patchset sent to the CQ was uploaded after l-g-t-m from
mattcary@chromium.org
Link to the patchset: https://codereview.chromium.org/1813723002/#ps60001
(title: ".")

[commit-bot: I haz the power, 2016-03-22 09:36:12]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1813723002/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1813723002/60001

[commit-bot: I haz the power, 2016-03-22 10:18:28]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2016-03-22 10:19:52]

Description was changed from

==========
clovis: Identify prefetchable resources from dependencies and tracing.

Resources that are discoverable by the preload scanner are behind a
"parser" dependency. However, this is a superset of the actual
discoverable resources. Use tracing to find the actual resources, that
are then matched to requests.
==========

to

==========
clovis: Identify prefetchable resources from dependencies and tracing.

Resources that are discoverable by the preload scanner are behind a
"parser" dependency. However, this is a superset of the actual
discoverable resources. Use tracing to find the actual resources, that
are then matched to requests.

Committed: https://crrev.com/7f2bd1dc11f2e24416a0c0380bf4d908d4e82b62
Cr-Commit-Position: refs/heads/master@{#382542}
==========

[commit-bot: I haz the power, 2016-03-22 10:19:53]

Patchset 4 (id:??) landed as
https://crrev.com/7f2bd1dc11f2e24416a0c0380bf4d908d4e82b62
Cr-Commit-Position: refs/heads/master@{#382542}