Get rid of quadratic behavior in ResourceScheduler

Get rid of quadratic behavior in ResourceScheduler

The ResourceScheduler often receives bursts of IPCs from the renderer,
which call LoadAnyStartablePendingRequests. This method is O(n) for n 
pending requests for that client/tab.

Because the IPCs are busty, we often have a message queue of m messages,
each one calling into LoadAnyStartablePendingRequests, yielding O(m*n)
behavior.

This patch removes the O(m*n) behavior. As soon as one of these "bursty"
messages is handled, we schedule a new task to call
LoadAnyStartablePendingRequests. If the message queue has m messages
queued up, this will put the call to LoadAnyStartablePendingRequests at
the end. By ensuring we only have one scheduled task to load the startable
requests, we effectively coalesce all of the other calls into this method.

Another technique to remove this inefficiency would be to batch the IPC
messages into one. This is being explored by kinuko@ in issue 672370.
This approach however is very simple, and could easily be removed if we
move to a batching system.

BUG=664174
Review-Url: https://codereview.chromium.org/2670843007
Cr-Commit-Position: refs/heads/master@{#448634}
Committed: https://chromium.googlesource.com/chromium/src/+/59501351d872c1348665ad6dfd23b09396821056

[Charlie Harrison, 2017-02-04 17:18:23]

The CQ bit was checked by csharrison@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-02-04 17:18:32]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-02-04 18:04:13]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-02-04 18:04:14]

Dry run: Try jobs failed on following builders:
  linux_android_rel_ng on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/linux_androi...)

[Charlie Harrison, 2017-02-04 21:59:10]

The CQ bit was checked by csharrison@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-02-04 21:59:19]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-02-04 23:59:57]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-02-04 23:59:58]

Dry run: Try jobs failed on following builders:
  cast_shell_linux on master.tryserver.chromium.linux (JOB_TIMED_OUT, no build
URL)
  chromeos_amd64-generic_chromium_compile_only_ng on
master.tryserver.chromium.linux (JOB_TIMED_OUT, no build URL)
  chromeos_daisy_chromium_compile_only_ng on master.tryserver.chromium.linux
(JOB_TIMED_OUT, no build URL)
  chromium_presubmit on master.tryserver.chromium.linux (JOB_TIMED_OUT, no build
URL)
  linux_chromium_asan_rel_ng on master.tryserver.chromium.linux (JOB_TIMED_OUT,
no build URL)
  linux_chromium_chromeos_ozone_rel_ng on master.tryserver.chromium.linux
(JOB_TIMED_OUT, no build URL)
  linux_chromium_compile_dbg_ng on master.tryserver.chromium.linux
(JOB_TIMED_OUT, no build URL)
  linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_TIMED_OUT, no
build URL)
  linux_chromium_tsan_rel_ng on master.tryserver.chromium.linux (JOB_TIMED_OUT,
no build URL)
  win_chromium_compile_dbg_ng on master.tryserver.chromium.win (JOB_TIMED_OUT,
no build URL)
  win_chromium_rel_ng on master.tryserver.chromium.win (JOB_TIMED_OUT, no build
URL)
  win_chromium_x64_rel_ng on master.tryserver.chromium.win (JOB_TIMED_OUT, no
build URL)
  win_clang on master.tryserver.chromium.win (JOB_TIMED_OUT, no build URL)

[Charlie Harrison, 2017-02-05 19:46:13]

The CQ bit was checked by csharrison@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-02-05 19:46:27]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-02-05 20:50:45]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-02-05 20:50:46]

Dry run: This issue passed the CQ dry run.

[Charlie Harrison, 2017-02-05 22:06:42]

Description was changed from

==========
Get rid of O(n^2) behavior in ResourceScheduler

BUG=
==========

to

==========
Get rid of quadratic behavior in ResourceScheduler

The ResourceScheduler often receives bursts of IPCs from the renderer,
which call LoadAnyStartablePendingRequests. This method is O(n) for n pending
requests for that client/tab.

Because the IPCs are busty, we often have a message queue of m messages,
each one calling into LoadAnyStartablePendingRequests, yielding O(m*n)
behavior.

