Skip to content

Commit

Permalink
[JENKINS-27395] Add per-stage test splitting option
Browse files Browse the repository at this point in the history
  • Loading branch information
@abayer
abayer committed Oct 17, 2017
1 parent 3961df3 commit 7d09e31
Show file tree
Hide file tree
Showing 6 changed files with 219 additions and 72 deletions.
49 changes: 36 additions & 13 deletions pom.xml
View file
Expand Up @@ -3,7 +3,7 @@
<parent>
<groupId>org.jenkins-ci.plugins</groupId>
<artifactId>plugin</artifactId>
<version>2.15</version>
<version>2.36</version>
<relativePath />
</parent>
<artifactId>parallel-test-executor</artifactId>
Expand All @@ -18,7 +18,7 @@
</license>
</licenses>
<properties>
<jenkins.version>1.642.3</jenkins.version>
<jenkins.version>2.7.3</jenkins.version>
</properties>
<repositories>
<repository>
Expand All @@ -42,12 +42,18 @@
<dependency>
<groupId>org.jenkins-ci.plugins</groupId>
<artifactId>parameterized-trigger</artifactId>
<version>2.18</version>
<version>2.33</version>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins</groupId>
<artifactId>matrix-project</artifactId>
<version>1.7.1</version>
<scope>test</scope>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins</groupId>
<artifactId>junit</artifactId>
<version>1.15</version>
<version>1.22-beta-1</version><!-- TODO: Switch to 1.22 post-beta -->
</dependency>
<dependency>
<groupId>org.mockito</groupId>
Expand All @@ -64,41 +70,58 @@
<dependency>
<groupId>org.jenkins-ci.plugins.workflow</groupId>
<artifactId>workflow-step-api</artifactId>
<version>2.3</version>
<version>2.12</version>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins</groupId>
<artifactId>script-security</artifactId>
<version>1.21</version>
<version>1.30</version>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins</groupId>
<artifactId>variant</artifactId>
<version>1.1</version>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins.workflow</groupId>
<artifactId>workflow-cps</artifactId>
<version>2.10</version>
<scope>test</scope>
<version>2.37</version>
<optional>true</optional>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins.workflow</groupId>
<artifactId>workflow-api</artifactId>
<version>2.22</version>
<optional>true</optional>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins.workflow</groupId>
<artifactId>workflow-job</artifactId>
<version>2.3</version>
<scope>test</scope>
<version>2.11.1</version>
<optional>true</optional>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins</groupId>
<artifactId>pipeline-stage-step</artifactId>
<version>2.2</version>
<optional>true</optional>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins.workflow</groupId>
<artifactId>workflow-durable-task-step</artifactId>
<version>2.3</version>
<version>2.13</version>
<scope>test</scope>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins.workflow</groupId>
<artifactId>workflow-basic-steps</artifactId>
<version>2.1</version>
<version>2.6</version>
<scope>test</scope>
</dependency>
<dependency>
<groupId>org.jenkins-ci.plugins.workflow</groupId>
<artifactId>workflow-cps</artifactId>
<version>2.10</version>
<version>2.37</version>
<classifier>tests</classifier>
<scope>test</scope>
</dependency>
Expand Down
114 changes: 59 additions & 55 deletions src/main/java/org/jenkinsci/plugins/parallel_test_executor/ParallelTestExecutor.java
View file
Expand Up @@ -122,7 +122,8 @@ public boolean perform(AbstractBuild<?, ?> build, Launcher launcher, BuildListen
}
FilePath dir = workspace.child("test-splits");
dir.deleteRecursive();
List<InclusionExclusionPattern> splits = findTestSplits(parallelism, build, listener, includesPatternFile != null);
List<InclusionExclusionPattern> splits = findTestSplits(parallelism, build, listener, includesPatternFile != null,
null);
for (int i = 0; i < splits.size(); i++) {
InclusionExclusionPattern pattern = splits.get(i);
try (OutputStream os = dir.child("split." + i + "." + (pattern.isIncludes() ? "include" : "exclude") + ".txt").write();
Expand All @@ -143,70 +144,73 @@ public boolean perform(AbstractBuild<?, ?> build, Launcher launcher, BuildListen
return true;
}

static List<InclusionExclusionPattern> findTestSplits(Parallelism parallelism, Run<?,?> build, TaskListener listener, boolean generateInclusions) {
static List<InclusionExclusionPattern> findTestSplits(Parallelism parallelism, Run<?,?> build, TaskListener listener,
boolean generateInclusions,
@CheckForNull final PreviousTestResultLookup lookup) {
TestResult tr = findPreviousTestResult(build, listener);
if (tr == null) {
listener.getLogger().println("No record available, so executing everything in one place");
return Collections.singletonList(new InclusionExclusionPattern(Collections.<String>emptyList(), false));
} else {

Map<String/*fully qualified class name*/, TestClass> data = new TreeMap<>();
collect(tr, data);

// sort in the descending order of the duration
List<TestClass> sorted = new ArrayList<>(data.values());
Collections.sort(sorted);

// degree of the parallelism. we need minimum 1
final int n = Math.max(1, parallelism.calculate(sorted));
} else if (lookup != null) {
tr = lookup.lookupTestResult(tr);
}

List<Knapsack> knapsacks = new ArrayList<>(n);
for (int i = 0; i < n; i++)
knapsacks.add(new Knapsack());
Map<String/*fully qualified class name*/, TestClass> data = new TreeMap<>();
collect(tr, data);

// sort in the descending order of the duration
List<TestClass> sorted = new ArrayList<>(data.values());
Collections.sort(sorted);

// degree of the parallelism. we need minimum 1
final int n = Math.max(1, parallelism.calculate(sorted));

List<Knapsack> knapsacks = new ArrayList<>(n);
for (int i = 0; i < n; i++)
knapsacks.add(new Knapsack());

/*
This packing problem is a NP-complete problem, so we solve
this simply by a greedy algorithm. We pack heavier items first,
and the result should be of roughly equal size
*/
PriorityQueue<Knapsack> q = new PriorityQueue<>(knapsacks);
for (TestClass d : sorted) {
Knapsack k = q.poll();
k.add(d);
q.add(k);
}

/*
This packing problem is a NP-complete problem, so we solve
this simply by a greedy algorithm. We pack heavier items first,
and the result should be of roughly equal size
*/
PriorityQueue<Knapsack> q = new PriorityQueue<>(knapsacks);
long total = 0, min = Long.MAX_VALUE, max = Long.MIN_VALUE;
for (Knapsack k : knapsacks) {
total += k.total;
max = Math.max(max, k.total);
min = Math.min(min, k.total);
}
long average = total / n;
long variance = 0;
for (Knapsack k : knapsacks) {
variance += pow(k.total - average);
}
variance /= n;
long stddev = (long) Math.sqrt(variance);
listener.getLogger().printf("%d test classes (%dms) divided into %d sets. Min=%dms, Average=%dms, Max=%dms, stddev=%dms%n",
data.size(), total, n, min, average, max, stddev);

List<InclusionExclusionPattern> r = new ArrayList<>();
for (int i = 0; i < n; i++) {
Knapsack k = knapsacks.get(i);
boolean shouldIncludeElements = generateInclusions && i != 0;
List<String> elements = new ArrayList<>();
r.add(new InclusionExclusionPattern(elements, shouldIncludeElements));
for (TestClass d : sorted) {
Knapsack k = q.poll();
k.add(d);
q.add(k);
}

long total = 0, min = Long.MAX_VALUE, max = Long.MIN_VALUE;
for (Knapsack k : knapsacks) {
total += k.total;
max = Math.max(max, k.total);
min = Math.min(min, k.total);
}
long average = total / n;
long variance = 0;
for (Knapsack k : knapsacks) {
variance += pow(k.total - average);
}
variance /= n;
long stddev = (long) Math.sqrt(variance);
listener.getLogger().printf("%d test classes (%dms) divided into %d sets. Min=%dms, Average=%dms, Max=%dms, stddev=%dms%n",
data.size(), total, n, min, average, max, stddev);

List<InclusionExclusionPattern> r = new ArrayList<>();
for (int i = 0; i < n; i++) {
Knapsack k = knapsacks.get(i);
boolean shouldIncludeElements = generateInclusions && i != 0;
List<String> elements = new ArrayList<>();
r.add(new InclusionExclusionPattern(elements, shouldIncludeElements));
for (TestClass d : sorted) {
if (shouldIncludeElements == (d.knapsack == k)) {
elements.add(d.getSourceFileName(".java"));
elements.add(d.getSourceFileName(".class"));
}
if (shouldIncludeElements == (d.knapsack == k)) {
elements.add(d.getSourceFileName(".java"));
elements.add(d.getSourceFileName(".class"));
}
}
return r;
}
return r;
}

/**
Expand Down
61 changes: 61 additions & 0 deletions src/main/java/org/jenkinsci/plugins/parallel_test_executor/PreviousTestResultLookup.java
View file
@@ -0,0 +1,61 @@
package org.jenkinsci.plugins.parallel_test_executor;

import com.google.common.base.Predicate;
import hudson.ExtensionPoint;
import hudson.model.Run;
import hudson.tasks.test.TestResult;
import org.jenkinsci.plugins.variant.OptionalExtension;
import org.jenkinsci.plugins.workflow.cps.nodes.StepStartNode;
import org.jenkinsci.plugins.workflow.flow.FlowExecution;
import org.jenkinsci.plugins.workflow.graph.FlowNode;
import org.jenkinsci.plugins.workflow.graphanalysis.DepthFirstScanner;
import org.jenkinsci.plugins.workflow.job.WorkflowRun;
import org.jenkinsci.plugins.workflow.support.steps.StageStep;

import javax.annotation.CheckForNull;
import javax.annotation.Nonnull;
import javax.annotation.Nullable;

public abstract class PreviousTestResultLookup implements ExtensionPoint {
public abstract TestResult lookupTestResult(@Nonnull TestResult result);

@OptionalExtension(requirePlugins = {"pipeline-stage-step","workflow-cps","workflow-job"})
public static class LookupInStage extends PreviousTestResultLookup {
@CheckForNull
private String stageName;

public LookupInStage() {

}

public LookupInStage(String stageName) {
this.stageName = stageName;
}

@Override
public TestResult lookupTestResult(@Nonnull TestResult result) {
Run<?,?> r = result.getRun();
if (r instanceof WorkflowRun && stageName != null) {
FlowExecution execution = ((WorkflowRun) r).getExecution();
if (execution != null) {
DepthFirstScanner scanner = new DepthFirstScanner();
FlowNode stageId = scanner.findFirstMatch(execution, new Predicate<FlowNode>() {
@Override
public boolean apply(@Nullable FlowNode input) {
return input instanceof StepStartNode &&
((StepStartNode) input).getDescriptor() instanceof StageStep.DescriptorImpl &&
input.getDisplayName().equals(stageName);
}
});
if (stageId != null) {
return ((hudson.tasks.junit.TestResult) result).getResultForPipelineBlock(r.getExternalizableId(),
stageId.getId());
}

}
}

return result;
}
}
}
17 changes: 15 additions & 2 deletions src/main/java/org/jenkinsci/plugins/parallel_test_executor/SplitStep.java
View file
Expand Up @@ -24,6 +24,8 @@ public final class SplitStep extends AbstractStepImpl {

private boolean generateInclusions;

private String stage;

@DataBoundConstructor public SplitStep(Parallelism parallelism) {
this.parallelism = parallelism;
}
Expand All @@ -39,6 +41,15 @@ public void setGenerateInclusions(boolean generateInclusions) {
this.generateInclusions = generateInclusions;
}

public String getStage() {
return stage;
}

@DataBoundSetter
public void setStage(String stage) {
this.stage = stage;
}

@Extension public static final class DescriptorImpl extends AbstractStepDescriptorImpl {

public DescriptorImpl() {
Expand All @@ -65,10 +76,12 @@ public static final class Execution extends AbstractSynchronousStepExecution<Lis

@Override protected List<?> run() throws Exception {
if (step.generateInclusions) {
return ParallelTestExecutor.findTestSplits(step.parallelism, build, listener, step.generateInclusions);
return ParallelTestExecutor.findTestSplits(step.parallelism, build, listener, step.generateInclusions,
new PreviousTestResultLookup.LookupInStage(step.stage));
} else {
List<List<String>> result = new ArrayList<>();
for (InclusionExclusionPattern pattern : ParallelTestExecutor.findTestSplits(step.parallelism, build, listener, step.generateInclusions)) {
for (InclusionExclusionPattern pattern : ParallelTestExecutor.findTestSplits(step.parallelism, build, listener,
step.generateInclusions, new PreviousTestResultLookup.LookupInStage(step.stage))) {
result.add(pattern.getList());
}
return result;
Expand Down

0 comments on commit 7d09e31

Please sign in to comment.