比 GIN 更快的路径匹配算法来了

在uRouter v1.2.4版本中, 大幅改进了路由映射性能, 零开销路径匹配, 成为了速度最快的 net/http 框架之一.

Benchmark

uRouter

goos: darwin
goarch: arm64
pkg: github.com/lxzan/uRouter
BenchmarkOneRoute-8             	77647704	        13.53 ns/op	       0 B/op	       0 allocs/op
BenchmarkOneRouteDynamic-8      	34728837	        34.69 ns/op	       0 B/op	       0 allocs/op
BenchmarkRecoveryMiddleware-8   	70822222	        16.99 ns/op	       0 B/op	       0 allocs/op
Benchmark5Params-8              	15952770	        73.23 ns/op	       0 B/op	       0 allocs/op
BenchmarkOneRouteJSON-8         	89840808	        13.39 ns/op	       0 B/op	       0 allocs/op
Benchmark404-8                  	81540667	        14.89 ns/op	       0 B/op	       0 allocs/op
Benchmark404Many-8              	35411809	        34.11 ns/op	       0 B/op	       0 allocs/op
PASS

goos: darwin
goarch: arm64
pkg: github.com/gin-gonic/gin
BenchmarkOneRoute-8             	45460980	        26.13 ns/op	       0 B/op	       0 allocs/op
BenchmarkRecoveryMiddleware-8   	38337534	        31.00 ns/op	       0 B/op	       0 allocs/op
Benchmark5Params-8              	18889320	        63.42 ns/op	       0 B/op	       0 allocs/op
BenchmarkOneRouteJSON-8         	 7542141	       162.7 ns/op	      48 B/op	       3 allocs/op
Benchmark404-8                  	29467527	        43.23 ns/op	       0 B/op	       0 allocs/op
Benchmark404Many-8              	27458932	        43.92 ns/op	       0 B/op	       0 allocs/op
PASS

得益于`map`, 大部分测试项目都比`gin`快. `uRouter`的路由算法采用动静分离模式, 静态路由使用`map`, 动态路由使用`trie`.

在 v1.2.4 版本中, 主要改进如下:

零开销分割字符串
Get 方法改递归为循环

func FastSplit(str string, f func(segment string) bool) {
	var n = len(str)
	var i = 1
	var j = i
	for k := i; k < n; k++ {
		if str[k] == SeparatorByte || k == n-1 {
			if k == n-1 {
				j++
			}
			if !f(str[i:j]) {
				return
			}
			i = k + 1
			j = i
		} else {
			j++
		}
	}
}

func (c *routeTree) Get(path string) (*apiHandler, bool) {
	var tree = c
	var expected = 0
	var actual = 0

	FastSplit(path, func(str string) bool {
		expected++
		if v, ok := tree.Children[str]; ok {
			tree = v
			actual++
			return true
		}
		if v, ok := tree.Children["*"]; ok {
			tree = v
			actual++
			return true
		}
		return false
	})

	if expected == actual {
		return tree.Value, tree.Value != nil
	}
	return nil, false
}

链接: https://github.com/lxzan/uRouter/blob/main/matcher.go