This patch removes the O(m*n) behavior. As soon as one of these "bursty"
messages is handled, we schedule a new task to call
LoadAnyStartablePendingRequests. If the message queue has m messages
queued up, this will put the call to LoadAnyStartablePendingRequests at
the end. By ensuring we only have one scheduled task to load the startable
requests, we effectively coalesce all of the other calls into this method.

BUG=664174
==========

[Charlie Harrison, 2017-02-05 22:06:52]

Description was changed from

==========
Get rid of quadratic behavior in ResourceScheduler

The ResourceScheduler often receives bursts of IPCs from the renderer,
which call LoadAnyStartablePendingRequests. This method is O(n) for n pending
requests for that client/tab.

Because the IPCs are busty, we often have a message queue of m messages,
each one calling into LoadAnyStartablePendingRequests, yielding O(m*n)
behavior.

This patch removes the O(m*n) behavior. As soon as one of these "bursty"
messages is handled, we schedule a new task to call
LoadAnyStartablePendingRequests. If the message queue has m messages
queued up, this will put the call to LoadAnyStartablePendingRequests at
the end. By ensuring we only have one scheduled task to load the startable
requests, we effectively coalesce all of the other calls into this method.

BUG=664174
==========

to

==========
Get rid of quadratic behavior in ResourceScheduler

The ResourceScheduler often receives bursts of IPCs from the renderer,
which call LoadAnyStartablePendingRequests. This method is O(n) for n 
pending requests for that client/tab.

Because the IPCs are busty, we often have a message queue of m messages,
each one calling into LoadAnyStartablePendingRequests, yielding O(m*n)
behavior.

This patch removes the O(m*n) behavior. As soon as one of these "bursty"
messages is handled, we schedule a new task to call
LoadAnyStartablePendingRequests. If the message queue has m messages
queued up, this will put the call to LoadAnyStartablePendingRequests at
the end. By ensuring we only have one scheduled task to load the startable
requests, we effectively coalesce all of the other calls into this method.

BUG=664174
==========

[Charlie Harrison, 2017-02-05 22:08:21]

Description was changed from

==========
Get rid of quadratic behavior in ResourceScheduler

The ResourceScheduler often receives bursts of IPCs from the renderer,
which call LoadAnyStartablePendingRequests. This method is O(n) for n 
pending requests for that client/tab.

Because the IPCs are busty, we often have a message queue of m messages,
each one calling into LoadAnyStartablePendingRequests, yielding O(m*n)
behavior.

This patch removes the O(m*n) behavior. As soon as one of these "bursty"
messages is handled, we schedule a new task to call
LoadAnyStartablePendingRequests. If the message queue has m messages
queued up, this will put the call to LoadAnyStartablePendingRequests at
the end. By ensuring we only have one scheduled task to load the startable
requests, we effectively coalesce all of the other calls into this method.

BUG=664174
==========

to

==========
Get rid of quadratic behavior in ResourceScheduler

The ResourceScheduler often receives bursts of IPCs from the renderer,
which call LoadAnyStartablePendingRequests. This method is O(n) for n 
pending requests for that client/tab.

Because the IPCs are busty, we often have a message queue of m messages,
each one calling into LoadAnyStartablePendingRequests, yielding O(m*n)
behavior.

This patch removes the O(m*n) behavior. As soon as one of these "bursty"
messages is handled, we schedule a new task to call
LoadAnyStartablePendingRequests. If the message queue has m messages
queued up, this will put the call to LoadAnyStartablePendingRequests at
the end. By ensuring we only have one scheduled task to load the startable
requests, we effectively coalesce all of the other calls into this method.

Another technique to remove this inefficiency would be to batch the IPC
messages into one. This is being explored by kinuko@ in issue 672370.
This approach however is very simple, and could easily be removed if we
move to a batching system.

BUG=664174
==========

[Charlie Harrison, 2017-02-05 22:11:02]

csharrison@chromium.org changed reviewers:
+ kinuko@chromium.org

[Charlie Harrison, 2017-02-05 22:11:02]

