ds4.c 学习笔记

Appearance

Part 2: 练习 ​

1. BPE 分词器 ​

练习 1：哈希表容量计算 ​

题目：table_init 用 next_pow2(expected * 2 + 16) 计算容量。DeepSeek V4 Flash 有 129,280 个 token。

  1. token_to_id 表的容量是多少？
  2. 负载因子（used/cap）是多少？
  3. 为什么负载因子要保持在 50% 以下？
参考答案（先自己尝试，再展开查看）
  1. next_pow2(129280 * 2 + 16) = next_pow2(258576) = 262144 = 2^18
  2. 129280 / 262144 ≈ 49.3%
  3. 开放寻址哈希表的性能随负载因子增加而恶化。超过 50% 后，冲突增多，探测链变长，查找从 O(1) 退化到接近 O(n)。50% 以下能保证大部分查找只需 1-2 次探测。

练习 2：线性探测追踪 ​

题目：假设哈希表 cap=8（mask=7），当前状态如下：

slot:  0    1    2    3    4    5    6    7
used:  F    T    T    F    T    F    F    T
key:   -   "a"  "b"   -   "c"   -    -   "d"

现在要插入 key="e"，hash("e") & 7 = 1。请追踪 table_put 的执行过程。

参考答案（先自己尝试，再展开查看）
i = 1
slot[1].used = true, key = "a" ≠ "e" → i = (1+1) & 7 = 2
slot[2].used = true, key = "b" ≠ "e" → i = (2+1) & 7 = 3
slot[3].used = false → 插入这里！
slot[3] = {key="e", value=..., used=true}

线性探测从 hash 位置开始，逐个检查，直到找到空位或匹配的 key。

练习 3：BPE 合并模拟 ​

题目：假设词表中有以下 token 和 merge rank：

Token IDs: 'l'=0, 'o'=1, 'w'=2, 'e'=3, 's'=4, 't'=5
Merge ranks: "e s"=1, "es t"=2, "lo"=3, "low"=5, "lo w"=4

请模拟 bpe_emit_piece 处理输入 "lowest" 的过程。

参考答案（先自己尝试，再展开查看）
初始: ['l', 'o', 'w', 'e', 's', 't']

第 1 轮：扫描所有相邻对
  'l'+'o': "l o" → 无 rank
  'o'+'w': "o w" → 无 rank
  'w'+'e': "w e" → 无 rank
  'e'+'s': "e s" → rank=1 ★ 最小
  's'+'t': "s t" → 无 rank
  合并 'e'+'s' → 'es'
  → ['l', 'o', 'w', 'es', 't']

第 2 轮：
  'l'+'o': 无 rank
  'o'+'w': 无 rank
  'w'+'es': 无 rank
  'es'+'t': "es t" → rank=2 ★
  合并 'es'+'t' → 'est'
  → ['l', 'o', 'w', 'est']

第 3 轮：
  'l'+'o': "lo" → rank=3 ★
  'o'+'w': 无 rank
  'w'+'est': 无 rank
  合并 'l'+'o' → 'lo'
  → ['lo', 'w', 'est']

第 4 轮：
  'lo'+'w': "lo w" → rank=4 ★
  'w'+'est': 无 rank
  合并 'lo'+'w' → 'low'
  → ['low', 'est']

第 5 轮：
  'low'+'est': 无 rank
  无可合并对 → 停止

最终: ['low', 'est'] → 查表得到 token IDs

练习 4：理解 GPT-2 字节编码 ​

题目：gpt2_byte_to_codepoint 把字节 0x20（空格）映射到码点 286（Ġ）。请解释为什么需要这个映射，以及解码时如何还原。

参考答案（先自己尝试，再展开查看）

BPE 的 token 字符串存储在 GGUF 中作为 UTF-8 文本。但原始字节 0x00-0x1F 是控制字符（换行、制表等），不是"可见"的 Unicode 字符。如果 token 字符串直接包含这些字节，会破坏字符串处理。

GPT-2 的映射方案：

  • 可打印 ASCII（33-126）和部分 Latin-1（161-172, 174-255）直接使用原码点
  • 不可打印的字节映射到 256 开始的码点区域

空格（0x20=32）不在可打印范围内（33-126），所以被映射到 256 + N。在 0-255 中，跳过可打印字符后，0x20 是第 30 个不可打印字节，所以映射到 256 + 30 = 286 = 'Ġ'（带点 G）。

解码时 gpt2_codepoint_to_byte 做逆映射：286 → 0x20 → ' '（空格）。

练习 5：动态数组增长 ​

题目：token_vec_push 的增长策略是翻倍。如果依次 push 1000 个 token：

  1. cap 会经历哪些值？
  2. 总共会发生多少次 realloc？
  3. 翻倍策略的均摊时间复杂度是多少？
参考答案（先自己尝试，再展开查看）
  1. cap 变化：0 → 64 → 128 → 256 → 512 → 1024 → 2048
  2. 6 次 realloc（64, 128, 256, 512, 1024, 2048）
  3. 均摊 O(1)。证明：N 次 push 的总拷贝量 = 64 + 128 + 256 + ... < 2N。平均每次 push 拷贝 < 2 个元素，是常数。

今日学习检查清单 ​

  • 能解释开放寻址哈希表的工作原理（线性探测）
  • 理解为什么哈希表容量要是 2 的幂（用 & mask 代替 % cap）
  • 能手动模拟 BPE 合并过程
  • 理解 GPT-2 字节编码的目的（为什么空格变成 Ġ）
  • 能描述预分词的作用
  • 理解 Chat 模板中特殊 token 的作用
  • 能追踪从文本到 token ID 的完整调用链
  • 理解动态数组翻倍增长的均摊复杂度

