From 142edf8ad4baccd991a6a8a3e5283d0b575acca2 Mon Sep 17 00:00:00 2001
From: Zach Mullen <zach.mullen@kitware.com>
Date: Thu, 1 Jul 2010 14:10:49 -0400
Subject: More robust cost-based scheduling impl

---
 Source/CTest/cmCTestMultiProcessHandler.cxx | 114 ++++++++++++++--------------
 Source/CTest/cmCTestMultiProcessHandler.h   |   5 +-
 2 files changed, 60 insertions(+), 59 deletions(-)

diff --git a/Source/CTest/cmCTestMultiProcessHandler.cxx b/Source/CTest/cmCTestMultiProcessHandler.cxx
index 4d39367..2d3853b 100644
--- a/Source/CTest/cmCTestMultiProcessHandler.cxx
+++ b/Source/CTest/cmCTestMultiProcessHandler.cxx
@@ -18,6 +18,23 @@
 #include <stack>
 #include <float.h>
 
+class TestComparator
+{
+public:
+  TestComparator(cmCTestMultiProcessHandler* handler) : Handler(handler) {}
+  ~TestComparator() {}
+
+  // Sorts tests in descending order of cost
+  bool operator() (int index1, int index2) const
+    {
+    return Handler->Properties[index1]->Cost >
+      Handler->Properties[index2]->Cost;
+    }
+
+private:
+  cmCTestMultiProcessHandler* Handler;
+};
+
 cmCTestMultiProcessHandler::cmCTestMultiProcessHandler()
 {
   this->ParallelLevel = 1;
@@ -154,15 +171,8 @@ void cmCTestMultiProcessHandler::UnlockResources(int index)
 void cmCTestMultiProcessHandler::EraseTest(int test)
 {
   this->Tests.erase(test);
-  for(TestCostMap::iterator i = this->TestCosts.begin();
-      i != this->TestCosts.end(); ++i)
-    {
-    if(i->second.find(test) != i->second.end())
-      {
-      i->second.erase(test);
-      return;
-      }
-    }
+  this->SortedTests.erase(
+    std::find(this->SortedTests.begin(), this->SortedTests.end(), test));
 }
 
 //---------------------------------------------------------
@@ -244,41 +254,36 @@ void cmCTestMultiProcessHandler::StartNextTests()
     return;
     }
 
-  for(TestCostMap::reverse_iterator i = this->TestCosts.rbegin();
-      i != this->TestCosts.rend(); ++i)
+  TestList copy = this->SortedTests;
+  for(TestList::iterator test = copy.begin(); test != copy.end(); ++test)
     {
-    TestSet tests = i->second; //copy the test set
-    for(TestSet::iterator test = tests.begin();
-        test != tests.end(); ++test)
+    //in case this test has already been started due to dependency
+    if(this->TestRunningMap[*test] || this->TestFinishMap[*test])
       {
-      //in case this test has already been started due to dependency
-      if(this->TestRunningMap[*test] || this->TestFinishMap[*test])
-        {
-        continue;
-        }
-      size_t processors = GetProcessorsUsed(*test);
-      if(processors > numToStart)
-        {
-        return;
-        }
-      if(this->StartTest(*test))
-        {
-        if(this->StopTimePassed)
-          {
-          return;
-          }
-        numToStart -= processors;
-        }
-      else
-        {
-        cmCTestLog(this->CTest, HANDLER_VERBOSE_OUTPUT, std::endl
-                   << "Test did not start waiting on depends to finish: "
-                   << *test << "\n");
-        }
-      if(numToStart == 0)
+      continue;
+      }
+    size_t processors = GetProcessorsUsed(*test);
+    if(processors > numToStart)
+      {
+      return;
+      }
+    if(this->StartTest(*test))
+      {
+      if(this->StopTimePassed)
         {
         return;
         }
+      numToStart -= processors;
+      }
+    else
+      {
+      cmCTestLog(this->CTest, HANDLER_VERBOSE_OUTPUT, std::endl
+                 << "Test did not start waiting on depends to finish: "
+                 << *test << "\n");
+      }
+    if(numToStart == 0)
+      {
+      return;
       }
     }
 }
@@ -468,27 +473,22 @@ void cmCTestMultiProcessHandler::CreateTestCostList()
   for(TestMap::iterator i = this->Tests.begin();
       i != this->Tests.end(); ++i)
     {
-    //We only want to schedule them by cost in a parallel situation
-    if(this->ParallelLevel > 1)
-      {
-      std::string name = this->Properties[i->first]->Name;
-      if(std::find(this->LastTestsFailed.begin(), this->LastTestsFailed.end(),
-         name) != this->LastTestsFailed.end())
-        {
-        this->TestCosts[FLT_MAX].insert(i->first);
-        }
-      else
-        {
-        this->TestCosts[this->Properties[i->first]->Cost].insert(i->first);
-        }
-      }
-    else //we ignore their cost
+    SortedTests.push_back(i->first);
+
+    //If the test failed last time, it should be run first, so max the cost
+    if(std::find(this->LastTestsFailed.begin(),
+                 this->LastTestsFailed.end(),
+                 this->Properties[i->first]->Name)
+       != this->LastTestsFailed.end())
       {
-      size_t index = this->Tests.size()
-        - static_cast<size_t>(this->Properties[i->first]->Index);
-      this->TestCosts[index].insert(i->first);
+      this->Properties[i->first]->Cost = FLT_MAX;
       }
     }
+  if(this->ParallelLevel > 1)
+    {
+    TestComparator comp(this);
+    std::sort(SortedTests.begin(), SortedTests.end(), comp);
+    }
 }
 
 //---------------------------------------------------------
diff --git a/Source/CTest/cmCTestMultiProcessHandler.h b/Source/CTest/cmCTestMultiProcessHandler.h
index 4f51b0b..cc330f7 100644
--- a/Source/CTest/cmCTestMultiProcessHandler.h
+++ b/Source/CTest/cmCTestMultiProcessHandler.h
@@ -23,10 +23,11 @@
  */
 class cmCTestMultiProcessHandler 
 {
+  friend class TestComparator;
 public:
   struct TestSet : public std::set<int> {};
   struct TestMap : public std::map<int, TestSet> {};
-  struct TestCostMap : public std::map<float, TestSet> {};
+  struct TestList : public std::vector<int> {};
   struct PropertiesMap : public 
      std::map<int, cmCTestTestHandler::cmCTestTestProperties*> {};
 
@@ -88,7 +89,7 @@ protected:
   void UnlockResources(int index);
   // map from test number to set of depend tests
   TestMap Tests;
-  TestCostMap TestCosts;
+  TestList SortedTests;
   //Total number of tests we'll be running
   size_t Total;
   //Number of tests that are complete
-- 
cgit v0.12