1
17
18 package wrr
19
20 import (
21 "errors"
22 "math"
23 "math/rand"
24 "strconv"
25 "testing"
26
27 "github.com/google/go-cmp/cmp"
28 "google.golang.org/grpc/internal/grpctest"
29 )
30
31 type s struct {
32 grpctest.Tester
33 }
34
35 func Test(t *testing.T) {
36 grpctest.RunSubTests(t, s{})
37 }
38
39 const iterCount = 10000
40
41 func equalApproximate(a, b float64) error {
42 opt := cmp.Comparer(func(x, y float64) bool {
43 delta := math.Abs(x - y)
44 mean := math.Abs(x+y) / 2.0
45 return delta/mean < 0.05
46 })
47 if !cmp.Equal(a, b, opt) {
48 return errors.New(cmp.Diff(a, b))
49 }
50 return nil
51 }
52
53 func testWRRNext(t *testing.T, newWRR func() WRR) {
54 tests := []struct {
55 name string
56 weights []int64
57 }{
58 {
59 name: "1-1-1",
60 weights: []int64{1, 1, 1},
61 },
62 {
63 name: "1-2-3",
64 weights: []int64{1, 2, 3},
65 },
66 {
67 name: "5-3-2",
68 weights: []int64{5, 3, 2},
69 },
70 {
71 name: "17-23-37",
72 weights: []int64{17, 23, 37},
73 },
74 {
75 name: "no items",
76 weights: []int64{},
77 },
78 }
79 for _, tt := range tests {
80 t.Run(tt.name, func(t *testing.T) {
81 w := newWRR()
82 if len(tt.weights) == 0 {
83 if next := w.Next(); next != nil {
84 t.Fatalf("w.Next returns non nil value:%v when there is no item", next)
85 }
86 return
87 }
88
89 var sumOfWeights int64
90 for i, weight := range tt.weights {
91 w.Add(i, weight)
92 sumOfWeights += weight
93 }
94
95 results := make(map[int]int)
96 for i := 0; i < iterCount; i++ {
97 results[w.Next().(int)]++
98 }
99
100 wantRatio := make([]float64, len(tt.weights))
101 for i, weight := range tt.weights {
102 wantRatio[i] = float64(weight) / float64(sumOfWeights)
103 }
104 gotRatio := make([]float64, len(tt.weights))
105 for i, count := range results {
106 gotRatio[i] = float64(count) / iterCount
107 }
108
109 for i := range wantRatio {
110 if err := equalApproximate(gotRatio[i], wantRatio[i]); err != nil {
111 t.Errorf("%v not equal %v", i, err)
112 }
113 }
114 })
115 }
116 }
117
118 func (s) TestRandomWRRNext(t *testing.T) {
119 testWRRNext(t, NewRandom)
120 }
121
122 func (s) TestEdfWrrNext(t *testing.T) {
123 testWRRNext(t, NewEDF)
124 }
125
126 func BenchmarkRandomWRRNext(b *testing.B) {
127 for _, n := range []int{100, 500, 1000} {
128 b.Run("equal-weights-"+strconv.Itoa(n)+"-items", func(b *testing.B) {
129 w := NewRandom()
130 sumOfWeights := n
131 for i := 0; i < n; i++ {
132 w.Add(i, 1)
133 }
134 b.ResetTimer()
135 for i := 0; i < b.N; i++ {
136 for i := 0; i < sumOfWeights; i++ {
137 w.Next()
138 }
139 }
140 })
141 }
142
143 var maxWeight int64 = 1024
144 for _, n := range []int{100, 500, 1000} {
145 b.Run("random-weights-"+strconv.Itoa(n)+"-items", func(b *testing.B) {
146 w := NewRandom()
147 var sumOfWeights int64
148 for i := 0; i < n; i++ {
149 weight := rand.Int63n(maxWeight + 1)
150 w.Add(i, weight)
151 sumOfWeights += weight
152 }
153 b.ResetTimer()
154 for i := 0; i < b.N; i++ {
155 for i := 0; i < int(sumOfWeights); i++ {
156 w.Next()
157 }
158 }
159 })
160 }
161
162 itemsNum := 200
163 heavyWeight := int64(itemsNum)
164 lightWeight := int64(1)
165 heavyIndices := []int{0, itemsNum / 2, itemsNum - 1}
166 for _, heavyIndex := range heavyIndices {
167 b.Run("skew-weights-heavy-index-"+strconv.Itoa(heavyIndex), func(b *testing.B) {
168 w := NewRandom()
169 var sumOfWeights int64
170 for i := 0; i < itemsNum; i++ {
171 var weight int64
172 if i == heavyIndex {
173 weight = heavyWeight
174 } else {
175 weight = lightWeight
176 }
177 sumOfWeights += weight
178 w.Add(i, weight)
179 }
180 b.ResetTimer()
181 for i := 0; i < b.N; i++ {
182 for i := 0; i < int(sumOfWeights); i++ {
183 w.Next()
184 }
185 }
186 })
187 }
188 }
189
190 func init() {
191 r := rand.New(rand.NewSource(0))
192 grpcrandInt63n = r.Int63n
193 }
194
View as plain text