Make Task Manager sort more meaningful

chrome/browser/task_management/sampling/task_manager_impl.cc

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/task_management/sampling/task_manager_impl.h"
 
+#include <algorithm>
 #include <string>
+#include <unordered_map>
 #include <vector>
 
 #include "base/command_line.h"
 #include "base/stl_util.h"
 #include "build/build_config.h"
 #include "chrome/browser/task_management/providers/browser_process_task_provider.h"
 #include "chrome/browser/task_management/providers/child_process_task_provider.h"
 #include "chrome/browser/task_management/providers/web_contents/web_contents_task_provider.h"
 #include "content/public/browser/browser_thread.h"
 #include "content/public/browser/gpu_data_manager.h"
@@ skipping 221 matching lines @@
   *stats = task->GetWebCacheStats();
 
   return true;
 }
 
 const TaskIdList& TaskManagerImpl::GetTaskIdsList() const {
   DCHECK(is_running_) << "Task manager is not running. You must observe the "
       "task manager for it to start running";
 
   if (sorted_task_ids_.empty()) {
-    sorted_task_ids_.reserve(task_groups_by_task_id_.size());
+    // |comparator| groups and sorts by subtask-ness (to push all subtasks to be
+    // last), then by process type (e.g. the browser process should be first;
+    // renderer processes should be together), then tab id (processes used by
+    // the same tab should be kept together, and a tab should have a stable
+    // position in the list as it cycles through processes, and tab creation
+    // order is meaningful), and finally by task id (when all else is equal, put
+    // the oldest tasks first).
+    auto comparator = [](const Task* a, const Task* b) -> bool {
+      return std::make_tuple(!!a->GetParentTask(), a->GetType(), a->GetTabId(),

[afakhry, 2016/06/06 18:11:59]

First, using a tuple is brilliant.

Second, how about adding a bool Task::HasParentTask() which encapsulates "return
!!GetParentTask();"?

The code here and below in several places will be nicer to look at.

[ncarter (slow), 2016/06/20 17:40:00]

Done.

+                             a->task_id()) <

[ncarter (slow), 2016/06/08 21:37:50]

FYI using tuples for lexicographic comparison is a common C++11 idiom. I think
it's essentially why we have std::tie, and is listed as the example usage
here:http://en.cppreference.com/w/cpp/utility/tuple/tie.

std::tie is better than make_tuple, but it doesn't work here, since the args
aren't lvalues. I wonder if I can use std::tie after adding HasParentTask() as
you suggest.

[afakhry, 2016/06/09 13:33:53]

Thanks for sharing! I liked the std::tie example.

+             std::make_tuple(!!b->GetParentTask(), b->GetType(), b->GetTabId(),
+                             b->task_id());
+    };
 
-    // Ensure browser process group of task IDs are at the beginning of the
-    // list.
-    auto it = task_groups_by_proc_id_.find(base::GetCurrentProcId());
-    DCHECK(it != task_groups_by_proc_id_.end());
-    const TaskGroup* browser_group = it->second;
-    browser_group->AppendSortedTaskIds(&sorted_task_ids_);
+    const size_t num_groups = task_groups_by_proc_id_.size();
+    const size_t num_tasks = task_groups_by_task_id_.size();
 
+    // Populate |tasks_to_visit| with one task from each group.
+    std::vector<const Task*> tasks_to_visit;
+    tasks_to_visit.reserve(num_groups);
+    std::unordered_map<const Task*, std::vector<const Task*>> children;

[afakhry, 2016/06/06 18:11:59]

Optional: Tracking the children here using a priority queue saves you the sort
at line 328 and the reverse insert in line 329. Unfortunately, I had to get rid
of your awesome lamda for an old-fashioned functor :D. So:

struct Comparator {
  bool operator() (const Task* a, const Task* b) {
    return std::make_tuple(!!a->GetParentTask(), 
                           a->GetType(), 
                           a->GetTabId(),
                           a->task_id()) <
           std::make_tuple(!!b->GetParentTask(), 
                           b->GetType(), 
                           b->GetTabId(),
                           b->task_id());
   }
} comparator;

  - Then here at line 271:

using ChildrenQueue = std::priority_queue<const Task*,
                                          std::vector<const Task*>,
                                          Comparator>;
std::unordered_map<const Task*, ChildrenQueue> children;

  - line 283 becomes:

children[task->GetParentTask()].push(task);

  - finally lines 326~330 become something like:

if (children_it == children.end())
  continue;
while (!children_it->second.empty()) {
  tasks_to_visit.push_back(children_it->second.top());
  children_it->second.pop();
}


I measured both timings and they're similar. Up to you.

[ncarter (slow), 2016/06/08 21:37:50]

Interesting idea. They're essentially the same under the hood; it's just that we
use heapsort vs an explicit std::sort. I'll take a look at this with fresh eyes
tomorrow. [Note to self: before touching this, make sure the tests actually
fails if we omit the existing std::sort.]

[afakhry, 2016/06/09 13:33:53]

Yes, they're definitely the same algorithm. The suggested one aims to improve
readability.

[ncarter (slow), 2016/06/20 17:39:59]

Thanks for this suggestion. My overall sense is that sorting in retrospect
captures the essence of what I'm trying to do a little better, since there are
no "pop min" operations during insertion.

I've made some other changes that hopefully make the directionality of the
sorting a little clearer, including using base::Reversed() for the |parent|
iteration.

[afakhry, 2016/06/22 13:49:46]

Acknowledged.

     for (const auto& groups_pair : task_groups_by_proc_id_) {
-      if (groups_pair.second == browser_group)
+      // The first task in the group (per |comparator|) is the one used for
+      // sorting the group relative to other groups.
+      const std::vector<Task*>& tasks = groups_pair.second->tasks();
+      Task* group_task =
+          *std::min_element(tasks.begin(), tasks.end(), comparator);
+      tasks_to_visit.push_back(group_task);
+
+      // Build the parent-to-child map, for use later.
+      for (const Task* task : tasks) {
+        if (task->GetParentTask())
+          children[task->GetParentTask()].push_back(task);
+        else
+          DCHECK(group_task->GetParentTask() == nullptr);
+      }
+    }
+
+    // Now sort |tasks_to_visit| in reverse order (putting the browser process
+    // at back()). We will treat it as a stack from now on.
+    std::sort(tasks_to_visit.rbegin(), tasks_to_visit.rend(), comparator);
+    DCHECK_EQ(Task::BROWSER, tasks_to_visit.back()->GetType());
+
+    // Using |tasks_to_visit| as a stack, and |visited_groups| to track which
+    // groups we've already added, add groups to |sorted_task_ids_| until all
+    // groups have been added.
+    sorted_task_ids_.reserve(num_tasks);
+    std::unordered_set<TaskGroup*> visited_groups;

[afakhry, 2016/06/03 17:53:42]

Do you need to #include <unordered_set>?

[ncarter (slow), 2016/06/20 17:39:59]

Done.

+    visited_groups.reserve(num_groups);
+    std::vector<Task*> current_group_tasks;  // Outside loop for fewer mallocs.
+    while (visited_groups.size() < num_groups) {
+      CHECK(!tasks_to_visit.empty());

[afakhry, 2016/06/06 18:11:59]

I think a DCHECK() is enough here.

[ncarter (slow), 2016/06/20 17:40:00]

Done.

+      TaskGroup* current_group =
+          GetTaskGroupByTaskId(tasks_to_visit.back()->task_id());
+      tasks_to_visit.pop_back();
+
+      // Mark |current_group| as visited. If this fails, we've already added
+      // the group, and should skip over it.
+      if (!visited_groups.insert(current_group).second)
         continue;
 
-      groups_pair.second->AppendSortedTaskIds(&sorted_task_ids_);
+      // Make a copy of |current_group->tasks()|, sort it, and append the ids.
+      current_group_tasks = current_group->tasks();
+      std::sort(current_group_tasks.begin(), current_group_tasks.end(),
+                comparator);
+      for (Task* task : current_group_tasks) {

[afakhry, 2016/06/03 17:53:42]

const auto& ?

[afakhry, 2016/06/03 17:53:42]

Nit: Remove curly braces.

[ncarter (slow), 2016/06/20 17:39:59]

Done.

[ncarter (slow), 2016/06/20 17:40:00]

I prefer Task* here, since it makes it clearer to the reader what's being
iterated over. Unless there's a functional reason for this -- does "const auto&"
produce better code?

[afakhry, 2016/06/22 13:49:46]

It may or may not. const auto& is generally preferred for read-only access of
the elements in the container.

In our case above, using Task* will access an element by-value, i.e. copies a
Task pointer. This is likely not a big deal; it's just an address.

const auto&, will access the element by-const-ref. Which one performs better for
a good-old pointer? We can never tell until we look at the disassembly of this
code, and see what the compiler is doing. Hopefully the compiler can optimize
these things.

See:
http://stackoverflow.com/questions/15927033/what-is-the-correct-way-of-using-...

+        sorted_task_ids_.push_back(task->task_id());
+      }
+
+      // Find the children of the tasks we just added, and push them into
+      // |tasks_to_visit|, so that we visit them soon. Push in reverse order,
+      // so that we visit them in forward order.
+      for (auto parent_task = current_group_tasks.rbegin();
+           parent_task != current_group_tasks.rend(); ++parent_task) {
+        auto children_it = children.find(*parent_task);
+        if (children_it != children.end()) {
+          std::vector<const Task*>& children = children_it->second;

[afakhry, 2016/06/03 17:53:42]

This children vector hides the outer children unordered_map. It's confusing. Can
you please rename it?

[ncarter (slow), 2016/06/08 21:37:50]

YUCK. Thanks for pointing this out, it was an accident -- it was an artifact of
some last-minute renaming (originally the outer |children| was called |parents|,
but I thought calling it |children| read better.). I'm actually surprised this
collision didn't cause a compile error or functional bug!

[afakhry, 2016/06/09 13:33:53]

I think you got lucky as you were only accessing |children| defined in the
inner-most scope and the compiler assumed you want to use it as well. If you had
wanted to user the outer one, that would have been a disaster! :D

[ncarter (slow), 2016/06/20 17:40:00]

Done.

+          std::sort(children.begin(), children.end(), comparator);
+          tasks_to_visit.insert(tasks_to_visit.end(), children.rbegin(),
+                                children.rend());
+        }
+      }
     }
+    DCHECK_EQ(num_tasks, sorted_task_ids_.size());
   }
 
   return sorted_task_ids_;
 }
 
 TaskIdList TaskManagerImpl::GetIdsOfTasksSharingSameProcess(
     TaskId task_id) const {
   DCHECK(is_running_) << "Task manager is not running. You must observe the "
       "task manager for it to start running";
 
   TaskIdList result;
-  GetTaskGroupByTaskId(task_id)->AppendSortedTaskIds(&result);
+  TaskGroup* group = GetTaskGroupByTaskId(task_id);
+  if (group) {
+    result.reserve(group->tasks().size());
+    for (Task* task : group->tasks()) {

[afakhry, 2016/06/03 17:53:42]

Nit: the curly braces.

[afakhry, 2016/06/03 17:53:42]

Also const auto& ?

[ncarter (slow), 2016/06/20 17:39:59]

I prefer 'Task*' to 'const auto&' here; it's is fewer characters and makes it
clear what we're iterating over.

[ncarter (slow), 2016/06/20 17:40:00]

Done.

[afakhry, 2016/06/22 13:49:46]

Acknowledged.

+      result.push_back(task->task_id());
+    }
+  }
   return result;
 }
 
 size_t TaskManagerImpl::GetNumberOfTasksOnSameProcess(TaskId task_id) const {
   return GetTaskGroupByTaskId(task_id)->num_tasks();
 }
 
 void TaskManagerImpl::TaskAdded(Task* task) {
   DCHECK(task);
 
@@ skipping 159 matching lines @@
         groups_itr.second->AreBackgroundCalculationsDone();
   }
   if (are_all_processes_data_ready) {
     NotifyObserversOnRefreshWithBackgroundCalculations(GetTaskIdsList());
     for (const auto& groups_itr : task_groups_by_proc_id_)
       groups_itr.second->ClearCurrentBackgroundCalculationsFlags();
   }
 }
 
 }  // namespace task_management