TaskGraphRunner Group support

TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the task graph.

Other regressions are less clear, but probably have to do with the additional cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
CQ_INCLUDE_TRYBOTS=tryserver.chromium.win:win_chromium_gn_x64_rel

Committed: https://crrev.com/05ca4bc9df381e6345f9cf7ee29cdfa075be30c4
Cr-Commit-Position: refs/heads/master@{#365140}

Committed: https://crrev.com/3b4338fc32cf20703baa8066bdad7ce07c5ae696
Cr-Commit-Position: refs/heads/master@{#365646}

Committed: https://crrev.com/5a1188c6c3b464ed96694881dfec6c70c7d58a29
Cr-Commit-Position: refs/heads/master@{#366180}

[ericrk, 2015-12-02 04:09:04]

Description was changed from

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be
used by an implementation along with priority
in order to decide how to execute tasks.

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

to

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be
used by an implementation along with priority
in order to decide how to execute tasks.

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[ericrk, 2015-12-02 21:39:04]

Description was changed from

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be
used by an implementation along with priority
in order to decide how to execute tasks.

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[ericrk, 2015-12-02 21:39:04]

ericrk@chromium.org changed reviewers:
+ reveman@chromium.org

[ericrk, 2015-12-03 02:48:45]

This is the first part of a few CLs which add thread affinity for SW and GPU
raster. This CL just adds the ability for the TaskGraphWorkQueue to support
sub-groups. Each group is maintained as its own heap of tasks.

[reveman, 2015-12-04 02:30:54]

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_r...
File cc/raster/task_graph_runner.h (right):

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_r...
cc/raster/task_graph_runner.h:49: // a group, a priority and a run count that
matches the number of dependencies.
how do you feel about "category" instead of "group"? "group" is OK but my
initial thought was that this implies some form of atomic execution guarantees.
e.g. all or none of the tasks in a group will execute.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_r...
cc/raster/task_graph_runner.h:52: // implementation and its consumer to
determine the meaning (if any) of a group.
Can we make it clear here that group and priority might be linked? E.g. a
TaskGraphRunner implementation may prioritize all tasks in one group
(independent of |priority|) over tasks in another group.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_r...
cc/raster/task_graph_runner.h:55: typedef std::vector<Node> Vector;
Btw, I'd like to remove all these Vector typedefs and just use std::vector
directly. These kind of typedef was always a bad idea. No need to do that as
part of this patch though, just fyi.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_r...
cc/raster/task_graph_runner.h:66: size_t dependencies;
How about we also change |dependencies| to uint32_t? as that makes a Node two
words in size on 64bit and three on 32bit platforms

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
File cc/raster/task_graph_work_queue.cc (right):

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:16: void ClearAllVectors(T* array_of_vectors)
{
nit: remove vector specific references as T can be any type that you can iterate
and contains items that implement clear(). maybe rename to ClearEach or
ForEachClear..

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:24: bool AllVectorsEmpty(const T&
array_of_vectors) {
ditto.

maybe std::for_each and std::find_if with lambdas are just as easy to read as
calls to these helper functions, don't know. just something to consider..

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:38: class CompareTaskNamespacePriority {
nit: this code predates c++11 support in chromium. no need for a class anymore.
please change this to a CompareTaskNamespacePriority function and use a lambda
below when calling it. maybe you can even remove it completely and call
CompareTaskPriority directly in the lambda.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:123: for (auto& vector :
task_namespace.ready_to_run_tasks) {
nit: s/vector/ready_to_run_tasks/ not a fan of naming variables based on the
container type as that makes it harder to change the container without making
the code confusing..

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:153: for (auto& it : namespaces_) {
would be nice if this could be something like:

for (auto& namespace_it : namespaces_) {
  for (auto& ready_to_run_tasks_it : it.second.ready_to_run_tasks) {
    ...
  }
}

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:173: TaskNamespace::Vector&
namespaces_for_group = ready_to_run_namespaces_[group];
nit: s/namespaces_for_group/ready_to_run_namespaces_for_group/ or maybe just
ready_to_run_namespaces

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:182: PrioritizedTask::Vector& tasks_for_group
=
nit: s/tasks_for_group/ready_to_run_tasks_for_group/ or maybe just
ready_to_run_tasks

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:239: PrioritizedTask::Vector& tasks_for_group
=
nit: same as above, ready_to_run_tasks_for_group or just ready_to_run_tasks

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:252: TaskNamespace::Vector&
namespaces_for_group =
ditto

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
File cc/raster/task_graph_work_queue.h (right):

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.h:27: enum : uint16_t { kMaxTaskGroups = 3 };
hm, not a huge fan of this. if this is going to be only 2 or 3 values then I'd
suggest we just use std::map as that would be consistent with how we handle
TaskNamespaces and it resulted in cleaner code that was actually performing a
bit better in the common case

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.h:82: PrioritizedTask GetNextTaskToRun();
Is this the only code in TaskGraphWorkQueue that treats group as a priority? In
that case I'd suggest we force the higher level TGR implementation to implement
it and leave this class completely free of interpreting the meaning of |group|.

[ericrk, 2015-12-04 19:00:01]

Patchset #9 (id:160001) has been deleted

[ericrk, 2015-12-04 19:14:31]

Thanks for the feedback - I was going back and forth between map/array myself,
and map is definitely a little bit cleaner.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_r...
File cc/raster/task_graph_runner.h (right):

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_r...
cc/raster/task_graph_runner.h:49: // a group, a priority and a run count that
matches the number of dependencies.
On 2015/12/04 02:30:53, reveman wrote:
> how do you feel about "category" instead of "group"? "group" is OK but my
> initial thought was that this implies some form of atomic execution
guarantees.
> e.g. all or none of the tasks in a group will execute.

hmm, either seems fine to me, I'll switch to category.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_r...
cc/raster/task_graph_runner.h:52: // implementation and its consumer to
determine the meaning (if any) of a group.
On 2015/12/04 02:30:53, reveman wrote:
> Can we make it clear here that group and priority might be linked? E.g. a
> TaskGraphRunner implementation may prioritize all tasks in one group
> (independent of |priority|) over tasks in another group.

Done.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_r...
cc/raster/task_graph_runner.h:55: typedef std::vector<Node> Vector;
On 2015/12/04 02:30:53, reveman wrote:
> Btw, I'd like to remove all these Vector typedefs and just use std::vector
> directly. These kind of typedef was always a bad idea. No need to do that as
> part of this patch though, just fyi.

will clean these up in a follow-up

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_r...
cc/raster/task_graph_runner.h:66: size_t dependencies;
On 2015/12/04 02:30:53, reveman wrote:
> How about we also change |dependencies| to uint32_t? as that makes a Node two
> words in size on 64bit and three on 32bit platforms

yup - that's definitely better.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
File cc/raster/task_graph_work_queue.cc (right):

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:16: void ClearAllVectors(T* array_of_vectors)
{
On 2015/12/04 02:30:53, reveman wrote:
> nit: remove vector specific references as T can be any type that you can
iterate
> and contains items that implement clear(). maybe rename to ClearEach or
> ForEachClear..

no longer needed when using map - but good point.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:24: bool AllVectorsEmpty(const T&
array_of_vectors) {
On 2015/12/04 02:30:54, reveman wrote:
> ditto.
> 
> maybe std::for_each and std::find_if with lambdas are just as easy to read as
> calls to these helper functions, don't know. just something to consider..

Acknowledged.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:38: class CompareTaskNamespacePriority {
On 2015/12/04 02:30:54, reveman wrote:
> nit: this code predates c++11 support in chromium. no need for a class
anymore.
> please change this to a CompareTaskNamespacePriority function and use a lambda
> below when calling it. maybe you can even remove it completely and call
> CompareTaskPriority directly in the lambda.

Using a lambda directly is a lot more verbose at the call-site, and there are 4
call sites - I actually wrapped the original free-function in a class to clean
up the various uses.

Consider:

    std::make_heap(task_namespace.begin(), task_namespace.end(),
                   CompareTaskNamespacePriority(category));

Vs. the following with a free function:

    std::make_heap(task_namespace.begin(), task_namespace.end(),
                   [category](const TaskGraphWorkQueue::TaskNamespace* a,
                              const TaskGraphWorkQueue::TaskNamespace* b) {
                     CompareTaskNamespacePriority(category, a, b);
                   });

Or the following when calling directly:

    std::make_heap(task_namespace.begin(), task_namespace.end(),
                   [category](const TaskGraphWorkQueue::TaskNamespace* a,
                              const TaskGraphWorkQueue::TaskNamespace* b) {
                     return CompareTaskPriority(
                         a->ready_to_run_tasks.at(category_).front(),
                         b->ready_to_run_tasks.at(category_).front())
                   });

If it was just one case, I'd do the lambda, but at 4 uses the helper class
seemed cleaner? WDYT?

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:123: for (auto& vector :
task_namespace.ready_to_run_tasks) {
On 2015/12/04 02:30:54, reveman wrote:
> nit: s/vector/ready_to_run_tasks/ not a fan of naming variables based on the
> container type as that makes it harder to change the container without making
> the code confusing..

Done.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:153: for (auto& it : namespaces_) {
On 2015/12/04 02:30:53, reveman wrote:
> would be nice if this could be something like:
> 
> for (auto& namespace_it : namespaces_) {
>   for (auto& ready_to_run_tasks_it : it.second.ready_to_run_tasks) {
>     ...
>   }
> }

Couldn't do that before (when  using an array), as we needed the group/category,
which we wouldn't get with range-based-for. Now when using map we have keys, so
this has been changed to that form.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:173: TaskNamespace::Vector&
namespaces_for_group = ready_to_run_namespaces_[group];
On 2015/12/04 02:30:54, reveman wrote:
> nit: s/namespaces_for_group/ready_to_run_namespaces_for_group/ or maybe just
> ready_to_run_namespaces

Done.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:182: PrioritizedTask::Vector& tasks_for_group
=
On 2015/12/04 02:30:54, reveman wrote:
> nit: s/tasks_for_group/ready_to_run_tasks_for_group/ or maybe just
> ready_to_run_tasks

Done.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:239: PrioritizedTask::Vector& tasks_for_group
=
On 2015/12/04 02:30:53, reveman wrote:
> nit: same as above, ready_to_run_tasks_for_group or just ready_to_run_tasks

Done.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:252: TaskNamespace::Vector&
namespaces_for_group =
On 2015/12/04 02:30:53, reveman wrote:
> ditto

Done.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
File cc/raster/task_graph_work_queue.h (right):

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.h:27: enum : uint16_t { kMaxTaskGroups = 3 };
On 2015/12/04 02:30:54, reveman wrote:
> hm, not a huge fan of this. if this is going to be only 2 or 3 values then I'd
> suggest we just use std::map as that would be consistent with how we handle
> TaskNamespaces and it resulted in cleaner code that was actually performing a
> bit better in the common case

ok - heh... I have that code 2 or 3 CLs back in the history :D - changed to this
as I worried about the cost of map doing dynamic allocations - but for 2 or 3
values this is probably fine.

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.h:82: PrioritizedTask GetNextTaskToRun();
On 2015/12/04 02:30:54, reveman wrote:
> Is this the only code in TaskGraphWorkQueue that treats group as a priority?
In
> that case I'd suggest we force the higher level TGR implementation to
implement
> it and leave this class completely free of interpreting the meaning of
|group|.

sgtm

[reveman, 2015-12-04 20:55:51]

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
File cc/raster/task_graph_work_queue.cc (right):

https://codereview.chromium.org/1489233003/diff/140001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:38: class CompareTaskNamespacePriority {
On 2015/12/04 at 19:14:30, ericrk wrote:
> On 2015/12/04 02:30:54, reveman wrote:
> > nit: this code predates c++11 support in chromium. no need for a class
anymore.
> > please change this to a CompareTaskNamespacePriority function and use a
lambda
> > below when calling it. maybe you can even remove it completely and call
> > CompareTaskPriority directly in the lambda.
> 
> Using a lambda directly is a lot more verbose at the call-site, and there are
4 call sites - I actually wrapped the original free-function in a class to clean
up the various uses.
> 
> Consider:
> 
>     std::make_heap(task_namespace.begin(), task_namespace.end(),
>                    CompareTaskNamespacePriority(category));
> 
> Vs. the following with a free function:
> 
>     std::make_heap(task_namespace.begin(), task_namespace.end(),
>                    [category](const TaskGraphWorkQueue::TaskNamespace* a,
>                               const TaskGraphWorkQueue::TaskNamespace* b) {
>                      CompareTaskNamespacePriority(category, a, b);
>                    });

I think this would be OK with auto for arguments but it's perfectly fine to keep
the existing CompareTaskNamespacePriority class if you prefer that.

> 
> Or the following when calling directly:
> 
>     std::make_heap(task_namespace.begin(), task_namespace.end(),
>                    [category](const TaskGraphWorkQueue::TaskNamespace* a,
>                               const TaskGraphWorkQueue::TaskNamespace* b) {
>                      return CompareTaskPriority(
>                          a->ready_to_run_tasks.at(category_).front(),
>                          b->ready_to_run_tasks.at(category_).front())
>                    });
> 
> If it was just one case, I'd do the lambda, but at 4 uses the helper class
seemed cleaner? WDYT?

Yea, keeping the code in the current patch in this regard might be best.

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
File cc/raster/task_graph_work_queue.cc (right):

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:36:
b->ready_to_run_tasks.at(category_).front());
ready_to_run_tasks[category_] instead?

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:139: for (auto& tasks_it :
task_namespace.ready_to_run_tasks) {
nit: ready_to_run_tasks_it to be perfectly consistent

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:157:
DCHECK_GT(ready_to_run_namespaces_.count(category), 0u);
nit: this failing isn't really a problem but
ready_to_run_namespaces_[category].empty() being true is. should we check that
instead?

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:167:
DCHECK_GT(task_namespace->ready_to_run_tasks.count(category), 0u);
same here, DCHECK(!empty()) instead?

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:191:
ready_to_run_namespaces_.erase(category);
Will this and the above erase not cause a large amount of heap allocations in
the common use case? existing code has been tuned to not require any heap
allocation for the common case where we schedule a task graph that is the same
as the previous one and it might be best to keep it that way. what if we let the
map grow as needed and instead use the !vector.empty() to determine if category
has ready to run tasks? seems like that would be fine as we expect a limited
number of categories to be used..

Either way, can you post the results from running task graph perf tests in a
release build before and after this change to this code review? that would
useful to know independent of how we solve this.

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
File cc/raster/task_graph_work_queue.h (right):

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.h:109: return
ready_to_run_namespaces_.count(category) > 0;
nit: ready_to_run_namespaces_.find(category)?

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.h:129: static void
UncategorizeTaskGraph(TaskGraph* graph);
I don't think we should modify the task graph in any other way than what Swap
does. ie. TaskGraph::nodes should be const from the TaskGraphRunners
perspective.

Would it be possible to instead create or schedule tasks in the work queue using
a category rewrite filter of some sort that would map category to 0 without
modifying the nodes?

or maybe it's fine to just run all tasks by category in the single threaded
case? I would prefer that if possible

[ericrk, 2015-12-07 17:51:58]

Patchset #13 (id:260001) has been deleted

[ericrk, 2015-12-08 00:30:43]

Patchset #13 (id:280001) has been deleted

[ericrk, 2015-12-08 00:31:06]

Patchset #12 (id:240001) has been deleted

[ericrk, 2015-12-08 00:31:15]

Patchset #11 (id:220001) has been deleted

[ericrk, 2015-12-08 00:38:40]

Patchset #10 (id:200001) has been deleted

[ericrk, 2015-12-08 01:03:40]

Patchset #10 (id:300001) has been deleted

[ericrk, 2015-12-09 22:56:44]

Made the suggested changes.

Not sure about the addition of task_category.h - wanted to keep
TaskGraphWorkQueue generic (not assign meanings to task categories) so split
these off into their own file for consumption by raster related TaskGraphRunners
which want to use this set.

FWIW, this change shows a 15-30% regression in the perf tests for
TaskGraphRunner - mostly seems to be around the increased iteration (begin/end
calls) and operator[]. Will look into this a bit more to see if we can reduce
this overhead.

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
File cc/raster/task_graph_work_queue.cc (right):

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:36:
b->ready_to_run_tasks.at(category_).front());
On 2015/12/04 20:55:51, reveman wrote:
> ready_to_run_tasks[category_] instead?

Can't call operator[] on const maps (as it may need to create an entry).

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:139: for (auto& tasks_it :
task_namespace.ready_to_run_tasks) {
On 2015/12/04 20:55:51, reveman wrote:
> nit: ready_to_run_tasks_it to be perfectly consistent

Done.

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:157:
DCHECK_GT(ready_to_run_namespaces_.count(category), 0u);
On 2015/12/04 20:55:51, reveman wrote:
> nit: this failing isn't really a problem but
> ready_to_run_namespaces_[category].empty() being true is. should we check that
> instead?

yup = this made more sense when I was erasing things, updated.

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:167:
DCHECK_GT(task_namespace->ready_to_run_tasks.count(category), 0u);
On 2015/12/04 20:55:51, reveman wrote:
> same here, DCHECK(!empty()) instead?
done.

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.cc:191:
ready_to_run_namespaces_.erase(category);
On 2015/12/04 20:55:51, reveman wrote:
> Will this and the above erase not cause a large amount of heap allocations in
> the common use case? existing code has been tuned to not require any heap
> allocation for the common case where we schedule a task graph that is the same
> as the previous one and it might be best to keep it that way. what if we let
the
> map grow as needed and instead use the !vector.empty() to determine if
category
> has ready to run tasks? seems like that would be fine as we expect a limited
> number of categories to be used..
> 
> Either way, can you post the results from running task graph perf tests in a
> release build before and after this change to this code review? that would
> useful to know independent of how we solve this.

Got rid of the erasing - took some benchmarks and it was a 50% regression in
many cases. - without erasing we're at a 30% regression max - will add some
numbers in the reply.

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
File cc/raster/task_graph_work_queue.h (right):

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.h:109: return
ready_to_run_namespaces_.count(category) > 0;
On 2015/12/04 20:55:51, reveman wrote:
> nit: ready_to_run_namespaces_.find(category)?

now that a category can be empty (but still exist), restructured this.

https://codereview.chromium.org/1489233003/diff/180001/cc/raster/task_graph_w...
cc/raster/task_graph_work_queue.h:129: static void
UncategorizeTaskGraph(TaskGraph* graph);
On 2015/12/04 20:55:51, reveman wrote:
> I don't think we should modify the task graph in any other way than what Swap
> does. ie. TaskGraph::nodes should be const from the TaskGraphRunners
> perspective.
> 
> Would it be possible to instead create or schedule tasks in the work queue
using
> a category rewrite filter of some sort that would map category to 0 without
> modifying the nodes?
> 
> or maybe it's fine to just run all tasks by category in the single threaded
> case? I would prefer that if possible

Re-worked things per our discussion on fri.

[reveman, 2015-12-10 16:49:57]

looks great, just one thing really, see my comment.

and regarding the performance regression, I think we can live with that but it
would be good to compare before/after cpu profiles to be sure it's what we
expect if you haven't already.

https://codereview.chromium.org/1489233003/diff/320001/cc/raster/synchronous_...
File cc/raster/synchronous_task_graph_runner.cc (right):

https://codereview.chromium.org/1489233003/diff/320001/cc/raster/synchronous_...
cc/raster/synchronous_task_graph_runner.cc:71: for (category = 0u; category <
kNumTaskCategories; ++category) {
I'd like to avoid making the kNumTaskCategories assumption. See my other
comment.

https://codereview.chromium.org/1489233003/diff/320001/cc/raster/task_category.h
File cc/raster/task_category.h (right):

https://codereview.chromium.org/1489233003/diff/320001/cc/raster/task_categor...
cc/raster/task_category.h:18: };
This look good but I'd rather not have any task graph runner implementations
assume that these are the only valid values. I thinking of this as more of a
hint which it's perfectly fine by an implementation to ignore. Just like it's
fine to ignore the priority of tasks. What I'm really trying to say is that I
don't think we should have the kNumTaskCategories below.

Would it help to just expose TaskGraphWorkQueue::ready_to_run_namespaces_ to the
TGR implementations? Add a "ready_to_run_namespaces() const { return
ready_to_run_namespaces_; }" getter? As the work queue is just some helper
function I feel like that would be ok.

[ericrk, 2015-12-12 00:34:43]

Description was changed from

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate regression in cc_perftests for TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[ericrk, 2015-12-12 00:36:19]

Description was changed from

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate regression in cc_perftests for TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[ericrk, 2015-12-14 19:40:58]

Added perf notes to the description and fixed things up re. your comment.

https://codereview.chromium.org/1489233003/diff/320001/cc/raster/synchronous_...
File cc/raster/synchronous_task_graph_runner.cc (right):

https://codereview.chromium.org/1489233003/diff/320001/cc/raster/synchronous_...
cc/raster/synchronous_task_graph_runner.cc:71: for (category = 0u; category <
kNumTaskCategories; ++category) {
On 2015/12/10 16:49:57, reveman wrote:
> I'd like to avoid making the kNumTaskCategories assumption. See my other
> comment.

What do you think about this approach? It's a bit annoying that we have to do
find_if (as we can't just take the first one, as the list could be empty) - I
thought about trying to write some sort of iterator adapter to just show
non-empty elements, but seemed like more trouble than it was worth.

[reveman, 2015-12-14 20:04:03]

lgtm

[ericrk, 2015-12-14 21:22:24]

ericrk@chromium.org changed reviewers:
+ sievers@chromium.org

[ericrk, 2015-12-14 21:22:24]

+sievers for content. Thanks!

[no sievers, 2015-12-14 21:28:23]

On 2015/12/14 21:22:24, ericrk wrote:
> +sievers for content. Thanks!

lgtm

[ericrk, 2015-12-14 21:38:39]

The CQ bit was checked by ericrk@chromium.org

[commit-bot: I haz the power, 2015-12-14 21:39:56]

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

[commit-bot: I haz the power, 2015-12-15 02:58:05]

Description was changed from

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[commit-bot: I haz the power, 2015-12-15 02:58:06]

Committed patchset #11 (id:340001)

[commit-bot: I haz the power, 2015-12-15 02:58:50]

Description was changed from

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/05ca4bc9df381e6345f9cf7ee29cdfa075be30c4
Cr-Commit-Position: refs/heads/master@{#365140}
==========

[commit-bot: I haz the power, 2015-12-15 02:58:51]

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

[yoichio, 2015-12-15 04:26:44]

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

The reason for reverting is: This might cause test failure on
SynchronousTaskGraphRunner/SingleThreadTaskGraphRunnerTest/
http://test-results.appspot.com/dashboards/flakiness_dashboard.html#tests=Syn....

[haraken, 2015-12-15 04:36:50]

haraken@chromium.org changed reviewers:
+ haraken@chromium.org, oilpan-reviews@chromium.org

[haraken, 2015-12-15 04:36:51]

cc_unittests started failing on Oilpan bots after this CL.

http://build.chromium.org/p/chromium.webkit/builders/WebKit%20Linux%20Oilpan/...

[ericrk, 2015-12-16 21:31:00]

Had a bug where code that needed to run was wrapped in DCHECK - got through bots
due to DCHECK_ALWAYS_ENABLED, but failed on some secondary bots after submit.
Fixed this, resubmitting.

[ericrk, 2015-12-16 21:31:38]

The CQ bit was checked by ericrk@chromium.org

[ericrk, 2015-12-16 21:31:38]

The patchset sent to the CQ was uploaded after l-g-t-m from
reveman@chromium.org, sievers@chromium.org
Link to the patchset: https://codereview.chromium.org/1489233003/#ps360001
(title: "fix dcheck")

[commit-bot: I haz the power, 2015-12-16 21:33:18]

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

[commit-bot: I haz the power, 2015-12-16 22:39:50]

Committed patchset #12 (id:360001)

[commit-bot: I haz the power, 2015-12-16 22:40:51]

Description was changed from

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/05ca4bc9df381e6345f9cf7ee29cdfa075be30c4
Cr-Commit-Position: refs/heads/master@{#365140}
==========

to

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/05ca4bc9df381e6345f9cf7ee29cdfa075be30c4
Cr-Commit-Position: refs/heads/master@{#365140}

Committed: https://crrev.com/3b4338fc32cf20703baa8066bdad7ce07c5ae696
Cr-Commit-Position: refs/heads/master@{#365646}
==========

[commit-bot: I haz the power, 2015-12-16 22:40:52]

Patchset 12 (id:??) landed as
https://crrev.com/3b4338fc32cf20703baa8066bdad7ce07c5ae696
Cr-Commit-Position: refs/heads/master@{#365646}

[Yuta Kitamura, 2015-12-17 05:10:50]

A revert of this CL (patchset #12 id:360001) has been created in
https://codereview.chromium.org/1538433002/ by yutak@chromium.org.

The reason for reverting is: Broke compile on Win x64 GN

https://build.chromium.org/p/chromium.win/builders/Win%20x64%20GN/builds/9223
.

[dtu, 2015-12-17 05:25:25]

On 2015/12/17 at 05:10:50, yutak wrote:
> A revert of this CL (patchset #12 id:360001) has been created in
https://codereview.chromium.org/1538433002/ by yutak@chromium.org.
> 
> The reason for reverting is: Broke compile on Win x64 GN
> 
> https://build.chromium.org/p/chromium.win/builders/Win%20x64%20GN/builds/9223
> .

Perf official Win x64 as well.
https://build.chromium.org/p/chromium.perf/builders/Win%20x64%20Builder/build...

[ericrk, 2015-12-18 19:45:04]

Description was changed from

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/05ca4bc9df381e6345f9cf7ee29cdfa075be30c4
Cr-Commit-Position: refs/heads/master@{#365140}

Committed: https://crrev.com/3b4338fc32cf20703baa8066bdad7ce07c5ae696
Cr-Commit-Position: refs/heads/master@{#365646}
==========

to

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
CQ_INCLUDE_TRYBOTS=tryserver.chromium.win:win_chromium_gn_x64_rel

Committed: https://crrev.com/05ca4bc9df381e6345f9cf7ee29cdfa075be30c4
Cr-Commit-Position: refs/heads/master@{#365140}

Committed: https://crrev.com/3b4338fc32cf20703baa8066bdad7ce07c5ae696
Cr-Commit-Position: refs/heads/master@{#365646}
==========

[ericrk, 2015-12-18 19:50:16]

The CQ bit was checked by ericrk@chromium.org

[ericrk, 2015-12-18 19:50:16]

The patchset sent to the CQ was uploaded after l-g-t-m from
reveman@chromium.org, sievers@chromium.org
Link to the patchset: https://codereview.chromium.org/1489233003/#ps380001
(title: "Fix conversions for x64")

[ericrk, 2015-12-18 19:50:19]

The CQ bit was unchecked by ericrk@chromium.org

[ericrk, 2015-12-18 21:01:52]

The CQ bit was checked by ericrk@chromium.org

[commit-bot: I haz the power, 2015-12-18 21:03:09]

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

[commit-bot: I haz the power, 2015-12-18 22:04:12]

Description was changed from

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
CQ_INCLUDE_TRYBOTS=tryserver.chromium.win:win_chromium_gn_x64_rel

Committed: https://crrev.com/05ca4bc9df381e6345f9cf7ee29cdfa075be30c4
Cr-Commit-Position: refs/heads/master@{#365140}

Committed: https://crrev.com/3b4338fc32cf20703baa8066bdad7ce07c5ae696
Cr-Commit-Position: refs/heads/master@{#365646}
==========

to

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
CQ_INCLUDE_TRYBOTS=tryserver.chromium.win:win_chromium_gn_x64_rel

Committed: https://crrev.com/05ca4bc9df381e6345f9cf7ee29cdfa075be30c4
Cr-Commit-Position: refs/heads/master@{#365140}

Committed: https://crrev.com/3b4338fc32cf20703baa8066bdad7ce07c5ae696
Cr-Commit-Position: refs/heads/master@{#365646}
==========

[commit-bot: I haz the power, 2015-12-18 22:04:12]

Committed patchset #13 (id:380001)

[commit-bot: I haz the power, 2015-12-18 22:05:09]

Description was changed from

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
CQ_INCLUDE_TRYBOTS=tryserver.chromium.win:win_chromium_gn_x64_rel

Committed: https://crrev.com/05ca4bc9df381e6345f9cf7ee29cdfa075be30c4
Cr-Commit-Position: refs/heads/master@{#365140}

Committed: https://crrev.com/3b4338fc32cf20703baa8066bdad7ce07c5ae696
Cr-Commit-Position: refs/heads/master@{#365646}
==========

to

==========
TaskGraphRunner Group support

Adds a group to TaskGraphRunner, this can be used by an
implementation along with priority in order to decide how to execute
tasks.

This is a prerequisite patch for thread affinity changes which are
coming in a follow-up.

This patch causes a moderate (~15%) regression in cc_perftests for
TaskGraphRunner.

The main regressions I'm seeing are:

In ScheduleTasks, we're seeing an additional 3% time spent in operator[] for the
two new maps vs ToT.

We're also seeing an additional 5.5% of time spent in test code which builds the
task graph.

Other regressions are less clear, but probably have to do with the additional
cost of ScheduleTasks in the function body itself (inlined looping).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
CQ_INCLUDE_TRYBOTS=tryserver.chromium.win:win_chromium_gn_x64_rel

Committed: https://crrev.com/05ca4bc9df381e6345f9cf7ee29cdfa075be30c4
Cr-Commit-Position: refs/heads/master@{#365140}

Committed: https://crrev.com/3b4338fc32cf20703baa8066bdad7ce07c5ae696
Cr-Commit-Position: refs/heads/master@{#365646}

Committed: https://crrev.com/5a1188c6c3b464ed96694881dfec6c70c7d58a29
Cr-Commit-Position: refs/heads/master@{#366180}
==========

[commit-bot: I haz the power, 2015-12-18 22:05:10]

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