Skip to content

Commit 3a4b453

Browse files
jknackjknack
committed
router: improve performance on non-static path matches
1 parent c2ac32f commit 3a4b453

File tree

5 files changed

+163
-15
lines changed

5 files changed

+163
-15
lines changed

‎jooby/src/main/java/io/jooby/internal/Chi.java‎

Lines changed: 84 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -20,16 +20,89 @@
2020
/** Sync: May 22, 2020 Commit: 5704d7ee98edd3fe55169b506531bdd061667c70 */
2121
class Chi implements RouteTree {
2222
private static final String EMPTY_STRING = "";
23+
private static final Slice EMPTY_SLICE = new Slice(EMPTY_STRING);
2324
private static final byte ntStatic = 0; // /home
2425
private static final byte ntRegexp = 1; // /{id:[0-9]+}
2526
private static final byte ntParam = 2; // /{user}
2627
private static final byte ntCatchAll = 3; // /api/v1/*
2728

2829
private static final int NODE_SIZE = ntCatchAll + 1;
2930

30-
static final char ZERO_CHAR = (char) 0;
31+
static final char ZERO_CHAR = Character.MIN_VALUE;
3132
private MessageEncoder encoder;
3233

34+
/** Avoid string allocation */
35+
private static class Slice implements CharSequence {
36+
private final String base;
37+
private final int startIndex;
38+
39+
private final int endIndex;
40+
41+
public Slice(String base, int startIndex, int endIndex) {
42+
this.base = base;
43+
this.startIndex = startIndex;
44+
this.endIndex = endIndex;
45+
}
46+
47+
public Slice(String base, int startIndex) {
48+
this(base, startIndex, base.length());
49+
}
50+
51+
public Slice(String base) {
52+
this(base, 0);
53+
}
54+
55+
@Override
56+
public int length() {
57+
return endIndex - startIndex;
58+
}
59+
60+
@Override
61+
public char charAt(int index) {
62+
return base.charAt(startIndex + index);
63+
}
64+
65+
@Override
66+
public Slice subSequence(int start, int end) {
67+
return new Slice(base, startIndex + start, startIndex + end);
68+
}
69+
70+
@Override
71+
public String toString() {
72+
return base.substring(startIndex, endIndex);
73+
}
74+
75+
public Slice substring(int start) {
76+
return substring(start, length());
77+
}
78+
79+
public Slice substring(int start, int end) {
80+
return subSequence(start, end);
81+
}
82+
83+
public int indexOf(int ch) {
84+
for (int i = startIndex; i < endIndex; i++) {
85+
if (base.charAt(i) == ch) {
86+
return i - startIndex;
87+
}
88+
}
89+
return -1;
90+
}
91+
92+
public boolean startsWith(String prefix) {
93+
int len = prefix.length();
94+
if (len <= length()) {
95+
for (int i = 0; i < len; i++) {
96+
if (base.charAt(i + startIndex) != prefix.charAt(i)) {
97+
return false;
98+
}
99+
}
100+
return true;
101+
}
102+
return false;
103+
}
104+
}
105+
33106
private interface MethodMatcher {
34107
StaticRouterMatch get(String method);
35108

@@ -434,15 +507,15 @@ void setEndpoint(String method, Route route) {
434507

435508
// Recursive edge traversal by checking all nodeTyp groups along the way.
436509
// It's like searching through a multi-dimensional radix trie.
437-
Route findRoute(RouterMatch rctx, String method, String path) {
510+
Route findRoute(RouterMatch rctx, String method, Slice path) {
438511

439512
for (int ntyp = 0; ntyp < NODE_SIZE; ntyp++) {
440513
Node[] nds = this.children[ntyp];
441514
if (nds != null) {
442515
Node xn = null;
443-
String xsearch = path;
516+
Slice xsearch = path;
444517

445-
char label = path.length() > 0 ? path.charAt(0) : ZERO_CHAR;
518+
char label = xsearch.isEmpty() ? ZERO_CHAR : xsearch.charAt(0);
446519

447520
switch (ntyp) {
448521
case ntStatic:
@@ -475,17 +548,18 @@ Route findRoute(RouterMatch rctx, String method, String path) {
475548
}
476549

477550
if (ntyp == ntRegexp && xn.rex != null) {
551+
// 12, ar, page, arx
478552
if (!xn.rex.matcher(xsearch.substring(0, p)).matches()) {
479553
continue;
480554
}
481-
} else if (xsearch.substring(0, p).indexOf('/') != -1) {
555+
} else if (xsearch.substring(0, p).indexOf('/') > 0) {
482556
// avoid a newRuntimeRoute across path segments
483557
continue;
484558
}
485559

486560
// rctx.routeParams.Values = append(rctx.routeParams.Values, xsearch[:p])
487561
int prevlen = rctx.vars.size();
488-
rctx.value(xsearch.substring(0, p));
562+
rctx.value(xsearch.substring(0, p).toString());
489563
xsearch = xsearch.substring(p);
490564

491565
if (xsearch.length() == 0) {
@@ -514,10 +588,10 @@ Route findRoute(RouterMatch rctx, String method, String path) {
514588
// catch-all nodes
515589
// rctx.routeParams.Values = append(rctx.routeParams.Values, search)
516590
if (xsearch.length() > 0) {
517-
rctx.value(xsearch);
591+
rctx.value(xsearch.toString());
518592
}
519593
xn = nds[0];
520-
xsearch = EMPTY_STRING;
594+
xsearch = EMPTY_SLICE;
521595
}
522596

523597
if (xn == null) {
@@ -632,7 +706,7 @@ Segment patNextSegment(String pattern) {
632706
}
633707

634708
// Sanity check
635-
if (ps >= 0 && ws >= 0 && ws < ps) {
709+
if (ws >= 0 && ws < ps) {
636710
throw new IllegalArgumentException(
637711
"chi: wildcard '*' must be the last pattern in a route, otherwise use a '{param}'");
638712
}
@@ -778,7 +852,7 @@ public Router.Match find(String method, String path) {
778852
private Router.Match findInternal(String method, String path) {
779853
// use radix tree
780854
RouterMatch result = new RouterMatch();
781-
Route route = root.findRoute(result, method, path);
855+
Route route = root.findRoute(result, method, new Slice(path));
782856
if (route == null) {
783857
return result.missing(method, path, encoder);
784858
}

‎jooby/src/main/java/io/jooby/internal/RouterMatch.java‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,6 @@
1010
import java.util.List;
1111
import java.util.Map;
1212
import java.util.Set;
13-
import java.util.stream.Collectors;
1413

1514
import edu.umd.cs.findbugs.annotations.NonNull;
1615
import io.jooby.Context;
@@ -54,7 +53,7 @@ public void pop() {
5453
}
5554

5655
public void methodNotAllowed(Set<String> allow) {
57-
String allowString = allow.stream().collect(Collectors.joining(","));
56+
String allowString = String.join(",", allow);
5857
Route.Filter filter =
5958
next ->
6059
ctx -> {

‎jooby/src/test/java/io/jooby/internal/ChiTest.java‎

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,6 @@
2020
import io.jooby.SneakyThrows;
2121

2222
public class ChiTest {
23-
2423
@Test
2524
public void routeOverride() {
2625
Chi router = new Chi();
@@ -116,8 +115,6 @@ public void wildOnRoot() throws Exception {
116115
public void searchString() throws Exception {
117116
Chi router = new Chi();
118117

119-
// app.get("/regex/{zid:[0-9]+}/edit", ctx -> ctx.getRoute().getPathKeys());
120-
121118
router.insert(route("GET", "/regex/{nid:[0-9]+}", stringHandler("nid")));
122119
router.insert(route("GET", "/regex/{zid:[0-9]+}/edit", stringHandler("zid")));
123120
router.insert(route("GET", "/articles/{id}", stringHandler("id")));
@@ -152,9 +149,19 @@ public void searchString() throws Exception {
152149
public void searchParam() throws Exception {
153150
Chi router = new Chi();
154151

152+
router.insert(route("GET", "/catchallWithVarPrefix/{id}/*path", stringHandler("path")));
153+
155154
router.insert(route("GET", "/articles/{id}", stringHandler("id")));
156155
router.insert(route("GET", "/articles/*", stringHandler("catchall")));
157156

157+
find(
158+
router,
159+
"/catchallWithVarPrefix/55/js/index.js",
160+
(ctx, result) -> {
161+
assertTrue(result.matches());
162+
assertEquals("path", result.route().getPipeline().apply(ctx));
163+
});
164+
158165
find(
159166
router,
160167
"/articles/123",

‎tests/pom.xml‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -218,6 +218,20 @@
218218
<scope>test</scope>
219219
</dependency>
220220

221+
<dependency>
222+
<groupId>org.openjdk.jmh</groupId>
223+
<artifactId>jmh-core</artifactId>
224+
<version>1.37</version>
225+
<scope>test</scope>
226+
</dependency>
227+
228+
<dependency>
229+
<groupId>org.openjdk.jmh</groupId>
230+
<artifactId>jmh-generator-annprocess</artifactId>
231+
<version>1.37</version>
232+
<scope>test</scope>
233+
</dependency>
234+
221235
</dependencies>
222236

223237
<build>

‎tests/src/test/java/io/jooby/internal/ChiBench.java‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/*
2+
* Jooby https://jooby.io
3+
* Apache License Version 2.0 https://jooby.io/LICENSE.txt
4+
* Copyright 2014 Edgar Espina
5+
*/
6+
package io.jooby.internal;
7+
8+
import java.util.concurrent.TimeUnit;
9+
10+
import org.openjdk.jmh.annotations.*;
11+
12+
import io.jooby.MessageEncoder;
13+
import io.jooby.Route;
14+
15+
@Fork(5)
16+
@Warmup(iterations = 5, time = 1)
17+
@Measurement(iterations = 10, time = 1)
18+
@BenchmarkMode(Mode.Throughput)
19+
@OutputTimeUnit(TimeUnit.SECONDS)
20+
@State(Scope.Benchmark)
21+
public class ChiBench {
22+
23+
private Chi router;
24+
25+
@Setup
26+
public void setup() {
27+
this.router = new Chi();
28+
router.insert(route("GET", "/api/user/edit", stringHandler("static")));
29+
router.insert(route("GET", "/api/user/{id}", stringHandler("param")));
30+
router.insert(route("GET", "/api/user/*", stringHandler("tail")));
31+
// put more
32+
router.insert(route("GET", "/api/page/edit", stringHandler("static")));
33+
router.insert(route("GET", "/api/page/{id}", stringHandler("id")));
34+
router.insert(route("GET", "/api/page/*", stringHandler("tail")));
35+
}
36+
37+
@Benchmark
38+
public void dynamicPath() {
39+
router.find("GET", "/api/user/123").matches();
40+
}
41+
42+
@Benchmark
43+
public void staticPath() {
44+
router.find("GET", "/api/page/edit").matches();
45+
}
46+
47+
private Route.Handler stringHandler(String foo) {
48+
return ctx -> foo;
49+
}
50+
51+
private Route route(String method, String pattern, Route.Handler handler) {
52+
return new Route(method, pattern, handler).setEncoder(MessageEncoder.TO_STRING);
53+
}
54+
}

0 commit comments

Comments
 (0)