| 1 |
/* |
| 2 |
Copyright 2022 The Kubernetes Authors. |
| 3 |
|
| 4 |
Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 |
you may not use this file except in compliance with the License. |
| 6 |
You may obtain a copy of the License at |
| 7 |
|
| 8 |
http://www.apache.org/licenses/LICENSE-2.0 |
| 9 |
|
| 10 |
Unless required by applicable law or agreed to in writing, software |
| 11 |
distributed under the License is distributed on an "AS IS" BASIS, |
| 12 |
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 |
See the License for the specific language governing permissions and |
| 14 |
limitations under the License. |
| 15 |
*/ |
| 16 |
|
| 17 |
package flowcontrol |
| 18 |
|
| 19 |
import ( |
| 20 |
"math" |
| 21 |
"math/rand" |
| 22 |
"sort" |
| 23 |
"testing" |
| 24 |
) |
| 25 |
|
| 26 |
// floating-point imprecision |
| 27 |
const fpSlack = 1e-10 |
| 28 |
|
| 29 |
// TestConcAlloc tests computeConcurrencyAllocation with a bunch of randomly generated cases. |
| 30 |
func TestConcAlloc(t *testing.T) { |
| 31 |
rands := rand.New(rand.NewSource(1234567890)) |
| 32 |
for i := 0; i < 10000; i++ { |
| 33 |
test1ConcAlloc(t, rands) |
| 34 |
} |
| 35 |
} |
| 36 |
|
| 37 |
func test1ConcAlloc(t *testing.T, rands *rand.Rand) { |
| 38 |
probLen := ([]int{0, 1, 2, 3, 4, 6, 9})[rands.Intn(7)] |
| 39 |
classes := make([]allocProblemItem, probLen) |
| 40 |
var lowSum, highSum float64 |
| 41 |
var requiredSum int |
| 42 |
var requiredSumF float64 |
| 43 |
style := "empty" |
| 44 |
if probLen > 0 { |
| 45 |
switch rands.Intn(20) { |
| 46 |
case 0: |
| 47 |
style = "bound from below" |
| 48 |
requiredSum = rands.Intn(probLen * 3) |
| 49 |
requiredSumF = float64(requiredSum) |
| 50 |
partition64(rands, probLen, requiredSumF, func(j int, x float64) { |
| 51 |
classes[j].lowerBound = x |
| 52 |
classes[j].target = x + 2*rands.Float64() |
| 53 |
classes[j].upperBound = x + 3*rands.Float64() |
| 54 |
lowSum += classes[j].lowerBound |
| 55 |
highSum += classes[j].upperBound |
| 56 |
}) |
| 57 |
case 1: |
| 58 |
style = "bound from above" |
| 59 |
requiredSum = rands.Intn(probLen*3) + 1 |
| 60 |
requiredSumF = float64(requiredSum) |
| 61 |
partition64(rands, probLen, requiredSumF, func(j int, x float64) { |
| 62 |
classes[j].upperBound = x |
| 63 |
classes[j].lowerBound = x * math.Max(0, 1.25*rands.Float64()-1) |
| 64 |
classes[j].target = classes[j].lowerBound + rands.Float64() |
| 65 |
lowSum += classes[j].lowerBound |
| 66 |
highSum += classes[j].upperBound |
| 67 |
}) |
| 68 |
default: |
| 69 |
style = "not-set-by-bounds" |
| 70 |
for j := 0; j < probLen; j++ { |
| 71 |
x := math.Max(0, rands.Float64()*5-1) |
| 72 |
classes[j].lowerBound = x |
| 73 |
classes[j].target = x + 2*rands.Float64() |
| 74 |
classes[j].upperBound = x + 3*rands.Float64() |
| 75 |
lowSum += classes[j].lowerBound |
| 76 |
highSum += classes[j].upperBound |
| 77 |
} |
| 78 |
requiredSumF = math.Round(float64(lowSum + (highSum-lowSum)*rands.Float64())) |
| 79 |
requiredSum = int(requiredSumF) |
| 80 |
} |
| 81 |
} |
| 82 |
for rands.Float64() < 0.25 { |
| 83 |
// Add a class with a target of zero |
| 84 |
classes = append(classes, allocProblemItem{target: 0, upperBound: rands.Float64() + 0.00001}) |
| 85 |
highSum += classes[probLen].upperBound |
| 86 |
if probLen > 1 { |
| 87 |
m := rands.Intn(probLen) |
| 88 |
classes[m], classes[probLen] = classes[probLen], classes[m] |
| 89 |
} |
| 90 |
probLen = len(classes) |
| 91 |
} |
| 92 |
allocs, fairProp, err := computeConcurrencyAllocation(requiredSum, classes) |
| 93 |
var actualSumF float64 |
| 94 |
for _, item := range allocs { |
| 95 |
actualSumF += item |
| 96 |
} |
| 97 |
expectErr := lowSum-requiredSumF > fpSlack || requiredSumF-highSum > fpSlack |
| 98 |
if err != nil { |
| 99 |
if expectErr { |
| 100 |
t.Logf("For requiredSum=%v, %s classes=%#+v expected error and got %#+v", requiredSum, style, classes, err) |
| 101 |
return |
| 102 |
} |
| 103 |
t.Fatalf("For requiredSum=%v, %s classes=%#+v got unexpected error %#+v", requiredSum, style, classes, err) |
| 104 |
} |
| 105 |
if expectErr { |
| 106 |
t.Fatalf("Expected error from requiredSum=%v, %s classes=%#+v but got solution %v, %v instead", requiredSum, style, classes, allocs, fairProp) |
| 107 |
} |
| 108 |
rd := f64RelDiff(requiredSumF, actualSumF) |
| 109 |
if rd > fpSlack { |
| 110 |
t.Fatalf("For requiredSum=%v, %s classes=%#+v got solution %v, %v which has sum %v", requiredSum, style, classes, allocs, fairProp, actualSumF) |
| 111 |
} |
| 112 |
for idx, item := range classes { |
| 113 |
target := math.Max(item.target, MinTarget) |
| 114 |
alloc := fairProp * target |
| 115 |
if alloc <= item.lowerBound { |
| 116 |
if allocs[idx] != item.lowerBound { |
| 117 |
t.Fatalf("For requiredSum=%v, %s classes=%#+v got solution %v, %v in which item %d should be its lower bound but is not", requiredSum, style, classes, allocs, fairProp, idx) |
| 118 |
} |
| 119 |
} else if alloc >= item.upperBound { |
| 120 |
if allocs[idx] != item.upperBound { |
| 121 |
t.Fatalf("For requiredSum=%v, %s classes=%#+v got solution %v, %v in which item %d should be its upper bound but is not", requiredSum, style, classes, allocs, fairProp, idx) |
| 122 |
} |
| 123 |
} else if f64RelDiff(alloc, allocs[idx]) > fpSlack { |
| 124 |
t.Fatalf("For requiredSum=%v, %s classes=%#+v got solution %v, %v in which item %d got alloc %v should be %v (which is proportional to its target) but is not", requiredSum, style, classes, allocs, fairProp, idx, allocs[idx], alloc) |
| 125 |
} |
| 126 |
} |
| 127 |
t.Logf("For requiredSum=%v, %s classes=%#+v got solution %v, %v", requiredSum, style, classes, allocs, fairProp) |
| 128 |
} |
| 129 |
|
| 130 |
// partition64 calls consume n times, passing ints [0,n) and floats that sum to x |
| 131 |
func partition64(rands *rand.Rand, n int, x float64, consume func(int, float64)) { |
| 132 |
if n <= 0 { |
| 133 |
return |
| 134 |
} |
| 135 |
divs := make([]float64, n-1) |
| 136 |
for idx := range divs { |
| 137 |
divs[idx] = float64(rands.Float64()) |
| 138 |
} |
| 139 |
sort.Float64s(divs) |
| 140 |
var last float64 |
| 141 |
for idx, div := range divs { |
| 142 |
div32 := float64(div) |
| 143 |
delta := div32 - last |
| 144 |
consume(idx, delta*x) |
| 145 |
last = div32 |
| 146 |
} |
| 147 |
consume(n-1, (1-last)*x) |
| 148 |
} |
| 149 |
|
| 150 |
func f64RelDiff(a, b float64) float64 { |
| 151 |
den := math.Max(math.Abs(a), math.Abs(b)) |
| 152 |
if den == 0 { |
| 153 |
return 0 |
| 154 |
} |
| 155 |
return math.Abs(a-b) / den |
| 156 |
} |