Skip to content

2-runtime/PC 与帧寻址:调用深度导致 key 长度 O(D)、活跃 key 总量 O(D²) —— 评估 [ctlflow,irseq,params] 三维地址 #116

Description

@miaobyte

结论先行

三维地址方向正确。定稿形态——ctlflow 独立成段,与 ir 序列之间用 / 分隔:

PC          /vthread/<vtid>/[<帧号>]/[irseq, params]
帧目录       /vthread/<vtid>/[<帧号>]/          → extindex 到 /lib/<func>/
命名局部     /vthread/<vtid>/[<帧号>]/<name>
实参槽       /vthread/<vtid>/[<帧号>]/[0,-j]
系统变量     /vthread/<vtid>/[<帧号>]/‥lib、‥returnpc、‥callpc

三类分隔符各归其位:/ 划结构(vthread → 帧 → 指令槽),[i,j] 坐标段定位指令平面,· 完全不出现在帧结构里、继续专供用户成员键族。

为什么用 / 而不是 ·——· 是成员专用分隔符,帧不是成员。 这不是权衡,是套用 kvspace 自己的公理。kvspace篇-04-系统变量.md「三种键形态:一眼判型」已把三类键的所有权划死(下表按 #66 迁移后的分隔符改写):

形态 性质 所有权
X/名 /vthread/7/[3,0]/_while_2/[0,0] 结构:帧、指令槽、scope 帧 VM
X·名 /c0·nextframe/obj·prop 用户数据成员(键族) 用户
X/‥名 /vthread/7/‥pcarr/‥shape 系统变量(影子元数据) VM

该表第一行原文就把 /vthread/7/[3,0] 列为「结构」。帧号是帧的结构标识,归 VM,不归用户数据平面。若改用 ·,等于把帧塞进用户键族的命名空间,与该表直接冲突,也让「一眼判型」失效——看到 · 不再能断定是用户数据。

为什么 ctlflow 不能挤进同一个坐标段(即 [c,i,j] 三分量写法):extindex、命名局部变量、‥lib/‥returnpc 三者都要挂在目录上(kvspace-durable/src/kvspace.rs:24-38 validate_dir),而 [c,i,j] 整体是 /vthread/<vtid>/ 下的一个成员名,不构成可挂载的前缀。ctlflow 必须自成一段。

这个形态把 PC 长度从 O(D) 压到 O(1),同时保留 extindex、Ptr 参数链、逐槽寻址全部不变。

实测补充见 下方评论[c]·[i,j] 形态的 extindex 在 fs 与 shm 两个后端均静默失效[c]/[i,j] 形态六项检查全通过,且 runtime 各 keytree 函数逐项不变。但那是当下实现状态、可以被修好;分隔符语义划分是设计公理、修不掉也不该修。即使 kvspace 把 · 目录的 extindex 修好,本方案仍然用 /——该评论中「今天就能用」的选型理由,以本节的分隔符语义为准。

另外需要先澄清一个前提:控制流不加深栈。scope 帧是 rwfunc 帧的平级兄弟(runtime/src/kvcpu.c:203 handle_scope 取的是 FuncFrameRoot 而非当前帧),设计文档也明确「所有 ScopeStmt 为函数体平级兄弟节点」。深度只来自函数调用。但控制流会放大每层调用的字节增量,见下。


一、现状:PC 实际怎么长

tutorial/02-func/tco_depth.kvtailrec_fact 为例。layout 产物实测(fs:// 后端 dump):

/lib/tailrec_fact/[1,0]          = goto
/lib/tailrec_fact/_if_2[1,0]     = br
/lib/tailrec_fact/_else_4[3,0]   = tailrec_fact     ← 递归调用点
/lib/tailrec_fact/_else_4[4,0]   = goto _merge_5

handle_call 直接把当前 PC 当作被调帧根(runtime/src/kvcpu.c:302 char *frame_root = strdup(pc);),而递归调用点位于 _else_4 scope 内,于是运行时 PC 链是:

d=1  /vthread/1/[1,0]/[3,0]                                       22 B
d=2  /vthread/1/[1,0]/[3,0]/_else_4/[3,0]                         36 B
d=3  /vthread/1/[1,0]/[3,0]/_else_4/[3,0]/_else_4/[3,0]           50 B

每层 +14 B/_else_4 8 B + /[3,0] 6 B)。若递归调用点在函数体顶层而不在 if/else 内,增量是 6 B——这就是「控制流放大每层增量」的确切含义:它不增加深度,但让每层的路径段翻倍。

PC(d) = 22 + 14(d - 1)MAX_STACK_DEPTH = 256runtime/src/runtime_internal.h:53)时 PC ≈ 3.5 KB

