Test multideque

cc/resources/resource_pool_unittest.cc

Index: cc/resources/resource_pool_unittest.cc
diff --git a/cc/resources/resource_pool_unittest.cc b/cc/resources/resource_pool_unittest.cc
index bde9d748b7e9f72218312ed9aa494b668bd4192e..45e39893686aaff5003da586045e4737e5c81e43 100644
--- a/cc/resources/resource_pool_unittest.cc
+++ b/cc/resources/resource_pool_unittest.cc
@@ -4,6 +4,9 @@
 
 #include "cc/resources/resource_pool.h"
 
+#include <iostream>
+#include <map>
+
 #include "base/run_loop.h"
 #include "base/thread_task_runner_handle.h"
 #include "cc/resources/resource_util.h"
@@ -218,5 +221,186 @@ TEST_F(ResourcePoolTest, UnusedResourcesEventuallyFreed) {
   EXPECT_EQ(0u, resource_pool_->GetTotalMemoryUsageForTesting());
 }
 
+struct TestResource {
+  explicit TestResource(const gfx::Size& size) { this->size = size; }
+
+  gfx::Size size;
+  // uint64_t content_id;
+};
+
+class TestDeque {
+ public:
+  TestResource* Acquire(const gfx::Size& size) {
+    TestResource* resource = nullptr;
+    for (DQ::iterator it = unused_.begin(); it != unused_.end(); ++it) {
+      resource = *it;
+      if (resource->size == size)
+        return resource;

[danakj, 2015/11/09 19:32:51]

don't you need to erase from from unused_ here?

[prashant.n, 2015/11/10 04:10:50]

No. Basically test is -

1. create n resources
2. Append those to unused
3. Then actual test of traversing resources from unused_. (which is done 1m
times). Here the cost is computed for the resource which would not be there at
all, e.g. resource of size 1024 x 1024.

In this test Acquire() is used for creating and traversing purpose only.

4. Finally removing all.

[danakj, 2015/11/10 22:12:05]

But the actual acquire does erase.

+    }
+
+    return new TestResource(size);
+  }
+
+  void AppendToUnused(TestResource* resource) { unused_.push_front(resource); }
+
+  void RemoveAll() {
+    for (DQ::iterator it = unused_.begin(); it != unused_.end(); ++it) {
+      delete *it;
+    }
+    unused_.clear();
+  }
+
+ private:
+  typedef std::deque<TestResource*> DQ;
+  DQ unused_;
+};
+
+class TestMultiDeque {
+ public:
+  TestResource* Acquire(const gfx::Size& size) {
+    TestResource* resource = nullptr;
+    Key key = std::make_pair(size.width(), size.height());
+    DQM::iterator kit = unused_.find(key);
+
+    if (kit != unused_.end()) {
+      DQ* dq = kit->second;
+
+      for (DQ::iterator it = dq->begin(); it != dq->end(); ++it) {
+        resource = *it;
+        if (resource->size == size)
+          return resource;

[danakj, 2015/11/09 19:32:51]

and erase from dq and possibly from unused_ here?

+      }
+    }
+
+    return new TestResource(size);
+  }
+
+  void AppendToUnused(TestResource* resource) {
+    Key key = std::make_pair(resource->size.width(), resource->size.height());
+    DQM::iterator kit = unused_.find(key);
+    if (kit != unused_.end()) {
+      DQ* dq = kit->second;
+      dq->push_front(resource);
+    } else {
+      DQ* dq = new DQ;
+      dq->push_front(resource);
+      unused_[key] = dq;
+    }
+  }
+
+  void RemoveAll() {
+    for (DQM::iterator kit = unused_.begin(); kit != unused_.end(); ++kit) {
+      DQ* dq = kit->second;
+      for (DQ::iterator it = dq->begin(); it != dq->end(); ++it) {
+        delete *it;
+      }
+      delete dq;
+    }
+    unused_.clear();
+  }
+
+ private:
+  typedef std::pair<int, int> Key;
+  typedef std::deque<TestResource*> DQ;
+  typedef std::map<Key, DQ*> DQM;
+  DQM unused_;
+};
+
+void RunTestDeque(int how_many, int tile_round_up, int tile_size_max) {
+  TestDeque tdq;
+  gfx::Size size;
+  int rounds = tile_size_max / tile_round_up;
+  const int r_max = rounds * rounds * how_many;
+  TestResource* resource[r_max];
+
+  int i = 0;
+  for (int w = tile_round_up; w <= tile_size_max; w += tile_round_up) {
+    for (int h = tile_round_up; h <= tile_size_max; h += tile_round_up) {
+      size = gfx::Size(w, h);
+      for (int j = 0; j < how_many; ++j)
+        resource[i++] = tdq.Acquire(size);
+    }
+  }
+
+  for (int i = 0; i < r_max; ++i)
+    tdq.AppendToUnused(resource[i]);

[danakj, 2015/11/09 19:32:51]

Your results appear to include the cost of creating and appending all the items
too. Is that intentional?

I suggest base::TimeTicks::Now() before and after the acquire loop and LOG the
delta.

[prashant.n, 2015/11/10 04:10:50]

It was not intentional. I thought creating and appending mechanisms are  needed
in both tests so kept there. But I did not add the test for those. Basically for
creating, there is no cost, but for appending to queue, multi-deque is costlier
than deque, (cost of finding the deque of required size is extra).

As suggested by you, we can measure the cost of traversing only, as that is the
major concern to be solved by multi-deque.

+
+  size = gfx::Size(1024, 1024);
+  for (int k = 0; k < 1000000; ++k) {
+    TestResource* r = tdq.Acquire(size);
+    delete r;
+  }
+
+  tdq.RemoveAll();
+}
+
+void RunTestMultiDeque(int how_many, int tile_round_up, int tile_size_max) {
+  TestMultiDeque tdq;
+  gfx::Size size;
+  int rounds = tile_size_max / tile_round_up;
+  const int r_max = rounds * rounds * how_many;
+  TestResource* resource[r_max];
+
+  int i = 0;
+  for (int w = tile_round_up; w <= tile_size_max; w += tile_round_up) {
+    for (int h = tile_round_up; h <= tile_size_max; h += tile_round_up) {
+      size = gfx::Size(w, h);
+      for (int j = 0; j < how_many; ++j)
+        resource[i++] = tdq.Acquire(size);
+    }
+  }
+
+  for (int i = 0; i < r_max; ++i)
+    tdq.AppendToUnused(resource[i]);
+
+  size = gfx::Size(1024, 1024);
+  for (int k = 0; k < 1000000; ++k) {
+    TestResource* r = tdq.Acquire(size);
+    delete r;
+  }
+
+  tdq.RemoveAll();
+}
+
+TEST_F(ResourcePoolTest, TestDequeSingle) {
+  RunTestDeque(1, 64, 64);
+}
+
+TEST_F(ResourcePoolTest, TestMultiDequeSingle) {
+  RunTestMultiDeque(1, 64, 64);
+}
+
+TEST_F(ResourcePoolTest, TestDequeManyOfOneSize) {
+  RunTestDeque(50, 64, 64);
+}
+
+TEST_F(ResourcePoolTest, TestMultiDequeManyOfOneSize) {
+  RunTestMultiDeque(50, 64, 64);
+}
+
+TEST_F(ResourcePoolTest, TestDequeOneOfEachSize) {
+  RunTestDeque(1, 64, 512);
+}
+
+TEST_F(ResourcePoolTest, TestMultiDequeOneOfEachSize) {
+  RunTestMultiDeque(1, 64, 512);
+}
+
+TEST_F(ResourcePoolTest, TestDequeManyOfEachSize) {
+  RunTestDeque(5, 64, 512);
+}
+
+TEST_F(ResourcePoolTest, TestMultiDequeManyOfEachSize) {
+  RunTestMultiDeque(5, 64, 512);
+}
+
+TEST_F(ResourcePoolTest, TestDequeTooManyOfEachSize) {
+  RunTestDeque(20, 64, 512);
+}
+
+TEST_F(ResourcePoolTest, TestMultiDequeTooManyOfEachSize) {
+  RunTestMultiDeque(20, 64, 512);
+}
+
 }  // namespace
 }  // namespace cc