Repository: labstack/echo
Pull request #1689 (2020-11-22 02:44:33)

Improve router performance with dedicated child types
Before this commit, all the node types were added to the same list of children nodes. Taking in consideration that only one Param and Any type of node could exist per node, two new node struct field were added to hold the references to those kind of nodes.
This avoid the need to iterate through all the Static type nodes just to find one Param or Any type node. Those iterations could be performed multiple times in the same iteration of Router#Find.
Removing the route comments of the Router benchmark tests.
Updating the Router benchmarks tests to find the routes defined to each particular benchmark. Before, all the benchmarks tried to find only the GitHub API.
Adding new router benchmarks to measure when the Router try to find routes that are not registered.

To be fair in the below benchmarks, I did the same modifications to the Router benchmarks on master. Also I performed 10 iterations per each benchmark, and compared the results with benchstat

benchstat bench_master.txt bench_new.txt
```
name                         old time/op    new time/op    delta
RouterStaticRoutes-2           20.0µs ± 2%    20.3µs ± 5%     ~     (p=0.065 n=10+9)
RouterStaticRoutesMisses-2     1.02µs ± 2%    0.66µs ± 4%  -35.43%  (p=0.000 n=8+9)
RouterGitHubAPI-2              38.9µs ± 3%    37.0µs ± 4%   -4.77%  (p=0.000 n=10+10)
RouterGitHubAPIMisses-2        1.25µs ± 3%    0.77µs ± 6%  -38.39%  (p=0.000 n=10+10)
RouterParseAPI-2               2.08µs ±10%    1.98µs ± 3%   -4.71%  (p=0.029 n=10+10)
RouterParseAPIMisses-2          442ns ± 4%     452ns ± 3%     ~     (p=0.066 n=9+9)
RouterGooglePlusAPI-2          1.35µs ± 2%    1.29µs ± 3%   -4.27%  (p=0.000 n=10+10)
RouterGooglePlusAPIMisses-2     989ns ± 4%     662ns ± 8%  -33.06%  (p=0.000 n=10+10)
RouterParamsAndAnyAPI-2        3.34µs ± 1%    2.96µs ± 3%  -11.41%  (p=0.000 n=8+10)

name                         old alloc/op   new alloc/op   delta
RouterStaticRoutes-2            0.00B          0.00B          ~     (all equal)
RouterStaticRoutesMisses-2      0.00B          0.00B          ~     (all equal)
RouterGitHubAPI-2               0.00B          0.00B          ~     (all equal)
RouterGitHubAPIMisses-2         0.00B          0.00B          ~     (all equal)
RouterParseAPI-2                0.00B          0.00B          ~     (all equal)
RouterParseAPIMisses-2          0.00B          0.00B          ~     (all equal)
RouterGooglePlusAPI-2           0.00B          0.00B          ~     (all equal)
RouterGooglePlusAPIMisses-2     0.00B          0.00B          ~     (all equal)
RouterParamsAndAnyAPI-2         0.00B          0.00B          ~     (all equal)

name                         old allocs/op  new allocs/op  delta
RouterStaticRoutes-2             0.00           0.00          ~     (all equal)
RouterStaticRoutesMisses-2       0.00           0.00          ~     (all equal)
RouterGitHubAPI-2                0.00           0.00          ~     (all equal)
RouterGitHubAPIMisses-2          0.00           0.00          ~     (all equal)
RouterParseAPI-2                 0.00           0.00          ~     (all equal)
RouterParseAPIMisses-2           0.00           0.00          ~     (all equal)
RouterGooglePlusAPI-2            0.00           0.00          ~     (all equal)
RouterGooglePlusAPIMisses-2      0.00           0.00          ~     (all equal)
RouterParamsAndAnyAPI-2          0.00           0.00          ~     (all equal)
```

