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

104 lines
6.4 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
# `clb_divmod` 的设计推理与实测数据
契约(签名、cell 数、吃什么留什么、谁验证)在 [`SPEC.md`](../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` 的进位就是"没借位")。