wangjiacai666 commented on PR #16544:
URL: https://github.com/apache/dubbo/pull/16544#issuecomment-6458902644
@LI123456mo thanks for trying it out. The numbers come from a standalone
microbenchmark, not a test method's wall time — and the gap only appears when
the call actually enters the weighted branch. Two things are worth checking in
your setup:
**1. The invoker URLs must make `needWeightLoadBalance()` return true.**
`RandomLoadBalance#doSelect` returns early at the very top:
```java
if (!needWeightLoadBalance(invokers, invocation)) {
return invokers.get(ThreadLocalRandom.current().nextInt(length));
}
```
The O(N²) loop only runs on the weighted path, which is taken when the
invoker URL has a method-level `weight` or a non-empty `timestamp` (provider
publish time → warmup). A mock invoker built from a bare
`URL.valueOf("dubbo://...")` has neither, so before and after take the
equal-weight shortcut and the timing is identical by construction. In
production every provider URL carries `timestamp=...`, so the weighted path is
always taken.
**2. The list must be a `BitList`, not an `ArrayList`.**
On an `ArrayList`, `get(i)` is O(1) and the old loop is already O(N) — there
is nothing to gain (the delta there is just `Iterator` vs indexed access). The
O(N²) only shows up on `BitList`, where `get(index)` restarts `nextSetBit` from
-1 and walks `index + 1` bits on every call, which is exactly what the router
chain hands to the load balancer.
**Harness** (JDK 21, single thread, 200 warmup calls, then best of 100):
```java
List<Invoker<Object>> raw = new ArrayList<>();
for (int i = 0; i < 3125; i++) {
raw.add(new MockInvoker(URL.valueOf("dubbo://10.0.1." + (i % 254)
+
":20880/com.foo.Bar?interface=com.foo.Bar×tamp=1700000000000")));
}
List<Invoker<Object>> invokers = new BitList<>(raw); // weighted path, 3125
matched addresses
// warm up, then time a single select() per sample
```
Results (per `select()`):
| list | weighted | before | after |
|---|---|---|---|
| `BitList`, 3125/3125 matched | yes | 16.29 ms | 0.14 ms |
| `BitList`, 782/3125 matched | yes | 1.03 ms | 0.04 ms |
| `ArrayList`, 3125 | yes | 0.14 ms | 0.21 ms |
| `BitList`, 3125 | no | < 1 µs | < 1 µs |
The loop is O(cardinality²): 3125 matched addresses means ~4.9M `nextSetBit`
calls in the accumulation alone (`BitList#get` is also `synchronized`, so
threads contend on it in production, which is part of why the real number is
higher).
On the 33.5 ms in the description: that figure is `arthas trace` of
`doSelect` on a production consumer with a 3125-element `BitList`, so it
includes `getWeight` and lock contention. The "~38 ms → ~14 ms" line is a
separate measurement — average RT of the downstream Dubbo calls on that
consumer before/after switching the reference to the patched `doSelect`, not a
microbenchmark.
One more thing: if your test is time-boxed (run for N seconds and print
elapsed), both builds will show the same wall time by construction — compare
per-call latency or throughput instead.
<details>
<summary>Full benchmark source</summary>
```java
package org.apache.dubbo.rpc.cluster.loadbalance;
import org.apache.dubbo.common.URL;
import org.apache.dubbo.common.utils.StringUtils;
import org.apache.dubbo.rpc.Invocation;
import org.apache.dubbo.rpc.Invoker;
import org.apache.dubbo.rpc.Result;
import org.apache.dubbo.rpc.RpcInvocation;
import org.apache.dubbo.rpc.cluster.router.state.BitList;
import org.apache.dubbo.rpc.support.RpcUtils;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
public class Bench {
static final int N = 3125;
static final int WARMUP = 200;
static final int RUNS = 100;
public static class MockInvoker implements Invoker<Object> {
private final URL url;
MockInvoker(URL url) {
this.url = url;
}
@Override
public URL getUrl() {
return url;
}
@Override
public boolean isAvailable() {
return true;
}
@Override
public void destroy() {
}
@Override
public Class<Object> getInterface() {
return Object.class;
}
@Override
public Result invoke(Invocation invocation) {
return null;
}
}
/** stock RandomLoadBalance#doSelect, index-based accumulation */
static class Stock extends RandomLoadBalance {
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL
url, Invocation invocation) {
int length = invokers.size();
if (!needWeight(invokers, invocation)) {
return
invokers.get(ThreadLocalRandom.current().nextInt(length));
}
boolean sameWeight = true;
int[] weights = new int[length];
int totalWeight = 0;
for (int i = 0; i < length; i++) {
int weight = getWeight(invokers.get(i), invocation);
totalWeight += weight;
weights[i] = totalWeight;
if (sameWeight && totalWeight != weight * (i + 1)) {
sameWeight = false;
}
}
if (totalWeight > 0 && !sameWeight) {
int offset =
ThreadLocalRandom.current().nextInt(totalWeight);
if (length <= 4) {
for (int i = 0; i < length; i++) {
if (offset < weights[i]) {
return invokers.get(i);
}
}
} else {
int i = Arrays.binarySearch(weights, offset);
if (i < 0) {
i = -i - 1;
} else {
while (weights[i + 1] == offset) {
i++;
}
i++;
}
return invokers.get(i);
}
}
return invokers.get(ThreadLocalRandom.current().nextInt(length));
}
}
/** patched doSelect: for-each accumulation */
static class Patched extends RandomLoadBalance {
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL
url, Invocation invocation) {
int length = invokers.size();
if (!needWeight(invokers, invocation)) {
return
invokers.get(ThreadLocalRandom.current().nextInt(length));
}
boolean sameWeight = true;
int[] weights = new int[length];
int totalWeight = 0;
int i = 0;
for (Invoker<T> invoker : invokers) {
int weight = getWeight(invoker, invocation);
totalWeight += weight;
weights[i] = totalWeight;
if (sameWeight && totalWeight != weight * (i + 1)) {
sameWeight = false;
}
i++;
}
if (totalWeight > 0 && !sameWeight) {
int offset =
ThreadLocalRandom.current().nextInt(totalWeight);
if (length <= 4) {
for (int j = 0; j < length; j++) {
if (offset < weights[j]) {
return invokers.get(j);
}
}
} else {
int j = Arrays.binarySearch(weights, offset);
if (j < 0) {
j = -j - 1;
} else {
while (weights[j + 1] == offset) {
j++;
}
j++;
}
return invokers.get(j);
}
}
return invokers.get(ThreadLocalRandom.current().nextInt(length));
}
}
// same as the private RandomLoadBalance#needWeightLoadBalance,
// minus the ClusterInvoker branch (MockInvoker is not a ClusterInvoker)
static boolean needWeight(List<? extends Invoker<?>> invokers,
Invocation invocation) {
URL invokerUrl = invokers.get(0).getUrl();
String weight =
invokerUrl.getMethodParameter(RpcUtils.getMethodName(invocation), "weight");
if (StringUtils.isNotEmpty(weight)) {
return true;
}
return
StringUtils.isNotEmpty(invokers.get(0).getUrl().getParameter("timestamp"));
}
static List<Invoker<Object>> invokers(boolean withTimestamp) {
List<Invoker<Object>> list = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
String q = "dubbo://10.0.1." + (i % 254) +
":20880/com.foo.Bar?interface=com.foo.Bar";
if (withTimestamp) {
q += "×tamp=1700000000000";
}
list.add(new MockInvoker(URL.valueOf(q)));
}
return list;
}
static long time(RandomLoadBalance lb, List<Invoker<Object>> list, URL
url, RpcInvocation inv, int rounds) {
long best = Long.MAX_VALUE;
for (int r = 0; r < rounds; r++) {
long t0 = System.nanoTime();
lb.select(list, url, inv);
long d = System.nanoTime() - t0;
if (d < best) {
best = d;
}
}
return best;
}
public static void main(String[] args) {
URL url = URL.valueOf("consumer://10.0.0.1/com.foo.Bar");
RpcInvocation inv = new RpcInvocation();
inv.setMethodName("go");
for (String mode : new String[]{"with-timestamp", "no-timestamp"}) {
boolean ts = "with-timestamp".equals(mode);
List<Invoker<Object>> raw = invokers(ts);
List<Invoker<Object>> dense = new BitList<>(raw);
BitSet sparseSet = new BitSet();
for (int i = 0; i < raw.size(); i += 4) {
sparseSet.set(i);
}
List<Invoker<Object>> sparse = new BitList<>(raw, sparseSet,
null);
List<Invoker<Object>> al = new ArrayList<>(raw);
System.out.println("== " + mode + " (origin=" + N + ", dense=" +
dense.size()
+ ", sparse=" + sparse.size() + ") needWeight=" +
needWeight(dense, inv));
Stock stock = new Stock();
Patched patched = new Patched();
for (int i = 0; i < WARMUP; i++) {
stock.select(dense, url, inv);
patched.select(dense, url, inv);
stock.select(sparse, url, inv);
patched.select(sparse, url, inv);
}
print("BitList dense ", stock, patched, dense, url, inv);
print("BitList sparse", stock, patched, sparse, url, inv);
print("ArrayList ", stock, patched, al, url, inv);
}
}
static void print(String label, RandomLoadBalance stock,
RandomLoadBalance patched,
List<Invoker<Object>> list, URL url, RpcInvocation
inv) {
System.out.printf("%s stock=%10.1f us patched=%8.1f us%n",
label, time(stock, list, url, inv, RUNS) / 1e3,
time(patched, list, url, inv, RUNS) / 1e3);
}
}
```
</details>
--
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]