---
tags: [nanochat, pretraining, dataloader]
阶段: 05-预训练Pretraining
难度: ★★★
created: 2026-10-22
related: "[[训练数据与FineWeb]], [[训练脚本与speedrun]], [[检查点与恢复]], [[有监督微调SFT]]"
---

# 数据加载器 dataloader

## 定义

**BOS 对齐 best-fit 裁剪数据加载器**（BOS-aligned best-fit crop dataloader）是 nanochat 预训练阶段的数据供给器：它从 parquet 行组中取出文档，为每篇文档前置一个 BOS token，然后以 best-fit 策略把文档整篇或裁剪后装入长度为 $T+1$ 的行，使每一行都以 BOS 开头、且恰好填满而不留 padding。

本篇出现的符号与术语：

- $T$：上下文长度，`--max-seq-len`，预训练默认 2048。
- $B$：每个 rank 的批大小，`--device-batch-size`，speedrun 为 16。
- row_capacity：一行可容纳的 token 数，等于 $T+1$，因为第 $T+1$ 个位置只作为最后一个目标的来源。
- row（行）：一条训练样本，形状 $(T+1,)$ 的 token 序列；其前 $T$ 个 token 构成输入，后 $T$ 个构成目标。
- document（文档）：一篇文本经 `tokenizer.encode` 编码并前置 BOS 后的 token 列表。
- `doc_buffer`：存放待打包文档 token 列表的 Python 列表，长度维持在 `buffer_size`。
- buffer_size：缓冲区文档数，函数默认 1000。
- tokenizer_batch_size：一次送入分词器的文档数，默认 128；它只影响分词吞吐与 state 粒度，不影响打包结果。
- utilization（利用率）：$\text{placed}/(\text{rows}\times\text{row\_capacity})$，best-fit 下恒为 1。
- crop rate（裁剪率）：$\text{cropped}/\text{consumed}$，即被读入但未参与训练的 token 比例，$T=2048$ 时约 34.6%。
- `pq_idx` / `rg_idx` / `epoch`：parquet 文件下标、行组下标、轮次，三者构成续训状态 `state_dict`。
- DDP（DistributedDataParallel）：此处只借用其「多进程各取一份数据」的语义；nanochat 的梯度同步在优化器内部完成，不使用 `nn.parallel.DistributedDataParallel`。

## 为什么重要

- 它决定每个训练 token 是否拥有完整上下文。平坦 token 流切出的行可能从文档中间开始，模型需要在没有 BOS 与前置文本的条件下预测下一个 token；推理时输入总是以 BOS 开头，训练与推理的输入分布因此不一致。BOS 对齐消除了这一差异。
- 它决定算力是否被浪费。padding 方案让部分位置不参与损失，等于用 GPU 计算零梯度；裁剪方案把浪费留在 CPU 与磁盘侧，保持 100% 利用率。
- 它决定数据需求。34.6% 的裁剪率意味着读入 1 个 token 只有 0.654 个进入梯度，token 预算需要按 1.53 倍放大，这与 [[训练数据与FineWeb]] 中「170 个 shard 而不是 150 个」直接相关。
- 它决定分布式与续训是否正确。行组级分片、`(pq_idx, rg_idx, epoch)` 状态、以及「续训时跳过一整轮行组」的约定，三者共同保证每个 token 在一个 epoch 内被且仅被一个 rank 消费一次。
- 它决定损失曲线是否可读。切换到 BOS 对齐后，验证损失的绝对值整体下降，`dev/LOG.md` 明确标注此前的实验数值不可直接比较。
- 在全书中的位置：前置为 [[训练数据与FineWeb]]（shard 与行组）与 [[词表与特殊token]]（BOS 与编码接口）；后续为 [[训练脚本与speedrun]]（消费该 loader 的循环）与 [[检查点与恢复]]（保存与恢复 state_dict）。对应能力目标：懂原理对应「说明 best-fit 的约束与下界」，能复现对应「写出等价打包器并核对裁剪率」，懂工程对应「解释 DDP 分片与续训跳过量」。

## 原理与推导

### 步骤 1 平坦 token 流的问题

最直接的做法是把所有文档编码后拼成一条长 token 流，再按 $B\times T$ 切片。旧的 `tokenizing_distributed_data_loader` 正是这样做的：维护一个 token 缓冲，每次取 $B\cdot T$ 个 token 重塑为矩阵。它有两个后果。

