CTest: Add bin-packing algorithm

This algorithm is used to determine whether or not a test can
execute with the available resources. It uses a recursive largest-
first algorithm to try to place the tests into their respective
slots.

3 files changed, 233 insertions, 0 deletions

diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt
index 57229db..63e08de 100644
--- a/Source/CMakeLists.txt
+++ b/Source/CMakeLists.txt
@@ -899,6 +899,7 @@ include_directories(
 #
 set(CTEST_SRCS cmCTest.cxx
   CTest/cmProcess.cxx
+  CTest/cmCTestBinPacker.cxx
   CTest/cmCTestBuildAndTestHandler.cxx
   CTest/cmCTestBuildCommand.cxx
   CTest/cmCTestBuildHandler.cxx
diff --git a/Source/CTest/cmCTestBinPacker.cxx b/Source/CTest/cmCTestBinPacker.cxx
new file mode 100644
index 0000000..e9e3bee
--- /dev/null
+++ b/Source/CTest/cmCTestBinPacker.cxx
@@ -0,0 +1,201 @@
+/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
+   file Copyright.txt or https://cmake.org/licensing for details.  */
+#include "cmCTestBinPacker.h"
+
+#include <algorithm>
+#include <utility>
+
+bool cmCTestBinPackerAllocation::operator==(
+  const cmCTestBinPackerAllocation& other) const
+{
+  return this->ProcessIndex == other.ProcessIndex &&
+    this->SlotsNeeded == other.SlotsNeeded && this->Id == other.Id;
+}
+
+bool cmCTestBinPackerAllocation::operator!=(
+  const cmCTestBinPackerAllocation& other) const
+{
+  return !(*this == other);
+}
+
+namespace {
+
+/*
+ * The following algorithm is used to do two things:
+ *
+ * 1) Determine if a test's hardware requirements can fit within the hardware
+ *    present on the system, and
+ * 2) Do the actual allocation
+ *
+ * This algorithm performs a recursive search, looking for a bin pack that will
+ * fit the specified requirements. It has a template to specify different
+ * optimization strategies. If it ever runs out of room, it backtracks as far
+ * down the stack as it needs to and tries a different combination until no
+ * more combinations can be tried.
+ */
+template <typename AllocationStrategy>
+static bool AllocateCTestHardware(
+  const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+  const std::vector<std::string>& hardwareSorted, std::size_t currentIndex,
+  std::vector<cmCTestBinPackerAllocation*>& allocations)
+{
+  // Iterate through all large enough resources until we find a solution
+  std::size_t hardwareIndex = 0;
+  while (hardwareIndex < hardwareSorted.size()) {
+    auto const& resource = hardware.at(hardwareSorted[hardwareIndex]);
+    if (resource.Free() >=
+        static_cast<unsigned int>(allocations[currentIndex]->SlotsNeeded)) {
+      // Preemptively allocate the resource
+      allocations[currentIndex]->Id = hardwareSorted[hardwareIndex];
+      if (currentIndex + 1 >= allocations.size()) {
+        // We have a solution
+        return true;
+      }
+
+      // Move the resource up the list until it is sorted again
+      auto hardware2 = hardware;
+      auto hardwareSorted2 = hardwareSorted;
+      hardware2[hardwareSorted2[hardwareIndex]].Locked +=
+        allocations[currentIndex]->SlotsNeeded;
+      AllocationStrategy::IncrementalSort(hardware2, hardwareSorted2,
+                                          hardwareIndex);
+
+      // Recurse one level deeper
+      if (AllocateCTestHardware<AllocationStrategy>(
+            hardware2, hardwareSorted2, currentIndex + 1, allocations)) {
+        return true;
+      }
+    }
+
+    // No solution found here, deallocate the resource and try the next one
+    allocations[currentIndex]->Id.clear();
+    auto freeSlots = hardware.at(hardwareSorted.at(hardwareIndex)).Free();
+    do {
+      ++hardwareIndex;
+    } while (hardwareIndex < hardwareSorted.size() &&
+             hardware.at(hardwareSorted.at(hardwareIndex)).Free() ==
+               freeSlots);
+  }
+
+  // No solution was found
+  return false;
+}
+
+template <typename AllocationStrategy>
+static bool AllocateCTestHardware(
+  const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+  std::vector<cmCTestBinPackerAllocation>& allocations)
+{
+  // Sort the resource requirements in descending order by slots needed
+  std::vector<cmCTestBinPackerAllocation*> allocationsPtr;
+  allocationsPtr.reserve(allocations.size());
+  for (auto& allocation : allocations) {
+    allocationsPtr.push_back(&allocation);
+  }
+  std::stable_sort(
+    allocationsPtr.rbegin(), allocationsPtr.rend(),
+    [](cmCTestBinPackerAllocation* a1, cmCTestBinPackerAllocation* a2) {
+      return a1->SlotsNeeded < a2->SlotsNeeded;
+    });
+
+  // Sort the resources according to sort strategy
+  std::vector<std::string> hardwareSorted;
+  hardwareSorted.reserve(hardware.size());
+  for (auto const& hw : hardware) {
+    hardwareSorted.push_back(hw.first);
+  }
+  AllocationStrategy::InitialSort(hardware, hardwareSorted);
+
+  // Do the actual allocation
+  return AllocateCTestHardware<AllocationStrategy>(
+    hardware, hardwareSorted, std::size_t(0), allocationsPtr);
+}
+
+class RoundRobinAllocationStrategy
+{
+public:
+  static void InitialSort(
+    const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+    std::vector<std::string>& hardwareSorted);
+
+  static void IncrementalSort(
+    const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+    std::vector<std::string>& hardwareSorted, std::size_t lastAllocatedIndex);
+};
+
+void RoundRobinAllocationStrategy::InitialSort(
+  const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+  std::vector<std::string>& hardwareSorted)
+{
+  std::stable_sort(
+    hardwareSorted.rbegin(), hardwareSorted.rend(),
+    [&hardware](const std::string& id1, const std::string& id2) {
+      return hardware.at(id1).Free() < hardware.at(id2).Free();
+    });
+}
+
+void RoundRobinAllocationStrategy::IncrementalSort(
+  const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+  std::vector<std::string>& hardwareSorted, std::size_t lastAllocatedIndex)
+{
+  auto tmp = hardwareSorted[lastAllocatedIndex];
+  std::size_t i = lastAllocatedIndex;
+  while (i < hardwareSorted.size() - 1 &&
+         hardware.at(hardwareSorted[i + 1]).Free() > hardware.at(tmp).Free()) {
+    hardwareSorted[i] = hardwareSorted[i + 1];
+    ++i;
+  }
+  hardwareSorted[i] = tmp;
+}
+
+class BlockAllocationStrategy
+{
+public:
+  static void InitialSort(
+    const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+    std::vector<std::string>& hardwareSorted);
+
+  static void IncrementalSort(
+    const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+    std::vector<std::string>& hardwareSorted, std::size_t lastAllocatedIndex);
+};
+
+void BlockAllocationStrategy::InitialSort(
+  const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+  std::vector<std::string>& hardwareSorted)
+{
+  std::stable_sort(
+    hardwareSorted.rbegin(), hardwareSorted.rend(),
+    [&hardware](const std::string& id1, const std::string& id2) {
+      return hardware.at(id1).Free() < hardware.at(id2).Free();
+    });
+}
+
+void BlockAllocationStrategy::IncrementalSort(
+  const std::map<std::string, cmCTestHardwareAllocator::Resource>&,
+  std::vector<std::string>& hardwareSorted, std::size_t lastAllocatedIndex)
+{
+  auto tmp = hardwareSorted[lastAllocatedIndex];
+  std::size_t i = lastAllocatedIndex;
+  while (i > 0) {
+    hardwareSorted[i] = hardwareSorted[i - 1];
+    --i;
+  }
+  hardwareSorted[i] = tmp;
+}
+}
+
+bool cmAllocateCTestHardwareRoundRobin(
+  const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+  std::vector<cmCTestBinPackerAllocation>& allocations)
+{
+  return AllocateCTestHardware<RoundRobinAllocationStrategy>(hardware,
+                                                             allocations);
+}
+
+bool cmAllocateCTestHardwareBlock(
+  const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+  std::vector<cmCTestBinPackerAllocation>& allocations)
+{
+  return AllocateCTestHardware<BlockAllocationStrategy>(hardware, allocations);
+}
diff --git a/Source/CTest/cmCTestBinPacker.h b/Source/CTest/cmCTestBinPacker.h
new file mode 100644
index 0000000..54f03d7
--- /dev/null
+++ b/Source/CTest/cmCTestBinPacker.h
@@ -0,0 +1,31 @@
+/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
+   file Copyright.txt or https://cmake.org/licensing for details.  */
+#ifndef cmCTestBinPacker_h
+#define cmCTestBinPacker_h
+
+#include <cstddef>
+#include <map>
+#include <string>
+#include <vector>
+
+#include "cmCTestHardwareAllocator.h"
+
+struct cmCTestBinPackerAllocation
+{
+  std::size_t ProcessIndex;
+  int SlotsNeeded;
+  std::string Id;
+
+  bool operator==(const cmCTestBinPackerAllocation& other) const;
+  bool operator!=(const cmCTestBinPackerAllocation& other) const;
+};
+
+bool cmAllocateCTestHardwareRoundRobin(
+  const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+  std::vector<cmCTestBinPackerAllocation>& allocations);
+
+bool cmAllocateCTestHardwareBlock(
+  const std::map<std::string, cmCTestHardwareAllocator::Resource>& hardware,
+  std::vector<cmCTestBinPackerAllocation>& allocations);
+
+#endif