cmCTestBinPacker.cxx 7.07 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* 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:
 *
26
 * 1) Determine if a test's resource requirements can fit within the resources
27
28
29
30
31
32
33
34
35
36
 *    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>
37
38
39
static bool AllocateCTestResources(
  const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
  const std::vector<std::string>& resourcesSorted, std::size_t currentIndex,
40
41
42
  std::vector<cmCTestBinPackerAllocation*>& allocations)
{
  // Iterate through all large enough resources until we find a solution
43
44
45
  std::size_t resourceIndex = 0;
  while (resourceIndex < resourcesSorted.size()) {
    auto const& resource = resources.at(resourcesSorted[resourceIndex]);
46
47
48
    if (resource.Free() >=
        static_cast<unsigned int>(allocations[currentIndex]->SlotsNeeded)) {
      // Preemptively allocate the resource
49
      allocations[currentIndex]->Id = resourcesSorted[resourceIndex];
50
51
52
53
54
55
      if (currentIndex + 1 >= allocations.size()) {
        // We have a solution
        return true;
      }

      // Move the resource up the list until it is sorted again
56
57
58
      auto resources2 = resources;
      auto resourcesSorted2 = resourcesSorted;
      resources2[resourcesSorted2[resourceIndex]].Locked +=
59
        allocations[currentIndex]->SlotsNeeded;
60
61
      AllocationStrategy::IncrementalSort(resources2, resourcesSorted2,
                                          resourceIndex);
62
63

      // Recurse one level deeper
64
65
      if (AllocateCTestResources<AllocationStrategy>(
            resources2, resourcesSorted2, currentIndex + 1, allocations)) {
66
67
68
69
70
71
        return true;
      }
    }

    // No solution found here, deallocate the resource and try the next one
    allocations[currentIndex]->Id.clear();
72
    auto freeSlots = resources.at(resourcesSorted.at(resourceIndex)).Free();
73
    do {
74
75
76
      ++resourceIndex;
    } while (resourceIndex < resourcesSorted.size() &&
             resources.at(resourcesSorted.at(resourceIndex)).Free() ==
77
78
79
80
81
82
83
84
               freeSlots);
  }

  // No solution was found
  return false;
}

template <typename AllocationStrategy>
85
86
static bool AllocateCTestResources(
  const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
  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
102
103
104
105
  std::vector<std::string> resourcesSorted;
  resourcesSorted.reserve(resources.size());
  for (auto const& res : resources) {
    resourcesSorted.push_back(res.first);
106
  }
107
  AllocationStrategy::InitialSort(resources, resourcesSorted);
108
109

  // Do the actual allocation
110
111
  return AllocateCTestResources<AllocationStrategy>(
    resources, resourcesSorted, std::size_t(0), allocationsPtr);
112
113
114
115
116
117
}

class RoundRobinAllocationStrategy
{
public:
  static void InitialSort(
118
119
    const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
    std::vector<std::string>& resourcesSorted);
120
121

  static void IncrementalSort(
122
123
    const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
    std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex);
124
125
126
};

void RoundRobinAllocationStrategy::InitialSort(
127
128
  const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
  std::vector<std::string>& resourcesSorted)
129
130
{
  std::stable_sort(
131
132
133
    resourcesSorted.rbegin(), resourcesSorted.rend(),
    [&resources](const std::string& id1, const std::string& id2) {
      return resources.at(id1).Free() < resources.at(id2).Free();
134
135
136
137
    });
}

void RoundRobinAllocationStrategy::IncrementalSort(
138
139
  const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
  std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex)
140
{
141
  auto tmp = resourcesSorted[lastAllocatedIndex];
142
  std::size_t i = lastAllocatedIndex;
143
144
145
146
  while (i < resourcesSorted.size() - 1 &&
         resources.at(resourcesSorted[i + 1]).Free() >
           resources.at(tmp).Free()) {
    resourcesSorted[i] = resourcesSorted[i + 1];
147
148
    ++i;
  }
149
  resourcesSorted[i] = tmp;
150
151
152
153
154
155
}

class BlockAllocationStrategy
{
public:
  static void InitialSort(
156
157
    const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
    std::vector<std::string>& resourcesSorted);
158
159

  static void IncrementalSort(
160
161
    const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
    std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex);
162
163
164
};

void BlockAllocationStrategy::InitialSort(
165
166
  const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
  std::vector<std::string>& resourcesSorted)
167
168
{
  std::stable_sort(
169
170
171
    resourcesSorted.rbegin(), resourcesSorted.rend(),
    [&resources](const std::string& id1, const std::string& id2) {
      return resources.at(id1).Free() < resources.at(id2).Free();
172
173
174
175
    });
}

void BlockAllocationStrategy::IncrementalSort(
176
177
  const std::map<std::string, cmCTestResourceAllocator::Resource>&,
  std::vector<std::string>& resourcesSorted, std::size_t lastAllocatedIndex)
178
{
179
  auto tmp = resourcesSorted[lastAllocatedIndex];
180
181
  std::size_t i = lastAllocatedIndex;
  while (i > 0) {
182
    resourcesSorted[i] = resourcesSorted[i - 1];
183
184
    --i;
  }
185
  resourcesSorted[i] = tmp;
186
187
188
}
}

189
190
bool cmAllocateCTestResourcesRoundRobin(
  const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
191
192
  std::vector<cmCTestBinPackerAllocation>& allocations)
{
193
194
  return AllocateCTestResources<RoundRobinAllocationStrategy>(resources,
                                                              allocations);
195
196
}

197
198
bool cmAllocateCTestResourcesBlock(
  const std::map<std::string, cmCTestResourceAllocator::Resource>& resources,
199
200
  std::vector<cmCTestBinPackerAllocation>& allocations)
{
201
202
  return AllocateCTestResources<BlockAllocationStrategy>(resources,
                                                         allocations);
203
}