二、成本模型

帧内每个键都是 帧根 + /名,即每个键都是 O(D)。tailrec_fact 一帧约 15 个键(N/acc/r/acc1/acc1_m/n1 + ‥lib/‥returnpc/‥callpc + [0,-1]/[0,-2]/[0,1] + 两个 scope 帧各自的 ‥callpc/‥returnpc)。

活跃栈的键字节总量:

Σ(d=1..D) 15 × (22 + 14(d-1)) ≈ 105 D²
D PC 长度 活跃 key 字节总量
10 148 B ~10 KB
100 1.4 KB ~1 MB
256 3.5 KB ~6.9 MB

纯 key 字符串,不含 value。这是 D² 项,不是常数项。

三、depth 耦合的三个热路径

  1. 每条指令写一次 O(D) 字符串kvlangVthreadSet 把完整 PC 写进 ‥pckvcpu.c:393/400/408/424/591/596),每条指令一次。
  2. 每条指令读四次。循环顶 kvlangVthreadGetkvcpu.c:549)+ 执行后再一次(kvcpu.c:645),各取 ‥pc/‥status 两个键。
  3. 每条指令解码探测 257 个槽runtime/src/rwir.c:87 nslots = 1 + 2 * MAX_PARAMSMAX_PARAMS = 128fs 后端 get 对每个 key 做 join_path(prefix, k) 再落盘探测(kvspace-durable/src/fs/kvspace.rs:360-392),未命中且帧有 extindex 时 join 一次走 ext 回落。于是每条指令构造 ~500 个长度为 O(D) 的字符串。D=100 时约 38 KB 字符串构造 / 指令

第 3 点是独立缺陷(应按签名的 nr/nw 精确取槽,而非盲扫 128 对),但它是把 PC 长度问题放大 257 倍的乘数。建议单独开 issue,与本 issue 并行修。

此外 ResolveWriteSlotruntime/src/builtin.c:143-183)在 fallback 路径上调用 FuncFrameRoot 两次(145 行、178 行),每次都是自帧根向上逐级 KV get 探 ‥lib

四、为什么 ctlflow 要独立成段

本表针对 [c,i,j] 三分量挤成一个成员名 的写法。至于把 ctlflow 拆出来但用 · 分隔([c]·[i,j])——那在类型上是成立的,· 本就是合法目录分隔符,被否掉的理由是分隔符语义(帧是结构不是成员,见开头),不是这张表。

现有机制 依赖 [c,i,j] 下能否成立
指令取数 帧根目录 extindex → /lib/<func>/kvcpu.c:307 validate_dir 拒绝非目录路径,坐标分量不是前缀
命名局部变量 帧根/<name>builtin.c:145-149 ✗ 坐标里放不下标识符
系统变量 帧根/‥lib‥returnpc‥callpc ✗ 同上
Ptr 参数链 帧根/<name> → ext → Ptr("[0,-1]")帧根/[0,-1] ✗ 依赖前两条

补充一点坐标语义的现存瑕疵:kvspace-durable/src/coord.rsparse_coord 只接受非负整数,负的读参坐标 [0,-1] 解析失败后退化成字典序而非 row-major 数值序。三维方案若把 params 放进坐标第三维,这个瑕疵会跟着进去。

五、推荐方案

分两步,每步独立可验证。

步骤 1:label 降为整数 irseq 偏移,删除 scope 帧

scope 帧不提供任何作用域。 所有变量读写都定位到 rwfunc 帧——读走 resolve_read_pathFuncFrameRootkvcpu.c:126),写走 ResolveWriteSlotFuncFrameRootbuiltin.c:145)。scope 帧里只有 ‥callpc‥returnpc 两个续体记录键。所以把它拍平语义零损失

layout 侧:把 /lib/f/_while_2[i,j] 合并进 /lib/f/[i,j] 单一指令平面,label 在 layout 期解析为整数行号,goto/br 的读参直接是目标 irseq(label 名保留在 /lib/f/‥labels/<name> 供调试)。