csharrison@chromium.org changed reviewers:
+ kinuko@chromium.org

[Charlie Harrison, 2017-02-05 22:11:03]

Hey Kinuko, WDYT about this approach to make resource scheduler a bit more CPU
friendly as a stop gap until IPC batching is a more mature pattern?

[Charlie Harrison, 2017-02-05 22:11:03]

Hey Kinuko, WDYT about this approach to make resource scheduler a bit more CPU
friendly as a stop gap until IPC batching is a more mature pattern?

[kinuko, 2017-02-06 20:57:14]

Looks reasonable, but I'm a bit concerned about how this might change the
behavior.

https://codereview.chromium.org/2670843007/diff/40001/content/browser/loader/...
File content/browser/loader/resource_scheduler.cc (right):

https://codereview.chromium.org/2670843007/diff/40001/content/browser/loader/...
content/browser/loader/resource_scheduler.cc:738:
weak_ptr_factory_.GetWeakPtr(), trigger));
This changes when we actually triggers startable requests esp. if we already
have lots of inflight tasks already in the queue (and during contentious loading
it looks it's often the case).  Do you think it could affect performance?

[Charlie Harrison, 2017-02-06 21:24:29]

https://codereview.chromium.org/2670843007/diff/40001/content/browser/loader/...
File content/browser/loader/resource_scheduler.cc (right):

https://codereview.chromium.org/2670843007/diff/40001/content/browser/loader/...
content/browser/loader/resource_scheduler.cc:738:
weak_ptr_factory_.GetWeakPtr(), trigger));
On 2017/02/06 20:57:14, kinuko wrote:
> This changes when we actually triggers startable requests esp. if we already
> have lots of inflight tasks already in the queue (and during contentious
loading
> it looks it's often the case).  Do you think it could affect performance?

This is a valid concern. We currently "schedule" these start tasks on two
conditions.
1. Reprioritization (which often comes in batches for image priorities)
2. Request tear down (~ResourceThrottle). I think this will only come from
batches from callers of ResourceFetcher::stopFetching (e.g. stopAllLoaders). 

In my mind, if we have a bloated queue during these times it feels better to
delay here than delaying the current work on the queue with lots of CPU bound
work. A single extra post task during request finish / reprioritization seems
not too bad to me.

If you'd like, I can add a histogram of the wait time for the scheduled task?

[kinuko, 2017-02-07 05:19:15]

On 2017/02/06 21:24:29, Charlie Harrison wrote:
>
https://codereview.chromium.org/2670843007/diff/40001/content/browser/loader/...
> File content/browser/loader/resource_scheduler.cc (right):
> 
>
https://codereview.chromium.org/2670843007/diff/40001/content/browser/loader/...
> content/browser/loader/resource_scheduler.cc:738:
> weak_ptr_factory_.GetWeakPtr(), trigger));
> On 2017/02/06 20:57:14, kinuko wrote:
> > This changes when we actually triggers startable requests esp. if we already
> > have lots of inflight tasks already in the queue (and during contentious
> loading
> > it looks it's often the case).  Do you think it could affect performance?
> 
> This is a valid concern. We currently "schedule" these start tasks on two
> conditions.
> 1. Reprioritization (which often comes in batches for image priorities)
> 2. Request tear down (~ResourceThrottle). I think this will only come from
> batches from callers of ResourceFetcher::stopFetching (e.g. stopAllLoaders). 
> 
> In my mind, if we have a bloated queue during these times it feels better to
> delay here than delaying the current work on the queue with lots of CPU bound
> work. A single extra post task during request finish / reprioritization seems
> not too bad to me.
> 
> If you'd like, I can add a histogram of the wait time for the scheduled task?

Case #1 made me worry a bit as it looks it could be called during layout also
before FMP, but if you don't think that'd be an issue I'm fine with this change.
 Or I think for this one we could possibly also just batch them in the renderer
too for now.

[Charlie Harrison, 2017-02-07 05:59:10]

On 2017/02/07 05:19:15, kinuko wrote:
> On 2017/02/06 21:24:29, Charlie Harrison wrote:
> >
>
https://codereview.chromium.org/2670843007/diff/40001/content/browser/loader/...
> > File content/browser/loader/resource_scheduler.cc (right):
> > 
> >
>
https://codereview.chromium.org/2670843007/diff/40001/content/browser/loader/...
> > content/browser/loader/resource_scheduler.cc:738:
> > weak_ptr_factory_.GetWeakPtr(), trigger));
> > On 2017/02/06 20:57:14, kinuko wrote:
> > > This changes when we actually triggers startable requests esp. if we
already
> > > have lots of inflight tasks already in the queue (and during contentious
> > loading
> > > it looks it's often the case).  Do you think it could affect performance?
> > 
> > This is a valid concern. We currently "schedule" these start tasks on two
> > conditions.
> > 1. Reprioritization (which often comes in batches for image priorities)
> > 2. Request tear down (~ResourceThrottle). I think this will only come from
> > batches from callers of ResourceFetcher::stopFetching (e.g. stopAllLoaders).

> > 
> > In my mind, if we have a bloated queue during these times it feels better to
> > delay here than delaying the current work on the queue with lots of CPU
bound
> > work. A single extra post task during request finish / reprioritization
seems
> > not too bad to me.
> > 
> > If you'd like, I can add a histogram of the wait time for the scheduled
task?
> 
> Case #1 made me worry a bit as it looks it could be called during layout also
> before FMP, but if you don't think that'd be an issue I'm fine with this
change.
>  Or I think for this one we could possibly also just batch them in the
renderer
> too for now.

I think for #1 the only real danger is if N more tasks are posted to the IO
thread
between the 1st reprioritization task sent, and it being handled, where N >= M
reprioritization messages.

If N = M, then we only have to handle the M reprioritization tasks, saving us
lots of CPU.
I liked this change because it was very simple, but now I am feeling less sure.
Honestly
if the IO thread is super busy with servicing requests, etc. Then maybe adding
some delay here is a good thing?

Note that Randy already implemented batch IPC from the renderer here:
https://codereview.chromium.org/2552703003/ but we decided to wait for the more
general
thing.

LMK what you think. Happy to go with whatever you think if best here.

[kinuko, 2017-02-07 06:34:16]

On 2017/02/07 05:59:10, Charlie Harrison wrote:
> On 2017/02/07 05:19:15, kinuko wrote:
> > On 2017/02/06 21:24:29, Charlie Harrison wrote:
> > >
> >
>
https://codereview.chromium.org/2670843007/diff/40001/content/browser/loader/...
> > > File content/browser/loader/resource_scheduler.cc (right):
> > > 
> > >
> >
>
https://codereview.chromium.org/2670843007/diff/40001/content/browser/loader/...
> > > content/browser/loader/resource_scheduler.cc:738:
> > > weak_ptr_factory_.GetWeakPtr(), trigger));
> > > On 2017/02/06 20:57:14, kinuko wrote:
> > > > This changes when we actually triggers startable requests esp. if we
> already
> > > > have lots of inflight tasks already in the queue (and during contentious
> > > loading
> > > > it looks it's often the case).  Do you think it could affect
performance?
> > > 
> > > This is a valid concern. We currently "schedule" these start tasks on two
> > > conditions.
> > > 1. Reprioritization (which often comes in batches for image priorities)
> > > 2. Request tear down (~ResourceThrottle). I think this will only come from
> > > batches from callers of ResourceFetcher::stopFetching (e.g.
stopAllLoaders).
> 
> > > 
> > > In my mind, if we have a bloated queue during these times it feels better
to
> > > delay here than delaying the current work on the queue with lots of CPU
> bound
> > > work. A single extra post task during request finish / reprioritization
> seems
> > > not too bad to me.
> > > 
> > > If you'd like, I can add a histogram of the wait time for the scheduled
> task?
> > 
> > Case #1 made me worry a bit as it looks it could be called during layout
also
> > before FMP, but if you don't think that'd be an issue I'm fine with this
> change.
> >  Or I think for this one we could possibly also just batch them in the
> renderer
> > too for now.
> 
> I think for #1 the only real danger is if N more tasks are posted to the IO
> thread
> between the 1st reprioritization task sent, and it being handled, where N >= M
> reprioritization messages.
> 
> If N = M, then we only have to handle the M reprioritization tasks, saving us
> lots of CPU.
> I liked this change because it was very simple, but now I am feeling less
sure.
> Honestly
> if the IO thread is super busy with servicing requests, etc. Then maybe adding
> some delay here is a good thing?
> 
> Note that Randy already implemented batch IPC from the renderer here:
> https://codereview.chromium.org/2552703003/ but we decided to wait for the
more
> general
> thing.

Yes I remember this, I thought we could plumb this from Blink too.

> LMK what you think. Happy to go with whatever you think if best here.

Ok, we can land this and see how it goes. lgtm

Do you have a set of particular sites + stats we want to watch after this lands?

[Charlie Harrison, 2017-02-07 14:59:07]

I am hoping page cyclers will catch regressions or perf improvements. Other than
that I think the main win is image heavy sites like google images, but even then
it is more of death-by-thousand-cuts thing.

[Charlie Harrison, 2017-02-07 15:04:11]

The CQ bit was checked by csharrison@chromium.org

[commit-bot: I haz the power, 2017-02-07 15:04:20]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-02-07 16:02:47]

