Files
dsh 3543003a78 digits: reorder the scratch block -- 22% fewer steps, 15% less tape
The profile said 77% of clb_digits' steps are pointer moves, so the layout of its
13 cell scratch block (S..S+12) is the cost.  The block is one rigid 7 cell unit
(clb_divmod owns its internal order: Rhi,Sd,Bo,Cm=Bc,Ci,buf,NR) plus six free
units, so the legal space is 5040 permutations.  All 5040 were assembled and run
(minimal driver, value 2047):

  old: TEN Q R [block] counter T F
  new: T1 R [block] TEN Q F counter

   tape 13,717 -> 11,717 chars (-14.6%)
   steps 145,114 -> 113,264 (-21.9%)
   pointer moves 111,958 -> 80,108 (-28.4%)   non-move steps identical (33,156)

Full 2048 value sweep: worst 164,843 -> 123,731 (-24.9%), mean 144,904 -> 112,552
(-22.3%), better on all 2048 values.  The old layout ranked 3459/5040.

Two things worth remembering.  First, ordering the units by the wrapper's first
visit order is *worse* than the old layout (150,748 steps): first visit ignores
revisit frequency -- the counter is touched once per round, TEN is copied into Bc
every round, T1 is hammered by clb_add_ip's carry chain.  Second, the n-1 lower
bound is not reachable here: 74% of the steps still execute inside clb_divmod's
block, whose order is not clb_digits' to choose, so this lever is now exhausted
(that is what the exhaustive search proves).

Min tape is not min steps either: block-first BQTRT1F1C gives the shortest tape
(10,713) but 123,890 steps.  Tape counts a .tp once, steps count its execution.

Ripple: asm/test.r8asm 64,513 -> 62,513 chars, 236,439 -> 206,491 steps, INS_SIZE
headroom ~1k -> ~3k; --opt 58,060 -> 56,350; calc --opt 52,857; calc_op 77,356 ->
69,324 chars / 599,090 -> 476,170 steps.

Verified: ctest 8/8, byte_op_test 21 items (digits 2048/2048), examples_test 18,
--opt assembles, SPEC 7.7/10.2 + AGENTS + README + docs/calc.md + docs/divmod.md
numbers updated.  New driver drv/digits_layout.r8asm keeps the measurement honest
(one clb_digits call, no output, value fed as 0=2047).
2026-11-18 17:27:05 +08:00

6.4 KiB
Raw Permalink Blame History

clb_divmod 的设计推理与实测数据

契约(签名、cell 数、吃什么留什么、谁验证)在 SPEC.md §7.6;这里只放 "为什么这么写"和实测数字。原来的位置是 SPEC §14。

1. 为什么换、每轮的状态

旧版 O(N/D):2047/1 要 2047 轮、每轮约 2.4k 步,直接撞 2000 万步上限(实测 HANG)。 新版固定 W 轮(11 轮),跟 N、D 的值无关。

N    被除数(W 位)。每轮 `rol N`,于是 N 的 LSB 就是**最高位起**的下一位
     (rol 把 bit W-1 转到 bit0) —— 转满 W 轮 N 自动复原,所以 N 不被消耗
R    部分余数 = (Rhi:Rlo),Rlo 是普通 cell,Rhi 只有 bit0 有意义(轮内布尔)
D    除数(W 位),每轮都要拿它去比/减 → 必须保留 → 这就是 `raw_sub` 存在的理由
Sd   减法结果(W 位,Rlo - D)
Bo   raw_sub 给的"没借位"(1 表示 Rlo >= D)

每轮:R = (R << 1) | 位,然后 R >= D ? (R -= D, 商位 = 1) : (商位 = 0)。

2. W+1 位比较拆成"一个 W 位减 + 一个布尔"(实际用到的版本)

R = (Rhi:Rlo)、D < 2^W。先算 Sd = Rlo - D 与 Bo = (Rlo >= D),那么

提交(R >= D)   ⟺  Rhi == 1 或 Bo == 1     →  **commit = Rhi | Bo**

四种情况都对得上(Rhi = 0, Bo = 0 就是 R < D,不提交)。所以不需要真的做 W+1 位减法,只要一个 W 位 raw_sub(顺带给出 Bo)+ 一个按位或。

原设计里还有一条 Shi = Rhi & Bo("提交后的新高位")和对应的 clb_bit_and, 实际实现把它省掉了:每轮开头 R < D < 2^W(提交之后 R 一定小于 D),所以 Rhi 在轮首恒为 0;而 Rhi = 1 且 Bo = 1 这个组合会要求 R = 2^W + Rlo >= 2D,与 "轮首 R < D ⇒ 左移后 R < 2D" 矛盾,不可能出现。于是新高位恒为 0,Rhi 只是轮内的 H,clb_bit_or 顺手把它清零就够了 —— 省一个 clb_bit_and、一次 copy 和一个变量。

