Test multideque

cc/resources/resource_pool_unittest.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 "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"
 #include "cc/resources/scoped_resource.h"
 #include "cc/test/fake_output_surface.h"
 #include "cc/test/fake_output_surface_client.h"
 #include "cc/test/fake_resource_provider.h"
 #include "cc/test/test_shared_bitmap_manager.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
@@ skipping 194 matching lines @@
   // released within 100 ms, give the thread up to 200.
   base::RunLoop run_loop;
   task_runner_->PostDelayedTask(FROM_HERE, run_loop.QuitClosure(),
                                 base::TimeDelta::FromMillisecondsD(200));
   run_loop.Run();
 
   EXPECT_EQ(0u, resource_provider_->num_resources());
   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