京公网安备11010502063487号常有人说 Gin 的路由“把常用的路由排在前面”。这篇用逐条注册看 indices 怎么重排,再对 20 万次请求前后的整棵树做对比,最后量出排在第 26 位和第 1 位到底差多少纳秒,看这个优化究竟优化了什么。
tree.go(Gin v1.12.0):
111 | func (n *node) incrementChildPrio(pos int) int {
112 | cs := n.children
113 | cs[pos].priority++
114 | prio := cs[pos].priority
115 |
116 | // Adjust position (move to front)
117 | newPos := pos
118 | for ; newPos > 0 && cs[newPos-1].priority < prio; newPos-- {
119 | // Swap node positions
120 | cs[newPos-1], cs[newPos] = cs[newPos], cs[newPos-1]
121 | }
122 |
123 | // Build new index char string
124 | if newPos != pos {
125 | n.indices = n.indices[:newPos] + // Unchanged prefix, might be empty
126 | n.indices[pos:pos+1] + // The index char we move
127 | n.indices[newPos:pos] + n.indices[pos+1:] // Rest without char at 'pos'
128 | }
129 |
130 | return newPos
131 | }
132 |
133 | // addRoute adds a node with the given handle to the path.
134 | // Not concurrency-safe!
135 | func (n *node) addRoute(path string, handlers HandlersChain) {每注册一条经过某个子节点的路由,incrementChildPrio 先把它的 priority 加 1,再和前面的兄弟比:前一个兄弟的 priority 严格小于它就换位置,并同步改写 indices。这一步只在注册时发生。
注册 /a/1 → "/a/1" [root prio=1 indices=""] handlers=1 full="/a/1"
注册 /b/1 → "/" [root prio=2 indices="ab"]
注册 /c/1 → "/" [root prio=3 indices="abc"]
注册 /b/2 → "/" [root prio=4 indices="bac"]
注册 /c/2 → "/" [root prio=5 indices="bca"]
注册 /c/3 → "/" [root prio=6 indices="cba"]
注册 /c/4 → "/" [root prio=7 indices="cba"]
注册 /a/2 → "/" [root prio=8 indices="cba"]
注册 /a/3 → "/" [root prio=9 indices="cab"]
注册 /a/4 → "/" [root prio=10 indices="cab"]
注册 /a/5 → "/" [root prio=11 indices="acb"]
最终的树:
"/" [root prio=11 indices="acb"]
"a/" [static prio=5 indices="12345"]
"1" [static prio=1 indices=""] handlers=1 full="/a/1"
"2" [static prio=1 indices=""] handlers=1 full="/a/2"
"3" [static prio=1 indices=""] handlers=1 full="/a/3"
"4" [static prio=1 indices=""] handlers=1 full="/a/4"
"5" [static prio=1 indices=""] handlers=1 full="/a/5"
"c/" [static prio=4 indices="1234"]
"1" [static prio=1 indices=""] handlers=1 full="/c/1"
"2" [static prio=1 indices=""] handlers=1 full="/c/2"
"3" [static prio=1 indices=""] handlers=1 full="/c/3"
"4" [static prio=1 indices=""] handlers=1 full="/c/4"
"b/" [static prio=2 indices="12"]
"1" [static prio=1 indices=""] handlers=1 full="/b/1"
"2" [static prio=1 indices=""] handlers=1 full="/b/2"indices 记录的是兄弟节点按 priority 从大到小排列的首字节。注册 /b/2 让 b 的 2 条超过 a 的 1 条(abc → bac);注册 /c/3 让 c 的 3 条排到最前(cba);/a/3 让 a 的 3 条超过 b 的 2 条(cab);最后 /a/5 让 a 的 5 条超过 c 的 4 条(acb)。平局时(如 /c/4、/a/2 之后)顺序保持不变。
请求前,根节点和它的两个孩子:
"/" [root prio=21 indices="az"]
"a/" [static prio=20 indices="1023456789"]
"z/hot" [static prio=1 indices=""] handlers=1 full="/z/hot"
200000 次 GET /z/hot 之后整棵树( 23 个节点)与之前逐字节相同: true文章标题里的“常用路由”容易误导:Gin 并不统计访问。priority 是子树里的路由条数,假设“路由多的分支更可能被访问”。实验里对 /z/hot 发了 20 万次请求,整棵树和请求前逐字节相同,z 仍然排在 a(20 条路由)后面。
树 A 的根: "/" [root prio=26 indices="abcdefghijklmnopqrstuvwxyz"]
树 B 的根: "/" [root prio=35 indices="zabcdefghijklmnopqrstuvwxy"]
第 1 轮
A: GET /z/item0(z 在第 26 位) 中位 32.6 ns/op(最小 32.5 / 最大 32.7)
B: GET /z/item0(z 在第 1 位) 中位 27.7 ns/op(最小 27.6 / 最大 27.9)
A: GET /a/item0(a 在第 1 位) 中位 24.3 ns/op(最小 24.2 / 最大 24.5)
B: GET /a/item0(a 在第 2 位) 中位 24.5 ns/op(最小 24.4 / 最大 24.6)
第 2 轮
A: GET /z/item0(z 在第 26 位) 中位 32.6 ns/op(最小 32.4 / 最大 33.2)
B: GET /z/item0(z 在第 1 位) 中位 27.7 ns/op(最小 27.5 / 最大 27.8)
A: GET /a/item0(a 在第 1 位) 中位 24.3 ns/op(最小 24.1 / 最大 24.3)
B: GET /a/item0(a 在第 2 位) 中位 24.4 ns/op(最小 24.4 / 最大 24.5)查找时用请求路径的下一个字节在 indices 里线性扫描。两棵形状相同的树,查同一条路由,它在 indices 里排第 26 位比排第 1 位多约 8 ns,折合每个兄弟 0.3 ns 左右。一次完整的 ServeHTTP 本身只有二三十纳秒,所以兄弟多的时候这个顺序才有一点意义;树 B 里 z 的数字(27.7 ns)比树 A 的 a(24.3 ns)高,是因为 z 子树里多了一层(item0…item9),不是顺序的问题。