3. 每轮实际骨架(asm/divmod.r8asm)

.tp N ; rol                                  ; 下一位进 N 的 LSB
.tp R ; rol ; clb_bit_mov Rhi                ; Rlo 左移,绕回位先搬进 Rhi(顺带清 bit0)
.tp N ; bit_copy Rlo buf                     ; 注入这一位(38 字符,保留 N)
raw_sub Rlo D Sd Bo Cm Ci buf                ; Sd = Rlo - D,Bo = (Rlo >= D)
clb_bit_or Rhi Bo Cm                         ; 提交条件(两个输入都被吃掉)
.tp Q ; rol                                  ; 商左旋一位(bit0 一定是 0)
.tp Cm ; biz
    .tp Sd ; copy R buf                      ; R = Sd(495 字符,只在提交时跑)
    .tp Q ; set_1                            ; 商位 = 1
    .tp Cm ; flb                             ; 吃掉条件
rnz
.tp NR ; set_0 ; ror                         ; 轮数吃掉一个

7 个草稿格(S+0..S+6):Rhi、Sd、Bo、Cm(= raw_sub 的 Bc,兼提交标志)、Ci、 buf、NR。固定代价里最大的是 raw_sub 的 2793 字符和提交时那个 copy 的 495 字符。

4. 坑(都踩过或实测过)

  1. R 的跨格左移顺序:rol 把 Rlo 的最高位绕回 bit0,必须先把它搬进 Rhi (clb_bit_mov 搬的同时清掉绕回位),再 bit_copy 注入 N 的那一位。 顺序错了就丢位 —— clb_mul 当年在这里返工两轮。单点验证驱动是 drv/div_shift.r8asm(r8forge_derive drv/div_shift.r8asm -1 0=1024 2=0 4=1 等三条,见文件头)。
  2. biz 是循环对:门控提交的 body 最后必须把条件吃掉(flb);商位的 set_1 和那个 flb 合在同一个块里。条件块的身体都回到自己的条件 cell(净位移 0)。
  3. Rhi 只有 bit0 有意义,它当布尔用,别当字节。
  4. 轮数计数器:%rep _CELL_SIZE { set_1; ror } 造出来的就是 W 个 1,轮首的 LSB 已经是 1、不用再补一条 rol —— 原来的设计笔记里说要补,实测不需要 (clb_mul 也是这么用的)。
  5. N 要保留就得用 bit_copy(保留源),不能用 clb_bit_mov(吃源);代价是 每轮 38 字符 + 约 40 步。余数因此要单独一格 R(旧版"余数就在 N 里"的约定没有了)。

5. 验收(实测)

  • Q/R 逐对比:byte_op_test 的 test_divmod 现在跑 8 个除数 × 全部 2048 个 被除数 = 16384 组(旧的 76 组抽样表是它的子集),全对;顺带断言 N、D 原样返回。

  • 步数(drv/divmod.r8asm,11 位):

    算式 旧(重复减法) 新(移位-恢复)
    2047/10 495,986 28,593
    2047/2 2,461,650 31,997
    999/7 340,086 28,661
    2047/1 HANG(>2000 万) 32,383
    7/10 3,014 25,315
    100/7 34,940 27,460

    16384 组里最坏 32,383 步。N/D 很小时反而慢(固定 11 轮),和 clb_mul 的取舍一样:拿它换"除数和商再大也不会挂"。

  • clb_digits:test_digits 现在穷举全部 2048 个值,全对;0=2047 从 740,695 步降到 113,288 步(最坏 123,755 —— 小值反而慢,同上)。纸带 clb_digits 11717(13 格草稿重排之前 13717,再往前 10829 —— 重排见 SPEC §7.7), clb_divmod 4499(旧 4189)。

纠正一个流传的数字:这里原来写"2047/10 要 148 万步"、"clb_digits 的 1.48M 步"。 按 SPEC §1.3 的口径实测旧实现是 495,986(2047/10)和 740,695(digits 0=2047), 没有 148 万 —— 那个数不知道是别的驱动还是别的版本量的,别再引用。

6. 没做的优化(想让除法再快一档的话)

把"每轮 copy 一份 D 再取反"(raw_sub 内部,单轮 2019 步)换成开循环前预计算 NegD = ~D、每轮只跑 raw_add Rlo NegD Ci Sd Bo buf:单轮 973 步(两者都是拿同一 张驱动单独跑出来的),纸带基本不变(循环体 −594、循环外 +518,净 −76)。按这个差值 估计 clb_divmod 28.6k → 约 17.6k 步(未实测)。没换的原因是 §3 指名用 raw_sub、而它是上一轮专门为长除法加的(SPEC §7.8)。真要换的话注意:多一个 NegD 草稿格;Ci = 1 在循环外设一次就够(raw_add 结束会把 Ci 还原成进入时的值,实测两次 调用都保持 1);Bo 语义不变(A + ~D + 1 的进位就是"没借位")。