Skip to content

Commit 59fb97f

Browse files
jknackjknack
committed
performance improvements for routing algorithm
- static paths don`t create a new string - dynamic paths don`t create a new string
1 parent 9864949 commit 59fb97f

File tree

3 files changed

+56
-27
lines changed

3 files changed

+56
-27
lines changed

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

Lines changed: 30 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -19,13 +19,14 @@
1919
import java.util.concurrent.ConcurrentHashMap;
2020
import java.util.regex.Pattern;
2121
import java.util.stream.Collectors;
22+
import java.util.stream.IntStream;
2223
import java.util.stream.Stream;
2324

2425
class $Chi implements RadixTree {
25-
private static final int ntStatic = 0;// /home
26-
private static final int ntRegexp = 1; // /{id:[0-9]+}
27-
private static final int ntParam = 2; // /{user}
28-
private static final int ntCatchAll = 3; // /api/v1/*
26+
private static final byte ntStatic = 0;// /home
27+
private static final byte ntRegexp = 1; // /{id:[0-9]+}
28+
private static final byte ntParam = 2; // /{user}
29+
private static final byte ntCatchAll = 3; // /api/v1/*
2930

3031
private static int NODE_SIZE = ntCatchAll + 1;
3132

@@ -41,7 +42,7 @@ public StaticRoute(Map<String, Route> methods) {
4142
}
4243

4344
public StaticRoute() {
44-
this(new ConcurrentHashMap<>(Router.METHODS.size()));
45+
this(newMap(Router.METHODS.size()));
4546
}
4647

4748
public void put(String method, Route route) {
@@ -162,8 +163,8 @@ public boolean startsWith(ZeroCopyString prefix) {
162163
}
163164

164165
static class Segment {
165-
int nodeType;
166-
String key = "";
166+
byte nodeType;
167+
// String key = "";
167168
ZeroCopyString rexPat = ZeroCopyString.EMPTY;
168169
char tail;
169170
int startIndex;
@@ -172,10 +173,10 @@ static class Segment {
172173
public Segment() {
173174
}
174175

175-
public Segment(int nodeType, String key, ZeroCopyString regex, char tail, int startIndex,
176+
public Segment(byte nodeType, /*String key,*/ ZeroCopyString regex, char tail, int startIndex,
176177
int endIndex) {
177178
this.nodeType = nodeType;
178-
this.key = key;
179+
// this.key = key;
179180
this.rexPat = regex;
180181
this.tail = tail;
181182
this.startIndex = startIndex;
@@ -185,7 +186,7 @@ public Segment(int nodeType, String key, ZeroCopyString regex, char tail, int st
185186

186187
private static class Node implements Comparable<Node> {
187188
// node type: static, regexp, param, catchAll
188-
int typ;
189+
byte typ;
189190

190191
// first byte of the prefix
191192
char label;
@@ -209,7 +210,7 @@ private static class Node implements Comparable<Node> {
209210
// in groups of the node type.
210211
Node[][] children = new Node[NODE_SIZE][];
211212

212-
public Node typ(int typ) {
213+
public Node typ(byte typ) {
213214
this.typ = typ;
214215
return this;
215216
}
@@ -367,7 +368,7 @@ Node addChild(Node child, ZeroCopyString search) {
367368
// Parse next segment
368369
// segTyp, _, segRexpat, segTail, segStartIdx, segEndIdx := patNextSegment(search)
369370
Segment seg = patNextSegment(search);
370-
int segTyp = seg.nodeType;
371+
byte segTyp = seg.nodeType;
371372
int segStartIdx = seg.startIndex;
372373
int segEndIdx = seg.endIndex;
373374
// Add child depending on next up segment
@@ -668,7 +669,7 @@ Segment patNextSegment(ZeroCopyString pattern) {
668669
int ws = pattern.indexOf('*');
669670

670671
if (ps < 0 && ws < 0) {
671-
return new Segment(ntStatic, "", ZeroCopyString.EMPTY, (char) 0, 0,
672+
return new Segment(ntStatic, ZeroCopyString.EMPTY, (char) 0, 0,
672673
pattern.length()); // we return the entire thing
673674
}
674675

@@ -682,7 +683,7 @@ Segment patNextSegment(ZeroCopyString pattern) {
682683

683684
if (ps >= 0) {
684685
// Param/Regexp pattern is next
685-
int nt = ntParam;
686+
byte nt = ntParam;
686687

687688
// Read to closing } taking into account opens and closes in curl count (cc)
688689
int cc = 0;
@@ -702,7 +703,7 @@ Segment patNextSegment(ZeroCopyString pattern) {
702703
}
703704
if (pe == ps) {
704705
throw new IllegalArgumentException(
705-
"chi: route param closing delimiter '}' is missing");
706+
"Router: route param closing delimiter '}' is missing");
706707
}
707708

708709
ZeroCopyString key = pattern.substring(ps + 1, pe);
@@ -717,7 +718,7 @@ Segment patNextSegment(ZeroCopyString pattern) {
717718
if (idx >= 0) {
718719
nt = ntRegexp;
719720
rexpat = key.substring(idx + 1).toString();
720-
key = key.substring(0, idx);
721+
// key = key.substring(0, idx);
721722
}
722723

723724
if (rexpat.length() > 0) {
@@ -729,14 +730,14 @@ Segment patNextSegment(ZeroCopyString pattern) {
729730
}
730731
}
731732

732-
return new Segment(nt, key.toString(), new ZeroCopyString(rexpat), tail, ps, pe);
733+
return new Segment(nt, new ZeroCopyString(rexpat), tail, ps, pe);
733734
}
734735

735736
// Wildcard pattern as finale
736737
// EDIT: should we panic if there is stuff after the * ???
737738
// We allow naming a wildcard: *path
738-
String key = ws == pattern.length() - 1 ? "*" : pattern.substring(ws + 1).toString();
739-
return new Segment(ntCatchAll, key, ZeroCopyString.EMPTY, (char) 0, ws, pattern.length());
739+
//String key = ws == pattern.length() - 1 ? "*" : pattern.substring(ws + 1).toString();
740+
return new Segment(ntCatchAll, ZeroCopyString.EMPTY, (char) 0, ws, pattern.length());
740741
}
741742

742743
public void destroy() {
@@ -763,7 +764,11 @@ public void destroy() {
763764
private Node root = new Node();
764765

765766
/** Not need to use a concurrent map, due we don't allow to add routes after application started. */
766-
private Map<Object, StaticRoute> staticPaths = new ConcurrentHashMap<>();
767+
private Map<Object, StaticRoute> staticPaths = newMap(16);
768+
769+
static <K, V> Map<K, V> newMap(int size) {
770+
return new ConcurrentHashMap<>(size);
771+
}
767772

768773
public void insert(String method, String pattern, Route route) {
769774
String baseCatchAll = baseCatchAll(pattern);
@@ -805,9 +810,7 @@ public RouterMatch find(Context context, MessageEncoder encoder,
805810
}
806811

807812
public boolean find(String method, String path) {
808-
StaticRoute staticRoute = staticPaths.getOrDefault(path, NO_MATCH);
809-
Route route = staticRoute.methods.get(method);
810-
if (route == null) {
813+
if (!staticPaths.getOrDefault(path, NO_MATCH).methods.containsKey(method)) {
811814
return root.findRoute(new RouterMatch(), method, new ZeroCopyString(path)) != null;
812815
}
813816
return true;
@@ -816,11 +819,10 @@ public boolean find(String method, String path) {
816819
public RouterMatch find(Context context, String path, MessageEncoder encoder,
817820
List<RadixTree> more) {
818821
String method = context.getMethod();
819-
RouterMatch result = new RouterMatch();
820-
StaticRoute staticRoute = staticPaths.getOrDefault(path, NO_MATCH);
821-
Route route = staticRoute.methods.get(method);
822+
Route route = staticPaths.getOrDefault(path, NO_MATCH).methods.get(method);
822823
if (route == null) {
823824
// use radix tree
825+
RouterMatch result = new RouterMatch();
824826
route = root.findRoute(result, method, new ZeroCopyString(path));
825827
if (route == null) {
826828
if (more != null) {
@@ -834,7 +836,8 @@ public RouterMatch find(Context context, String path, MessageEncoder encoder,
834836
}
835837
return result.missing(method, path, encoder);
836838
}
839+
return result.found(route);
837840
}
838-
return result.found(route);
841+
return new RouterMatch(route);
839842
}
840843
}

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

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,14 @@ public class RouterMatch implements Router.Match {
2727

2828
private Route.Handler handler;
2929

30+
public RouterMatch(Route route) {
31+
this.route = route;
32+
this.matches = true;
33+
}
34+
35+
public RouterMatch() {
36+
}
37+
3038
public void key(List<String> keys) {
3139
for (int i = 0; i < Math.min(keys.size(), vars.size()); i++) {
3240
vars.put(keys.get(i), vars.remove(i));

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

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -123,6 +123,24 @@ public void searchString() throws Exception {
123123
});
124124
}
125125

126+
@Test
127+
public void searchParam() throws Exception {
128+
$Chi router = new $Chi();
129+
130+
router.insert(route("GET", "/articles/{id}", stringHandler("id")));
131+
router.insert(route("GET", "/articles/*", stringHandler("catchall")));
132+
133+
find(router, "/articles/123", (ctx, result) -> {
134+
assertTrue(result.matches);
135+
assertEquals("id", result.route().getPipeline().apply(ctx));
136+
});
137+
138+
find(router, "/articles/a/b", (ctx, result) -> {
139+
assertTrue(result.matches);
140+
assertEquals("catchall", result.route().getPipeline().apply(ctx));
141+
});
142+
}
143+
126144
private void find($Chi router, String pattern,
127145
SneakyThrows.Consumer2<Context, RouterMatch> consumer) {
128146
Context rootctx = ctx(pattern);

0 commit comments

Comments
 (0)