[testsharder] distribute tests evenly amongst shards
E.g. sharding (1,2,3,4,5) with max size 4 would result in:
Before:
(1,2,3,4), (5)
After:
(1,2,3), (4,5)
Bug: IN-1433
Change-Id: I042630ba46d3c63eaaea00eab9b9603029478525
diff --git a/testsharder/shard.go b/testsharder/shard.go
index b5c71b2..64ff3ae 100644
--- a/testsharder/shard.go
+++ b/testsharder/shard.go
@@ -105,6 +105,14 @@
return b
}
+func divRoundUp(a, b int) int {
+ if a % b == 0 {
+ return a / b
+ } else {
+ return (a / b) + 1
+ }
+}
+
// WithMaxSize returns a list of shards such that each shard contains fewer than maxShardSize tests.
// If maxShardSize <= 0, just returns its input.
func WithMaxSize(shards []*Shard, maxShardSize int) []*Shard {
@@ -113,11 +121,18 @@
}
output := make([]*Shard, 0, len(shards))
for _, shard := range shards {
- for i := 0; i*maxShardSize < len(shard.Tests); i++ {
- sliceStart := i * maxShardSize
- sliceLimit := min((i+1)*maxShardSize, len(shard.Tests))
+ numNewShards := divRoundUp(len(shard.Tests), maxShardSize)
+ // Evenly distribute the tests between the new shards.
+ maxTestsPerNewShard := divRoundUp(len(shard.Tests), numNewShards)
+ for i := 0; i < numNewShards; i++ {
+ sliceStart := i * maxTestsPerNewShard
+ sliceLimit := min((i+1)*maxTestsPerNewShard, len(shard.Tests))
+ newName := shard.Name
+ if numNewShards > 1 {
+ newName = fmt.Sprintf("%s-(%d)", shard.Name, i+1)
+ }
output = append(output, &Shard{
- Name: fmt.Sprintf("%s-(%d)", shard.Name, i),
+ Name: newName,
Tests: shard.Tests[sliceStart:sliceLimit],
Env: shard.Env,
})
diff --git a/testsharder/shard_test.go b/testsharder/shard_test.go
index eea167c..9c5545e 100644
--- a/testsharder/shard_test.go
+++ b/testsharder/shard_test.go
@@ -279,6 +279,13 @@
})
}
+func max(a, b int) int {
+ if a > b {
+ return a
+ }
+ return b
+}
+
func TestWithMaxSize(t *testing.T) {
env1 := Environment{
Tags: []string{"env1"},
@@ -301,22 +308,29 @@
}
}
}
- t.Run("max is larger than all shards", func(t *testing.T) {
- maxSize := len(input[0].Tests)+len(input[1].Tests)
+ t.Run("max is larger greater or equal to all shards", func(t *testing.T) {
+ maxSize := max(len(input[0].Tests), len(input[1].Tests))
actual := WithMaxSize(input, maxSize)
- assertEqual(t, []*Shard{
- // Returns equivalent shards, but renamed.
- namedShard(env1, "env1-(0)", 1, 2, 3, 4, 5), namedShard(env2, "env2-(0)", 6, 7, 8)},
- actual)
- assertShardsLessThanSize(t, actual, maxSize)
+ assertEqual(t, input, actual)
+ assertShardsLessThanSize(t, actual, maxSize)
})
+
t.Run("applies max", func(t *testing.T) {
maxSize := 2
actual := WithMaxSize(input, maxSize)
assertEqual(t, []*Shard{
- namedShard(env1, "env1-(0)", 1, 2), namedShard(env1, "env1-(1)", 3, 4),
- namedShard(env1, "env1-(2)", 5),
- namedShard(env2, "env2-(0)", 6, 7), namedShard(env2, "env2-(1)", 8)},
+ namedShard(env1, "env1-(1)", 1, 2), namedShard(env1, "env1-(2)", 3, 4),
+ namedShard(env1, "env1-(3)", 5),
+ namedShard(env2, "env2-(1)", 6, 7), namedShard(env2, "env2-(2)", 8)},
+ actual)
+ assertShardsLessThanSize(t, actual, maxSize)
+ })
+ t.Run("evenly distributes tests", func(t *testing.T) {
+ maxSize := 4
+ actual := WithMaxSize(input, maxSize)
+ assertEqual(t, []*Shard{
+ namedShard(env1, "env1-(1)", 1, 2, 3), namedShard(env1, "env1-(2)", 4, 5),
+ namedShard(env2, "env2", 6, 7, 8)},
actual)
assertShardsLessThanSize(t, actual, maxSize)
})