延伸挑战 ​

挑战 1（中级）：追踪真实文本的分词过程 ​

运行 ./ds4 并输入一段包含中英文混合的文本。在 ds4.c 的 bpe_emit_piece 函数中加一个 fprintf(stderr, ...) 打印每次合并的 token 对，观察 BPE 如何处理中文和数字。

挑战 2（高级）：实现前缀匹配分词 ​

分词器需要支持 special token 的最长匹配。写一个简化版：给定一个有序的 token 列表和输入字符串，用二分查找实现最长前缀匹配，时间复杂度 O(log n)。

2. 采样策略 ​

练习 1：数值稳定的 softmax ​

题目：假设 logits = [3.0, 1.0, -1.0, 5.0]，temperature = 1.0。请手动计算：

  1. 减去最大值后的值
  2. 每个值的 exp
  3. 概率分布
参考答案（先自己尝试，再展开查看）
原始:    [3.0,  1.0,  -1.0,  5.0]
最大值:  5.0
减最大值: [-2.0, -4.0, -6.0,  0.0]
exp:     [0.135, 0.018, 0.0025, 1.0]
总和:    1.1555
概率:    [0.117, 0.016, 0.002, 0.865]

token 3（logit=5.0）有 86.5% 的概率被选中。

练习 2：Temperature 效果 ​

题目：同样的 logits = [3.0, 1.0, -1.0, 5.0]，分别计算 temperature = 0.5 和 temperature = 2.0 时的概率分布。

参考答案（先自己尝试，再展开查看）

T=0.5（更集中）：

减最大值/T: [-4.0, -8.0, -12.0, 0.0]
exp:        [0.018, 0.000335, 0.0000061, 1.0]
概率:       [0.018, 0.0003, 0.000006, 0.982]

最高概率的 token 从 86.5% 提升到 98.2%。

T=2.0（更均匀）：

减最大值/T: [-1.0, -2.0, -3.0, 0.0]
exp:        [0.368, 0.135, 0.0498, 1.0]
概率:       [0.231, 0.085, 0.031, 0.628]

分布变平，其他 token 的概率增加了。

练习 3：Top-P 模拟 ​

题目：假设排序后的概率分布为：

Token  概率     累计
D     0.50     0.50
A     0.25     0.75
B     0.15     0.90
C     0.08     0.98
E     0.02     1.00

top_p = 0.9 时，哪些 token 会被保留？

参考答案（先自己尝试，再展开查看）
D: 0.50 → 累计 0.50 < 0.90 ✓ 保留
A: 0.25 → 累计 0.75 < 0.90 ✓ 保留
B: 0.15 → 累计 0.90 >= 0.90 ✓ 保留（包含达到阈值的那一个）
C: 0.08 → 累计 0.98 > 0.90 ✗ 不保留
E: 0.02 → 不保留

保留 D, A, B（累计 90%）。这三个 token 的概率会被重新归一化后用于随机采样。

练习 4：理解 xorshift64 PRNG ​

题目：sample_rng_next 的初始状态为 state = 1。请手动执行一次：

c
uint64_t x = 1;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
return x * 0x2545f4914f6cdd1dULL;

只需要描述每一步的变换类型，不需要精确计算 64 位结果。

参考答案（先自己尝试，再展开查看）
初始:   x = 1 (0x0000000000000001)
步骤1:  x ^= x >> 12    — 右移 12 位后异或，高位不变，低位被高位影响
步骤2:  x ^= x << 25    — 左移 25 位后异或，低位不变，高位被低位影响
步骤3:  x ^= x >> 27    — 右移 27 位后异或
步骤4:  x * 0x2545...   — 乘法混合，增加随机性

三次移位异或确保所有 bit 都被充分混合。这个设计的关键是三个移位量（12, 25, 27）经过数学验证，能产生良好的统计特性（完整周期、均匀分布）。

练习 5：采样策略选择 ​

题目：在以下场景中，你会选择什么采样参数？

  1. 代码生成（需要精确、确定）
  2. 创意写作（需要多样性）
  3. 事实问答（需要平衡准确和自然）
  4. 批量测试（需要完全可复现）
参考答案（先自己尝试，再展开查看）
  1. temperature=0（贪心），或 temperature=0.2, top_p=0.9：代码需要精确，低温度确保选最可能的 token
  2. temperature=0.8-1.0, top_p=0.95, min_p=0.05：保持多样性，但避免极端低概率 token
  3. temperature=0.5-0.7, top_p=0.9：偏向正确答案，但保留一定变化
  4. temperature=0, seed=固定值：完全确定性，每次运行结果完全相同

今日学习检查清单 ​

  • 能解释 softmax 为什么需要减去最大值
  • 理解 temperature 对概率分布的影响
  • 能手动模拟 top-k 和 top-p 过滤
  • 理解 min-p 的相对阈值设计
  • 能描述完整的采样调用链
  • 理解插入排序在 top-k 中的应用
  • 能解释 xorshift64 PRNG 的工作原理
  • 理解无分支三路比较的技巧

延伸挑战 ​

挑战 1（中级）：实现 Min-P 采样 ​

Top-P 按累积概率截断，Min-P 按相对阈值截断。在 sample_top_p_min_p 的基础上，用你自己的话解释 min_p 参数如何与 top_p 协同工作，然后构造一个例子：top_p 保留的 token 比预期多，min_p 如何进一步裁剪。

挑战 2（高级）：对比采样策略的输出分布 ​

写一个脚本，用 ds4-server 的 API 分别以 temperature=0.1、0.7、1.5 生成 20 次相同的 prompt。统计每个温度下输出长度的方差和词汇多样性（unique token / total tokens），验证"温度越高输出越多样"的直觉。