CQ is committing da patch.

Bot data: {"patchset_id": 40001, "attempt_start_ts": 1486479851016940,
"parent_rev": "d86a44963ae8521c90be4cc0343ed6bfa8a872a7", "commit_rev":
"59501351d872c1348665ad6dfd23b09396821056"}

[commit-bot: I haz the power, 2017-02-07 16:03:21]

Description was changed from

==========
Get rid of quadratic behavior in ResourceScheduler

The ResourceScheduler often receives bursts of IPCs from the renderer,
which call LoadAnyStartablePendingRequests. This method is O(n) for n 
pending requests for that client/tab.

Because the IPCs are busty, we often have a message queue of m messages,
each one calling into LoadAnyStartablePendingRequests, yielding O(m*n)
behavior.

This patch removes the O(m*n) behavior. As soon as one of these "bursty"
messages is handled, we schedule a new task to call
LoadAnyStartablePendingRequests. If the message queue has m messages
queued up, this will put the call to LoadAnyStartablePendingRequests at
the end. By ensuring we only have one scheduled task to load the startable
requests, we effectively coalesce all of the other calls into this method.

Another technique to remove this inefficiency would be to batch the IPC
messages into one. This is being explored by kinuko@ in issue 672370.
This approach however is very simple, and could easily be removed if we
move to a batching system.

