Rust in Everything
基于 pulldown-cmark 0.13.5

一次解析分配了什么

主线位置：块主线和行内主线的内存账。Parser::new_ext 跑完第一遍，手里是一棵树和一个 Allocations；Parser::next 跑第二遍时再借几个栈、往表里添东西；Parser 被 drop 时一起释放。这一页把这三个阶段的每一次分配都记下来，按来源归类。

flowchart TB
  newp["Parser::new_ext"] --> tree["树 起步 6144 B"]
  newp --> links["links 表 10240 B"]
  newp --> fp["第一遍扫行"]
  fp --> grow["树翻倍扩容"]
  fp --> small["spine 等小表"]
  nx["Parser::next"] --> stk["行内用的两个栈"]
  nx --> cows["cows 表扩容"]
  nx --> bx["少量 Boxed"]
  dropp["drop Parser"] --> free["一次释放"]

README 说这个库「a bare minimum of allocation and copying」。这一页用数字核对这句话：分配次数确实少，但每个解析器起步就要 16 KB，字节数主要花在树上。

实验方法

实验 crate exp-pulldown-cmark/events-exp 的 allocs（M2 Max、macOS 27、rustc 1.99.0，release，带调试信息）装了一个 #[global_allocator]：包一层 System，在每次 alloc 和 realloc 里沿 aarch64 的帧指针链（x29）往上走最多 28 层，把返回地址连同大小记进一张静态哈希表。走栈本身不分配，所以不会递归；记录结束、关掉开关之后才用 backtrace crate 把地址解析成函数名和行号（包括内联进来的帧），按最内层的几个 pulldown-cmark 帧归类。

  • 分配次数：alloc 调用数；realloc 单独计。
  • 字节数：alloc 的大小加上 realloc 增长的部分，是累计申请量，不是同时占用量。
  • 峰值：测量期间同时存活的字节数的最大值。
  • 阶段：new_ext（第一遍）、逐个取事件并立即丢弃（第二遍）、drop(parser)；TextMergeStream 和 into_static 各自另跑一遍完整解析。
  • 正式测量前先解析一份小文档预热，排除进程里只发生一次的初始化。

Allocations 的六张表

第一遍和第二遍要交给事件的数据，不放在树节点里，而是放在 Allocations 的表里，节点只记一个下标（扁平数组上的树讲过为什么）：

pub(crate) struct Allocations<'a> {
    pub refdefs: RefDefs<'a>,
    pub footdefs: FootnoteDefs<'a>,
    links: Vec<(LinkType, CowStr<'a>, CowStr<'a>, CowStr<'a>)>,
    cows: Vec<CowStr<'a>>,
    alignments: Vec<Vec<Alignment>>,
    headings: Vec<HeadingAttributes<'a>>,
}
表谁往里写谁取走
refdefs第一遍 parse_block 收链接引用定义，同名的先到先得（entry(label).or_insert）第二遍解析引用链接时查，每次 clone
footdefs第一遍收脚注定义第二遍查，记 use_count
links第二遍 allocate_link，每个解析成功的链接、图片、自动链接一项item_to_event 用 take_link 取走
cows两遍都写：实体、围栏 info string、脚注标签、长串连字符（第一遍），行内代码、公式、脚注引用、跨行的行内 HTML（第二遍）take_cow 取走
alignments第一遍识别到表格时Table 的 Start 用 take_alignment 取走
headings第一遍解析标题属性时Heading 的 Start 每次 clone

取走（take_*）是 std::mem::replace 成空串或默认值，槽位不回收，Vec 也不缩：表只增不减，一直活到 Parser 被 drop。Allocations::new 只给 links 预留了 128 项，其余都从空开始。

例子文档：9 次分配

一份文档那 21 行（502 字节，ENABLE_TABLES）。阶段汇总：

input 502 bytes, 72 events, 70 after TextMergeStream
phase                          allocs reallocs    frees        bytes    peak_live
new_ext (first pass)                7        0        0        17012        17012
iterate (second pass)               2        1        1          288        17292
drop Parser                         0        0        8            0        11148
new_ext + TextMergeStream          10        3       10        17312        17292
new_ext + into_static              14        1       14        17489        17292

（drop Parser 一行的 peak_live 是进入这个阶段时的存量，不是新增。）每一次分配，[1] 是第一遍，[2] 是第二遍：