收益:

  • goto/br 从「建帧 + get ‥callpc + set ‥callpc」(kvcpu.c:216-238,每次进入 label 都付)变成一次 irseq 赋值,0 次额外 KV 操作。一轮 while 循环现在要走 5 条指令(cond / br / body×2 / goto),其中 br 和 goto 各带 2 次 KV 往返,全部消掉。
  • runtime/src/rwir.c:22-64 scope_prefix_and_base 整个删除。顺带说明:它支持的嵌套 scope 前缀(_while_2·_if_1)是死代码——handle_scope 恒以 FuncFrameRoot 为父,scope 永远只有一层。
  • handle_scope / handle_scope_returnkvcpu.c:201-243163-177)删除,ext_kind 分支(kvcpu.c:19-30588)删除。
  • 每层调用的 PC 增量从 14 B 回落到 6 B。

步骤 2:帧根改为扁平帧号

/vthread/<vtid>/[<帧号>]/[irseq, params]

帧号取调用深度,不需要计数器:kvlang 无闭包/协程,帧严格栈式,深度 d 的帧恒为 /vthread/7/[d]/,return 即 del_tree 该目录。帧号写成坐标段 [d] 而非裸数字 dcmp_coord 对坐标段按数值 row-major 排序且恒排在非坐标段之前,于是 kvspace list /vthread/7/ 直接给出按栈序排列的帧列表

  • PC 恒长:/vthread/7/[256]/[3,0] = 23 B,与深度无关。
  • stack_depthkvcpu.c:13-17,现在靠数 [ 字符)变成读一个整数,O(1) 且精确。
  • extindex、‥lib/‥returnpc/‥callpc、命名局部、Ptr 三跳链全部原样保留——帧根仍是目录。
  • FuncFrameRoot 的向上探测(builtin.c:88-104)消失:步骤 1 之后不存在 scope 帧,当前帧就是 rwfunc 帧。
  • 活跃 key 字节总量从 O(D²) 降到 O(D)。

唯一前提假设:帧不逃逸。若将来引入闭包或协程使帧生命周期超出父帧,帧号 = 调用深度 失效,届时需换成 vthread 级单调计数器(多一个可变计数键)。这个假设需要明确记录。

六、代价:会失去什么

deepx-design/.claude/writing-standards.mdC2「路径深度即调用栈深度」 列为对外文章必须传达的核心概念。本方案下:

  • C3「PC 是路径字符串」保留——PC 仍是路径,跳转仍是字符串拼接。
  • C2 形式改变但语义更强:深度不再是路径的 / 层数,而是路径里那一段帧号,从「隐式且 O(D) 才能算出」变成「显式且 O(1) 可读」。文档口径需相应改写为「路径中的帧号即调用栈深度」。
  • C6「崩溃可恢复」保留,但重建完整调用链从「读一个 PC 字符串即得全链」变成「沿 ‥returnpc 走 D 次读」。仅发生在恢复路径,非热路径。若不可接受,可在 vthread 级冗余一个 ‥stack 全链字符串。
  • 可观测性kvspace tree /vthread/7/ 从嵌套调用树变成扁平的编号帧列表。对 dashboard 而言这更接近一个真实的栈视图,但确实是外观改变kvlang-device-screen 需同步。

七、关联

八、待决策

  1. 步骤 1 与步骤 2 是否合并为一次不兼容变更?(p5 不向后兼容,倾向合并,一次改到最终态)
  2. 帧号 = 调用深度 是否接受「帧不逃逸」这条前提?还是直接上 vthread 级计数器留出闭包空间?
  3. C2 的对外口径改写谁来定?涉及 README / article 已发布内容。
  4. rwirext C ABI 是否会破? 已核查:runtime-rwirext_example/ 下 rust/term、go/json、py/numpy 三个扩展均把 PC 当不透明字符串,只构造 /vthread/<vid>/‥pc 这类 vthread 级键(term/src/main.rs:231json.go:623numpy.py:320),无一解析 PC 内部结构。kvlang_rwirextNextPc 新形态下仍是纯字符串操作(解析 [i,j] 后 i+1),ABI 签名与语义均不变。此项无阻塞。

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions