[2/2] mesos git commit: Added a benchmark test for hierarchical sorter.

[ne...@apache.org]

Added a benchmark test for hierarchical sorter.

This test is very similar to Sorter_BENCHMARK_Test.FullSort, except
that hierarchical role is built instead of flat one.

Review: https://reviews.apache.org/r/58533/


Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/b271e885
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/b271e885
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/b271e885

Branch: refs/heads/master
Commit: b271e8850ca2dee376a1da56aefe2cadc127039a
Parents: 73c9628
Author: Jay Guo <gu...@gmail.com>
Authored: Wed Apr 26 14:38:24 2017 -0400
Committer: Neil Conway <ne...@gmail.com>
Committed: Wed Apr 26 15:14:29 2017 -0400

----------------------------------------------------------------------
 src/tests/sorter_tests.cpp | 185 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 185 insertions(+)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/mesos/blob/b271e885/src/tests/sorter_tests.cpp
----------------------------------------------------------------------
diff --git a/src/tests/sorter_tests.cpp b/src/tests/sorter_tests.cpp
index 2ddf64e..6508983 100644
--- a/src/tests/sorter_tests.cpp
+++ b/src/tests/sorter_tests.cpp
@@ -1531,6 +1531,191 @@ TEST_P(Sorter_BENCHMARK_Test, FullSort)
        << watch.elapsed() << endl;
 }
 
+
+class HSorter_BENCHMARK_Test
+  : public ::testing::Test,
+    public ::testing::WithParamInterface<
+        std::tr1::tuple<size_t, std::tr1::tuple<size_t, size_t>>> {};
+
+
+INSTANTIATE_TEST_CASE_P(
+    AgentAndClientCount,
+    HSorter_BENCHMARK_Test,
+    ::testing::Combine(
+      ::testing::Values(1000U, 5000U, 10000U, 20000U, 30000U, 50000U),
+      ::testing::Values(
+          // ~1000 clients with various depth & breadth.
+          std::tr1::tuple<size_t, size_t>{3U, 32U},   // 1056
+          std::tr1::tuple<size_t, size_t>{7U, 3U},    // 1092
+          std::tr1::tuple<size_t, size_t>{10U, 2U}))  // 1022
+    );
+
+
+// This benchmark simulates sorting a hierarchy of clients that have
+// different amount of allocations. The hierarchy is determined by
+// depth and breadth, where depth represents height of tree including
+// root, breadth represents number of children of each internal node.
+TEST_P(HSorter_BENCHMARK_Test, FullSort)
+{
+  const size_t agentCount = std::tr1::get<0>(GetParam());
+  const std::tr1::tuple<size_t, size_t> tuple = std::tr1::get<1>(GetParam());
+  const size_t clientDepth = std::tr1::get<0>(tuple);
+  const size_t clientBreadth = std::tr1::get<1>(tuple);
+
+  vector<SlaveID> agents;
+  agents.reserve(agentCount);
+
+  // Compute total number of clients in a tree of given depth and
+  // breadth, including root node.
+  std::function<size_t (size_t, size_t)> totalClients =
+    [&totalClients](size_t depth, size_t breadth) -> size_t {
+      if (depth == 0) {
+        return 0;
+      }
+
+      if (depth == 1) {
+        return 1;
+      }
+
+      return 1 + breadth * totalClients(depth - 1, breadth);
+    };
+
+  const size_t clientCount = totalClients(clientDepth, clientBreadth) - 1;
+
+  vector<string> clients;
+  clients.reserve(clientCount);
+
+  DRFSorter sorter;
+  Stopwatch watch;
+
+  watch.start();
+  {
+    // Build the tree of given depth and breadth in depth-first fashion.
+    std::function<void (string, size_t)> buildTree =
+      [&buildTree, &sorter, &clients, &clientBreadth](
+          string path, size_t depth) {
+        if (depth == 0) {
+          return;
+        }
+
+        if (depth > 1) {
+          for (size_t i = 0; i < clientBreadth; i++) {
+            buildTree(path + stringify(i) + "/", depth - 1);
+          }
+        }
+
+        const string client = strings::remove(path, "/", strings::SUFFIX);
+        if (!client.empty()) {
+          sorter.add(client);
+          clients.push_back(client);
+        }
+      };
+
+    buildTree("", clientDepth);
+  }
+  watch.stop();
+
+  cout << "Added " << clientCount << " clients in "
+       << watch.elapsed() << endl;
+
+  Resources agentResources = Resources::parse(
+      "cpus:24;mem:4096;disk:4096;ports:[31000-32000]").get();
+
+  watch.start();
+  {
+    for (size_t i = 0; i < agentCount; i++) {
+      SlaveID slaveId;
+      slaveId.set_value("agent" + stringify(i));
+
+      agents.push_back(slaveId);
+
+      sorter.add(slaveId, agentResources);
+    }
+  }
+  watch.stop();
+
+  cout << "Added " << agentCount << " agents in "
+       << watch.elapsed() << endl;
+
+  Resources allocated = Resources::parse(
+      "cpus:16;mem:2014;disk:1024").get();
+
+  // TODO(gyliu513): Parameterize the number of range for the fragment.
+  Try<::mesos::Value::Ranges> ranges = fragment(createRange(31000, 32000), 100);
+  ASSERT_SOME(ranges);
+  ASSERT_EQ(100, ranges->range_size());
+
+  allocated += createPorts(ranges.get());
+
+  watch.start();
+  {
+    // Allocate resources on all agents, round-robin through the clients.
+    size_t clientIndex = 0;
+    foreach (const SlaveID& slaveId, agents) {
+      const string& client = clients[clientIndex++ % clients.size()];
+      sorter.allocated(client, slaveId, allocated);
+    }
+  }
+  watch.stop();
+
+  cout << "Added allocations for " << agentCount << " agents in "
+         << watch.elapsed() << endl;
+
+  watch.start();
+  {
+    sorter.sort();
+  }
+  watch.stop();
+
+  cout << "Full sort of " << clientCount << " clients took "
+       << watch.elapsed() << endl;
+
+  watch.start();
+  {
+    sorter.sort();
+  }
+  watch.stop();
+
+  cout << "No-op sort of " << clientCount << " clients took "
+       << watch.elapsed() << endl;
+
+  watch.start();
+  {
+    // Unallocate resources on all agents, round-robin through the clients.
+    size_t clientIndex = 0;
+    foreach (const SlaveID& slaveId, agents) {
+      const string& client = clients[clientIndex++ % clients.size()];
+      sorter.unallocated(client, slaveId, allocated);
+    }
+  }
+  watch.stop();
+
+  cout << "Removed allocations for " << agentCount << " agents in "
+         << watch.elapsed() << endl;
+
+  watch.start();
+  {
+    foreach (const SlaveID& slaveId, agents) {
+      sorter.remove(slaveId, agentResources);
+    }
+  }
+  watch.stop();
+
+  cout << "Removed " << agentCount << " agents in "
+       << watch.elapsed() << endl;
+
+  watch.start();
+  {
+    foreach (const string& clientId, clients) {
+      sorter.remove(clientId);
+    }
+  }
+  watch.stop();
+
+  cout << "Removed " << clientCount << " clients in "
+       << watch.elapsed() << endl;
+}
+
 } // namespace tests {
 } // namespace internal {
 } // namespace mesos {