V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Nazz
V2EX  ›  程序员

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

  •  
  •   Nazz · 2023-02-13 13:19:34 +08:00 · 1596 次点击
    这是一个创建于 409 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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

    4 条回复    2023-02-13 14:08:52 +08:00
    missdeer
        1
    missdeer  
       2023-02-13 13:41:09 +08:00
    好像之前看过一个评测说 gin 算是比较慢的梯队里的,连 beego 都比它快得多。。
    Nazz
        2
    Nazz  
    OP
       2023-02-13 13:49:46 +08:00
    @missdeer 除非 beego 用了非 net/http 实现, 否则不可能, gin 性能和 裸 http 差不多.
    R18
        3
    R18  
       2023-02-13 13:52:19 +08:00 via Android
    有和 echo 的对比吗,毕竟 gin 已经很"老"了
    Nazz
        4
    Nazz  
    OP
       2023-02-13 14:08:52 +08:00
    @R18 echo 出现时间和 gin 差不多吧. 没对比过 echo, 但是我和 bare net/http 对比过 RPS
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1402 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 17:29 · PVG 01:29 · LAX 10:29 · JFK 13:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.