BUG=664174
==========

to

==========
Get rid of quadratic behavior in ResourceScheduler

The ResourceScheduler often receives bursts of IPCs from the renderer,
which call LoadAnyStartablePendingRequests. This method is O(n) for n 
pending requests for that client/tab.

Because the IPCs are busty, we often have a message queue of m messages,
each one calling into LoadAnyStartablePendingRequests, yielding O(m*n)
behavior.

This patch removes the O(m*n) behavior. As soon as one of these "bursty"
messages is handled, we schedule a new task to call
LoadAnyStartablePendingRequests. If the message queue has m messages
queued up, this will put the call to LoadAnyStartablePendingRequests at
the end. By ensuring we only have one scheduled task to load the startable
requests, we effectively coalesce all of the other calls into this method.

Another technique to remove this inefficiency would be to batch the IPC
messages into one. This is being explored by kinuko@ in issue 672370.
This approach however is very simple, and could easily be removed if we
move to a batching system.

BUG=664174

Review-Url: https://codereview.chromium.org/2670843007
Cr-Commit-Position: refs/heads/master@{#448634}
Committed:
https://chromium.googlesource.com/chromium/src/+/59501351d872c1348665ad6dfd23...
==========

[commit-bot: I haz the power, 2017-02-07 16:03:22]

Committed patchset #3 (id:40001) as
https://chromium.googlesource.com/chromium/src/+/59501351d872c1348665ad6dfd23...