Run task queue manager work in batches

Run task queue manager work in batches

This patch lets the task queue manager run more than one posted task
per invocation. This helps reduce the overhead of yielding to and from
the main message loop and can speed up cases where tasks are posted
very frequently. One example is indexeddb, where some operations such as
index building can result in 2500 posted tasks/s (Nexus 7).

This patch also adds accounting for the desired run time of the next
pending delayed task. This information is used to break out of a work
batch if a delayed task should be run instead. Doing this avoids adding
extra delay to delayed tasks.

A potential downside of this change is that it can penalize work that
runs on the message loop without going through the task queue manager.
Based on performance tests[1], almost all tasks on the renderer main
thread are already getting executed by the task queue manager, so I
believe this change shouldn't cause a regression.

Note that this version of the patch still uses a batch size of 1 while
we investigate some mac test failures triggered by larger batch sizes.

[1] https://docs.google.com/a/chromium.org/spreadsheets/d/1IJZpBabW1pr4fb2T8BlkleHcOvHYrjvmCx_dLesxfMA/edit#gid=1492760051

BUG=444764, 451593, 453898
Committed: https://crrev.com/a11ff40fc19b20b4b47f6875e81859978be3be84
Cr-Commit-Position: refs/heads/master@{#314364}

[Sami, 2015-01-14 17:02:15]

skyostil@chromium.org changed reviewers:
+ alexclarke@chromium.org, rmcilroy@chromium.org

[rmcilroy, 2015-01-14 17:56:37]

https://codereview.chromium.org/845543004/diff/20001/content/renderer/schedul...
File content/renderer/scheduler/task_queue_manager.cc (right):

https://codereview.chromium.org/845543004/diff/20001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager.cc:347: }
Would the following work:

if (!UpdateWorkQueues())
  return;
MaybePostDoWorkOnMainRunner();

for (int i = 0; i < work_batch_size_; i++) {
  if (!SelectWorkQueueToService(&queue_index))
     return;
  ProcessTaskFromWorkQueue(queue_index);
}

It's a bit simpler, and ensures that we only take the locks in UpdateWorkQueues
once per batch, but does mean that that a given batch won't include any work
posted from any DoWorks for that batch. Would this prevent any batching being
possible on the indexdb perf test?

[Sami, 2015-01-14 18:11:50]

https://codereview.chromium.org/845543004/diff/20001/content/renderer/schedul...
File content/renderer/scheduler/task_queue_manager.cc (right):

https://codereview.chromium.org/845543004/diff/20001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager.cc:347: }
I had the same idea and chose to do polling inside the batch to minimize the
chances that we yield and then immediately come back since there was more work.
The idea was simply that it's more likely there's more work waiting for us
inside the task queue manager than outside of it. I can definitely see the point
about taking fewer locks if there really isn't anything to do. 

Let me check how this fares with the indexeddb benchmark.

On 2015/01/14 17:56:37, rmcilroy wrote:
> Would the following work:
> 
> if (!UpdateWorkQueues())
>   return;
> MaybePostDoWorkOnMainRunner();

I don't think we can do this here because the selector should be able to prevent
any DoWorks from getting posted if it wants.

> for (int i = 0; i < work_batch_size_; i++) {
>   if (!SelectWorkQueueToService(&queue_index))
>      return;
>   ProcessTaskFromWorkQueue(queue_index);

Here we need to check if any of the queues became empty and bail out.

> }
> 
> It's a bit simpler, and ensures that we only take the locks in
UpdateWorkQueues
> once per batch, but does mean that that a given batch won't include any work
> posted from any DoWorks for that batch. Would this prevent any batching being
> possible on the indexdb perf test?

[Sami, 2015-01-14 18:14:40]

On 2015/01/14 18:11:50, Sami wrote:
> Let me check how this fares with the indexeddb benchmark.

Turns out we lose the benefit if we only check for new work once :(

baseline
--------
RESULT Total Perf: perf_test.html=
[1491.669000,1482.178000,1568.115000,1538.940000,1525.330000] ms
Avg Total Perf: 1521.246400ms
Sd  Total Perf: 35.098317ms

4x pipelining with one update
-----------------------------
RESULT Total Perf: perf_test.html=
[1832.062000,1529.022000,1482.513000,1699.829000,1617.218000] ms
Avg Total Perf: 1632.128800ms
Sd  Total Perf: 139.458626ms

I think it's because the benchmark posts the next task from within the current
one, so you'll always have 1 pending task in the queue.

[rmcilroy, 2015-01-14 19:34:48]

Looks good, but this seems to be breaking TestIdleTaskExceedsDeadline on the
bots.  I think this is a test issue rather than a problem with the batching -
probably something to do with the comment on
renderer_scheduler_impl_unittest.cc:123 [1].  Let me know if I can help fixing
this.

[1]
https://code.google.com/p/chromium/codesearch#chromium/src/content/renderer/s...

https://codereview.chromium.org/845543004/diff/20001/content/renderer/schedul...
File content/renderer/scheduler/task_queue_manager.cc (right):

https://codereview.chromium.org/845543004/diff/20001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager.cc:347: }
On 2015/01/14 18:11:49, Sami wrote:
> I had the same idea and chose to do polling inside the batch to minimize the
> chances that we yield and then immediately come back since there was more
work.
> The idea was simply that it's more likely there's more work waiting for us
> inside the task queue manager than outside of it. I can definitely see the
point
> about taking fewer locks if there really isn't anything to do. 
> 
> Let me check how this fares with the indexeddb benchmark.
> 
> On 2015/01/14 17:56:37, rmcilroy wrote:
> > Would the following work:
> > 
> > if (!UpdateWorkQueues())
> >   return;
> > MaybePostDoWorkOnMainRunner();
> 
> I don't think we can do this here because the selector should be able to
prevent
> any DoWorks from getting posted if it wants.

Good point

> 
> > for (int i = 0; i < work_batch_size_; i++) {
> >   if (!SelectWorkQueueToService(&queue_index))
> >      return;
> >   ProcessTaskFromWorkQueue(queue_index);
> 
> Here we need to check if any of the queues became empty and bail out.

Ack

> 
> > }
> > 
> > It's a bit simpler, and ensures that we only take the locks in
> UpdateWorkQueues
> > once per batch, but does mean that that a given batch won't include any work
> > posted from any DoWorks for that batch. Would this prevent any batching
being
> > possible on the indexdb perf test?
> 

> Turns out we lose the benefit if we only check for new work once :(

Ahh that's sad, but having thought about it a bit more it probably wouldn't be a
great plan anyway because without updating the work queues every cycle the
selector wouldn't necessarily make the correct decision.

[Sami, 2015-01-19 18:40:17]

I've updated the patch to keep track of the next pending delayed task. This adds
some bookkeeping, but is still cheap enough to make the asymptotic cost of
posting a task though the scheduler much smaller than before. PTAL.

[picksi1, 2015-01-21 11:16:08]

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

[picksi1, 2015-01-21 11:16:09]

Interesting stuff!

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
File content/renderer/scheduler/task_queue_manager.cc (right):

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager.cc:371: Now() >=
next_pending_delayed_task)
The checks for i>0 and (on line 377) checking for i==0 makes this for loop a bit
tricky to understand (plus adds some inefficiency here?). How much duplicated
code would result in pulling the i==0 work out of the loop?

also (I haven't followed the logic entirely...) is the check for !=
kMaxTimeTicks needed here? If UpdateWorkQueues returns true doesn't it imply
that the next_pending_delayed_task has a decent value?

[rmcilroy, 2015-01-21 12:18:26]

Generally looks good to me, but I have a suggestion on moving the priority queue
to the TQM rather than the TQ - let me know what you think.

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
File content/renderer/scheduler/task_queue_manager.cc (right):

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager.cc:86:
std::greater<base::TimeTicks>> delayed_task_run_times_;
Would it be simpler to maintain a single queue in the TaskQueueManager rather
than one in each TaskQueue?  Delayed runtimes could be pushed in
TaskQueueManager::PostDelayedTask and popped in DoWork. WDYT?

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
File content/renderer/scheduler/task_queue_manager_unittest.cc (right):

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager_unittest.cc:515: namespace {
Do you need the anonymous namespace?  (You don't use it on TestTask)

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager_unittest.cc:516: void
AdvanceNow(int value,
nit - AdvanceNowTestTask

[Sami, 2015-01-21 14:31:16]

Thanks for the comments!

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
File content/renderer/scheduler/task_queue_manager.cc (right):

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager.cc:86:
std::greater<base::TimeTicks>> delayed_task_run_times_;
On 2015/01/21 12:18:26, rmcilroy wrote:
> Would it be simpler to maintain a single queue in the TaskQueueManager rather
> than one in each TaskQueue?  Delayed runtimes could be pushed in
> TaskQueueManager::PostDelayedTask and popped in DoWork. WDYT?

Like we talked about, having a shared queue would need a lock around it. My
handwavey feeling is that having an extra lock would be worse than the current
code which polls each queue for the nearest task (basically an std::min<int64>
per task queue). Any preference?

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager.cc:371: Now() >=
next_pending_delayed_task)
On 2015/01/21 11:16:08, picksi1 wrote:
> The checks for i>0 and (on line 377) checking for i==0 makes this for loop a
bit
> tricky to understand (plus adds some inefficiency here?). How much duplicated
> code would result in pulling the i==0 work out of the loop?

Actually the i==0 is a bit of a premature optimization so I've gotten rid of it.
Pulling it out would've meant duplicating almost all of the loop :\

> also (I haven't followed the logic entirely...) is the check for !=
> kMaxTimeTicks needed here? If UpdateWorkQueues returns true doesn't it imply
> that the next_pending_delayed_task has a decent value?

Good question. We need the check because it's possible that we won't have any
pending *delayed* tasks (just normal tasks), and I wanted to avoid the overhead
of reading the current time in that case.

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
File content/renderer/scheduler/task_queue_manager_unittest.cc (right):

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager_unittest.cc:515: namespace {
On 2015/01/21 12:18:26, rmcilroy wrote:
> Do you need the anonymous namespace?  (You don't use it on TestTask)

Ah, thanks, this is all in an anonymous namespace already.

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager_unittest.cc:516: void
AdvanceNow(int value,
On 2015/01/21 12:18:26, rmcilroy wrote:
> nit - AdvanceNowTestTask

Done.

[rmcilroy, 2015-01-21 15:13:09]

lgtm, thanks!

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
File content/renderer/scheduler/task_queue_manager.cc (right):

https://codereview.chromium.org/845543004/diff/60001/content/renderer/schedul...
content/renderer/scheduler/task_queue_manager.cc:86:
std::greater<base::TimeTicks>> delayed_task_run_times_;
On 2015/01/21 14:31:16, Sami wrote:
> On 2015/01/21 12:18:26, rmcilroy wrote:
> > Would it be simpler to maintain a single queue in the TaskQueueManager
rather
> > than one in each TaskQueue?  Delayed runtimes could be pushed in
> > TaskQueueManager::PostDelayedTask and popped in DoWork. WDYT?
> 
> Like we talked about, having a shared queue would need a lock around it. My
> handwavey feeling is that having an extra lock would be worse than the current
> code which polls each queue for the nearest task (basically an std::min<int64>
> per task queue). Any preference?

Yeah I agree, it's better to keep these in seperate queues to avoid a global TQM
lock.

https://codereview.chromium.org/845543004/diff/100001/content/renderer/schedu...
File content/renderer/scheduler/task_queue_manager.cc (right):

https://codereview.chromium.org/845543004/diff/100001/content/renderer/schedu...
content/renderer/scheduler/task_queue_manager.cc:377:
MaybePostDoWorkOnMainRunner();
Could you add a comment that the logic in MaybePostDoWork will prevent us
spamming the message loop n =i natter what the work_batch_size is.

[Sami, 2015-01-21 15:30:40]

https://codereview.chromium.org/845543004/diff/100001/content/renderer/schedu...
File content/renderer/scheduler/task_queue_manager.cc (right):

https://codereview.chromium.org/845543004/diff/100001/content/renderer/schedu...
content/renderer/scheduler/task_queue_manager.cc:377:
MaybePostDoWorkOnMainRunner();
On 2015/01/21 15:13:09, rmcilroy wrote:
> Could you add a comment that the logic in MaybePostDoWork will prevent us
> spamming the message loop n =i natter what the work_batch_size is.

Good idea, done.

[Sami, 2015-01-21 15:30:54]

The CQ bit was checked by skyostil@chromium.org

[commit-bot: I haz the power, 2015-01-21 15:31:43]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/845543004/120001

[commit-bot: I haz the power, 2015-01-21 15:34:33]

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

[commit-bot: I haz the power, 2015-01-21 15:34:34]

Try jobs failed on following builders:
  ios_dbg_simulator on tryserver.chromium.mac
(http://build.chromium.org/p/tryserver.chromium.mac/builders/ios_dbg_simulator...)

Try jobs failed on following builders:
  linux_gpu on tryserver.chromium.gpu
(http://build.chromium.org/p/tryserver.chromium.gpu/builders/linux_gpu/builds/...)
  android_aosp on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/android_aosp/bu...)
  android_arm64_dbg_recipe on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/android_arm64_d...)
  android_compile_rel on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/android_compile...)
  linux_chromium_rel_ng on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
  ios_dbg_simulator on tryserver.chromium.mac
(http://build.chromium.org/p/tryserver.chromium.mac/builders/ios_dbg_simulator...)
  ios_rel_device_ninja_ng on tryserver.chromium.mac
(http://build.chromium.org/p/tryserver.chromium.mac/builders/ios_rel_device_ni...)

[Sami, 2015-01-21 15:47:03]

The CQ bit was checked by skyostil@chromium.org

[commit-bot: I haz the power, 2015-01-21 15:47:49]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/845543004/160001

[commit-bot: I haz the power, 2015-01-21 18:03:52]

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

[commit-bot: I haz the power, 2015-01-21 18:03:54]

Try jobs failed on following builders:
  mac_chromium_rel_ng on tryserver.chromium.mac
(http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)

[Sami, 2015-01-21 19:32:17]

The CQ bit was checked by skyostil@chromium.org

[commit-bot: I haz the power, 2015-01-21 19:33:01]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/845543004/160001

[commit-bot: I haz the power, 2015-01-21 19:34:37]

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

[commit-bot: I haz the power, 2015-01-21 19:34:38]

Try jobs failed on following builders:
  mac_chromium_rel_ng on tryserver.chromium.mac
(http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)

[Sami, 2015-01-23 14:22:32]

The CQ bit was checked by skyostil@chromium.org

[commit-bot: I haz the power, 2015-01-23 14:23:13]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/845543004/160001

[commit-bot: I haz the power, 2015-01-23 14:24:29]

Committed patchset #9 (id:160001)

[commit-bot: I haz the power, 2015-01-23 14:25:28]

Patchset 9 (id:??) landed as
https://crrev.com/d9684457b5349dfc1cc19e8a2d98a69ba00ed058
Cr-Commit-Position: refs/heads/master@{#312839}

[jam, 2015-01-23 19:00:01]

A revert of this CL (patchset #9 id:160001) has been created in
https://codereview.chromium.org/867353002/ by jam@chromium.org.

The reason for reverting is: Trying to see if this is the cause of
MediaTest.Yuv* failures on Mac:

http://build.chromium.org/p/chromium.mac/builders/Mac10.9%20Tests/builds/2373
http://build.chromium.org/p/chromium.mac/builders/Mac10.6%20Tests/builds/3274.

[jam, 2015-01-23 20:19:27]

On 2015/01/23 19:00:01, jam wrote:
> A revert of this CL (patchset #9 id:160001) has been created in
> https://codereview.chromium.org/867353002/ by mailto:jam@chromium.org.
> 
> The reason for reverting is: Trying to see if this is the cause of
> MediaTest.Yuv* failures on Mac:
> 
> http://build.chromium.org/p/chromium.mac/builders/Mac10.9%20Tests/builds/2373
> http://build.chromium.org/p/chromium.mac/builders/Mac10.6%20Tests/builds/3274.

to follow up, the revert fixed the builds.

[Sami, 2015-01-25 15:08:44]

On 2015/01/23 20:19:27, jam wrote:
> On 2015/01/23 19:00:01, jam wrote:
> > A revert of this CL (patchset #9 id:160001) has been created in
> > https://codereview.chromium.org/867353002/ by mailto:jam@chromium.org.
> > 
> > The reason for reverting is: Trying to see if this is the cause of
> > MediaTest.Yuv* failures on Mac:
> > 
> >
http://build.chromium.org/p/chromium.mac/builders/Mac10.9%20Tests/builds/2373
> >
http://build.chromium.org/p/chromium.mac/builders/Mac10.6%20Tests/builds/3274.
> 
> to follow up, the revert fixed the builds.

jam@ confirmed that this patch was indeed the culprit. Ross, I was wondering if
we should reland this with N=1, figure out what's wrong with the mac flake and
then bump the work batch size to 4? That way your long idle time patch wouldn't
be blocked.

[rmcilroy, 2015-01-25 16:15:17]

On 2015/01/25 15:08:44, Sami wrote:
> On 2015/01/23 20:19:27, jam wrote:
> > On 2015/01/23 19:00:01, jam wrote:
> > > A revert of this CL (patchset #9 id:160001) has been created in
> > > https://codereview.chromium.org/867353002/ by mailto:jam@chromium.org.
> > > 
> > > The reason for reverting is: Trying to see if this is the cause of
> > > MediaTest.Yuv* failures on Mac:
> > > 
> > >
> http://build.chromium.org/p/chromium.mac/builders/Mac10.9%20Tests/builds/2373
> > >
> http://build.chromium.org/p/chromium.mac/builders/Mac10.6%20Tests/builds/3274.
> > 
> > to follow up, the revert fixed the builds.
> 
> jam@ confirmed that this patch was indeed the culprit. Ross, I was wondering
if
> we should reland this with N=1, figure out what's wrong with the mac flake and
> then bump the work batch size to 4? That way your long idle time patch
wouldn't
> be blocked.

SGTM, thanks!

[Sami, 2015-01-27 12:29:52]

Finally found the magic incantation to make ubsan happy about this patch. Ross,
could you PTAL?

[rmcilroy, 2015-01-27 13:30:19]

On 2015/01/27 12:29:52, Sami wrote:
> Finally found the magic incantation to make ubsan happy about this patch.
Ross,
> could you PTAL?

lgtm, thanks Sami.

[Sami, 2015-01-27 13:31:36]

The CQ bit was checked by skyostil@chromium.org

[commit-bot: I haz the power, 2015-01-27 13:31:57]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/845543004/200001

[commit-bot: I haz the power, 2015-01-27 14:13:08]

Committed patchset #11 (id:200001)

[commit-bot: I haz the power, 2015-01-27 14:14:06]

Patchset 11 (id:??) landed as
https://crrev.com/42ad8e954a2eafaa52bc3e566747eeb274ad1ad1
Cr-Commit-Position: refs/heads/master@{#313271}

[oystein (OOO til 10th of July), 2015-02-02 20:35:51]

A revert of this CL (patchset #11 id:200001) has been created in
https://codereview.chromium.org/894183002/ by oysteine@chromium.org.

The reason for reverting is: Speculative revert for crbug.com/453898.

[Sami, 2015-02-03 16:16:21]

The problem was that delayed tasks were getting enqueued with a non-zero
delayed_run_time after the delay was already applied. This meant that the
selector could starve them as long any other queue had a task in it, because
PendingTask::operator< takes delayed_run_time into account.

I suspect this got only triggered on mac because it has a slightly different
vsync architecture, which means if there's an animation, delayed tasks could get
delayed forever.

The latest patch set fixes the bug and adds a unit test. Diff against #11 to see
the fix.

[rmcilroy, 2015-02-03 17:42:01]

Yikes, good catch on the delayed_runtime - I wonder why this didn't crop up
until now...

lgtm.

[Sami, 2015-02-03 17:50:47]

On 2015/02/03 17:42:01, rmcilroy wrote:
> Yikes, good catch on the delayed_runtime - I wonder why this didn't crop up
> until now...

Only because my patch was the first one that started assigning anything non-zero
to delayed_run_time :P
 
> lgtm.

Thanks!

[Sami, 2015-02-03 17:51:11]

The CQ bit was checked by skyostil@chromium.org

[commit-bot: I haz the power, 2015-02-03 17:52:09]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/845543004/240001

[commit-bot: I haz the power, 2015-02-03 17:56:17]

Committed patchset #13 (id:240001)

[commit-bot: I haz the power, 2015-02-03 17:57:37]

Patchset 13 (id:??) landed as
https://crrev.com/a11ff40fc19b20b4b47f6875e81859978be3be84
Cr-Commit-Position: refs/heads/master@{#314364}