Avoid exponential behaviour

2 files changed, 238 insertions, 6 deletions

diff --git a/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/deployment/DeploymentStatus.java b/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/deployment/DeploymentStatus.java
index ad2274c4e30..6031239e0a9 100644
--- a/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/deployment/DeploymentStatus.java
+++ b/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/deployment/DeploymentStatus.java
@@ -33,13 +33,13 @@ import com.yahoo.vespa.hosted.controller.versions.VespaVersion.Confidence;
 import java.time.Duration;
 import java.time.Instant;
 import java.time.temporal.ChronoUnit;
-import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.Iterator;
 import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Objects;
@@ -738,13 +738,15 @@ public class DeploymentStatus {
      */
     private List<JobId> prerequisiteTests(JobId prodJob, JobType testType) {
         List<JobId> tests = new ArrayList<>();
-        Deque<InstanceName> instances = new ArrayDeque<>();
+        Set<InstanceName> instances = new LinkedHashSet<>();
         instances.add(prodJob.application().instance());
         while ( ! instances.isEmpty()) {
-            InstanceName instance = instances.poll();
+            Iterator<InstanceName> iterator = instances.iterator();
+            InstanceName instance = iterator.next();
+            iterator.remove();
             Optional<JobId> test = declaredTest(application().id().instance(instance), testType);
             if (test.isPresent()) tests.add(test.get());
-            else instances.addAll(instanceSteps().get(instance).dependencies().stream().map(StepStatus::instance).toList());
+            else instanceSteps().get(instance).dependencies().stream().map(StepStatus::instance).forEach(instances::add);
         }
         if (tests.isEmpty()) tests.add(firstDeclaredOrElseImplicitTest(testType));
         return tests;
diff --git a/controller-server/src/test/java/com/yahoo/vespa/hosted/controller/deployment/DeploymentTriggerTest.java b/controller-server/src/test/java/com/yahoo/vespa/hosted/controller/deployment/DeploymentTriggerTest.java
index d5f636b5294..13540246078 100644
--- a/controller-server/src/test/java/com/yahoo/vespa/hosted/controller/deployment/DeploymentTriggerTest.java
+++ b/controller-server/src/test/java/com/yahoo/vespa/hosted/controller/deployment/DeploymentTriggerTest.java
@@ -2514,7 +2514,7 @@ public class DeploymentTriggerTest {
 
         Version version3 = new Version("6.4");
         tester.controllerTester().upgradeSystem(version3);
-        tests.runJob(systemTest)            // Success in default cloud.
+        tests.runJob(systemTest)              // Success in default cloud.
              .failDeployment(centuariTest);   // Failure in centauri cloud.
         tester.upgrader().run();
 
@@ -2897,4 +2897,234 @@ public class DeploymentTriggerTest {
         assertEquals(Change.empty(), app.instance().change());
     }
 
+    @Test
+    void miniBenchmark() {
+        String spec = """
+                      <deployment version="1.0">
+                          <parallel>
+                              <instance id="instance0">
+                                  <test tester-flavor="d-8-16-10" />
+                                  <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              </instance>
+                              <instance id="instance1">
+                                  <test tester-flavor="d-8-16-10" />
+                                  <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              </instance>
+                              <instance id="instance2">
+                                  <test tester-flavor="d-8-16-10" />
+                                  <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              </instance>
+                              <instance id="instance3">
+                                  <test tester-flavor="d-8-16-10" />
+                                  <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              </instance>
+                              <instance id="stress">
+                                  <staging />
+                                  <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              </instance>
+                          </parallel>
+                          <instance id="beta1">
+                              <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              <block-change version="true" revision="false" days="sat" hours="0-23" time-zone="UTC" />
+                              <upgrade revision-change='when-clear' rollout='separate' revision-target='next' policy='conservative'/>
+                              <prod>
+                                  <parallel>
+                                      <steps>
+                                          <region>us-east-3</region>
+                                          <test>us-east-3</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-west-1</region>
+                                          <test>us-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>eu-west-1</region>
+                                          <test>eu-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-central-1</region>
+                                          <test>us-central-1</test>
+                                      </steps>
+                                  </parallel>
+                              </prod>
+                          </instance>
+                          <instance id="gamma5">
+                              <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              <block-change version="true" revision="false" days="sat" hours="0-23" time-zone="UTC" />
+                              <upgrade revision-change='when-clear' rollout='separate' revision-target='next' policy='conservative'/>
+                              <prod>
+                                  <parallel>
+                                      <steps>
+                                          <region>us-east-3</region>
+                                          <test>us-east-3</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-west-1</region>
+                                          <test>us-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>eu-west-1</region>
+                                          <test>eu-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-central-1</region>
+                                          <test>us-central-1</test>
+                                      </steps>
+                                  </parallel>
+                              </prod>
+                          </instance>
+                          <instance id="delta21">
+                              <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              <block-change version="true" revision="false" days="sat" hours="0-23" time-zone="UTC" />
+                              <upgrade revision-change='when-clear' rollout='separate' revision-target='next' policy='conservative'/>
+                              <prod>
+                                  <parallel>
+                                      <steps>
+                                          <region>us-east-3</region>
+                                          <test>us-east-3</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-west-1</region>
+                                          <test>us-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>eu-west-1</region>
+                                          <test>eu-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-central-1</region>
+                                          <test>us-central-1</test>
+                                      </steps>
+                                  </parallel>
+                              </prod>
+                          </instance>
+                          <instance id="prod21a">
+                              <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              <block-change version="true" revision="false" days="sat" hours="0-23" time-zone="UTC" />
+                              <upgrade revision-change='when-clear' rollout='separate' revision-target='next' policy='conservative'/>
+                              <prod>
+                                  <parallel>
+                                      <steps>
+                                          <region>us-east-3</region>
+                                          <test>us-east-3</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-west-1</region>
+                                          <test>us-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>eu-west-1</region>
+                                          <test>eu-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-central-1</region>
+                                          <test>us-central-1</test>
+                                      </steps>
+                                  </parallel>
+                              </prod>
+                          </instance>
+                          <instance id="prod21b">
+                              <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              <block-change version="true" revision="false" days="sat" hours="0-23" time-zone="UTC" />
+                              <upgrade revision-change='when-clear' rollout='separate' revision-target='next' policy='conservative'/>
+                              <prod>
+                                  <parallel>
+                                      <steps>
+                                          <region>us-east-3</region>
+                                          <test>us-east-3</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-west-1</region>
+                                          <test>us-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>eu-west-1</region>
+                                          <test>eu-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-central-1</region>
+                                          <test>us-central-1</test>
+                                      </steps>
+                                  </parallel>
+                              </prod>
+                          </instance>
+                          <instance id="prod21c">
+                              <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              <block-change version="true" revision="false" days="sat" hours="0-23" time-zone="UTC" />
+                              <upgrade revision-change='when-clear' rollout='separate' revision-target='next' policy='conservative'/>
+                              <prod>
+                                  <parallel>
+                                      <steps>
+                                          <region>us-east-3</region>
+                                          <test>us-east-3</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-west-1</region>
+                                          <test>us-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>eu-west-1</region>
+                                          <test>eu-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-central-1</region>
+                                          <test>us-central-1</test>
+                                      </steps>
+                                  </parallel>
+                              </prod>
+                          </instance>
+                          <instance id="cd10">
+                              <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              <block-change version="true" revision="false" days="sat" hours="0-23" time-zone="UTC" />
+                              <upgrade revision-change='when-clear' rollout='separate' revision-target='next' policy='conservative'/>
+                              <prod>
+                                  <parallel>
+                                      <steps>
+                                          <region>us-east-3</region>
+                                          <test>us-east-3</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-west-1</region>
+                                          <test>us-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>eu-west-1</region>
+                                          <test>eu-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-central-1</region>
+                                          <test>us-central-1</test>
+                                      </steps>
+                                  </parallel>
+                              </prod>
+                          </instance>
+                          <instance id="prod1">
+                              <block-change version="true" revision="false" days="mon-fri,sun" hours="4-23" time-zone="UTC" />
+                              <block-change version="true" revision="false" days="sat" hours="0-23" time-zone="UTC" />
+                              <upgrade revision-change='when-clear' rollout='separate' revision-target='next' policy='conservative'/>
+                              <prod>
+                                  <parallel>
+                                      <steps>
+                                          <region>us-east-3</region>
+                                          <test>us-east-3</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-west-1</region>
+                                          <test>us-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>eu-west-1</region>
+                                          <test>eu-west-1</test>
+                                      </steps>
+                                      <steps>
+                                          <region>us-central-1</region>
+                                          <test>us-central-1</test>
+                                      </steps>
+                                  </parallel>
+                              </prod>
+                          </instance>
+                      </deployment>""";
+        tester.newDeploymentContext("t", "a", "prod1").submit(ApplicationPackageBuilder.fromDeploymentXml(spec)).deploy();
+    }
+
 }