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)