Debian Codegraph @

pkg/util/flowcontrol/conc_alloc_test.go

raw
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 }