Appearance
Part 2: 代码走读
1. BPE 分词器
追踪 1：分词完整调用链
从用户输入到 token ID 序列：
用户输入: "Hello world"
│
▼
ds4_tokenize_text(e, "Hello world", &tokens) [行 13963]
│
▼
bpe_tokenize_text(&vocab, "Hello world", &out) [行 13808]
│
│ 预分词：按 JoyAI regex 拆分
├── "Hello" → bpe_emit_piece(...) [行 13632]
└── " world" → bpe_emit_piece(...)
│
▼ 每个 piece
bpe_emit_piece(vocab, {" world", 6}, out) [行 13632]
│
├── byte_encode(" world") → 编码为 GPT-2 字节字符
│ 每个字节 → Unicode 码点
│ ' '→286, 'w'→119, 'o'→111, 'r'→114, 'l'→108, 'd'→100
│ → UTF-8 字符串: "Ġworld"（Ġ 是编码后的空格）
│
├── 拆分为初始符号（每个 UTF-8 字符一个符号）
│ ['Ġ', 'w', 'o', 'r', 'l', 'd']
│
├── BPE 合并循环：
│ for(;;) {
│ 找 rank 最小的相邻对
│ 找不到 → break
│ 合并该对
│ }
│ 例如: 'w'+'o'→rank=321 → 合并 → ['Ġ', 'wo', 'r', 'l', 'd']
│ 继续: 'wo'+'r'→rank=... → ...
│ 最终: ['Ġworld'] （或多个子词）
│
└── 查表获取 token ID
table_get(token_to_id, "Ġworld") → 995
token_vec_push(out, 995)追踪 2：哈希表操作
初始化
vocab_load() [行 13888]
│
├── model_get_array(model, "tokenizer.ggml.tokens", &tokens)
│ 从 GGUF 元数据获取 token 字符串数组的位置
│
├── vocab->token = xcalloc(n_vocab, sizeof(ds4_str))
│ 分配 token 字符串数组
│
├── table_init(&vocab->token_to_id, tokens.len) [行 13438]
│ cap = next_pow2(129280 * 2 + 16) = 262144
│ entry = xcalloc(262144, sizeof(str_i32_entry))
│
└── for i = 0..n_vocab-1:
cursor_string(&c, &vocab->token[i]) 读 token 字符串（指向 mmap）
table_put(&token_to_id, token[i], i) 插入哈希表查找过程
table_get(&token_to_id, "Ġworld", 6, &id) [行 13467]
│
├── hash_bytes("Ġworld", 6) → 某个 64-bit 哈希值
├── i = hash & (cap - 1) → 起始槽位
│
└── 线性探测：
slot[i].used == true
slot[i].key.len == 6 && memcmp(key.ptr, "Ġworld", 6) == 0
→ 找到！返回 id = 995追踪 3：BPE 合并的内存管理
bpe_emit_piece 中的内存操作：
c
// 初始符号数组（动态增长）
int cap_sym = 32;
owned_str *sym = xcalloc(cap_sym, sizeof(sym[0]));
// 合并时：
// 1. 分配新字符串
merged.ptr = xmalloc(sym[i].len + sym[i+1].len);
memcpy(...); // 拼接
// 2. 释放旧的两个字符串
free(sym[i].ptr);
free(sym[i+1].ptr);
// 3. 替换
sym[i] = merged;
// 4. 前移后续元素
for (int j = i+1; j+1 < n_sym; j++)
sym[j] = sym[j+1];
n_sym--;
// 最终：释放所有符号和编码字符串
for (int i = 0; i < n_sym; i++) free(sym[i].ptr);
free(sym);
free(encoded);注意：bpe_emit_piece 是分词阶段调用的，不在推理热循环中，所以这里的 xmalloc/free 不会触发分配守卫。
追踪 4：Token 解码（ID → 文本）
ds4_token_text(e, 995, &len) [行 14138]
│
├── vocab->token[995] = {"Ġworld", 6} 从 token 数组获取字符串
│
├── vocab_token_is_literal_special()? 检查是否是特殊 token
│ （包含 U+FF5C 全角竖线的是特殊 token）
│ → 否，执行 GPT-2 字节解码
│
└── 逐 UTF-8 字符解码：
cp = utf8_decode_one(s.ptr, ...) 读一个 Unicode 码点
b = gpt2_codepoint_to_byte(cp) 码点 → 原始字节
out[n++] = (char)b
'Ġ' → 码点 286 → 字节 0x20 → ' ' （空格的 GPT-2 编码）
'w' → 码点 119 → 字节 0x77 → 'w'
...
→ " world"追踪 5：Chat 模板组装
ds4_encode_chat_prompt(e, "You are helpful.", "Hello", DS4_THINK_HIGH, &out)
│ [行 13940]
│
├── token_vec_push(out, bos_id) <｜begin▁of▁sentence｜>
│
├── bpe_tokenize_text(vocab, "You are helpful."
│ "You are helpful.", out) → [token_ids...]
│
├── token_vec_push(out, user_id) <｜User｜>
│
├── bpe_tokenize_text(vocab, "Hello"
│ "Hello", out) → [token_ids...]
│
├── token_vec_push(out, assistant_id) <｜Assistant｜>
│
└── token_vec_push(out, think_start_id) 💭（思考模式开启）
最终 token 序列:
[BOS] You are helpful. <｜User｜> Hello <｜Assistant｜> 💭2. 采样策略
追踪 1：随机数生成器（xorshift64）
PRNG 状态与演进
c
// 行 14907: SplitMix64 状态转移 + 乘法输出混合
static uint64_t sample_rng_next(uint64_t *state) {
uint64_t x = *state;
if (x == 0) x = 0x9e3779b97f4a7c15ULL; // 黄金比例常数，防止全零种子
x ^= x >> 12; // 右移异或
x ^= x << 25; // 左移异或
x ^= x >> 27; // 再右移异或
*state = x;
return x * 0x2545f4914f6cdd1dULL; // SplitMix64 输出混合
}三步异或移位（xorshift）的几何意义：
初始: 1011001110101011...
>>12: 0000000000001011001110101011
XOR: 1011001110100000... ← 高 12 位不变，低位被打乱
<<25: ...被打乱的低位左移25位填充高位
>>27: 再次从高位取回低位浮点均匀分布
c
// 行 14917: 将 64-bit 随机数映射到 [0, 1) 区间
static float sample_rng_f32(uint64_t *state) {
const uint64_t x = sample_rng_next(state);
return (float)((x >> 40) & 0xffffffu) / 16777216.0f;
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^
// 取高 24 位 (0 ~ 2^24-1) 除以 2^24 = 16777216
}为什么取高 24 位？float 的尾数只有 23 位 + 1 隐含位 = 24 位精度。取更多位无法提高分辨率。
追踪 2：Argmax 贪心采样
c
// 行 14874: 线性扫描找最大 logit 对应的 token ID
static int sample_argmax(const float *logits, uint32_t n_vocab) {
int best = 0;
float best_v = DS4_NEG_INF; // -1e30f 作为初始哨兵
for (uint32_t i = 0; i < n_vocab; i++) {
const float v = logits[i];
if (v > best_v) {
best_v = v;
best = (int)i;
}
}
return best;
}logits[0] = -2.3 best_v=-1e30 → 更新: best=0, best_v=-2.3
logits[1] = 5.1 best_v=-2.3 → 更新: best=1, best_v=5.1
logits[2] = 3.7 best_v=5.1 → 不更新
...
logits[N]= 8.2 best_v=5.1 → 更新: best=N, best_v=8.2
返回 best = N（概率最大的 token）另有通用版本 argmax_f32（行 8019），返回 uint64_t 索引，用于非采样场景。
追踪 3：降序排序比较器
c
// 行 14922-14926: 采样候选项结构
typedef struct {
int id; // token ID
float logit; // 原始 logit 值
float prob; // softmax 后的概率
} sample_candidate;
// 行 14928: qsort 降序比较器
static int sample_candidate_cmp_desc(const void *a, const void *b) {
const sample_candidate *ca = a;
const sample_candidate *cb = b;
return (cb->logit > ca->logit) - (cb->logit < ca->logit);
// ^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^
// b > a 时为 1 b < a 时为 1
// 组合结果: b>a 返回 1（b 排前面 → 降序）
}无分支三路比较技巧：(b > a) - (b < a) 等价于：
b > a: 返回 1 (b 应排在 a 前面 → 降序)
b < a: 返回 -1 (a 应排在 b 前面)
b = a: 返回 0避免了 if-else 分支，对现代 CPU 流水线友好。
追踪 4：全词表温度采样
完整流水线
c
// 行 14934: 完整采样流水线
static int sample_full_vocab(
const float *logits, // 模型输出的 129280 个 logit
uint32_t n_vocab, // 129280
float temperature,
float top_p,
float min_p,
uint64_t *rng) { // 随机数状态logits[129280]
│
▼ 第一步: 找最大值 + 统计有限值个数
│
max_logit = max(logits[])
finite = count(isfinite(logits[i]))
│
▼ 第二步: Softmax + 温度缩放
│
for each i:
if !isfinite(v): skip
p = expf((v - max_logit) / temperature)
// ^^^^^^^^^ 温度 T > 1 使分布更平滑
// T < 1 使分布更尖锐
│
▼ 第三步: 快速路径 vs 排序路径
│
┌─ top_p >= 1.0? ──→ 快速路径: 无排序，线性扫描采样
│ 无堆分配，适合大部分场景
│
└─ top_p < 1.0 ──→ 排序路径: qsort 降序
累积概率直到 ≥ top_p
截断并重归一化快速路径详解（top_p >= 1.0 时）
c
// 行 14955: 不排序，直接在线性扫描中采样
double sum = 0.0;
for (uint32_t i = 0; i < n_vocab; i++) {
const float v = logits[i];
if (!isfinite(v)) continue;
const float p = expf((v - max_logit) / temperature);
candidates[i].prob = p; // 直接存在大数组中
sum += p;
}
const float r = sample_rng_f32(rng) * sum; // 随机阈值
float acc = 0.0f;
for (uint32_t i = 0; i < n_vocab; i++) {
acc += candidates[i].prob;
if (acc > r) return (int)i; // 命中！
}追踪 5：Top-P / Min-P 过滤采样
c
// 行 15023: 带拓扑筛选的采样
static int sample_top_p_min_p(
const float *logits,
uint32_t n_vocab,
float temperature,
int top_k, // 只保留前 k 个候选
float top_p, // 累积概率阈值
float min_p, // 相对最小概率阈值
uint64_t *rng)栈上插入排序（零堆分配）
c
// 行 15041: 固定大小栈数组，避免 malloc
int ids[1024]; // 最多 1024 个候选
float vals[1024]; // 对应的 logit 值
int nk = 0;
for (uint32_t i = 0; i < n_vocab; i++) {
// 降序插入排序，只保留 top_k
for (int j = 0; j < nk; j++) {
if (logits[i] > vals[j]) {
// 后移腾出位置
for (int m = MIN(nk, top_k - 1); m > j; m--) {
vals[m] = vals[m - 1];
ids[m] = ids[m - 1];
}
vals[j] = logits[i];
ids[j] = (int)i;
if (nk < top_k) nk++;
goto next_logit;
}
}
// 比所有已有候选都小，但数组未满
if (nk < top_k) {
vals[nk] = logits[i];
ids[nk] = (int)i;
nk++;
}
next_logit:;
}过滤与采样
top-k 候选 (k=50)
│ softmax → 概率分布 probs[50]
│
▼ Min-P 过滤
│
min_prob = (probs[0] / sum) * min_p
// ^^^^^^^^ ^^^^^
// 最高概率 相对阈值
// 任何 probs[i] < min_prob 的候选被丢弃
│
▼ Top-P 累积截断
│
从最高概率开始累加: probs[0] + probs[1] + ...
当累积概率 >= top_p 时停止
│
▼ 重归一化 + 加权随机采样
│
r = rng_f32() * filtered_sum
线性扫描找到累积值 > r 的 token
→ 返回该 token ID为什么用插入排序而非 qsort？
top_k最多 1024，远小于 129280- 插入排序对"维护一个小的有序子集"是 O(n×k)，当 k << n 时比 O(n log n) 的 qsort 更快
- 栈上固定数组避免了
malloc/free，满足热循环零分配约束