Added perftests for layer sorting

cc/trees/layer_tree_host_common_perftest.cc

Index: cc/trees/layer_tree_host_common_perftest.cc
diff --git a/cc/trees/layer_tree_host_common_perftest.cc b/cc/trees/layer_tree_host_common_perftest.cc
index 7fe0d99146398f955ce5983432c4724001f43a7e..71692d8b6bbf0c17edf021da6bbebc42ebccfb1c 100644
--- a/cc/trees/layer_tree_host_common_perftest.cc
+++ b/cc/trees/layer_tree_host_common_perftest.cc
@@ -19,6 +19,7 @@
 #include "cc/test/layer_tree_json_parser.h"
 #include "cc/test/layer_tree_test.h"
 #include "cc/test/paths.h"
+#include "cc/trees/layer_sorter.h"
 #include "cc/trees/layer_tree_impl.h"
 #include "testing/perf/perf_test.h"
 
@@ -125,27 +126,95 @@ class CalcDrawPropsImplTest : public LayerTreeHostCommonPerfTest {
     do {
       bool can_render_to_separate_surface = true;
       int max_texture_size = 8096;
-      LayerImplList update_list;
-      LayerTreeHostCommon::CalcDrawPropsImplInputs inputs(
-          active_tree->root_layer(),
-          active_tree->DrawViewportSize(),
-          host_impl->DrawTransform(),
-          active_tree->device_scale_factor(),
-          active_tree->total_page_scale_factor(),
-          active_tree->InnerViewportContainerLayer(),
-          max_texture_size,
-          host_impl->settings().can_use_lcd_text,
-          can_render_to_separate_surface,
-          host_impl->settings().layer_transforms_should_scale_layer_contents,
-          &update_list,
-          0);
-      LayerTreeHostCommon::CalculateDrawProperties(&inputs);
+      DoCalcDrawPropertiesImpl(can_render_to_separate_surface,
+                               max_texture_size,
+                               active_tree,
+                               host_impl);
 
       timer_.NextLap();
     } while (!timer_.HasTimeLimitExpired());
 
     EndTest();
   }
+
+  void DoCalcDrawPropertiesImpl(bool can_render_to_separate_surface,
+                                int max_texture_size,
+                                LayerTreeImpl* active_tree,
+                                LayerTreeHostImpl* host_impl) {
+    LayerImplList update_list;
+    LayerTreeHostCommon::CalcDrawPropsImplInputs inputs(
+        active_tree->root_layer(),
+        active_tree->DrawViewportSize(),
+        host_impl->DrawTransform(),
+        active_tree->device_scale_factor(),
+        active_tree->total_page_scale_factor(),
+        active_tree->InnerViewportContainerLayer(),
+        max_texture_size,
+        host_impl->settings().can_use_lcd_text,
+        can_render_to_separate_surface,
+        host_impl->settings().layer_transforms_should_scale_layer_contents,
+        &update_list,
+        0);
+    LayerTreeHostCommon::CalculateDrawProperties(&inputs);
+  }
+};
+
+class LayerSorterMainTest : public CalcDrawPropsImplTest {
+ public:
+  void RunSortLayers() { RunTest(false, false, false); }
+
+  virtual void BeginTest() OVERRIDE { PostSetNeedsCommitToMainThread(); }
+
+  virtual void DrawLayersOnThread(LayerTreeHostImpl* host_impl) OVERRIDE {
+    LayerTreeImpl* active_tree = host_impl->active_tree();
+    // First build the tree and then we'll start running tests on layersorter
+    // itself
+    bool can_render_to_separate_surface = true;
+    int max_texture_size = 8096;
+    DoCalcDrawPropertiesImpl(can_render_to_separate_surface,
+                             max_texture_size,
+                             active_tree,
+                             host_impl);
+
+    BuildLayerImplList(active_tree->root_layer(), &base_list);
+
+    LayerImplList test_list;
+    timer_.Reset();
+    do {
+      // Here we'll move the layers into a LayerImpl list of their own to be
+      // sorted so we don't have a sorted list for every run after the first
+      test_list.clear();

[Ian Vollick, 2014/05/31 01:52:01]

For each list you sort (I think there should be one per 3d rendering context --
see below), I think you can just do this:

LayerImplList test_list = base_list;

to do a copy since it's really just a std::vector.

[Troy Hildebrandt, 2014/06/02 22:08:30]

Done.

+      for (LayerImplList::iterator it = base_list.begin(); it < base_list.end();
+           ++it) {
+        test_list.push_back(*it);
+      }
+
+      LayerSorter layer_sorter;
+      layer_sorter.Sort(test_list.begin(), test_list.end());
+      timer_.NextLap();
+    } while (!timer_.HasTimeLimitExpired());
+
+    EndTest();
+  }
+
+  void BuildLayerImplList(LayerImpl* layer,
+                          LayerImplList* list,
+                          size_t sorted_3d_level = 0) {
+    if (layer == NULL)

[Ian Vollick, 2014/05/31 01:52:01]

Will this ever be the case? Correct me if I'm wrong, but I don't think we have
NULL entries in children.

[Troy Hildebrandt, 2014/06/02 22:08:30]

As far as I can tell, it shouldn't be. I removed this.

+      return;
+
+    size_t sorted_3d = sorted_3d_level + (layer->is_3d_sorted() ? 1 : 0);

[Ian Vollick, 2014/05/31 01:52:01]

Using a size_t here is a little wonky and, I think, a little broken. The value
appears to be non-decreasing, so once sorted_3d > 0, every descendant will get
added to the list.

If you want to retain the current behavior, I'd ditch that parameter altogether
and just do
if (layer->is_3d_sorted())
  list->push_back(layer)

But I think there's a better option that I'd prefer you go with.
 - Store a std::vector<LayerImplList> rendering_contexts_;
 - Expose the functions LayerIsInExisting3DRenderingContext and
IsRootLayerOfNewRenderingContext from layer_tree_host_common.cc
 - During your recursion, if you hit a layer that's a root of a new rendering
context append a list for the context.
 - If the layer is 3d sorted, add it to the most recent context.
 - Each "lap" above will be a sort of each 3d rendering context.

[Troy Hildebrandt, 2014/06/02 22:08:30]

Removed, using layer->is_3d_sorted() now.

+    if (sorted_3d) {

[Ian Vollick, 2014/05/31 01:52:01]

Nit: no braces around one liners. Here and elsewhere.

[enne (OOO), 2014/06/02 17:54:19]

Nit nit: Braces on oneliners are not forbidden by Chrome style.  ;)

[Ian Vollick, 2014/06/02 20:19:30]

Wait, what?! That's awesome. I love braces around one-liners :)

+      list->push_back(layer);
+    }
+
+    for (size_t i = 0; i < layer->children().size(); ++i) {
+      BuildLayerImplList(layer->children()[i], list, sorted_3d);
+    }
+  }
+
+ private:
+  LayerImplList base_list;
 };
 
 TEST_F(CalcDrawPropsMainTest, TenTen) {
@@ -196,5 +265,17 @@ TEST_F(CalcDrawPropsImplTest, TouchRegionHeavy) {
   RunCalcDrawProps();
 }
 
+TEST_F(LayerSorterMainTest, LayerSorterCubes) {
+  SetTestName("layer_sort_cubes");
+  ReadTestFile("layer_sort_cubes");
+  RunSortLayers();
+}
+
+TEST_F(LayerSorterMainTest, LayerSorterRubik) {
+  SetTestName("layer_sort_rubik");
+  ReadTestFile("layer_sort_rubik");
+  RunSortLayers();
+}
+
 }  // namespace
 }  // namespace cc