第一，大多数行不从文档边界开始。若文档平均长度为 $\bar{L}$ 个 token，则 token 流中 BOS 的比例为 $1/\bar{L}$，随机切点落在 BOS 上的概率同为 $1/\bar{L}$。取 $\bar{L}=500$，只有约 0.2% 的行以 BOS 开头；其余 99.8% 的行从一个被截断的文档中间开始。

第二，被截断的前缀让预测变难。位置 $t$ 的 token 只能看到 $[0,t]$ 内的 token，若文档的前缀被切掉，模型缺少指代与主题信息，交叉熵偏高。这些位置在 `dev/LOG.md` 中称为 confusing tokens。它们不是模型能力不足，而是输入被人为破坏。

推理阶段不存在这个问题：`Engine` 与 `chat_cli` 的输入总是以 `<|bos|>` 开头，文档边界清晰。训练与推理的输入分布不一致会同时抬高训练损失与验证损失，并使验证损失高估模型在真实上下文下的能力。

> [!info] 版本说明
> 2026 年 1 月 13 日之前，预训练使用平坦 token 流的 `tokenizing_distributed_data_loader`。该实现已从当前快照删除，模块 docstring 只保留指向 commit `3c3a3d7` 的链接用于对照；当前 master 提供的是 `_bos_bestfit` 系列。docstring 建议在「数据极少且文档极长」时参考旧实现，但仓库不再提供可调用的回退，需要自行从历史提交取回。

### 步骤 2 目标的形式化

设第 $i$ 篇文档编码后的长度为 $l_i$（已含 BOS），行容量 $R=T+1$。打包问题是在线装箱：文档按流式顺序到达，每个文档必须整篇放入某一行，或裁掉尾部后放入；每行容量 $R$，且每行的第一个 token 必须是某个文档的 BOS。

定义两个指标：

