cc: Make TaskGraphRunner DependencyMismatch debug check faster.

When a new dependency graph is scheduled, TaskGraphRunner checks
that the number of dependencies explicitly set in the nodes matches
the dependencies defined by the edges of the graph.

While the performance of this check is not a real issue, since it
runs only in debug and usually the number of nodes/edges is small,
it can be a problem in tests where the number of nodes is artifically
high.

This CL makes the debug check faster changing the runtime complexity
of the code from O(|nodes| X |edges|) to O(max(|nodes|, |edges|).

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Review URL: https://codereview.chromium.org/1263223004

Cr-Commit-Position: refs/heads/master@{#341825}

1 files changed, 13 insertions, 30 deletions

diff --git a/cc/raster/task_graph_runner.cc b/cc/raster/task_graph_runner.cc
index c810aa5..5ffe6c4 100644
--- a/cc/raster/task_graph_runner.cc
+++ b/cc/raster/task_graph_runner.cc
@@ -6,6 +6,7 @@
 
 #include <algorithm>
 
+#include "base/containers/hash_tables.h"
 #include "base/strings/stringprintf.h"
 #include "base/threading/thread_restrictions.h"
 #include "base/trace_event/trace_event.h"
@@ -68,34 +69,19 @@ class DependentIterator {
   TaskGraph::Node* current_node_;
 };
 
-class DependencyMismatchComparator {
- public:
-  explicit DependencyMismatchComparator(const TaskGraph* graph)
-      : graph_(graph) {}
-
-  bool operator()(const TaskGraph::Node& node) const {
-    return static_cast<size_t>(std::count_if(graph_->edges.begin(),
-                                             graph_->edges.end(),
-                                             DependentComparator(node.task))) !=
-           node.dependencies;
-  }
+bool DependencyMismatch(const TaskGraph* graph) {
+  // Value storage will be 0-initialized.
+  base::hash_map<const Task*, size_t> dependents;
+  for (const TaskGraph::Edge& edge : graph->edges)
+    dependents[edge.dependent]++;
 
- private:
-  class DependentComparator {
-   public:
-    explicit DependentComparator(const Task* dependent)
-        : dependent_(dependent) {}
-
-    bool operator()(const TaskGraph::Edge& edge) const {
-      return edge.dependent == dependent_;
-    }
-
-   private:
-    const Task* dependent_;
-  };
+  for (const TaskGraph::Node& node : graph->nodes) {
+    if (dependents[node.task] != node.dependencies)
+      return true;
+  }
 
-  const TaskGraph* graph_;
-};
+  return false;
+}
 
 }  // namespace
 
@@ -171,10 +157,7 @@ void TaskGraphRunner::ScheduleTasks(NamespaceToken token, TaskGraph* graph) {
                graph->edges.size());
 
   DCHECK(token.IsValid());
-  DCHECK(std::find_if(graph->nodes.begin(),
-                      graph->nodes.end(),
-                      DependencyMismatchComparator(graph)) ==
-         graph->nodes.end());
+  DCHECK(!DependencyMismatch(graph));
 
   {
     base::AutoLock lock(lock_);