codecov[bot]: # [Codecov](https://codecov.io/gh/labstack/echo/pull/1689?src=pr&el=h1) Report
> Merging [#1689](https://codecov.io/gh/labstack/echo/pull/1689?src=pr&el=desc) (e280e4e) into [master](https://codecov.io/gh/labstack/echo/commit/ad3be08de1d58a99644a72dd1a62a20d76d91ec1?el=desc) (ad3be08) will **decrease** coverage by `0.19%`.
> The diff coverage is `85.18%`.

[![Impacted file tree graph](https://codecov.io/gh/labstack/echo/pull/1689/graphs/tree.svg?width=650&height=150&src=pr&token=vqnT76l79i)](https://codecov.io/gh/labstack/echo/pull/1689?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master    #1689      +/-   ##
==========================================
- Coverage   84.72%   84.52%   -0.20%     
==========================================
  Files          29       29              
  Lines        1938     1965      +27     
==========================================
+ Hits         1642     1661      +19     
- Misses        188      196       +8     
  Partials      108      108              
```


| [Impacted Files](https://codecov.io/gh/labstack/echo/pull/1689?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [router.go](https://codecov.io/gh/labstack/echo/pull/1689/diff?src=pr&el=tree#diff-cm91dGVyLmdv) | `94.34% <85.18%> (-2.53%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/labstack/echo/pull/1689?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/labstack/echo/pull/1689?src=pr&el=footer). Last update [ad3be08...e280e4e](https://codecov.io/gh/labstack/echo/pull/1689?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/router.go b/router.go
index 4c3898c..749dbf4 100644
--- a/router.go
+++ b/router.go
@@ -14,14 +14,16 @@ type (
 		echo   *Echo
 	}
 	node struct {
-		kind          kind
-		label         byte
-		prefix        string
-		parent        *node
-		children      children
-		ppath         string
-		pnames        []string
-		methodHandler *methodHandler
+		kind            kind
+		label           byte
+		prefix          string
+		parent          *node
+		staticChildrens children
+		ppath           string
+		pnames          []string
+		methodHandler   *methodHandler
+		paramChildren   *node
+		anyChildren     *node
 	}
 	kind          uint8
 	children      []*node
@@ -44,6 +46,9 @@ const (
 	skind kind = iota
 	pkind
 	akind
+
+	paramLabel = byte(':')
+	anyLabel   = byte('*')
 )
 
 // NewRouter returns a new Router instance.
@@ -134,23 +139,32 @@ func (r *Router) insert(method, path string, h HandlerFunc, t kind, ppath string
 			}
 		} else if l < pl {
 			// Split node
-			n := newNode(cn.kind, cn.prefix[l:], cn, cn.children, cn.methodHandler, cn.ppath, cn.pnames)
+			n := newNode(cn.kind, cn.prefix[l:], cn, cn.staticChildrens, cn.methodHandler, cn.ppath, cn.pnames, cn.paramChildren, cn.anyChildren)
 
 			// Update parent path for all children to new node
-			for _, child := range cn.children {
+			for _, child := range cn.staticChildrens {
 				child.parent = n
 			}
+			if cn.paramChildren != nil {
+				cn.paramChildren.parent = n
+			}
+			if cn.anyChildren != nil {
+				cn.anyChildren.parent = n
+			}
 
 			// Reset parent node
 			cn.kind = skind
 			cn.label = cn.prefix[0]
 			cn.prefix = cn.prefix[:l]
-			cn.children = nil
+			cn.staticChildrens = nil
 			cn.methodHandler = new(methodHandler)
 			cn.ppath = ""
 			cn.pnames = nil
+			cn.paramChildren = nil
+			cn.anyChildren = nil
 
-			cn.addChild(n)
+			// Only Static children could reach here
+			cn.addStaticChild(n)
 
 			if l == sl {
 				// At parent node
@@ -160,9 +174,10 @@ func (r *Router) insert(method, path string, h HandlerFunc, t kind, ppath string
 				cn.pnames = pnames
 			} else {
 				// Create child node
-				n = newNode(t, search[l:], cn, nil, new(methodHandler), ppath, pnames)
+				n = newNode(t, search[l:], cn, nil, new(methodHandler), ppath, pnames, nil, nil)
 				n.addHandler(method, h)
-				cn.addChild(n)
+				// Only Static children could reach here
+				cn.addStaticChild(n)
 			}
 		} else if l < sl {
 			search = search[l:]
@@ -173,9 +188,16 @@ func (r *Router) insert(method, path string, h HandlerFunc, t kind, ppath string
 				continue
 			}
 			// Create child node
-			n := newNode(t, search, cn, nil, new(methodHandler), ppath, pnames)
+			n := newNode(t, search, cn, nil, new(methodHandler), ppath, pnames, nil, nil)
 			n.addHandler(method, h)
-			cn.addChild(n)
+			switch t {
+			case skind:
+				cn.addStaticChild(n)
+			case pkind:
+				cn.paramChildren = n
+			case akind:
+				cn.anyChildren = n
+			}
 		} else {
 			// Node already exists
 			if h != nil {
@@ -190,26 +212,28 @@ func (r *Router) insert(method, path string, h HandlerFunc, t kind, ppath string
 	}
 }
 
-func newNode(t kind, pre string, p *node, c children, mh *methodHandler, ppath string, pnames []string) *node {
+func newNode(t kind, pre string, p *node, sc children, mh *methodHandler, ppath string, pnames []string, paramChildren, anyChildren *node) *node {
 	return &node{
-		kind:          t,
-		label:         pre[0],
-		prefix:        pre,
-		parent:        p,
-		children:      c,
-		ppath:         ppath,
-		pnames:        pnames,
-		methodHandler: mh,
+		kind:            t,
+		label:           pre[0],
+		prefix:          pre,
+		parent:          p,
+		staticChildrens: sc,
+		ppath:           ppath,
+		pnames:          pnames,
+		methodHandler:   mh,
+		paramChildren:   paramChildren,
+		anyChildren:     anyChildren,
 	}
 }
 
-func (n *node) addChild(c *node) {
-	n.children = append(n.children, c)
+func (n *node) addStaticChild(c *node) {
+	n.staticChildrens = append(n.staticChildrens, c)
 }
 
-func (n *node) findChild(l byte, t kind) *node {
-	for _, c := range n.children {
-		if c.label == l && c.kind == t {
+func (n *node) findStaticChild(l byte) *node {
+	for _, c := range n.staticChildrens {
+		if c.label == l {
 			return c
 		}
 	}
@@ -217,19 +241,16 @@ func (n *node) findChild(l byte, t kind) *node {
 }
 
 func (n *node) findChildWithLabel(l byte) *node {
-	for _, c := range n.children {
+	for _, c := range n.staticChildrens {
 		if c.label == l {
 			return c
 		}
 	}
-	return nil
-}
-
-func (n *node) findChildByKind(t kind) *node {
-	for _, c := range n.children {
-		if c.kind == t {
-			return c
-		}
+	if l == paramLabel {
+		return n.paramChildren
+	}
+	if l == anyLabel {
+		return n.anyChildren
 	}
 	return nil
 }
@@ -356,7 +377,7 @@ func (r *Router) Find(method, path string, c Context) {
 		// Attempt to go back up the tree on no matching prefix or no remaining search
 		if l != pl || search == "" {
 			// Handle special case of trailing slash route with existing any route (see #1526)
-			if path[len(path)-1] == '/' && cn.findChildByKind(akind) != nil {
+			if path[len(path)-1] == '/' && cn.anyChildren != nil {
 				goto Any
 			}
 			if nn == nil { // Issue #1348
@@ -372,7 +393,7 @@ func (r *Router) Find(method, path string, c Context) {
 		}
 
 		// Static node
-		if child = cn.findChild(search[0], skind); child != nil {
+		if child = cn.findStaticChild(search[0]); child != nil {
 			// Save next
 			if cn.prefix[len(cn.prefix)-1] == '/' { // Issue #623
 				nk = pkind
@@ -385,7 +406,7 @@ func (r *Router) Find(method, path string, c Context) {
 
 	Param:
 		// Param node
-		if child = cn.findChildByKind(pkind); child != nil {
+		if child = cn.paramChildren; child != nil {
 			// Issue #378
 			if len(pvalues) == n {
 				continue
@@ -410,7 +431,7 @@ func (r *Router) Find(method, path string, c Context) {
 
 	Any:
 		// Any node
-		if cn = cn.findChildByKind(akind); cn != nil {
+		if cn = cn.anyChildren; cn != nil {
 			// If any node is found, use remaining path for pvalues
 			pvalues[len(cn.pnames)-1] = search
 			break
@@ -424,7 +445,7 @@ func (r *Router) Find(method, path string, c Context) {
 			search = ns
 			np := nn.parent
 			// Consider param route one level up only
-			if cn = nn.findChildByKind(pkind); cn != nil {
+			if cn = nn.paramChildren; cn != nil {
 				pos := strings.IndexByte(ns, '/')
 				if pos == -1 {
 					// If no slash is remaining in search string set param value
@@ -443,7 +464,7 @@ func (r *Router) Find(method, path string, c Context) {
 			// No param route found, try to resolve nearest any route
 			for {
 				np = nn.parent
-				if cn = nn.findChildByKind(akind); cn != nil {
+				if cn = nn.anyChildren; cn != nil {
 					break
 				}
 				if np == nil {
@@ -474,7 +495,7 @@ func (r *Router) Find(method, path string, c Context) {
 
 		// Dig further for any, might have an empty value for *, e.g.
 		// serving a directory. Issue #207.
-		if cn = cn.findChildByKind(akind); cn == nil {
+		if cn = cn.anyChildren; cn == nil {
 			return
 		}
 		if h := cn.findHandler(method); h != nil {


Test patch:
diff --git a/router_test.go b/router_test.go
index fca3a79..36b681a 100644
--- a/router_test.go
+++ b/router_test.go
@@ -175,8 +175,10 @@ var (
 		{"GET", "/authorizations", ""},
 		{"GET", "/authorizations/:id", ""},
 		{"POST", "/authorizations", ""},
-		//{"PUT", "/authorizations/clients/:client_id", ""},
-		//{"PATCH", "/authorizations/:id", ""},
+
+		{"PUT", "/authorizations/clients/:client_id", ""},
+		{"PATCH", "/authorizations/:id", ""},
+
 		{"DELETE", "/authorizations/:id", ""},
 		{"GET", "/applications/:client_id/tokens/:access_token", ""},
 		{"DELETE", "/applications/:client_id/tokens", ""},
@@ -198,7 +200,9 @@ var (
 		{"PUT", "/notifications", ""},
 		{"PUT", "/repos/:owner/:repo/notifications", ""},
 		{"GET", "/notifications/threads/:id", ""},
-		//{"PATCH", "/notifications/threads/:id", ""},
+
+		{"PATCH", "/notifications/threads/:id", ""},
+
 		{"GET", "/notifications/threads/:id/subscription", ""},
 		{"PUT", "/notifications/threads/:id/subscription", ""},
 		{"DELETE", "/notifications/threads/:id/subscription", ""},
@@ -221,11 +225,15 @@ var (
 		// Gists
 		{"GET", "/users/:user/gists", ""},
 		{"GET", "/gists", ""},
-		//{"GET", "/gists/public", ""},
-		//{"GET", "/gists/starred", ""},
+
+		{"GET", "/gists/public", ""},
+		{"GET", "/gists/starred", ""},
+
 		{"GET", "/gists/:id", ""},
 		{"POST", "/gists", ""},
-		//{"PATCH", "/gists/:id", ""},
+
+		{"PATCH", "/gists/:id", ""},
+
 		{"PUT", "/gists/:id/star", ""},
 		{"DELETE", "/gists/:id/star", ""},
 		{"GET", "/gists/:id/star", ""},
@@ -237,11 +245,15 @@ var (
 		{"POST", "/repos/:owner/:repo/git/blobs", ""},
 		{"GET", "/repos/:owner/:repo/git/commits/:sha", ""},
 		{"POST", "/repos/:owner/:repo/git/commits", ""},
-		//{"GET", "/repos/:owner/:repo/git/refs/*ref", ""},
+
+		{"GET", "/repos/:owner/:repo/git/refs/*ref", ""},
+
 		{"GET", "/repos/:owner/:repo/git/refs", ""},
 		{"POST", "/repos/:owner/:repo/git/refs", ""},
-		//{"PATCH", "/repos/:owner/:repo/git/refs/*ref", ""},
-		//{"DELETE", "/repos/:owner/:repo/git/refs/*ref", ""},
+
+		{"PATCH", "/repos/:owner/:repo/git/refs/*ref", ""},
+		{"DELETE", "/repos/:owner/:repo/git/refs/*ref", ""},
+
 		{"GET", "/repos/:owner/:repo/git/tags/:sha", ""},
 		{"POST", "/repos/:owner/:repo/git/tags", ""},
 		{"GET", "/repos/:owner/:repo/git/trees/:sha", ""},
@@ -254,22 +266,32 @@ var (
 		{"GET", "/repos/:owner/:repo/issues", ""},
 		{"GET", "/repos/:owner/:repo/issues/:number", ""},
 		{"POST", "/repos/:owner/:repo/issues", ""},
-		//{"PATCH", "/repos/:owner/:repo/issues/:number", ""},
+
+		{"PATCH", "/repos/:owner/:repo/issues/:number", ""},
+
 		{"GET", "/repos/:owner/:repo/assignees", ""},
 		{"GET", "/repos/:owner/:repo/assignees/:assignee", ""},
 		{"GET", "/repos/:owner/:repo/issues/:number/comments", ""},
-		//{"GET", "/repos/:owner/:repo/issues/comments", ""},
-		//{"GET", "/repos/:owner/:repo/issues/comments/:id", ""},
+
+		{"GET", "/repos/:owner/:repo/issues/comments", ""},
+		{"GET", "/repos/:owner/:repo/issues/comments/:id", ""},
+
 		{"POST", "/repos/:owner/:repo/issues/:number/comments", ""},
-		//{"PATCH", "/repos/:owner/:repo/issues/comments/:id", ""},
-		//{"DELETE", "/repos/:owner/:repo/issues/comments/:id", ""},
+
+		{"PATCH", "/repos/:owner/:repo/issues/comments/:id", ""},
+		{"DELETE", "/repos/:owner/:repo/issues/comments/:id", ""},
+
 		{"GET", "/repos/:owner/:repo/issues/:number/events", ""},
-		//{"GET", "/repos/:owner/:repo/issues/events", ""},
-		//{"GET", "/repos/:owner/:repo/issues/events/:id", ""},
+
+		{"GET", "/repos/:owner/:repo/issues/events", ""},
+		{"GET", "/repos/:owner/:repo/issues/events/:id", ""},
+
 		{"GET", "/repos/:owner/:repo/labels", ""},
 		{"GET", "/repos/:owner/:repo/labels/:name", ""},
 		{"POST", "/repos/:owner/:repo/labels", ""},
-		//{"PATCH", "/repos/:owner/:repo/labels/:name", ""},
+
+		{"PATCH", "/repos/:owner/:repo/labels/:name", ""},
+
 		{"DELETE", "/repos/:owner/:repo/labels/:name", ""},
 		{"GET", "/repos/:owner/:repo/issues/:number/labels", ""},
 		{"POST", "/repos/:owner/:repo/issues/:number/labels", ""},
@@ -280,7 +302,9 @@ var (
 		{"GET", "/repos/:owner/:repo/milestones", ""},
 		{"GET", "/repos/:owner/:repo/milestones/:number", ""},
 		{"POST", "/repos/:owner/:repo/milestones", ""},
-		//{"PATCH", "/repos/:owner/:repo/milestones/:number", ""},
+
+		{"PATCH", "/repos/:owner/:repo/milestones/:number", ""},
+
 		{"DELETE", "/repos/:owner/:repo/milestones/:number", ""},
 
 		// Miscellaneous
@@ -296,7 +320,9 @@ var (
 		{"GET", "/users/:user/orgs", ""},
 		{"GET", "/user/orgs", ""},
 		{"GET", "/orgs/:org", ""},
-		//{"PATCH", "/orgs/:org", ""},
+
+		{"PATCH", "/orgs/:org", ""},
+
 		{"GET", "/orgs/:org/members", ""},
 		{"GET", "/orgs/:org/members/:user", ""},
 		{"DELETE", "/orgs/:org/members/:user", ""},
@@ -307,7 +333,9 @@ var (
 		{"GET", "/orgs/:org/teams", ""},
 		{"GET", "/teams/:id", ""},
 		{"POST", "/orgs/:org/teams", ""},
-		//{"PATCH", "/teams/:id", ""},
+
+		{"PATCH", "/teams/:id", ""},
+
 		{"DELETE", "/teams/:id", ""},
 		{"GET", "/teams/:id/members", ""},
 		{"GET", "/teams/:id/members/:user", ""},
@@ -323,17 +351,22 @@ var (
 		{"GET", "/repos/:owner/:repo/pulls", ""},
 		{"GET", "/repos/:owner/:repo/pulls/:number", ""},
 		{"POST", "/repos/:owner/:repo/pulls", ""},
-		//{"PATCH", "/repos/:owner/:repo/pulls/:number", ""},
+
+		{"PATCH", "/repos/:owner/:repo/pulls/:number", ""},
+
 		{"GET", "/repos/:owner/:repo/pulls/:number/commits", ""},
 		{"GET", "/repos/:owner/:repo/pulls/:number/files", ""},
 		{"GET", "/repos/:owner/:repo/pulls/:number/merge", ""},
 		{"PUT", "/repos/:owner/:repo/pulls/:number/merge", ""},
 		{"GET", "/repos/:owner/:repo/pulls/:number/comments", ""},
-		//{"GET", "/repos/:owner/:repo/pulls/comments", ""},
-		//{"GET", "/repos/:owner/:repo/pulls/comments/:number", ""},
+
+		{"GET", "/repos/:owner/:repo/pulls/comments", ""},
+		{"GET", "/repos/:owner/:repo/pulls/comments/:number", ""},
+
 		{"PUT", "/repos/:owner/:repo/pulls/:number/comments", ""},
-		//{"PATCH", "/repos/:owner/:repo/pulls/comments/:number", ""},
-		//{"DELETE", "/repos/:owner/:repo/pulls/comments/:number", ""},
+
+		{"PATCH", "/repos/:owner/:repo/pulls/comments/:number", ""},
+		{"DELETE", "/repos/:owner/:repo/pulls/comments/:number", ""},
 
 		// Repositories
 		{"GET", "/user/repos", ""},
@@ -343,7 +376,9 @@ var (
 		{"POST", "/user/repos", ""},
 		{"POST", "/orgs/:org/repos", ""},
 		{"GET", "/repos/:owner/:repo", ""},
-		//{"PATCH", "/repos/:owner/:repo", ""},
+
+		{"PATCH", "/repos/:owner/:repo", ""},
+
 		{"GET", "/repos/:owner/:repo/contributors", ""},
 		{"GET", "/repos/:owner/:repo/languages", ""},
 		{"GET", "/repos/:owner/:repo/teams", ""},
@@ -359,19 +394,26 @@ var (
 		{"GET", "/repos/:owner/:repo/commits/:sha/comments", ""},
 		{"POST", "/repos/:owner/:repo/commits/:sha/comments", ""},
 		{"GET", "/repos/:owner/:repo/comments/:id", ""},
-		//{"PATCH", "/repos/:owner/:repo/comments/:id", ""},
+
+		{"PATCH", "/repos/:owner/:repo/comments/:id", ""},
+
 		{"DELETE", "/repos/:owner/:repo/comments/:id", ""},
 		{"GET", "/repos/:owner/:repo/commits", ""},
 		{"GET", "/repos/:owner/:repo/commits/:sha", ""},
 		{"GET", "/repos/:owner/:repo/readme", ""},
+
 		//{"GET", "/repos/:owner/:repo/contents/*path", ""},
 		//{"PUT", "/repos/:owner/:repo/contents/*path", ""},
 		//{"DELETE", "/repos/:owner/:repo/contents/*path", ""},
-		//{"GET", "/repos/:owner/:repo/:archive_format/:ref", ""},
+
+		{"GET", "/repos/:owner/:repo/:archive_format/:ref", ""},
+
 		{"GET", "/repos/:owner/:repo/keys", ""},
 		{"GET", "/repos/:owner/:repo/keys/:id", ""},
 		{"POST", "/repos/:owner/:repo/keys", ""},
-		//{"PATCH", "/repos/:owner/:repo/keys/:id", ""},
+
+		{"PATCH", "/repos/:owner/:repo/keys/:id", ""},
+
 		{"DELETE", "/repos/:owner/:repo/keys/:id", ""},
 		{"GET", "/repos/:owner/:repo/downloads", ""},
 		{"GET", "/repos/:owner/:repo/downloads/:id", ""},
@@ -381,14 +423,18 @@ var (
 		{"GET", "/repos/:owner/:repo/hooks", ""},
 		{"GET", "/repos/:owner/:repo/hooks/:id", ""},
 		{"POST", "/repos/:owner/:repo/hooks", ""},
-		//{"PATCH", "/repos/:owner/:repo/hooks/:id", ""},
+
+		{"PATCH", "/repos/:owner/:repo/hooks/:id", ""},
+
 		{"POST", "/repos/:owner/:repo/hooks/:id/tests", ""},
 		{"DELETE", "/repos/:owner/:repo/hooks/:id", ""},
 		{"POST", "/repos/:owner/:repo/merges", ""},
 		{"GET", "/repos/:owner/:repo/releases", ""},
 		{"GET", "/repos/:owner/:repo/releases/:id", ""},
 		{"POST", "/repos/:owner/:repo/releases", ""},
-		//{"PATCH", "/repos/:owner/:repo/releases/:id", ""},
+
+		{"PATCH", "/repos/:owner/:repo/releases/:id", ""},
+
 		{"DELETE", "/repos/:owner/:repo/releases/:id", ""},
 		{"GET", "/repos/:owner/:repo/releases/:id/assets", ""},
 		{"GET", "/repos/:owner/:repo/stats/contributors", ""},
@@ -412,7 +458,9 @@ var (
 		// Users
 		{"GET", "/users/:user", ""},
 		{"GET", "/user", ""},
-		//{"PATCH", "/user", ""},
+
+		{"PATCH", "/user", ""},
+
 		{"GET", "/users", ""},
 		{"GET", "/user/emails", ""},
 		{"POST", "/user/emails", ""},
@@ -429,7 +477,9 @@ var (
 		{"GET", "/user/keys", ""},
 		{"GET", "/user/keys/:id", ""},
 		{"POST", "/user/keys", ""},
-		//{"PATCH", "/user/keys/:id", ""},
+
+		{"PATCH", "/user/keys/:id", ""},
+
 		{"DELETE", "/user/keys/:id", ""},
 	}
 
@@ -500,6 +550,88 @@ var (
 		{"DELETE", "/moments/:id", ""},
 	}
 
+	paramAndAnyAPI = []*Route{
+		{"GET", "/root/:first/foo/*", ""},
+		{"GET", "/root/:first/:second/*", ""},
+		{"GET", "/root/:first/bar/:second/*", ""},
+		{"GET", "/root/:first/qux/:second/:third/:fourth", ""},
+		{"GET", "/root/:first/qux/:second/:third/:fourth/*", ""},
+		{"GET", "/root/*", ""},
+
+		{"POST", "/root/:first/foo/*", ""},
+		{"POST", "/root/:first/:second/*", ""},
+		{"POST", "/root/:first/bar/:second/*", ""},
+		{"POST", "/root/:first/qux/:second/:third/:fourth", ""},
+		{"POST", "/root/:first/qux/:second/:third/:fourth/*", ""},
+		{"POST", "/root/*", ""},
+
+		{"PUT", "/root/:first/foo/*", ""},
+		{"PUT", "/root/:first/:second/*", ""},
+		{"PUT", "/root/:first/bar/:second/*", ""},
+		{"PUT", "/root/:first/qux/:second/:third/:fourth", ""},
+		{"PUT", "/root/:first/qux/:second/:third/:fourth/*", ""},
+		{"PUT", "/root/*", ""},
+
+		{"DELETE", "/root/:first/foo/*", ""},
+		{"DELETE", "/root/:first/:second/*", ""},
+		{"DELETE", "/root/:first/bar/:second/*", ""},
+		{"DELETE", "/root/:first/qux/:second/:third/:fourth", ""},
+		{"DELETE", "/root/:first/qux/:second/:third/:fourth/*", ""},
+		{"DELETE", "/root/*", ""},
+	}
+
+	paramAndAnyAPIToFind = []*Route{
+		{"GET", "/root/one/foo/after/the/asterisk", ""},
+		{"GET", "/root/one/foo/path/after/the/asterisk", ""},
+		{"GET", "/root/one/two/path/after/the/asterisk", ""},
+		{"GET", "/root/one/bar/two/after/the/asterisk", ""},
+		{"GET", "/root/one/qux/two/three/four", ""},
+		{"GET", "/root/one/qux/two/three/four/after/the/asterisk", ""},
+
+		{"POST", "/root/one/foo/after/the/asterisk", ""},
+		{"POST", "/root/one/foo/path/after/the/asterisk", ""},
+		{"POST", "/root/one/two/path/after/the/asterisk", ""},
+		{"POST", "/root/one/bar/two/after/the/asterisk", ""},
+		{"POST", "/root/one/qux/two/three/four", ""},
+		{"POST", "/root/one/qux/two/three/four/after/the/asterisk", ""},
+
+		{"PUT", "/root/one/foo/after/the/asterisk", ""},
+		{"PUT", "/root/one/foo/path/after/the/asterisk", ""},
+		{"PUT", "/root/one/two/path/after/the/asterisk", ""},
+		{"PUT", "/root/one/bar/two/after/the/asterisk", ""},
+		{"PUT", "/root/one/qux/two/three/four", ""},
+		{"PUT", "/root/one/qux/two/three/four/after/the/asterisk", ""},
+
+		{"DELETE", "/root/one/foo/after/the/asterisk", ""},
+		{"DELETE", "/root/one/foo/path/after/the/asterisk", ""},
+		{"DELETE", "/root/one/two/path/after/the/asterisk", ""},
+		{"DELETE", "/root/one/bar/two/after/the/asterisk", ""},
+		{"DELETE", "/root/one/qux/two/three/four", ""},
+		{"DELETE", "/root/one/qux/two/three/four/after/the/asterisk", ""},
+	}
+
+	missesAPI = []*Route{
+		{"GET", "/missOne", ""},
+		{"GET", "/miss/two", ""},
+		{"GET", "/miss/three/levels", ""},
+		{"GET", "/miss/four/levels/nooo", ""},
+
+		{"POST", "/missOne", ""},
+		{"POST", "/miss/two", ""},
+		{"POST", "/miss/three/levels", ""},
+		{"POST", "/miss/four/levels/nooo", ""},
+
+		{"PUT", "/missOne", ""},
+		{"PUT", "/miss/two", ""},
+		{"PUT", "/miss/three/levels", ""},
+		{"PUT", "/miss/four/levels/nooo", ""},
+
+		{"DELETE", "/missOne", ""},
+		{"DELETE", "/miss/two", ""},
+		{"DELETE", "/miss/three/levels", ""},
+		{"DELETE", "/miss/four/levels/nooo", ""},
+	}
+
 	// handlerHelper created a function that will set a context key for assertion
 	handlerHelper = func(key string, value int) func(c Context) error {
 		return func(c Context) error {
@@ -1332,7 +1464,7 @@ func TestRouterPanicWhenParamNoRootOnlyChildsFailsFind(t *testing.T) {
 	assert.Equal(t, http.StatusNotFound, he.Code)
 }
 
-func benchmarkRouterRoutes(b *testing.B, routes []*Route) {
+func benchmarkRouterRoutes(b *testing.B, routes []*Route, routesToFind []*Route) {
 	e := New()
 	r := e.router
 	b.ReportAllocs()
@@ -1344,9 +1476,12 @@ func benchmarkRouterRoutes(b *testing.B, routes []*Route) {
 		})
 	}
 
+	// Routes adding are performed just once, so it doesn't make sense to see that in the benchmark
+	b.ResetTimer()
+
 	// Find routes
 	for i := 0; i < b.N; i++ {
-		for _, route := range gitHubAPI {
+		for _, route := range routesToFind {
 			c := e.pool.Get().(*context)
 			r.Find(route.Method, route.Path, c)
 			e.pool.Put(c)
@@ -1355,28 +1490,56 @@ func benchmarkRouterRoutes(b *testing.B, routes []*Route) {
 }
 
 func BenchmarkRouterStaticRoutes(b *testing.B) {
-	benchmarkRouterRoutes(b, staticRoutes)
+	benchmarkRouterRoutes(b, staticRoutes, staticRoutes)
+}
+
+func BenchmarkRouterStaticRoutesMisses(b *testing.B) {
+	benchmarkRouterRoutes(b, staticRoutes, missesAPI)
 }
 
 func BenchmarkRouterGitHubAPI(b *testing.B) {
-	benchmarkRouterRoutes(b, gitHubAPI)
+	benchmarkRouterRoutes(b, gitHubAPI, gitHubAPI)
+}
+
+func BenchmarkRouterGitHubAPIMisses(b *testing.B) {
+	benchmarkRouterRoutes(b, gitHubAPI, missesAPI)
 }
 
 func BenchmarkRouterParseAPI(b *testing.B) {
-	benchmarkRouterRoutes(b, parseAPI)
+	benchmarkRouterRoutes(b, parseAPI, parseAPI)
+}
+
+func BenchmarkRouterParseAPIMisses(b *testing.B) {
+	benchmarkRouterRoutes(b, parseAPI, missesAPI)
 }
 
 func BenchmarkRouterGooglePlusAPI(b *testing.B) {
-	benchmarkRouterRoutes(b, googlePlusAPI)
+	benchmarkRouterRoutes(b, googlePlusAPI, googlePlusAPI)
+}
+
+func BenchmarkRouterGooglePlusAPIMisses(b *testing.B) {
+	benchmarkRouterRoutes(b, googlePlusAPI, missesAPI)
+}
+
+func BenchmarkRouterParamsAndAnyAPI(b *testing.B) {
+	benchmarkRouterRoutes(b, paramAndAnyAPI, paramAndAnyAPIToFind)
 }
 
 func (n *node) printTree(pfx string, tail bool) {
 	p := prefix(tail, pfx, "└── ", "├── ")
 	fmt.Printf("%s%s, %p: type=%d, parent=%p, handler=%v, pnames=%v\n", p, n.prefix, n, n.kind, n.parent, n.methodHandler, n.pnames)
 
-	children := n.children
-	l := len(children)
 	p = prefix(tail, pfx, "    ", "│   ")
+
+	children := n.staticChildrens
+	l := len(children)
+
+	if n.paramChildren != nil {
+		n.paramChildren.printTree(p, n.anyChildren == nil && l == 0)
+	}
+	if n.anyChildren != nil {
+		n.anyChildren.printTree(p, l == 0)
+	}
 	for i := 0; i < l-1; i++ {
 		children[i].printTree(p, false)
 	}