Use a sync.Pool to recycle Param slices
Zero allocations (amortized)!
diff --git a/router.go b/router.go
index 155b871..bdee266 100644
--- a/router.go
+++ b/router.go
@@ -78,6 +78,7 @@
import (
"net/http"
+ "sync"
)
// Handle is a function that can be registered to a route to handle HTTP
@@ -112,6 +113,9 @@
type Router struct {
trees map[string]*node
+ // pool to recycle Param slices
+ psPool sync.Pool
+
// Enables automatic redirection if the current route can't be matched but a
// handler for the path with (without) the trailing slash exists.
// For example if /foo/ is requested but a route only exists for /foo, the
@@ -168,6 +172,24 @@
}
}
+func (r *Router) paramsGet() *Params {
+ if vp := r.psPool.Get(); vp != nil {
+ psp := vp.(*Params)
+ *psp = (*psp)[0:0] // reset slice
+ return psp
+ }
+
+ // Allocate new slice if none is available
+ ps := make(Params, 0, 20) // TODO
+ return &ps
+}
+
+func (r *Router) paramsRecycle(psp *Params) {
+ if psp != nil {
+ r.psPool.Put(psp)
+ }
+}
+
// GET is a shortcut for router.Handle("GET", path, handle)
func (r *Router) GET(path string, handle Handle) {
r.Handle("GET", path, handle)
@@ -281,7 +303,13 @@
// the same path with an extra / without the trailing slash should be performed.
func (r *Router) Lookup(method, path string) (Handle, Params, bool) {
if root := r.trees[method]; root != nil {
- return root.getValue(path)
+ psp := r.paramsGet()
+ h, tsr := root.getValue(path, psp) // TODO
+ if h != nil {
+ return h, *psp, tsr
+ }
+ r.paramsRecycle(psp)
+ return nil, nil, tsr
}
return nil, nil, false
}
@@ -294,39 +322,44 @@
if root := r.trees[req.Method]; root != nil {
path := req.URL.Path
-
- if handle, ps, tsr := root.getValue(path); handle != nil {
- handle(w, req, ps)
+ psp := r.paramsGet()
+ if handle, tsr := root.getValue(path, psp); handle != nil {
+ handle(w, req, *psp)
+ r.paramsRecycle(psp)
return
- } else if req.Method != "CONNECT" && path != "/" {
- code := 301 // Permanent redirect, request with GET method
- if req.Method != "GET" {
- // Temporary redirect, request with same method
- // As of Go 1.3, Go does not support status code 308.
- code = 307
- }
+ } else {
+ r.paramsRecycle(psp)
- if tsr && r.RedirectTrailingSlash {
- if len(path) > 1 && path[len(path)-1] == '/' {
- req.URL.Path = path[:len(path)-1]
- } else {
- req.URL.Path = path + "/"
+ if req.Method != "CONNECT" && path != "/" {
+ code := 301 // Permanent redirect, request with GET method
+ if req.Method != "GET" {
+ // Temporary redirect, request with same method
+ // As of Go 1.3, Go does not support status code 308.
+ code = 307
}
- http.Redirect(w, req, req.URL.String(), code)
- return
- }
- // Try to fix the request path
- if r.RedirectFixedPath {
- fixedPath, found := root.findCaseInsensitivePath(
- CleanPath(path),
- r.RedirectTrailingSlash,
- )
- if found {
- req.URL.Path = string(fixedPath)
+ if tsr && r.RedirectTrailingSlash {
+ if len(path) > 1 && path[len(path)-1] == '/' {
+ req.URL.Path = path[:len(path)-1]
+ } else {
+ req.URL.Path = path + "/"
+ }
http.Redirect(w, req, req.URL.String(), code)
return
}
+
+ // Try to fix the request path
+ if r.RedirectFixedPath {
+ fixedPath, found := root.findCaseInsensitivePath(
+ CleanPath(path),
+ r.RedirectTrailingSlash,
+ )
+ if found {
+ req.URL.Path = string(fixedPath)
+ http.Redirect(w, req, req.URL.String(), code)
+ return
+ }
+ }
}
}
}
@@ -339,7 +372,7 @@
continue
}
- handle, _, _ := r.trees[method].getValue(req.URL.Path)
+ handle, _ := r.trees[method].getValue(req.URL.Path, nil)
if handle != nil {
if r.MethodNotAllowed != nil {
r.MethodNotAllowed(w, req)
diff --git a/router_test.go b/router_test.go
index 9dc6296..867c632 100644
--- a/router_test.go
+++ b/router_test.go
@@ -10,6 +10,7 @@
"net/http"
"net/http/httptest"
"reflect"
+ "runtime"
"testing"
)
@@ -49,9 +50,9 @@
router := New()
routed := false
+ want := Params{Param{"name", "gopher"}}
router.Handle("GET", "/user/:name", func(w http.ResponseWriter, r *http.Request, ps Params) {
routed = true
- want := Params{Param{"name", "gopher"}}
if !reflect.DeepEqual(ps, want) {
t.Fatalf("wrong wildcard values: want %v, got %v", want, ps)
}
@@ -67,6 +68,42 @@
}
}
+func TestRouterZeroAlloc(t *testing.T) {
+ runs := 1000
+ m := new(runtime.MemStats)
+
+ router := New()
+ router.Handle("GET", "/user/:name", func(w http.ResponseWriter, r *http.Request, ps Params) {
+ if val := ps.ByName("name"); val != "gordon" {
+ t.Errorf("Expected param value 'gordon', got '%s'", val)
+ }
+ })
+ r, _ := http.NewRequest("GET", "/user/gordon", nil)
+
+ w := new(mockResponseWriter)
+ u := r.URL
+ rq := u.RawQuery
+ r.RequestURI = u.RequestURI()
+
+ // before
+ runtime.GC()
+ runtime.ReadMemStats(m)
+ mallocs := 0 - m.Mallocs
+
+ for i := 0; i < runs; i++ {
+ u.RawQuery = rq
+ router.ServeHTTP(w, r)
+ }
+
+ // after
+ runtime.ReadMemStats(m)
+ mallocs += m.Mallocs
+
+ if aa := int(mallocs / uint64(runs)); aa > 0 {
+ t.Fatalf("Amortized allocations: %d", aa)
+ }
+}
+
type handlerStruct struct {
handeled *bool
}
diff --git a/tree.go b/tree.go
index a15bc2c..3ff6394 100644
--- a/tree.go
+++ b/tree.go
@@ -316,7 +316,7 @@
// If no handle can be found, a TSR (trailing slash redirect) recommendation is
// made if a handle exists with an extra (without the) trailing slash for the
// given path.
-func (n *node) getValue(path string) (handle Handle, p Params, tsr bool) {
+func (n *node) getValue(path string, psp *Params) (handle Handle, tsr bool) {
walk: // Outer loop for walking the tree
for {
if len(path) > len(n.path) {
@@ -353,14 +353,12 @@
}
// save param value
- if p == nil {
- // lazy allocation
- p = make(Params, 0, n.maxParams)
+ if psp != nil {
+ i := len(*psp)
+ *psp = (*psp)[:i+1] // expand slice within preallocated capacity
+ (*psp)[i].Key = n.path[1:]
+ (*psp)[i].Value = path[:end]
}
- i := len(p)
- p = p[:i+1] // expand slice within preallocated capacity
- p[i].Key = n.path[1:]
- p[i].Value = path[:end]
// we need to go deeper!
if end < len(path) {
@@ -388,14 +386,12 @@
case catchAll:
// save param value
- if p == nil {
- // lazy allocation
- p = make(Params, 0, n.maxParams)
+ if psp != nil {
+ i := len(*psp)
+ *psp = (*psp)[:i+1] // expand slice within preallocated capacity
+ (*psp)[i].Key = n.path[2:]
+ (*psp)[i].Value = path
}
- i := len(p)
- p = p[:i+1] // expand slice within preallocated capacity
- p[i].Key = n.path[2:]
- p[i].Value = path
handle = n.handle
return
diff --git a/tree_test.go b/tree_test.go
index 64f26d1..187b349 100644
--- a/tree_test.go
+++ b/tree_test.go
@@ -38,9 +38,15 @@
ps Params
}
+func getParams() *Params {
+ ps := make(Params, 0, 20)
+ return &ps
+}
+
func checkRequests(t *testing.T, tree *node, requests testRequests) {
for _, request := range requests {
- handler, ps, _ := tree.getValue(request.path)
+ psp := getParams()
+ handler, _ := tree.getValue(request.path, psp)
if handler == nil {
if !request.nilHandler {
@@ -55,7 +61,7 @@
}
}
- if !reflect.DeepEqual(ps, request.ps) {
+ if !reflect.DeepEqual(*psp, request.ps) && (len(request.ps) > 0 || len(*psp) > 0) {
t.Errorf("Params mismatch for route '%s'", request.path)
}
}
@@ -426,7 +432,7 @@
"/doc/",
}
for _, route := range tsrRoutes {
- handler, _, tsr := tree.getValue(route)
+ handler, tsr := tree.getValue(route, nil)
if handler != nil {
t.Fatalf("non-nil handler for TSR route '%s", route)
} else if !tsr {
@@ -443,7 +449,7 @@
"/api/world/abc",
}
for _, route := range noTsrRoutes {
- handler, _, tsr := tree.getValue(route)
+ handler, tsr := tree.getValue(route, nil)
if handler != nil {
t.Fatalf("non-nil handler for No-TSR route '%s", route)
} else if tsr {
@@ -595,7 +601,7 @@
// normal lookup
recv := catchPanic(func() {
- tree.getValue("/test")
+ tree.getValue("/test", nil)
})
if rs, ok := recv.(string); !ok || rs != panicMsg {
t.Fatalf("Expected panic '"+panicMsg+"', got '%v'", recv)