$$
U=\frac{\sum_{\text{rows}} \text{placed}}{\#\text{rows}\cdot R},\qquad
C=\frac{\sum_{\text{consumed}} (l_i-\text{placed}_i)}{\sum_{\text{consumed}} l_i}.
$$

$U$ 衡量行被填满的程度，$C$ 衡量读入 token 被丢弃的比例。两者分母不同，不能互相替代：padding 方案 $U<1$、$C$ 小；裁剪方案 $U=1$、$C$ 大。

三个约束共同决定了解空间：

1. 在线性：文档只能按到达顺序消费，不能预先看到全部语料后重排。
2. 整篇优先：能整篇放入的文档不应被裁剪，否则会无谓丢弃可用 token。
3. 行首 BOS：每行从一个文档的起点开始，因此行内第 $k$ 篇文档的 BOS 一定在行内，且位于前一文档结束之后。

裁剪率存在下界。长度超过 $R$ 的文档永远无法整篇放入，其超出 $R$ 的尾部必然被丢弃；若这类文档贡献的 token 占全部 token 的 22.9%，则任何满足上述约束的算法都有 $C\ge 22.9\%$。这个下界解释了为什么数据加载器的优化空间只有约 12 个百分点：39.4% 的贪心裁剪与 34.6% 的 best-fit 裁剪都在 22.9% 之上，差距来自「不巧的裁剪」。

### 步骤 3 四种策略的实测对比

`dev/LOG.md` 2026-01-13 在真实数据、$T=2048$ 上测得：

| 策略 | 利用率 | 裁剪率 | padding 率 | 说明 |
|---|---|---|---|---|
| Greedy-Crop | 100% | 39.4% | 0% | 取下一篇，放不下就裁 |
| Greedy-Pad | 78% | 23.0% | 22% | 放不下就 padding，浪费算力 |
| First-Fit Decreasing | 99.7% | 23.0% | 0.3% | 接近最优装箱，但需要预知全部长度 |
| BestFit-Crop | 100% | 34.6% | 0% | 在缓冲区中搜索，当前默认 |

理论上限与实现选择的关系可以这样读：FFD 的 23.0% 裁剪率几乎等于下界 22.9%，说明它几乎不产生「不巧的裁剪」；但它需要按长度降序排列全部文档，破坏在线性与流式读取，且留下 0.3% padding。best-fit 用 1000 篇的局部缓冲换取 34.6%，在流式约束下是折中。

### 步骤 4 best-fit 算法的逐步过程

对每一行执行：

1. 令 `pos = 0`。
2. 若 `doc_buffer` 中文档数小于 `buffer_size`，调用 `refill_buffer()` 补足到 1000 篇。
3. 计算 `remaining = row_capacity - pos`。
4. 线性扫描缓冲区，找长度不超过 `remaining` 且最长的文档 `best_idx`。
5. 若找到，弹出该文档，整篇写入 `row_buffer[row_idx, pos:pos+doc_len]`，`pos += doc_len`。
6. 若未找到，说明所有文档都长于 `remaining`；取缓冲区中最短的一篇，裁到 `remaining` 写入，`pos` 直接到达行尾。
7. 重复直到 `pos == row_capacity`。

两个选择各有理由。第 4 步取「能放下的最长文档」是 best-fit 的直接实现：它让剩余空间尽可能小，减少后续必须裁剪的概率。第 6 步取「最短文档」是因为此时无论选哪篇都要丢弃尾部，丢弃量 $l_i-\text{remaining}$ 在 $l_i$ 最小时最小。

复杂度可以估。每行需要的整篇文档数约为 $R/\bar{L}$，取 $R=2049$、$\bar{L}=500$ 时约 4 篇；每次扫描 1000 篇，故每行约 4000 次长度比较。一个训练步消费 $B=16$ 行、8 个 rank 共 128 行，约 $5.1\times10^{5}$ 次比较，与一个训练步约 $5\times10^{15}$ FLOPs 的计算量相比可忽略。

### 步骤 5 100% 利用率与 34.6% 裁剪的后果

100% 利用率意味着 `row_buffer` 的每个位置都被写入真实 token，`loss` 在全部 $B\cdot T$ 个位置上计算，没有 `ignore_index` 位置。这与 SFT 的 padding 方案形成对照：后者的 padding 位置必须在目标里置 -1，否则模型会学习预测 BOS。

34.6% 裁剪意味着有效 token 系数为 0.654。若训练需要 $D$ 个有效 token，则必须读入 $D/0.654\approx1.53D$ 个 token。对 d24 的 5.84B token 预算，需读入约 8.9B token；`dev/LOG.md` 估计约 150 个 shard 已够，而 `runs/speedrun.sh` 下载 170 个，脚本注释把多出的 20 个称为 padding，用于吸收裁剪与行组边界的波动。

裁剪还带来一个分布效应：长文档的尾部总会以更高概率被丢弃，因此训练分布相对原始语料略偏向文档前段。`dev/LOG.md` 指出这一偏移存在，但下游指标未观察到影响；原因是文档尾部与头部在语言建模上同分布的程度较高，且每个文档的头部仍被完整训练。

切换本身也改变了损失的绝对值。`dev/LOG.md` 在同一篇记录末尾给出说明：改用 BOS 对齐后，验证损失与之前所有实验不可直接比较，因为训练与验证批次中「令人困惑」的 token 大幅减少，每个 token 都能回看到 BOS 并获得完整文档上下文，损失看起来更低，但这一降低部分是人造效果；预期是此前做过的绝大多数相对比较在切换前后仍然成立。实践含义有两条：跨切换点比较只能看相对排序，不能看绝对 bpb；引用旧实验的损失数值时必须标注数据加载器版本。

### 步骤 6 `_document_batches`：DDP 分片与续训状态

该函数是一个无限迭代器，每次产出一批文本和三元组状态。核心逻辑分四层：

```python
ddp, ddp_rank, ddp_local_rank, ddp_world_size = get_dist_info()
warn_on_legacy = ddp_rank == 0 and split == "train"
parquet_paths = list_parquet_files(warn_on_legacy=warn_on_legacy)
assert len(parquet_paths) != 0, "No dataset parquet files found, did you run dataset.py?"
parquet_paths = parquet_paths[:-1] if split == "train" else parquet_paths[-1:]
```

第一层确定分片：沿用 [[训练数据与FineWeb]] 的约定，训练集为除最后一个文件外的全部 shard，验证集只含最后一个。

```python
resume_pq_idx = resume_state_dict["pq_idx"] if resume_state_dict is not None else 0
resume_rg_idx = resume_state_dict["rg_idx"] if resume_state_dict is not None else None
resume_epoch = resume_state_dict.get("epoch", 1) if resume_state_dict is not None else 1
first_pass = True
pq_idx = resume_pq_idx
epoch = resume_epoch
```

第二层读取续训状态。`epoch` 默认 1，`rg_idx` 默认 `None` 表示从头开始。

```python
while pq_idx < len(parquet_paths):
    pf = pq.ParquetFile(parquet_paths[pq_idx])
    if first_pass and (resume_rg_idx is not None) and (pq_idx == resume_pq_idx):
        base_idx = resume_rg_idx // ddp_world_size
        base_idx += 1  # advance by 1 so we don't repeat data after resuming
        rg_idx = base_idx * ddp_world_size + ddp_rank
        if rg_idx >= pf.num_row_groups:
            pq_idx += 1
            continue
        resume_rg_idx = None
    else:
        rg_idx = ddp_rank
    while rg_idx < pf.num_row_groups:
        rg = pf.read_row_group(rg_idx)
        batch = rg.column('text').to_pylist()
        for i in range(0, len(batch), tokenizer_batch_size):
            yield batch[i:i+tokenizer_batch_size], (pq_idx, rg_idx, epoch)
        rg_idx += ddp_world_size
    pq_idx += 1
```

第三层是分片本身：rank `r` 读取行组 $r, r+W, r+2W,\dots$，其中 $W$ 为世界大小。若 `num_row_groups` 不能被 $W$ 整除，最后一个不完整的轮次里部分 rank 少读一个行组，但没有任何行组被两个 rank 同时读取，也没有行组被跳过。

第四层是续训的具体算术。设 $W=8$，保存时 rank 0 的 `rg_idx = 8`。恢复时 `base_idx = 8//8 + 1 = 2`，于是各 rank 从 `2*8 + r` 即 16 至 23 开始，行组 8 至 15 被跳过。跳过的原因写在注释里：保存的 `rg_idx` 是「已经交给分词器的那一批」的位置，而该批的数据可能尚未完成一次参数更新，重复读取会导致同一批数据被训练两次；跳过一整轮是保守的近似。

该近似有代价：最多丢失 $W$ 个行组的数据，约 $8\times1024=8192$ 篇文档。对 5.84B token 的训练，这是可忽略的量，但它意味着续训后的 loss 曲线不是严格连续的。

### 步骤 7 `refill_buffer` 与 BOS 前置

`refill_buffer` 把文本批编码为 token 列表：

```python
def refill_buffer():
    nonlocal pq_idx, rg_idx, epoch
    doc_batch, (pq_idx, rg_idx, epoch) = next(batches)
    token_lists = tokenizer.encode(doc_batch, prepend=bos_token, num_threads=tokenizer_threads)
    for tokens in token_lists:
        doc_buffer.append(tokens)
```

`prepend` 的语义在 `nanochat/tokenizer.py` 中实现：

```python
ids = self.enc.encode_ordinary_batch(text, num_threads=num_threads)
if prepend is not None:
    for ids_row in ids:
        ids_row.insert(0, prepend_id)
```

因此 BOS 是在 Python 层插入列表首位的，不经过 BPE 合并。这保证了两件事：每个文档的第一个 token 恒为 BOS，且 BOS 不会被与后续字节合并。行首之所以恒为 BOS，是因为每行第一个放入的文档从它的 BOS 开始写。

`tokenizer_threads` 默认 4，`num_threads` 传给 tiktoken 的 `encode_ordinary_batch`；分词在 CPU 上完成，与 GPU 前向重叠。`tokenizer_batch_size=128` 决定每次 yield 的文档数，也决定 state 的粒度：state 记录的是行组，而不是 128 篇中的第几篇，因此续训无法精确到子批次。

### 步骤 8 预分配 buffer 与单次 HtoD

函数在进入循环前分配三块内存：

```python
row_capacity = T + 1
row_buffer = torch.empty((B, row_capacity), dtype=torch.long)                 # CPU
cpu_buffer = torch.empty(2 * B * T, dtype=torch.long, pin_memory=use_cuda)    # 固定页
gpu_buffer = torch.empty(2 * B * T, dtype=torch.long, device=device)          # 显存
cpu_inputs = cpu_buffer[:B * T].view(B, T)
cpu_targets = cpu_buffer[B * T:].view(B, T)
inputs = gpu_buffer[:B * T].view(B, T)
targets = gpu_buffer[B * T:].view(B, T)
```

布局是 `[inputs (B*T) | targets (B*T)]`，两块连续内存通过切片视图切开。填充完一行后：

```python
cpu_inputs.copy_(row_buffer[:, :-1])
cpu_targets.copy_(row_buffer[:, 1:])
state_dict = {"pq_idx": pq_idx, "rg_idx": rg_idx, "epoch": epoch}
gpu_buffer.copy_(cpu_buffer, non_blocking=use_cuda)
yield inputs, targets, state_dict
```

`row_buffer[:, :-1]` 是前 $T$ 个 token，`row_buffer[:, 1:]` 是后 $T$ 个，因此目标就是输入右移一位。行尾第 $T+1$ 个 token 只作为最后一个目标的来源，不进入输入。

三块 buffer 只分配一次，之后每批复用；HtoD 只有一次 `copy_`，且 `non_blocking=True` 使其可以与后续计算重叠。代价是 yielded 的 `inputs`/`targets` 是 `gpu_buffer` 的视图：下一批会覆盖同一块显存，消费者不能在两次 `next()` 之间保留引用。

### 步骤 9 函数体逐段注释

以下为 `nanochat/dataloader.py:74` 的函数体节选；`refill_buffer` 的定义与缓冲复制段已分别在步骤 7、8 给出，此处按原文保留其余结构。

```python
def tokenizing_distributed_data_loader_with_state_bos_bestfit(
    tokenizer, B, T, split,
    tokenizer_threads=4, tokenizer_batch_size=128,
    device="cuda", resume_state_dict=None,
    buffer_size=1000
):
    assert split in ["train", "val"], "split must be 'train' or 'val'"
    row_capacity = T + 1
    batches = _document_batches(split, resume_state_dict, tokenizer_batch_size)
    bos_token = tokenizer.get_bos_token_id()
    doc_buffer = []
    pq_idx, rg_idx, epoch = 0, 0, 1
    # refill_buffer 的定义见步骤 7
    while True:
        for row_idx in range(B):
            pos = 0
            while pos < row_capacity:
                while len(doc_buffer) < buffer_size:
                    refill_buffer()
                remaining = row_capacity - pos
                best_idx = -1
                best_len = 0
                for i, doc in enumerate(doc_buffer):
                    doc_len = len(doc)
                    if doc_len <= remaining and doc_len > best_len:
                        best_idx = i
                        best_len = doc_len
                if best_idx >= 0:
                    doc = doc_buffer.pop(best_idx)
                    doc_len = len(doc)
                    row_buffer[row_idx, pos:pos + doc_len] = torch.tensor(doc, dtype=torch.long)
                    pos += doc_len
                else:
                    shortest_idx = min(range(len(doc_buffer)), key=lambda i: len(doc_buffer[i]))
                    doc = doc_buffer.pop(shortest_idx)
                    row_buffer[row_idx, pos:pos + remaining] = torch.tensor(doc[:remaining], dtype=torch.long)
                    pos += remaining
        cpu_inputs.copy_(row_buffer[:, :-1])
        cpu_targets.copy_(row_buffer[:, 1:])
        state_dict = {"pq_idx": pq_idx, "rg_idx": rg_idx, "epoch": epoch}
        gpu_buffer.copy_(cpu_buffer, non_blocking=use_cuda)
        yield inputs, targets, state_dict
```

分段解读：

1. 参数默认值就是生产配置：1000 篇缓冲、4 线程分词、128 篇一批。speedrun 不覆盖这些值。
2. `while True` 与内层 `for row_idx in range(B)` 构成无限批次；没有 epoch 终止条件，训练步数由 `base_train.py` 的 `num_iterations` 决定，数据不足时自然进入第二个 epoch。
3. `while len(doc_buffer) < buffer_size` 是惰性补充：缓冲区低于 1000 时反复调用 `refill_buffer`，每次读入至多 128 篇，直到补足；这样避免每填一行都触发 I/O。
4. `row_buffer[row_idx, pos:pos + doc_len] = torch.tensor(doc, dtype=torch.long)` 把 Python 列表转成张量再写入切片；这是一次小的 CPU 拷贝，`row_buffer` 预分配的意义在于避免整行拼接。
5. `doc[:remaining]` 是唯一的裁剪点，裁掉的部分不再出现，也不计入任何目标。
6. `tokenizing_distributed_data_loader_bos_bestfit` 只是丢弃 state 的包装，供验证与评测使用；训练必须用带 state 的版本，否则无法续训。

### 步骤 10 SFT 为什么改为 best-fit-pad

`scripts/chat_sft.py:180` 的 `sft_data_generator_bos_bestfit` 复用同一套 best-fit 搜索，但最后一招不同：

```python
if best_idx >= 0:
    conv, conv_mask = conv_buffer.pop(best_idx)
    row.extend(conv)
    mask_row.extend(conv_mask)
else:
    content_len = len(row)
    row.extend([bos_token] * remaining)  # Pad with BOS tokens
    mask_row.extend([0] * remaining)
    padded = True
    break
```

差异有三点。缓冲从 1000 降到 100，因为对话远短于文档，100 已足够覆盖。放不下时 padding 而非裁剪，因为裁剪会截断 assistant 的回答，而 SFT 的监督信号只来自 assistant 段，截断会让模型学到不完整的回答。padding 位置用 BOS 填充且 mask 置 0，随后 `targets[mask_targets == 0] = -1` 与 `targets[i, content_len-1:] = -1` 双重屏蔽，不参与损失。

`dev/LOG.md` 记录 midtraining 的对话数据只有约 3.3% 的 token 被裁剪，远低于预训练文档的 34.6%，因此在 SFT 中改用 padding 的额外算力开销很小，而避免截断回答的收益明确。细节见 [[有监督微调SFT]]。

### 在 nanochat 中的落地

| 位置 | 作用 | 去掉或写错会怎样 |
|---|---|---|
| `nanochat/dataloader.py:_document_batches` | 行组级 DDP 分片、train/val 选择、续训起点 | 分片步长写成 1 会让所有 rank 读同一份数据；续训不跳过会重复训练 |
| `dataloader.py:refill_buffer` | 取文本批、`prepend=bos` 编码、追加到缓冲区 | 去掉 `prepend` 则行首不再是 BOS，退化为平坦流 |
| `dataloader.py` 的 `row_buffer`/`cpu_buffer`/`gpu_buffer` | 预分配与单次 HtoD | 每批新建张量会增加分配与同步开销，吞吐下降 |
| `dataloader.py` 的 best-fit 扫描与裁剪分支 | 100% 利用率、34.6% 裁剪 | 改成 greedy 则裁剪升至 39.4%；改成 padding 则利用率降至 78% |
| `dataloader.py:tokenizing_distributed_data_loader_with_state_bos_bestfit` | 训练用带 state 的接口 | 用无 state 版本训练则 checkpoint 缺少 `dataloader_state_dict`，续训退化为从头 |
| `scripts/base_train.py` 的 `train_loader` / `build_val_loader` | 训练用 with_state，验证每次重建 | 验证若复用训练 loader，会读到训练数据且不可比 |
| `scripts/base_eval.py` 的 `tokenizing_distributed_data_loader_bos_bestfit` | bpb 评测复用同一打包 | 若评测用平坦流，bpb 与训练日志不同口径 |
| `scripts/chat_sft.py:sft_data_generator_bos_bestfit` | SFT 的 best-fit-pad 变体 | 改成裁剪会截断回答，监督信号错误 |

`scripts/base_train.py` 的用法是：

```python
dataloader_resume_state_dict = None if not resuming else meta_data["dataloader_state_dict"]
train_loader = tokenizing_distributed_data_loader_with_state_bos_bestfit(
    tokenizer, args.device_batch_size, args.max_seq_len, split="train",
    device=device, resume_state_dict=dataloader_resume_state_dict)
build_val_loader = lambda: tokenizing_distributed_data_loader_bos_bestfit(
    tokenizer, args.device_batch_size, args.max_seq_len, split="val", device=device)
x, y, dataloader_state_dict = next(train_loader)
```

首批数据在训练循环之前预取，因此第一个训练步的 `next(train_loader)` 取的是第二批，预取与首步前向重叠。验证 loader 用 lambda 每次重建，保证每次评测都从验证 shard 的第一个行组开始，且缓冲状态不残留。

## 关键直觉

> [!tip] 100% 利用率与低裁剪率无法由「取下一篇、放不下就裁」同时达成，因为贪心只看流中的下一篇，遇到长度与剩余空间不匹配时必须整篇丢弃尾部。best-fit 用 1000 篇的局部缓冲把「读哪一篇」从顺序改为搜索，于是裁剪率从 39.4% 降到 34.6%，代价是每行约 4000 次长度比较。裁剪率的下界 22.9% 由长于 $R$ 的文档决定，与算法无关，因此这一层的优化空间只有约 12 个百分点；更大的收益来自选择更高质量的数据，见 [[训练数据与FineWeb]]。该表述与步骤 2 的 $U$、$C$ 定义和步骤 3 的实测表逐项对应。

## 例子与代码

下面的纯 Python 程序用固定长度序列模拟两种打包。为便于手算，取 $T=8$、`row_capacity=9`、缓冲 4 篇、共 8 行，文档长度序列写死。程序不依赖 torch，可直接运行。

```python
BUFFER, CAP, N_ROWS = 4, 9, 8
docs = [5,2,6,3,9,1,4,7,8,6,3,8,7,8,6,7,8,8,7,6,8,7,8,6,7,8]

def greedy():
    it, rows, placed, cropped, popped = iter(docs), [], 0, 0, 0
    for _ in range(N_ROWS):
        pos, row = 0, []
        while pos < CAP:
            d = next(it)
            take = min(d, CAP - pos)
            row.append(str(d) if take == d else f"{d}->{take}")
            placed += take; cropped += d - take; popped += d; pos += take
        rows.append(row)
    return rows, placed, cropped, popped

def bestfit():
    it, buf, rows, placed, cropped, popped = iter(docs), [], [], 0, 0, 0
    for _ in range(N_ROWS):
        pos, row = 0, []
        while pos < CAP:
            while len(buf) < BUFFER:
                buf.append(next(it))
            remaining = CAP - pos
            best, best_len = -1, 0
            for i, d in enumerate(buf):          # 找能整篇放入的最长文档
                if d <= remaining and d > best_len:
                    best, best_len = i, d
            if best >= 0:
                d = buf.pop(best); row.append(str(d))
                placed += d; popped += d; pos += d
            else:                                 # 都放不下，裁最短的填满
                j = min(range(len(buf)), key=lambda i: buf[i])
                d = buf.pop(j); row.append(f"{d}->{remaining}")
                placed += remaining; cropped += d - remaining; popped += d; pos += remaining
        rows.append(row)
    return rows, placed, cropped, popped

for name, fn in (("greedy", greedy), ("bestfit", bestfit)):
    rows, placed, cropped, popped = fn()
    print(name)
    for i, row in enumerate(rows):
        print(f"  row {i+1}: {' '.join(row)}")
    print(f"  util={placed/(N_ROWS*CAP):.3f} crop={cropped/popped:.3f} "
          f"placed={placed} cropped={cropped} consumed={popped}")
```

实际输出：

```text
greedy
  row 1: 5 2 6->2
  row 2: 3 9->6
  row 3: 1 4 7->4
  row 4: 8 6->1
  row 5: 3 8->6
  row 6: 7 8->2
  row 7: 6 7->3
  row 8: 8 8->1
  util=1.000 crop=0.321 placed=72 cropped=34 consumed=106
bestfit
  row 1: 6 3
  row 2: 9
  row 3: 5 4
  row 4: 8 1
  row 5: 7 2
  row 6: 8 3->1
  row 7: 8 6->1
  row 8: 8 6->1
  util=1.000 crop=0.143 placed=72 cropped=12 consumed=84
```

读法：两者的 `util` 都是 1.000，因为每行都写满 9 个 token；区别在 `crop`。贪心在 8 行里产生 34 个被裁 token，best-fit 只产生 12 个，相对减少 65%。注意 best-fit 的 `consumed` 更小（84 对 106），因为它更早停止消费新文档、更多使用缓冲区里已有的短文档。真实数据上差距被压缩到 4.8 个百分点（39.4% 对 34.6%），原因是 $T=2048$ 相对多数文档更长，两种算法都能整篇放入多数文档，剩下的差异只来自「剩余空间与下一篇不匹配」的少数情形。

下面的片段在真实 loader 上核对三件事：每行首 token 是 BOS、每行至少含一个 BOS、目标等于输入右移一位。需要 GPU 与已训练的 tokenizer。

```python
import torch
from nanochat.tokenizer import get_tokenizer
from nanochat.dataloader import tokenizing_distributed_data_loader_with_state_bos_bestfit

tok = get_tokenizer()
loader = tokenizing_distributed_data_loader_with_state_bos_bestfit(
    tok, B=2, T=64, split="val", device="cuda")
inputs, targets, state = next(loader)
bos = tok.get_bos_token_id()

assert (inputs[:, 0] == bos).all()                 # 每行以 BOS 开头
assert (inputs == bos).sum(dim=1).min() >= 1        # 每行至少一个 BOS
assert torch.equal(targets[:, :-1], inputs[:, 1:])  # 目标右移一位
print(state)  # {'pq_idx': 0, 'rg_idx': 0, 'epoch': 1} 附近的续训状态
```

`B=2, T=64` 仅用于检查形状与对齐，正式训练用 `B=16, T=2048`。最后一行断言的依据是 `cpu_targets.copy_(row_buffer[:, 1:])` 与 `cpu_inputs.copy_(row_buffer[:, :-1])` 共享同一行缓冲区。

## 易错点

> [!warning] 以下六条均可由一次 `next(loader)` 或一次源码核对验证。
>
> 1. 认为 `inputs` 与 `targets` 是两块独立显存。它们是 `gpu_buffer` 的两段视图，下一批会原地覆盖；把 `x` 存进列表跨步使用会读到被改写的数据。
> 2. 认为续训精确到文档。state 只记录行组，且恢复时 `base_idx += 1` 跳过一整轮行组；最多丢失 $W$ 个行组的数据，loss 曲线在恢复点不严格连续。
> 3. 把 34.6% 理解为「34.6% 的文档被裁」。它是 token 比例，被裁文档的头部仍参与训练，只有尾部被丢弃。
> 4. 认为验证 loader 也带 state。`tokenizing_distributed_data_loader_bos_bestfit` 只是丢弃 yield 中的 state，参数仍透传，`resume_state_dict` 会生效；真正的问题是验证不保存状态，且 `build_val_loader` 每次重建，验证总从固定起点开始。
> 5. 认为 DDP 分片按 batch 切。分片单位是行组（1024 篇文档），`tokenizer_batch_size=128` 只是行组内的分词子批，不改变分片。
> 6. 把 `buffer_size=1000` 当作 token 数。它是文档条数；短文档数据集上 1000 篇可能不足一行所需的 token，`refill_buffer` 会被反复调用而缓冲区仍很快耗尽。

## 关联笔记

- 前置：[[训练数据与FineWeb]] —— 本笔记的行组、shard 与 train/val 划分直接来自该篇的数据布局。
- 后续：[[训练脚本与speedrun]] —— `base_train.py` 如何消费本 loader，以及 grad accumulation 与预取如何重叠。
- 后续：[[检查点与恢复]] —— `dataloader_state_dict` 与 `meta_data["loop_state"]` 一起构成断点续训的完整状态。
- 对照：[[有监督微调SFT]] —— 同一 best-fit 思想在 SFT 中改为 padding，原因见步骤 10。
- 跨库：[[预训练-微调-对齐pipeline]] —— 通用原理见该篇，本篇只讲 nanochat 的在线装箱实现与状态管理。

## 达标检测

- [ ] 能写出 `U` 与 `C` 的公式，并说明为什么两者的分母不同。
- [ ] 能复述 best-fit 的 7 个步骤，并解释「取最长能放下的文档」与「裁最短文档」各自的理由。
- [ ] 能说明 Greedy-Crop、Greedy-Pad、FFD、BestFit-Crop 四种策略的利用率与裁剪率，并解释 FFD 为何未被采用。
- [ ] 能推导 22.9% 裁剪下界的来源，并说明剩余优化空间的大致范围。
- [ ] 给定世界大小与保存时的 `rg_idx`，能算出恢复后各 rank 的起始行组，并指出被跳过的行组区间。
- [ ] 能解释为什么 HtoD 只需要一次，以及 yielded 张量为何不能跨步保留。
- [ ] 能说明 SFT 改用 padding 的三条理由，并指出 padding 位置如何被屏蔽。
- [ ] 能运行本篇的纯 Python 模拟，把文档长度序列改一处并预测裁剪率的变化方向。

## 参考来源

- Karpathy, *nanochat*（commit `92d63d4`），`nanochat/dataloader.py` —— 对应本篇的 `_document_batches`、best-fit 循环、三块缓冲区与 yield 语义。
- Karpathy, *nanochat* `dev/LOG.md`（2026-01-13「BOS-Aligned Dataloader with Bin Packing」）—— 对应四种策略的实测利用率与裁剪率、22.9% 下界与 loss scale 说明。
- Karpathy, *nanochat* `scripts/chat_sft.py`（commit `92d63d4`）—— 对应 best-fit-pad 变体、BOS padding 与目标屏蔽。
- Hoffmann et al., *Training Compute-Optimal Large Language Models*（arXiv:2203.15556）—— 对应 token 预算与多 epoch 的取舍，即步骤 5 的有效 token 系数。
- Karpathy, *modded-nanogpt* —— 对应把文档打包进定长序列、并以 100% 利用率训练的工程传统，nanochat 的 best-fit 是其在线版本。
