[PERF] 0-kvspace: art_scan 从整树根全扫 → 下降到前缀子树根(递归/op密集 case 50~64% 指令的唯一大头)

[miaobyte]

现象

对 op 密集/深递归 benchmark 做 callgrind trace,三个 case 签名一致,art_scan 是绝对第一大头:

函数	fib(22)	nqueens(6)	binary_search(200)
art_scan	63.66%	59.47%	50.10%
sbo_find_alloc	10.28%	12.27%	14.37%
blockdata_offset+block_offset	7.84%	11.89%	10.34%
__memcmp_avx2(前缀过滤)	—	3.94%	3.86%

art_scan 吃掉全部指令 50~64%,它拖出的 malloc(每次 List 分配 4096 指针数组 + 逐叶 strdup + free)再占 1825%。

根因(逐行坐实)

1. 每次 kvlang 函数调用 = 2× DelTree:handle_call 建帧前删旧帧(runtime/src/kvcpu.c:383)+ handle_return 删帧(kvcpu.c:279)。
2. kvspaceShmDeltree → kvspaceShmList(逐层递归)。
3. 致命点 kvspace-c/src/kvspace.c:1935 kvspaceShmList:

   art_scan(kv, kv->hdr->art_root, buf, 0, ..., pfx, plen, &out, &n);

   从整树根 art_root 做 DFS 遍历整棵 ART 树,仅在每个叶子处 memcmp 前缀过滤(kvspace.c:700)。cost = O(全树 key 数)/次,与目标子树大小无关——常驻的 stdlib /lib 树很大,每次扫都付全额。
4. fib(22):kvspaceShmList 被调 186,007 次(≈3.25×/call),每次全树扫 → 39.8B 指令里 25.3B 花在 art_scan。

op 密集/深递归 case 差距最大(fib 7336× / nqueens 3917× / binary_search 2309× 慢于 Rust)正因函数调用最多 → 全树扫次数最多,与 art_scan 主导度线性正相关。

read_index_names(memindex · 目录)已短路避开全扫,但 / 前缀帧目录仍走全 art_scan——这正是要补的口子。

修法(与已完成的 resolve_path 快速路径同思路,低风险 localized)

art_scan 先沿 pfx 下降到覆盖前缀的最深子树根节点(复用 art_search 的下降逻辑,但停在覆盖节点),再只扫该子树。O(全树) → O(子树)。帧 DelTree 的子树只有几个槽,预期把这 50~64% 打到近零。

kvspaceShmList/kvspaceShmDeltree/kvspaceShmCpTree 全部经 List,一处修改全线受益。

验证

• callgrind 复现:KVSPACE=shm://... valgrind --tool=callgrind --cache-sim=no --branch-sim=no kvlang <case>.kv,callgrind_annotate 看 art_scan 自占比。
• 回归:tutorial 全量(191/191)+ benchmark fib/nqueens/binary_search 墙钟。

关联 #212(性能父·第3叉 kvspace-c)、#204、#194、kvspace-c #16。