[1]           6144  <tree::Tree<parse::Item>>::with_capacity (tree.rs:65)  <-  firstpass::run_first_pass (firstpass.rs:34)  <-  <parse::Parser>::new_with_broken_link_callback (parse.rs:283)
[1]          10240  <parse::Allocations>::new (parse.rs:2079)  <-  firstpass::run_first_pass (firstpass.rs:37)  <-  <parse::Parser>::new_with_broken_link_callback (parse.rs:283)
[1]             32  <tree::Tree<parse::Item>>::push (tree.rs:112)  <-  <firstpass::FirstPass>::parse_block (firstpass.rs:92)  <-  <firstpass::FirstPass>::run (firstpass.rs:75)
[1]             96  <parse::Allocations>::allocate_cow (parse.rs:2088)  <-  <firstpass::FirstPass>::parse_line::{closure#0} (firstpass.rs:1112)  <-  firstpass::scalar_iterate_special_bytes::<<firstpass::FirstPass>::parse_line::{closure#0}, parse::Item> (firstpass.rs:2456)
[1]              8  scanners::scan_table_head (scanners.rs:692)  <-  <firstpass::FirstPass>::parse_line::{closure#0} (firstpass.rs:831)  <-  firstpass::scalar_iterate_special_bytes::<<firstpass::FirstPass>::parse_line::{closure#0}, parse::Item> (firstpass.rs:2456)
[1]             96  <parse::Allocations>::allocate_alignment (parse.rs:2106)  <-  <firstpass::FirstPass>::parse_line::{closure#0} (firstpass.rs:840)  <-  firstpass::scalar_iterate_special_bytes::<<firstpass::FirstPass>::parse_line::{closure#0}, parse::Item> (firstpass.rs:2456)
[1]            396  <firstpass::FirstPass>::parse_block (firstpass.rs:380)  <-  <firstpass::FirstPass>::run (firstpass.rs:75)  <-  firstpass::run_first_pass (firstpass.rs:43)
[2]            128  <parse::InlineStack>::push (parse.rs:1742)  <-  <parse::Parser>::handle_emphasis_and_hard_break (parse.rs:1094)  <-  <parse::Parser>::handle_inline (parse.rs:391)
[2]             64  <parse::LinkStack>::push (parse.rs:1840)  <-  <parse::Parser>::handle_inline_pass1 (parse.rs:617)  <-  <parse::Parser>::handle_inline (parse.rs:390)
[2]      R 96->192  <parse::Allocations>::allocate_cow (parse.rs:2088)  <-  <parse::Parser>::make_code_span (parse.rs:1435)  <-  <parse::Parser>::handle_inline_pass1 (parse.rs:587)

逐行对账（行号是 0.13.5 的源码行）：

  • 6144 = 128 × 48。run_first_pass 按 max(128, text.len() / 32) 估节点数，502 字节估出 128；一个 Node<Item> 48 字节。这份文档实际用了 70 项。
  • 10240 = 128 × 80。links 预留的 128 项，每项是 (LinkType, CowStr, CowStr, CowStr)，实测 80 字节。整份文档只有 1 个链接。
  • 32：spine 第一次 push，Vec<TreeIndex> 起步 4 项 × 8 字节。
  • 96：cows 第一次 push，4 项 × 24 字节。推进去的是 &amp; 解出的 &，一个借静态表的 Borrowed，字符串本身不分配，分配的是表。
  • 8 和 96：表格。scan_table_head 收集每列对齐的 Vec<Alignment>（起步 8 项 × 1 字节），交给 alignments（起步 4 项 × 24 字节）。
  • 396：refdefs 第一次插入（firstpass.rs 第 380 行的 entry(label).or_insert），一个 HashMap 的第一块桶。
  • 128 和 64：第二遍的分隔符栈 InlineStack（4 项 × 32 字节）和链接栈 LinkStack（4 项 × 16 字节）第一次 push。这两个栈放在 Parser 里复用，整份文档只分配一次。
  • 96→192：第 5 个 CowStr 进 cows（行内代码 Parser::next），表从 4 项长到 8 项。

两遍合计 9 次分配、1 次 realloc，峰值 17 292 字节，是输入的 34 倍。其中 16 384 字节是 new_ext 一开头的两块，和文档内容无关。

📝NOTE
冷知识：两块预留来自 0.5.0 的「Smaller tree」

最早的 FirstPass::new 用 Tree::new()，节点数组从空开始一路翻倍。提交 fa89e46（「Reserve space for nodes in advance」）加上了 max(128, text.len() / 32) 和那句注释「This is a very naive heuristic for the number of nodes we'll need.」，同时把 Allocations 从 Default 改成手写的 new，给 cows 预留 128 项；同一个 PR 里稍后的提交 ee9c0ba（「Improve ergonomics of Allocations somewhat」）把这 128 项从 cows 挪给了 links。两个提交都随 PR #274（「Smaller tree」）首次发布于 0.5.0。那时 links 的元素只有 (LinkType, CowStr, CowStr)；PR #436 的提交 2ea7808（「add link identifiers into emitted tags」，首次发布于 0.10.0）加了第三个 CowStr 存引用标签，元素长到今天的 80 字节，预留的 128 项也跟着变成 10 KB。

本站语料：1099 篇

把本站内容仓库的 1099 篇 Markdown（去掉 frontmatter 后 17 971 168 字节，不做本站渲染前的 ::: 提示块转换）逐篇解析，选项用本站 mdx.rs 的七个：

1099 files, 17971168 bytes, 702096 events, 700582 after TextMergeStream
phase                          allocs reallocs    frees        bytes    peak_live
new_ext (first pass)             6300     2948      153     78591312       329840
iterate (second pass)            2155     4182     1329      6324827       352320
drop Parser                         0        0     6973            0        35308
new_ext + TextMergeStream        8914     8318     8914     84971376       352320
new_ext + into_static          161939     7130   161939     99091917       352800

平均每篇 7.7 次分配、6.5 次 realloc；逐篇统计，分配次数中位数 8、最多 18。把累计字节按最内层的 pulldown-cmark 函数归类：

来源阶段分配realloc累计字节
树扩容（Tree::create_node）第一遍0122739 332 160
树的初始容量（Tree::with_capacity）第一遍1099027 508 704
links 预留（Allocations::new）第一遍1099011 253 760
cows 表（allocate_cow）第二遍1641276 100 224
cows 表（allocate_cow）第一遍10831676391 680
分隔符栈（InlineStack::push）第二遍8420107 776
链接栈（LinkStack::push）第二遍1098070 272
表格对齐（allocate_alignment、scan_table_head）第一遍18024268 800
spine（Tree::push）两遍10991235 552
links 超过 128 项（allocate_link）第二遍0330 720
行内代码的分隔符表（CodeDelims::insert）第二遍163714 528
跨行行内代码的 String（make_code_span）第二遍36361 019

树占了第一遍字节的 85%，links 的固定预留占 14%；CowStr::Boxed 只有那 36 个跨行的行内代码，一共 1 KB。refdefs 的 HashMap 在整个语料里一次也没分配过。cows 在第一遍的 1083 次分配几乎都来自围栏代码块：每个代码块的 info string（哪怕是借用的 rust）都要进 cows。

估算偏小

第一遍的字节一半花在扩容上，因为 text.len() / 32 对这份语料估少了。用一份打了补丁、能读出节点数的源码副本（exp-pulldown-cmark/events-vendor-pcm，只加了一个返回 nodes.len() 的方法）数了每篇的节点：

docs 1099 bytes per node median 18.1 p10 13.5 p90 24.3
total bytes 17971168 nodes 1012782 events 702096 bytes/node 17.7 events/node 0.69
nodes exceed estimate 985

平均 17.7 字节一个节点，不到 32 的一半。1099 篇里 985 篇超出了初始容量：746 篇翻倍一次，236 篇两次，3 篇三次。这份语料行内代码多（17 万个 Code 事件，每个在第一遍是两个 MaybeCode 节点加中间的文本），表格多（2.6 万个单元格）。作为对照，英文的 CommonMark 规范 spec.txt（183 524 字节，不开选项）是 21.3 字节一个节点，初始估 5735 项、实际 8622 项，也扩容了一次。

翻倍扩容的代价是复制和空闲：峰值最高的一篇 53 170 字节，节点 3755 个，数组却已经翻到 6644 项（1661 × 4），近一半是空的，这篇的峰值 352 320 字节，是输入的 6.6 倍。逐篇看，峰值与输入之比中位数 4.6（10% 分位 3.65，90% 分位 9.6）；最小的一篇 323 字节，峰值 16 576 字节，51 倍，几乎全是那 16 KB 固定开销。

📝NOTE
没有蠢问题

问： 第二遍用 take_cow、take_link 把字符串交给事件了，内存是不是边走边降？

答： 不降。取走只是把槽位换成空串，Vec 的容量不变；树的节点一个也不删，第二遍还在原地改写它们（MaybeCode 变成 Code、方括号变成 Link）。所以峰值出现在第二遍，等于第一遍建好的全部结构加上第二遍新长出来的 cows、两个栈。例子文档的 8 次释放全部发生在 drop Parser 那一刻；第二遍唯一的一次释放是 Start(Table) 事件带走的对齐 Vec，随事件一起被丢掉。

TextMergeStream 多了什么

TextMergeStream 是 TextMergeWithOffset 套一个把偏移填成 0..0 的适配器。合并的核心在 TextMergeWithOffset::next：

            (
                Some((Event::Text(last_text), last_offset)),
                Some((Event::Text(next_text), next_offset)),
            ) => {
                // We need to start merging consecutive text events together into one
                let mut string_buf: String = last_text.into_string();
                string_buf.push_str(&next_text);
                // ...
                                break Some((
                                    Event::Text(CowStr::Boxed(string_buf.into_boxed_str())),
                                    offset,
                                ));

它总是先看一个事件：手里攥着上一个，再取下一个，两个都是 Text 才合并。合并必然分配：into_string 把第一段复制成 String，后面每段 push_str 可能扩容，最后 into_boxed_str 把多余容量缩掉，又是一次 realloc。例子文档里引用块那句 和 A、&、B， 被拼成一个，分配记录是：

[4]              6  <strings::CowStr>::into_string (strings.rs:0)  <-  <utils::TextMergeWithOffset<utils::DummyOffsets<parse::Parser>> as core::iter::traits::iterator::Iterator>::next (utils.rs:91)  <-  <utils::TextMergeStream<parse::Parser> as core::iter::traits::iterator::Iterator>::next (utils.rs:39)
[4]        R 6->12  <utils::TextMergeWithOffset<utils::DummyOffsets<parse::Parser>> as core::iter::traits::iterator::Iterator>::next (utils.rs:92)  <-  <utils::TextMergeStream<parse::Parser> as core::iter::traits::iterator::Iterator>::next (utils.rs:39)
[4]       R 12->11  <utils::TextMergeWithOffset<utils::DummyOffsets<parse::Parser>> as core::iter::traits::iterator::Iterator>::next (utils.rs:109)  <-  <utils::TextMergeStream<parse::Parser> as core::iter::traits::iterator::Iterator>::next (utils.rs:39)

一次 6 字节的分配，长到 12，再缩回 11 字节（ 和 A&B， 的 UTF-8 长度）。语料上合计多了 459 次分配、1188 次 realloc、55 237 字节，事件少了 1514 个，正好等于「紧跟在另一个 Text 后面的 Text」的个数。

分配不多，时间却明显变长。实验 census 不装计数分配器，对整个语料各跑 20 次取最小（测量时 uptime 负载 3.75）：

lookahead-only adapter 47.59 ms (702096)
min of 20: plain 42.73 ms (702096 events, 421 MB/s), TextMergeStream 54.06 ms (700582), plain+into_static 54.30 ms (702096)
方式时间比直接迭代
直接迭代 Parser42.73 ms
只缓冲一个事件、从不合并的适配器47.59 ms+11%
TextMergeStream54.06 ms+27%
每个事件 into_static54.30 ms+27%

459 次小分配解释不了 11 ms。只做「先看一个」缓冲的适配器已经多出 4.9 ms：每个 80 字节的事件（带偏移是 96 字节）要多搬进搬出一个 Option。TextMergeStream 在此之上还多一层 DummyOffsets，每个事件都过一遍四路 match。想要合并文本又在意这 27%，可以只在自己关心的那几种事件附近手工拼接。改写事件流的更多做法见改写事件流。

❗IMPORTANT
动脑筋：Parser::new_ext("", Options::empty()) 分配几次、多少字节？空字符串，没有一行要扫。答案在文末。

动脑筋答案

input 0 bytes, 0 events, 0 after TextMergeStream
phase                          allocs reallocs    frees        bytes    peak_live
new_ext (first pass)                2        0        0        16384        16384
iterate (second pass)               0        0        0            0            0
drop Parser                         0        0        2            0        10240
...
-- every allocation (R = realloc old->new)
[1]           6144  <tree::Tree<parse::Item>>::with_capacity (tree.rs:65)  <-  firstpass::run_first_pass (firstpass.rs:34)  <-  <parse::Parser>::new_with_broken_link_callback (parse.rs:283)
[1]          10240  <parse::Allocations>::new (parse.rs:2079)  <-  firstpass::run_first_pass (firstpass.rs:37)  <-  <parse::Parser>::new_with_broken_link_callback (parse.rs:283)

2 次，16 384 字节：树至少 128 项（6144 字节），links 固定 128 项（10 240 字节），和输入长度无关。只有一个单词的 hello\n 是 3 次、16 416 字节，多出来的 32 字节是 spine 第一次压栈。对一个要反复解析大量短字符串的程序（比如逐条渲染评论），这 16 KB 是每条都要付的。

小结

  • 解析器起步就分配两块：树 max(128, len/32) × 48 字节，links 128 × 80 = 10 240 字节；空字符串也是 16 384 字节。来自 PR #274（0.5.0），links 的元素在 PR #436（0.10.0）长到 80 字节。
  • 例子文档（502 字节）两遍共 9 次分配、1 次 realloc，峰值 17 292 字节；本站语料每篇中位 8 次分配，次数确实少。
  • 字节主要在树上：本站语料 17.7 字节一个节点，len / 32 估少了，90% 的文档要翻倍扩容，峰值中位数是输入的 4.6 倍。
  • Allocations 的表只增不减，take_* 只换空值；内存在 drop 时一次释放。CowStr::Boxed 在语料上只有 36 次、1 KB。
  • TextMergeStream 每次合并新分配一个 String，语料上多 459 次分配，但时间多 27%，主要花在逐个缓冲和搬动 80 字节的事件上。

💬 关联讨论

发起讨论
加载中...