Skip to content

Commit 3328046

Browse files
mars1024MikeSpreitzer
mars1024
authored and
MikeSpreitzer
committed
shuffle sharding: add some benchmarks and tests
Signed-off-by: Bruce Ma <brucema19901024@gmail.com>
1 parent 1d30ce1 commit 3328046

File tree

2 files changed

+196
-16
lines changed

2 files changed

+196
-16
lines changed

‎staging/src/k8s.io/apiserver/pkg/util/shufflesharding/shufflesharding.go‎

Lines changed: 3 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -72,9 +72,9 @@ func DealWithValidation(hashValue uint64, numQueues, handSize int32, pick func(i
7272
return Deal(hashValue, numQueues, handSize, pick)
7373
}
7474

75-
// DealToSlices will use specific pick function to return slices of indices
75+
// DealToSlice will use specific pick function to return slices of indices
7676
// after Deal
77-
func DealToSlices(hashValue uint64, numQueues, handSize int32) ([]int32, error) {
77+
func DealToSlice(hashValue uint64, numQueues, handSize int32) ([]int32, error) {
7878
if !ValidateParameters(numQueues, handSize) {
7979
return nil, errors.New("bad parameters")
8080
}
@@ -90,9 +90,7 @@ func DealToSlices(hashValue uint64, numQueues, handSize int32) ([]int32, error)
9090
return nil
9191
}
9292

93-
if err := Deal(hashValue, numQueues, handSize, pickToSlices); err != nil {
94-
return nil, err
95-
}
93+
_ = Deal(hashValue, numQueues, handSize, pickToSlices)
9694

9795
return candidates, nil
9896
}

‎staging/src/k8s.io/apiserver/pkg/util/shufflesharding/shufflesharding_test.go‎

Lines changed: 193 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -17,18 +17,20 @@ limitations under the License.
1717
package shufflesharding
1818

1919
import (
20+
"errors"
21+
"math/rand"
2022
"testing"
2123
)
2224

2325
func TestValidateParameters(t *testing.T) {
2426
tests := []struct {
2527
name string
26-
queueSize int32
28+
numQueues int32
2729
handSize int32
2830
validated bool
2931
}{
3032
{
31-
"queueSize is < 0",
33+
"numQueues is < 0",
3234
-100,
3335
8,
3436
false,
@@ -40,7 +42,7 @@ func TestValidateParameters(t *testing.T) {
4042
false,
4143
},
4244
{
43-
"queueSize is 0",
45+
"numQueues is 0",
4446
0,
4547
8,
4648
false,
@@ -52,33 +54,33 @@ func TestValidateParameters(t *testing.T) {
5254
false,
5355
},
5456
{
55-
"handSize is greater than queueSize",
57+
"handSize is greater than numQueues",
5658
128,
5759
129,
5860
false,
5961
},
6062
{
61-
"queueSize: 128 handSize: 6",
63+
"numQueues: 128 handSize: 6",
6264
128,
6365
6,
6466
true,
6567
},
6668
{
67-
"queueSize: 1024 handSize: 6",
69+
"numQueues: 1024 handSize: 6",
6870
1024,
6971
6,
7072
true,
7173
},
7274
{
73-
"queueSize: 512 handSize: 8",
75+
"numQueues: 512 handSize: 8",
7476
512,
7577
8,
7678
false,
7779
},
7880
}
7981
for _, test := range tests {
8082
t.Run(test.name, func(t *testing.T) {
81-
if ValidateParameters(test.queueSize, test.handSize) != test.validated {
83+
if ValidateParameters(test.numQueues, test.handSize) != test.validated {
8284
t.Errorf("test case %s fails", test.name)
8385
return
8486
}
@@ -87,9 +89,189 @@ func TestValidateParameters(t *testing.T) {
8789
}
8890

8991
func BenchmarkValidateParameters(b *testing.B) {
92+
queueSize, handSize := int32(512), int32(8)
9093
for i := 0; i < b.N; i++ {
91-
//queueSize, handSize := uint32(rand.Intn(513)), uint32(rand.Intn(17))
92-
queueSize, handSize := int32(512), int32(8)
93-
ValidateParameters(queueSize, handSize)
94+
_ = ValidateParameters(queueSize, handSize)
95+
}
96+
}
97+
98+
func TestDealWithValidation(t *testing.T) {
99+
tests := []struct {
100+
name string
101+
numQueues int32
102+
handSize int32
103+
pick func(int32) error
104+
validated bool
105+
}{
106+
{
107+
"numQueues is < 0",
108+
-100,
109+
8,
110+
func(i int32) error {
111+
return nil
112+
},
113+
false,
114+
},
115+
{
116+
"handSize is < 0",
117+
128,
118+
-100,
119+
func(i int32) error {
120+
return nil
121+
},
122+
false,
123+
},
124+
{
125+
"numQueues is 0",
126+
0,
127+
8,
128+
func(i int32) error {
129+
return nil
130+
},
131+
false,
132+
},
133+
{
134+
"handSize is 0",
135+
128,
136+
0,
137+
func(i int32) error {
138+
return nil
139+
},
140+
false,
141+
},
142+
{
143+
"handSize is greater than numQueues",
144+
128,
145+
129,
146+
func(i int32) error {
147+
return nil
148+
},
149+
false,
150+
},
151+
{
152+
"numQueues: 128 handSize: 6",
153+
128,
154+
6,
155+
func(i int32) error {
156+
return nil
157+
},
158+
true,
159+
},
160+
{
161+
"numQueues: 1024 handSize: 6",
162+
1024,
163+
6,
164+
func(i int32) error {
165+
return nil
166+
},
167+
true,
168+
},
169+
{
170+
"numQueues: 128 handSize: 6 with bad pick",
171+
128,
172+
6,
173+
func(i int32) error {
174+
return errors.New("for test")
175+
},
176+
false,
177+
},
178+
{
179+
"numQueues: 512 handSize: 8",
180+
512,
181+
8,
182+
func(i int32) error {
183+
return nil
184+
},
185+
false,
186+
},
187+
}
188+
for _, test := range tests {
189+
t.Run(test.name, func(t *testing.T) {
190+
if (DealWithValidation(rand.Uint64(), test.numQueues, test.handSize, test.pick) == nil) != test.validated {
191+
t.Errorf("test case %s fails", test.name)
192+
return
193+
}
194+
})
195+
}
196+
}
197+
198+
func BenchmarkDeal(b *testing.B) {
199+
hashValue := rand.Uint64()
200+
queueSize, handSize := int32(512), int32(8)
201+
pick := func(int32) error {
202+
return nil
203+
}
204+
for i := 0; i < b.N; i++ {
205+
_ = Deal(hashValue, queueSize, handSize, pick)
206+
}
207+
}
208+
209+
func TestDealToSlices(t *testing.T) {
210+
tests := []struct {
211+
name string
212+
numQueues int32
213+
handSize int32
214+
validated bool
215+
}{
216+
{
217+
"validation fails",
218+
-100,
219+
-100,
220+
false,
221+
},
222+
{
223+
"numQueues == handSize == 4",
224+
4,
225+
4,
226+
true,
227+
},
228+
{
229+
"numQueues == handSize == 8",
230+
8,
231+
8,
232+
true,
233+
},
234+
{
235+
"numQueues == handSize == 10",
236+
10,
237+
10,
238+
true,
239+
},
240+
{
241+
"numQueues == handSize == 12",
242+
12,
243+
12,
244+
true,
245+
},
246+
}
247+
for _, test := range tests {
248+
hashValue := rand.Uint64()
249+
t.Run(test.name, func(t *testing.T) {
250+
cards, err := DealToSlice(hashValue, test.numQueues, test.handSize)
251+
if (err == nil) != test.validated {
252+
t.Errorf("test case %s fails in validation check", test.name)
253+
return
254+
}
255+
256+
if test.validated {
257+
// check cards number
258+
if len(cards) != int(test.handSize) {
259+
t.Errorf("test case %s fails in cards number", test.name)
260+
return
261+
}
262+
263+
// check cards duplication
264+
cardMap := make(map[int32]struct{}, test.handSize)
265+
for _, cardIdx := range cards {
266+
cardMap[cardIdx] = struct{}{}
267+
}
268+
for i := int32(0); i < test.handSize; i++ {
269+
if _, ok := cardMap[i]; !ok {
270+
t.Errorf("test case %s fails in duplication check", test.name)
271+
return
272+
}
273+
}
274+
}
275+
})
94276
}
95277
}

0 commit comments

Comments
 (0)