京公网安备11010502063487号路由树的耗时和路由条数有什么关系?这篇把路由数从 10 条加到 10 万条,分别量注册耗时、内存、随机命中一条路由和 404 的耗时,再拆开看变慢到底是树变深还是别的原因,并和 Go 的 map 精确匹配做个对照。
[static 路由]
路由数 注册耗时 节点数 堆增量 命中 ns/op 404 ns/op
10 0.0 ms 11 0.0 MB 41.2 37.6
100 0.1 ms 110 0.0 MB 52.3 37.6
1000 0.4 ms 1100 0.2 MB 65.9 37.3
10000 4.5 ms 11000 2.3 MB 89.1 37.7
100000 43.5 ms 110000 22.8 MB 122.7 37.7
[param 路由]
路由数 注册耗时 节点数 堆增量 命中 ns/op 404 ns/op
10 0.0 ms 21 0.0 MB 45.7 37.1
100 0.1 ms 210 0.0 MB 58.6 37.2
1000 0.5 ms 2100 0.3 MB 77.4 36.9
10000 5.1 ms 21000 3.3 MB 102.2 37.3
100000 53.8 ms 210000 33.2 MB 135.8 37.1
[对照:Go 的 map[string]func 精确匹配,只能匹配静态路径,不能取参数]
10 条 map 查找 7.0 ns/op
1000 条 map 查找 7.9 ns/op
100000 条 map 查找 12.2 ns/op匹配耗时不是常数,但增长得很慢:路由数增加 1 万倍,命中一条路由的耗时约 3 倍(静态 41 → 123 ns,带参数 46 → 136 ns)。注册 10 万条路由只要几十毫秒,堆增加二三十 MB(静态路由 110000 个节点,带参数的 210000 个)。作为对照,Go 的 map 精确匹配是 7 → 12 ns,但它只能匹配完整的静态路径,取不了参数,也做不了前缀共享。
404 的耗时恒定约 37 ns,是因为这条测试路径(/api/v1/nothing/list)在树的前几层就匹配失败,不能代表所有 404 的情形。
1000 条路由:树最深 4 层;/api/v1/resource0/list 在第 2 层,最后一条 /api/v1/resource999/list 在第 4 层
重复查同一条:39.1 ns/op;随机查 1024 条轮流:66.2 ns/op
100000 条路由:树最深 6 层;/api/v1/resource0/list 在第 2 层,最后一条 /api/v1/resource99999/list 在第 6 层
重复查同一条:44.0 ns/op;随机查 1024 条轮流:122.9 ns/op树的深度只从 4 层增加到 6 层。同一棵树里重复查同一条路由,耗时几乎不变(39.1 → 44.0 ns),可见深度增加本身只贡献了几纳秒;而轮流查 1024 条不同的路径时从 66.2 ns 变成 122.9 ns,差距主要出现在访问分散的时候。我的判断是 CPU 缓存和分支预测的影响(树大了以后每次访问的节点更分散),但我没有用性能计数器验证这个解释,所以它是推测。