Copilot commented on code in PR #3114:
URL: https://github.com/apache/dubbo-go/pull/3114#discussion_r2621578265
##########
cluster/loadbalance/random/loadbalance.go:
##########
@@ -70,11 +71,21 @@ func (lb *randomLoadBalance) Select(invokers
[]base.Invoker, invocation base.Inv
if totalWeight > 0 && !sameWeight {
// If (not every invoker has the same weight & at least one
invoker's weight>0), select randomly based on totalWeight.
offset := rand.Int63n(totalWeight)
-
- for i := 0; i < length; i++ {
- if offset < weights[i] {
- return invokers[i]
+ if length <= 4 {
+ for i := 0; i < length; i++ {
+ if offset < weights[i] {
+ return invokers[i]
+ }
+ }
+ } else {
+ idx := sort.Search(len(weights), func(i int) bool {
return weights[i] >= offset })
+ if idx < length && weights[idx] == offset {
+ for idx+1 < length && weights[idx+1] == offset {
+ idx++
+ }
+ idx++
}
Review Comment:
The binary search implementation has a critical bug. The condition
`weights[idx] >= offset` will find the first index where the cumulative weight
is greater than or equal to offset, but the special handling when `weights[idx]
== offset` is incorrect.
The original loop returns the invoker when `offset < weights[i]`, which
correctly handles the case where offset falls within the weight range of
invoker i. However, the binary search logic attempts to handle the equality
case by incrementing idx, which breaks the weighted random selection algorithm.
For example, if offset=5 and weights=[3,5,10], the original code would
return invokers[2] (since 5 < 10 is the first true condition), but the new code
would find idx=1 (weights[1]==5), then increment to idx=2, then return
invokers[2]. While this might work in some cases, when offset equals a
cumulative weight boundary, the algorithm should return the invoker at that
boundary index, not skip past it.
The correct binary search should use `weights[i] > offset` as the search
predicate to match the original `offset < weights[i]` logic.
```suggestion
idx := sort.Search(len(weights), func(i int) bool {
return weights[i] > offset })
```
##########
cluster/loadbalance/random/loadbalance.go:
##########
@@ -70,11 +71,21 @@ func (lb *randomLoadBalance) Select(invokers
[]base.Invoker, invocation base.Inv
if totalWeight > 0 && !sameWeight {
// If (not every invoker has the same weight & at least one
invoker's weight>0), select randomly based on totalWeight.
offset := rand.Int63n(totalWeight)
-
- for i := 0; i < length; i++ {
- if offset < weights[i] {
- return invokers[i]
+ if length <= 4 {
+ for i := 0; i < length; i++ {
+ if offset < weights[i] {
+ return invokers[i]
+ }
+ }
+ } else {
+ idx := sort.Search(len(weights), func(i int) bool {
return weights[i] >= offset })
+ if idx < length && weights[idx] == offset {
+ for idx+1 < length && weights[idx+1] == offset {
+ idx++
+ }
+ idx++
}
+ return invokers[idx]
Review Comment:
The binary search implementation is missing bounds checking. When
`sort.Search` doesn't find a matching element, it returns `len(weights)`. If
this happens, accessing `invokers[idx]` at line 88 will cause an index out of
bounds panic.
While the condition at line 82 checks `idx < length`, this check only
applies to the special equality case. If the equality condition is false, the
code proceeds to line 88 without verifying that `idx < length`, which could
cause a runtime panic.
```suggestion
if idx < length {
return invokers[idx]
}
// Defensive fallback: should not happen, but return a
random invoker to avoid panic
return invokers[rand.Intn(length)]
```
##########
Makefile:
##########
@@ -42,7 +42,7 @@ test: clean
fmt: install-imports-formatter
# replace interface{} with any
- go run
golang.org/x/tools/gopls/internal/analysis/modernize/cmd/modernize@latest
-category=efaceany -fix -test ./...
+ go run
golang.org/x/tools/gopls/internal/analysis/modernize/cmd/modernize@latest
-any=true -fix -test ./...
Review Comment:
The Makefile change appears unrelated to the PR's stated purpose of
optimizing invoker selection logic. The change from `-category=efaceany` to
`-any=true` is a modification to the code formatting command, which should be
in a separate commit or PR focused on build/tooling updates rather than being
bundled with a performance optimization change.
```suggestion
go run
golang.org/x/tools/gopls/internal/analysis/modernize/cmd/modernize@latest
-category=efaceany -fix -test ./...
```
##########
cluster/loadbalance/random/loadbalance.go:
##########
@@ -70,11 +71,21 @@ func (lb *randomLoadBalance) Select(invokers
[]base.Invoker, invocation base.Inv
if totalWeight > 0 && !sameWeight {
// If (not every invoker has the same weight & at least one
invoker's weight>0), select randomly based on totalWeight.
offset := rand.Int63n(totalWeight)
-
- for i := 0; i < length; i++ {
- if offset < weights[i] {
- return invokers[i]
+ if length <= 4 {
Review Comment:
The threshold value of 4 for choosing between linear search and binary
search appears arbitrary and lacks justification. Binary search has O(log n)
complexity but includes overhead that may not be beneficial for small arrays.
While optimizing for larger arrays makes sense, the choice of 4 as the
cutoff should be based on benchmarking data. Typically, for such optimizations,
the threshold might be higher (e.g., 10-20 elements) depending on the specific
use case and performance characteristics. Consider providing justification for
this value or making it configurable.
##########
cluster/loadbalance/random/loadbalance.go:
##########
@@ -70,11 +71,21 @@ func (lb *randomLoadBalance) Select(invokers
[]base.Invoker, invocation base.Inv
if totalWeight > 0 && !sameWeight {
// If (not every invoker has the same weight & at least one
invoker's weight>0), select randomly based on totalWeight.
offset := rand.Int63n(totalWeight)
-
- for i := 0; i < length; i++ {
- if offset < weights[i] {
- return invokers[i]
+ if length <= 4 {
+ for i := 0; i < length; i++ {
+ if offset < weights[i] {
+ return invokers[i]
+ }
+ }
+ } else {
+ idx := sort.Search(len(weights), func(i int) bool {
return weights[i] >= offset })
+ if idx < length && weights[idx] == offset {
+ for idx+1 < length && weights[idx+1] == offset {
+ idx++
+ }
+ idx++
}
+ return invokers[idx]
}
Review Comment:
The new binary search optimization path (for length > 4) lacks test
coverage. The existing tests only verify basic selection and weighted selection
but don't specifically validate the correctness of the binary search
implementation with different array sizes and weight distributions.
Consider adding test cases that:
1. Test invoker selection with exactly 5 invokers to trigger the binary
search path
2. Verify correct behavior when offset equals cumulative weight boundaries
3. Test edge cases like all weights being equal in the binary search path
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
