第6章 单态化：泛型的编译期展开

零成本抽象不是没有成本，而是把成本从运行时搬到了编译时。单态化就是这笔账单的具体明细。

6.1 什么是单态化

在 Rust 中，泛型函数并不直接编译为可执行代码。编译器在编译期找到所有调用点，确定每次调用使用的具体类型参数，然后为每个独特的类型参数组合生成一份完全独立的函数实现。这个过程就是单态化——将多态（polymorphic）的泛型代码，转化为具体类型的单态（monomorphic）代码。

// 你写的泛型函数——一份源码
fn max<T: PartialOrd>(a: T, b: T) -> T {
    if a > b { a } else { b }
}

fn main() {
    max(1_i32, 2_i32);     // T = i32
    max(3.14_f64, 2.71);   // T = f64
    max("hello", "world"); // T = &str
}

编译器看到三种不同的类型参数，生成三份独立函数。在 LLVM IR 层面，i32 使用 icmp sgt（有符号整数比较），f64 使用 fcmp ogt（浮点数比较），&str 走 memcmp 字节序比较。运行时没有任何类型判断、没有虚函数调用、没有装箱拆箱——这就是零成本抽象的本质。

用 cargo rustc -- --emit=llvm-ir 可以直接观察产物（默认 debug 构建；release 构建下这三个实例会被内联进 main，而返回值没人用，最终整个被删掉，看不到独立函数）：

; crate 名为 example，rustc 1.96.0 debug 构建节选，省略 alloca/分支/属性
; max::<i32> - 使用整数比较指令
define internal i32 @_ZN7example3max17h350313e132ccfe85E(i32 %0, i32 %1) unnamed_addr #0 personality ptr @rust_eh_personality {
  ...
  %_0.i = icmp sgt i32 %_3.i, %_4.i
  ...
}

; max::<f64> - 使用浮点比较指令
define internal double @_ZN7example3max17h7a83d5bd55867237E(double %0, double %1) unnamed_addr #0 personality ptr @rust_eh_personality {
  ...
  %_0.i = fcmp ogt double %_3.i, %_4.i
  ...
}

函数名中的 h350313e1... 和 h7a83d5bd... 是编译器为不同实例生成的哈希值（随编译环境变化）；max::<&str> 是第三个 define，比较经由 str 的 PartialOrd 最终调用 memcmp。

6.2 为什么 Rust 选择单态化

编译型语言的泛型实现有三条截然不同的技术路线。Rust 选择了代码膨胀最严重但运行时性能最优的一条。

flowchart TB
    subgraph 类型擦除["类型擦除（Java）"]
        direction TB
        JE1["List&lt;String&gt;"] --> JE2["一份字节码<br/>List&lt;Object&gt;"]
        JE3["List&lt;Integer&gt;"] --> JE2
        JE2 --> JE5["接口方法分发<br/>invokeinterface"]
    end
    subgraph 字典传递["字典传递（Haskell/Swift）"]
        direction TB
        DP1["max :: Ord Int"] --> DP2["一份代码<br/>max + OrdDict"]
        DP3["max :: Ord Float"] --> DP2
        DP2 --> DP5["字典查找<br/>间接调用"]
    end
    subgraph 单态化["单态化（Rust/C++）"]
        direction TB
        MO1["max::&lt;i32&gt;"] --> MO2["i32 专用指令<br/>icmp sgt"]
        MO3["max::&lt;f64&gt;"] --> MO4["f64 专用指令<br/>fcmp ogt"]
    end
    style JE2 fill:#f59e0b,color:#333,stroke:none
    style JE5 fill:#dc2626,color:#fff,stroke:none
    style DP2 fill:#f59e0b,color:#333,stroke:none
    style DP5 fill:#dc2626,color:#fff,stroke:none
    style MO2 fill:#10b981,color:#333,stroke:none
    style MO4 fill:#10b981,color:#333,stroke:none

Java 类型擦除：编译器只生成一份代码，泛型参数擦除为上界（通常是 Object）。代价：基础类型必须装箱（int -> Integer），运行时类型信息丢失（List<String> 和 List<Integer> 运行时是同一个类），方法调用走虚分发，静态编译时无法内联（要靠 JIT）。

Haskell/Swift 字典传递：编译器生成一份代码，为每个 trait/protocol 约束生成一个字典（witness table），运行时通过字典查找方法地址。代价：每次方法调用多一次间接跳转，不做特化时无法内联泛型调用。

Rust/C++ 单态化：为每种具体类型生成独立代码副本。运行时零开销，完全支持内联，编译器可以做类型特化优化。代价：编译时间和二进制体积。

维度	单态化（Rust/C++）	类型擦除（Java）	字典传递（Haskell/Swift）
二进制体积	大（N 类型 = N 份代码）	小（一份代码）	小（一份代码 + 字典）
编译时间	长	短	中等
运行时性能	最优	较差（虚调用+装箱）	中等（字典间接调用）
内联可能性	完全可以	需要 JIT	困难
基础类型支持	直接支持	需要装箱	直接支持

Rust 为系统编程而生，运行时性能是第一优先级。单态化是唯一能做到"泛型调用和手写具体类型代码完全零差异"的方案。

6.3 rustc 核心数据结构：Instance 与 InstanceKind

单态化的核心概念由 compiler/rustc_middle/src/ty/instance.rs 中的两个数据结构表达。

Instance：单态化实例

// 来自 compiler/rustc_middle/src/ty/instance.rs
pub struct Instance<'tcx> {
    pub def: InstanceKind<'tcx>,   // 什么类型的可调用项
    pub args: GenericArgsRef<'tcx>, // 具体泛型参数
}

源码注释中有一段关键的设计说明：

Monomorphization happens on-the-fly and no monomorphized MIR is ever created. Instead, this type simply couples a potentially generic InstanceKind with some args, and codegen and const eval will do all required instantiations as they run.

rustc 不会真的创建单态化后的 MIR 副本。Instance 只是一个"承诺"——告诉代码生成器"用这个泛型定义配合这组类型参数去实例化"。真正的实例化在 codegen 阶段按需进行。

InstanceKind：实例的种类

InstanceKind 不仅仅是"用户定义的函数"，还包括编译器自动生成的各种 shim：

// compiler/rustc_middle/src/ty/instance.rs:62（节选，注释为本专栏所加）
pub enum InstanceKind<'tcx> {
    Item(DefId),                              // 用户定义的 fn、闭包、协程
    Intrinsic(DefId),                         // 编译器内建函数
    VTableShim(DefId),                        // VTable 垫片：处理 unsized self
    ReifyShim(DefId, Option<ReifyReason>),     // 函数指针具化垫片
    FnPtrShim(DefId, Ty<'tcx>),               // fn 指针的 FnTrait 实现
    Virtual(DefId, usize),                    // 动态分发：vtable 调用
    ClosureOnceShim { call_once: DefId, .. },  // FnOnce::call_once 闭包垫片
    DropGlue(DefId, Option<Ty<'tcx>>),         // drop_in_place::<T>
    CloneShim(DefId, Ty<'tcx>),                // 编译器生成的 Clone 实现
    AsyncDropGlue(DefId, Ty<'tcx>),            // 异步 drop 垫片
    // ...其他变体
}

这个枚举的丰富程度揭示了一个重要事实：编译器自动生成的代码同样需要大量单态化——每种类型的 drop_in_place、每种闭包的 FnOnce::call_once 适配、每种 dyn Trait 的 vtable 垫片。这些隐藏的实例往往是代码膨胀的重要贡献者。

关键变体解读：

• DropGlue(_, Some(T))：每种需要 drop 的类型都有一份。Vec<String> 的 drop glue 要先 drop 每个 String 再释放内存，而 Vec<i32> 只需释放内存——完全不同的代码
• Virtual(DefId, usize)：动态分发调用，不被单态化为独立函数。它是单态化的边界，标记了从静态分发过渡到动态分发的点
• ReifyShim：将函数从"直接调用"转换为"函数指针"时的垫片。带 #[track_caller] 的函数转为指针时需要固定调用者位置信息

Instance 的关键方法

// compiler/rustc_middle/src/ty/instance.rs:199-237（同 impl 块从 :185 起；
// 注释与 match 的 async drop 几支从略，条件判断按源码原样保留）
impl<'tcx> Instance<'tcx> {
    /// 查找上游 crate 中是否已有可复用的单态化实例
    pub fn upstream_monomorphization(&self, tcx: TyCtxt<'tcx>) -> Option<CrateNum> {
        if self.def_id().is_local() {
            return None;
        }
        if !tcx.sess.opts.share_generics()
            // 但 #[inline(never)] 的函数即便关了 share-generics 也可以直接复用上游的
            && tcx.codegen_fn_attrs(self.def_id()).inline != rustc_hir::attrs::InlineAttr::Never
        {
            return None;
        }
        self.args.non_erasable_generics().next()?;
        // compiler_builtins 不能用上游单态化
        if tcx.is_compiler_builtins(LOCAL_CRATE) {
            return None;
        }
        match self.def {
            InstanceKind::Item(def) => tcx
                .upstream_monomorphizations_for(def)
                .and_then(|monos| monos.get(&self.args).cloned()),
            InstanceKind::DropGlue(_, Some(_)) => tcx.upstream_drop_glue_for(self.args),
            _ => None,
        }
    }
}

这是 -Zshare-generics 功能的核心入口，我们在 6.6 节详述。

6.4 单态化收集算法

收集算法是整个单态化流程中最复杂的部分。它的任务是找出 crate 中所有需要生成机器码的实例。实现在 compiler/rustc_monomorphize/src/collector.rs 中。

flowchart TD
    A["阶段1: 发现根节点<br/>collect_roots"] --> B["遍历 HIR"]
    B --> C1["公开非泛型函数"]
    B --> C2["静态变量"]
    B --> C3["入口函数 main"]
    B --> C4["#[no_mangle] 函数"]
    C1 & C2 & C3 & C4 --> D["根节点集合"]
    D --> E["阶段2: 图遍历<br/>collect_items_rec"]
    E --> F["检查 MIR 中的使用"]
    F --> G1["函数调用"]
    F --> G2["函数引用（取地址）"]
    F --> G3["Drop glue"]
    F --> G4["Unsizing 转换（vtable）"]
    G1 & G2 & G3 & G4 --> H["新发现的实例"]
    H --> |"递归"|E
    H --> I["完整的 Mono Item 图"]
    style A fill:#2563eb,color:#fff,stroke:none
    style D fill:#7c3aed,color:#fff,stroke:none
    style E fill:#f59e0b,color:#333,stroke:none
    style I fill:#10b981,color:#333,stroke:none

阶段1：发现根节点

入口函数 collect_crate_mono_items 先收集根节点——不需要被别人调用就必须存在的实例：

// compiler/rustc_monomorphize/src/collector.rs:1798-1833（有删节）
pub(crate) fn collect_crate_mono_items<'tcx>(
    tcx: TyCtxt<'tcx>,
    strategy: MonoItemCollectionStrategy,
) -> (Vec<MonoItem<'tcx>>, UsageMap<'tcx>) {
    // 阶段1：收集根节点
    let roots = tcx.sess.time(
        "monomorphization_collector_root_collections",
        || collect_roots(tcx, strategy),
    );
    // 阶段2：图遍历（par_for_each_in 只在开启并行前端时才真正并行）
    let state = SharedState { visited: Lock::new(UnordSet::default()), /* ... */ };
    let recursion_limit = tcx.recursion_limit();
    tcx.sess.time("monomorphization_collector_graph_walk", || {
        par_for_each_in(roots, |root| {
            collect_items_root(tcx, dummy_spanned(*root), &state, recursion_limit);
        });
    });
    // 排序确保确定性输出
    // ...
}

根节点包括：非泛型的公开函数和方法、静态变量、入口函数、#[no_mangle] 函数。在 Eager 策略下，所有非泛型函数都成为根，还会加上所有非泛型 ADT 的 drop glue 和 trait impl 的默认方法实例（compiler/rustc_monomorphize/src/collector.rs:1504-1589 的 process_item）。collector.rs 的文档注释说 Eager 用于配合增量编译，但 1.96.0 实际只在 -C link-dead-code 时选 Eager，其余情况一律 Lazy（compiler/rustc_monomorphize/src/partitioning.rs:1132-1136）。

阶段2：MIR 遍历发现使用关系

核心遍历器 MirUsedCollector 实现了 MirVisitor trait：

// compiler/rustc_monomorphize/src/collector.rs:681（monomorphize 的 where 子句改写为行内约束，省略 trace!）
struct MirUsedCollector<'a, 'tcx> {
    tcx: TyCtxt<'tcx>,
    body: &'a mir::Body<'tcx>,
    used_items: &'a mut MonoItems<'tcx>,
    /// 记录"已经在遍历中处理过的 mention"，避免 mentioned-items 阶段重复走一遍
    used_mentioned_items: &'a mut UnordSet<MentionedItem<'tcx>>,
    instance: Instance<'tcx>,  // 当前正在分析的实例
}

impl<'a, 'tcx> MirUsedCollector<'a, 'tcx> {
    fn monomorphize<T: TypeFoldable<TyCtxt<'tcx>>>(&self, value: T) -> T {
        // 将泛型 MIR 中的类型参数替换为当前实例的具体类型
        self.instance.instantiate_mir_and_normalize_erasing_regions(
            self.tcx, ty::TypingEnv::fully_monomorphized(),
            ty::EarlyBinder::bind(value),
        )
    }
}

遍历器捕获四种使用关系：

1. 函数调用：foo::<i32>() 调用 bar::<i32>()，后者成为新实例
2. 函数引用：let f = print_val::<i32>; 不需要调用就创建实例
3. Drop glue：MIR 中的 drop 语句引入 drop_in_place::<T> 实例
4. Unsizing 转换：将具体类型转为 dyn Trait 时，需要实例化 trait 所有 dyn 兼容的方法来构建 vtable——即使这些方法从未被直接调用

第四点尤其值得注意。源码中处理 unsizing 的逻辑：

// compiler/rustc_monomorphize/src/collector.rs:751-760，visit_rvalue 遇到 Unsize 转换时
if target_ty.is_trait() && !source_ty.is_trait() {
    create_mono_items_for_vtable_methods(
        self.tcx, target_ty, source_ty, span, self.used_items,
    );
}

仅仅将一个类型转换为 dyn Trait，就会导致该类型对这个 trait 的所有可进 vtable 的方法被实例化。

递归深度限制

泛型递归实例化可能无限展开（foo::<T> -> foo::<Vec<T>> -> foo::<Vec<Vec<T>>> -> ...）。编译器通过 recursion_limit（默认 128）防止这种情况，可用 #![recursion_limit = "256"] 调整。

UsageMap：实例间的依赖关系

收集完成后构建 UsageMap——记录每个实例使用了哪些其他实例。这个图在后续的 CGU 分区中至关重要。

// compiler/rustc_monomorphize/src/collector.rs:260
pub(crate) struct UsageMap<'tcx> {
    pub used_map: UnordMap<MonoItem<'tcx>, Vec<MonoItem<'tcx>>>,  // 正向依赖
    user_map: UnordMap<MonoItem<'tcx>, Vec<MonoItem<'tcx>>>,       // 反向依赖
}

CollectionMode：为什么收集要"走两遍"

朴素理解里，单态化收集器的工作是"找出所有会被调用的实例"——听起来是单一任务。但翻开 compiler/rustc_monomorphize/src/collector.rs 文档注释（line 156-195），会发现一个看似吊诡的设计：收集器有两种模式，同一个 item 要按两种口径各收集一遍（mentioned 这一遍只补走 used 没覆盖到的项）。这个"啰嗦"的设计实际上堵了一个严重的合法性漏洞。

// compiler/rustc_middle/src/mono.rs:695
pub enum CollectionMode {
    /// Collect items that are used, i.e., actually needed for codegen.
    /// Which items are used can depend on optimization levels, as MIR
    /// optimizations can remove uses.
    UsedItems,
    /// Collect items that are mentioned. The goal of this mode is that
    /// it is independent of optimizations ...
    /// The key property of this set is that it is optimization-independent.
    MentionedItems,
}

问题的起源：依赖泛型参数的常量（比如下例的 const 块）要到单态化收集时才能求值——收集器的职责之一就是把所有被收集项用到的常量求值一遍（见 collector.rs 文档注释 "Collection-time const evaluation"）。考虑这段代码：

fn unused_if_optimized<T>() {
    const { assert!(std::mem::size_of::<T>() > 0) };  // T 不能是 ZST
}

fn main() {
    if false {                          // 死代码
        unused_if_optimized::<()>();    // ZST！会 const-eval 失败
    }
}

假如收集器只认优化后 MIR 里"用到"的项：MIR 优化（常量条件化简 + 死代码消除）一旦把 if false 分支整个删掉，单态化收集器就压根儿看不到那个调用，本该报的错被吞掉——编译过了；优化没删掉这个调用时，同一段代码又会报错。同一份代码、同一 rustc、不同优化级别得到不同的编译结果，这是复现性噩梦。实测 rustc 1.96.0 连 opt-level=0 都会删掉这条分支（--emit=mir 里 main 只剩一个 return），问题并非假想。

解法是拆两遍看。收集器每次处理一个 item 要做两件事：

1. CollectionMode::UsedItems——按优化后 MIR 走，发现的实例会被生成机器码。这条线决定了 codegen 的真正工作量。
2. CollectionMode::MentionedItems——按优化前 MIR（具体是 drop-elaboration 之后、优化开关打开之前，见 compiler/rustc_middle/src/mono.rs 里 MentionedItems 的注释 line 704-707，实际调用点在 compiler/rustc_mir_transform/src/lib.rs:820）走。发现的实例不生成机器码，但它们携带的常量会被 const-eval。如果常量失败，编译报错——即使这个实例在优化后完全不存在。

这就保证了合法性判断跟优化级别脱钩：上面那段代码无论什么 opt-level 都会编译失败（本机 rustc 1.96.0 实测 opt-level=0 与 3 均报 E0080，因为这个调用仍被 mentioned），消除了"release 过而 debug 挂"的反常现象。源码实现侧，SharedState（compiler/rustc_monomorphize/src/collector.rs:250）分别维护两个集合：

struct SharedState<'tcx> {
    visited:   Lock<UnordSet<MonoItem<'tcx>>>,  // UsedItems 去重
    mentioned: Lock<UnordSet<MonoItem<'tcx>>>,  // MentionedItems 去重
    usage_map: Lock<UsageMap<'tcx>>,
}

两个集合各自去重，Lock<_> 的包装提示另一个不起眼但重要的事实——收集器被设计成可以并行：文件第 212 行 par_for_each_in 出现在 import 里，compiler/rustc_monomorphize/src/collector.rs:1810 初始化 SharedState 时能看到 Lock::new 的并发保护。开启并行前端时，多个线程从各个根节点并发遍历 MIR，共享这三把锁。但并行前端默认关闭（需要 nightly 的 -Z threads=N，N>1），默认构建里 par_for_each_in 按顺序逐个处理根节点，详见第 1 章 §1.14。

这种"soundness 要严格、codegen 要只做真正需要的"的双模式架构是 rustc 长期演化的产物。

6.5 代码膨胀：零成本抽象的代价

每个独特的 (泛型函数, 类型参数组合) 对都会生成一份独立机器码。当泛型函数多、类型参数多时，组合爆炸不可避免。

flowchart TB
    subgraph 泛型函数["泛型函数（M 个）"]
        F1["Vec::push"]
        F2["Vec::pop"]
        F3["HashMap::insert"]
        F4["serialize"]
    end
    subgraph 类型["具体类型（N 种）"]
        T1["i32"]
        T2["String"]
        T3["MyStruct"]
    end
    subgraph 实例["单态化实例（最多 N x M 个）"]
        I1["push::<i32>"]
        I2["push::<String>"]
        I3["push::<MyStruct>"]
        I4["pop::<i32>"]
        I5["pop::<String>"]
        I6["insert::<String,i32>"]
        I7["serialize::<MyStruct>"]
    end
    F1 --> I1 & I2 & I3
    F2 --> I4 & I5
    F3 --> I6
    F4 --> I7
    style I1 fill:#dc2626,color:#fff,stroke:none
    style I2 fill:#dc2626,color:#fff,stroke:none
    style I3 fill:#dc2626,color:#fff,stroke:none
    style I4 fill:#dc2626,color:#fff,stroke:none
    style I5 fill:#dc2626,color:#fff,stroke:none
    style I6 fill:#dc2626,color:#fff,stroke:none
    style I7 fill:#dc2626,color:#fff,stroke:none

用 cargo-bloat 量化膨胀：

cargo bloat --release -n 20
# 输出形如（数值随项目而异，这里只示意格式）：
#  File  .text     Size  Crate Name
#  <占比> <占比>  <大小>  <crate> <函数符号>

cargo-bloat 按符号逐条列出体积，同一个泛型函数的不同实例各占一行；想直接看"一个泛型函数被实例化了几份"，用下面的 cargo-llvm-lines。

隐藏的膨胀源

用户代码中的泛型只是膨胀的一部分。编译器自动生成的代码同样膨胀：

• Drop glue：Vec<String> 和 Vec<i32> 的 drop_in_place 是完全不同的代码
• Clone 实现：#[derive(Clone)] 为每种类型生成独立的 clone 方法
• 格式化代码：println!("{:?}", my_vec) 会实例化 <Vec<T> as Debug>::fmt 的特定版本

实际影响度量

cargo install cargo-llvm-lines
cargo llvm-lines --release | head -20
# 输出形如（数值随项目而异，这里只示意格式）：
#   Lines  Copies  Function name
#   <行数>     15  <Vec<T> as serde::Deserialize>::deserialize
#   <行数>     12  hashbrown::raw::RawTable<T>::find

Lines 是该函数所有实例合计生成的 LLVM IR 行数，Copies 是实例份数。Lines 越大，对编译时间和二进制大小的贡献越大；Copies 大则说明膨胀来自单态化副本。

6.6 缓解膨胀的策略

策略一：LLVM 自动优化

• 函数合并（MergeFunctions Pass）：两个实例的 LLVM IR 完全相同时，合并为一个，另一个变成别名或跳转 thunk（rustc 默认传 -mergefunc-use-aliases 优先用别名，且只在优化构建中启用该 pass，见 compiler/rustc_codegen_ssa/src/back/write.rs:236-250、compiler/rustc_codegen_llvm/src/llvm_util.rs:98-103）
• 内联消除：小函数内联后消失，不再作为独立函数存在——反而减少体积
• 死代码消除：内联后不再被引用的独立副本被链接器丢弃

策略二：Shared Generics（-Zshare-generics）

当 crate A 已经为 Vec::<String>::push 生成了代码，crate B 可以直接链接到 crate A 的版本，无需重新编译。实现依赖前述的 upstream_monomorphization 方法——编译器为每个 crate 维护"已导出的单态化实例"表，下游编译时查询复用。

需要澄清一个常见误解：-Zshare-generics 虽然是 -Z 开头的不稳定开关，但不给它也不等于关闭。Options::share_generics（compiler/rustc_session/src/config.rs:1475-1483）在没有显式设置时按优化级别取默认值——OptLevel::No | Less | Size | SizeMin 返回 true，More | Aggressive 返回 false。也就是说 debug 构建（opt-level 0）默认就在共享泛型实例，而 --release（opt-level 3）默认关闭它，把内联机会让给 LLVM。

限制：只能共享完全相同的 (函数DefId, 泛型参数) 对；只有外部链接的实例才会导出给下游（compiler/rustc_codegen_ssa/src/back/symbol_export.rs:290），而走 LocalCopy 的实例（优化构建下的 #[inline] 函数、任何构建下的 #[inline(always)] 函数）是内部链接的私有副本，在 compiler/rustc_monomorphize/src/partitioning.rs:225 就被跳过，不进入共享。

策略三：Polymorphization（已暂停）

曾是 nightly 的实验性功能（-Zpolymorphize），思路是：如果函数体不依赖某个类型参数，不同值可以共享代码。例如 fn log_count<T>(items: &[T]) 只用了 items.len()，理论上 log_count::<i32> 和 log_count::<String> 可以共享。但实现复杂度过高，截至当前版本 rustc 源码中相关代码已被移除。

策略四：程序员手动优化

核心思路：将泛型函数中不依赖类型参数的部分提取到非泛型函数中。

// 不好：整个函数体都被单态化
fn process<T: Display>(items: &[T]) {
    setup_database();        // 与 T 无关，但每种 T 都生成一份
    for item in items { println!("{}", item); }
    cleanup();               // 与 T 无关
}

// 好：只有依赖 T 的部分被单态化
fn process<T: Display>(items: &[T]) {
    setup_and_prepare(items.len());  // 非泛型，只编译一份
    for item in items { println!("{}", item); }
    finish(items.len());             // 非泛型，只编译一份
}

fn setup_and_prepare(count: usize) { setup_database(); /* ... */ }
fn finish(count: usize) { cleanup(); /* ... */ }

标准库大量使用这个技巧——Vec 的内存分配逻辑提取到与元素类型 T 无关的 RawVecInner（只按传入的 Layout 关心字节数和对齐，仅对分配器 A 泛型，见 library/alloc/src/raw_vec/mod.rs:85），hashbrown 的探测算法不随 K、V 类型变化。

6.7 对编译时间的影响

单态化是 Rust 编译慢的核心原因之一：

1. 收集阶段：遍历所有可达实例的 MIR 并做类型替换
2. 代码生成线性放大：N 种实例化 = N 倍 LLVM 编译和优化时间
3. 链接时间增长：更多目标代码，更长的链接和去重时间
4. 增量编译不稳定性：新增一个泛型调用可能导致某个 CGU 需要重新编译

partitioning.rs 的注释（compiler/rustc_monomorphize/src/partitioning.rs:42-45）解释了编译器的应对策略——将每个源码模块分为两个 CGU：

There are two codegen units for every source-level module:

• One for "stable", that is non-generic, code
• One for more "volatile" code, i.e., monomorphized instances of functions defined in that module

这样新增泛型实例只影响"不稳定"CGU，不波及"稳定"CGU 中的非泛型代码。这个拆分只在增量编译时生效：place_mono_items 里 is_volatile = is_incremental_build && mono_item.is_generic_fn()（同文件 :229）。

InstantiationMode 控制实例的放置策略——GloballyShared（整个程序一份，减小体积）vs LocalCopy（每个 CGU 一份，允许内联）。源码中的决策逻辑：

// compiler/rustc_middle/src/mono.rs:228-232，MonoItem::instantiation_mode 末尾
// 兜底规则：优化构建用 LocalCopy，非优化构建用 GloballyShared
match tcx.sess.opts.optimize {
    OptLevel::No => InstantiationMode::GloballyShared { may_conflict: true },
    _ => InstantiationMode::LocalCopy,
}

这体现了编译器面临的核心张力：优化希望多副本（更多内联机会），增量编译希望少副本（更少重编译）。

6.8 跨 crate 单态化

泛型函数有一个独特的特性：定义和实例化可能发生在完全不同的 crate 中。这引出了一系列复杂的工程问题。

当 crate A 定义了 fn process<T>(x: T)，crate B 调用 process(42_i32) 时：

1. crate A 编译时，process 的 MIR 序列化到元数据中
2. crate B 编译时，从元数据读取 MIR，发现 process::<i32> 实例
3. 实例化在 crate B 中完成——crate A 从未见过 i32 这个参数

这就是为什么泛型函数的完整 MIR 必须包含在 crate 元数据中。也解释了为什么修改底层库中的泛型函数实现会导致所有下游 crate 重新编译。

should_codegen_locally 函数是跨 crate 的核心决策点：

// compiler/rustc_monomorphize/src/collector.rs:1047-1091（简化：省略 rustc_force_inline 检查、
// 上游 static 返回 false、上游 MIR 不可用时报 NoOptimizedMir 等分支）
fn should_codegen_locally<'tcx>(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) -> bool {
    let Some(def_id) = instance.def.def_id_if_not_guaranteed_local_codegen() else {
        return true;  // 大多数 shim 和空 drop glue 总是本地生成
    };
    if tcx.is_foreign_item(def_id) { return false; }  // FFI 项总是链接
    if def_id.is_local() { return true; }  // 本 crate 的项只能在本地生成
    // 上游导出的非泛型项，或上游已有可复用的单态化实例
    if tcx.is_reachable_non_generic(def_id) || instance.upstream_monomorphization(tcx).is_some() {
        return false;  // 直接链接
    }
    true
}

6.9 单态化 vs 动态分发：何时该用哪个

flowchart TD
    START["需要多态行为"] --> Q1{"在性能热路径上？"}
    Q1 -->|"是"| Q2{"类型数量少？<br/>（经验值，如个位数）"}
    Q1 -->|"否"| Q3{"需要异构集合？"}
    Q2 -->|"是"| A1["泛型（单态化）<br/>fn foo&lt;T: Trait&gt;(x: T)"]
    Q2 -->|"否"| Q4{"函数体很小？"}
    Q4 -->|"是"| A1
    Q4 -->|"否"| A2["dyn Trait<br/>fn foo(x: &dyn Trait)"]
    Q3 -->|"是"| A3["必须 dyn Trait<br/>Vec&lt;Box&lt;dyn Trait&gt;&gt;"]
    Q3 -->|"否"| A2
    style A1 fill:#10b981,color:#333,stroke:none
    style A2 fill:#2563eb,color:#fff,stroke:none
    style A3 fill:#7c3aed,color:#fff,stroke:none

场景	推荐策略	理由
调用类型少（经验上个位数）	泛型	膨胀有限，性能最优
调用类型多且函数体大	dyn Trait	避免 N 份大函数膨胀
性能关键路径	泛型	允许内联和类型特化
插件系统 / 可扩展架构	dyn Trait	编译时不知道有哪些类型
异构集合	dyn Trait	泛型无法实现
库的公开 API	泛型	给调用者最大灵活性
内部实现细节	dyn Trait	减少编译时间

最佳实践是混合策略——公开 API 用泛型保持灵活性，内部实现将不依赖类型参数的部分用非泛型函数或 dyn Trait 实现。

6.10 与 C++ 模板实例化和 Swift Witness Table 的对比

Rust 的单态化和 C++ 模板在核心原理上高度相似——都为每种具体类型生成独立代码。但在工程细节上有重要区别。

Rust vs C++ 模板

类型检查时机：C++ 模板在实例化时才做类型检查。如果模板体中使用了 T::foo()，只有实例化时才知道 T 有没有 foo 方法——这导致了臭名昭著的模板错误信息（几十行的 nested template 类型展开）。Rust 泛型在定义时就通过 trait bound 完成检查，不合法的调用在调用处报错，错误信息清晰。

特化支持：C++ 支持模板全特化和偏特化，允许为特定类型提供完全不同的实现：

template<typename T> void process(T x) { /* 通用版本 */ }
template<> void process<int>(int x) { /* int 专用版本 */ }

Rust 的 specialization 仍是不稳定特性（#![feature(specialization)]），且存在健全性问题。在稳定 Rust 中，不能为泛型函数的特定类型参数提供不同实现。

实例化控制：C++ 有 extern template 显式阻止某个编译单元中的实例化，并在另一个 .cpp 中显式实例化一次。Rust 没有等价机制，-Zshare-generics 在链接层面实现类似效果，但程序员无法精确控制实例化在哪个 crate 中发生。

编译模型：C++ 模板定义在头文件中，每个包含头文件的编译单元独立实例化。N 个 .cpp 都用 vector<int> 就编译 N 次，链接器通过 COMDAT 或弱符号去重，丢弃 N-1 份——浪费了 N-1 份编译时间。Rust 在 crate 级别做去重，一个 crate 内 Vec::<i32>::push 只在一个 CGU 中实例化（或以 LocalCopy 有意复制供内联），跨 crate 通过 -Zshare-generics 避免重复（debug 默认开启、release 默认关闭，见 §6.6）。去重的粒度是 crate 而不是单个源文件，这是它和 C++ "编译 N 次，链接时丢弃"模式的主要区别。

Rust vs Swift Witness Table

Swift 的泛型实现了一个有趣的混合方案。默认使用 witness table（协议见证表，protocol witness table）实现泛型——每个 protocol conformance 生成一个表，泛型函数通过表查找方法地址，类似 Haskell 的字典传递。但 Swift 编译器的 SIL optimizer 会在可能的情况下自动将泛型调用特化为具体类型，实质上执行了"按需单态化"。

这种混合策略的特点：

• 未优化的 Swift 代码使用字典传递，性能低于 Rust 的始终单态化
• 优化后的 Swift 代码在常见情况下接近 Rust 性能（优化器做了单态化）
• Swift 默认二进制更小（未特化的函数只有一份），但优化后也会膨胀
• Swift 可以在 ABI 层面保持稳定（因为默认的调用约定不依赖单态化），这是 Rust 目前做不到的——Rust 的泛型函数没有稳定的 ABI

6.11 实测：rustc 单态化基础设施 4840 行 + InstanceKind 15 变体

把本章贯穿讨论的几个 crate 实测——

路径	行	角色
compiler/rustc_monomorphize/src/collector.rs	1835	本章 §6.4 主角——两阶段图遍历 + UsageMap + CollectionMode 双模式
compiler/rustc_monomorphize/src/partitioning.rs	1345	CGU（Codegen Unit）划分 + InstantiationMode（GloballyShared / LocalCopy）决策（§6.6 -Zshare-generics 在这里）
compiler/rustc_middle/src/ty/instance.rs	942	Instance + InstanceKind 定义——本章 §6.3 主角；含 15 个 InstanceKind 变体
compiler/rustc_ty_utils/src/instance.rs	416	Instance::resolve 查询入口
compiler/rustc_monomorphize/src/errors.rs	186	单态化错误类型
compiler/rustc_monomorphize/src/util.rs + lib.rs	116	顶层 + 工具
本章主题合计	4840	—

InstanceKind 实测 15 变体（与 §6.13 所说"十几个变体"一致）——

#	Variant	用途
1	Item(DefId)	用户写的普通函数 / 方法
2	Intrinsic(DefId)	rustc 内置 intrinsic（size_of / transmute 等）
3	VTableShim(DefId)	给 vtable 用的 shim（处理 self by-value）
4	ReifyShim(DefId, Option<ReifyReason>)	把 fn item 转成 fn pointer 时的 shim
5	FnPtrShim(DefId, Ty<'tcx>)	Fn trait 调用包装
6	Virtual(DefId, usize)	虚函数调用占位（vtable 索引）
7	ClosureOnceShim	闭包 Fn/FnMut 转 FnOnce 的 shim
8	ConstructCoroutineInClosureShim	async 闭包构造内部协程的 shim（ch11 §11.10 提到的 CoroutineClosure 的运行时配套）
9	ThreadLocalShim(DefId)	thread-local 访问 shim
10	FutureDropPollShim(DefId, Ty, Ty)	future 异步 drop 的代理 shim
11	DropGlue(DefId, Option<Ty>)	drop 实现 glue（ch09 §9.10 提到 drop 是协程取消机制）
12	CloneShim(DefId, Ty)	编译器内建的 Clone 实现（Copy 类型、数组、元组、闭包；不是 #[derive(Clone)]）
13	FnPtrAddrShim(DefId, Ty)	fn pointer 的地址 shim
14	AsyncDropGlueCtorShim(DefId, Ty)	async drop 构造
15	AsyncDropGlue(DefId, Ty)	async drop 主体

两条值得记住的物理事实——

1. 15 个 InstanceKind 中只有 1 个是"用户代码"（Item）——其余 14 个里，除 Intrinsic（在调用处就地生成）和 Virtual（经 vtable 间接调用）不产生自己的函数体外，12 个都是编译器合成函数体的 shim / glue——印证 §6.3 "编译器自动生成的代码同样需要大量单态化"。注意 #[derive(Clone)] 生成的是普通 impl，它的 clone 走 Item；CloneShim 只给 Copy 类型、数组、元组、闭包这类内建 Clone 用
2. collector.rs 1835 + partitioning.rs 1345 = 3180 行——本章 §6.4（收集）+ §6.7 / §6.12（CGU 划分）的核心代码——约为 instance.rs 942 行（数据定义）的 3.4 倍——本章涉及的代码里，算法部分明显比数据定义重；ch05 §5.16 里 LayoutCalculator 算法 1599 行与 LayoutData 约 50 行字段定义的对比也是如此

口径说明：本节 4840 行是按本章主题挑选的文件（分属 rustc_monomorphize、rustc_middle、rustc_ty_utils），不是整 crate 统计；整个 rustc_monomorphize crate 是 4118 行（§1.18）。ch05、ch09、ch11 等章的实测表同样是各自挑选的文件，覆盖范围不同，不能与本节相加，也不能用来算占比。

6.12 从收集到 CGU：单态化不是“生成完就结束”

compiler/rustc_middle/src/ty/instance.rs:33-36 把 Instance 定义成 InstanceKind + GenericArgsRef，这正是“同一个函数定义 + 一组具体类型参数”的最小表示。InstanceKind 从 instance.rs:62 开始列出用户函数、intrinsic、vtable shim、fn pointer shim、drop glue 等不同来源，说明 mono item 并不只来自你手写的 fn；大量条目是编译器为了 ABI、drop、trait object 和闭包适配生成的胶水代码。

收集阶段在 compiler/rustc_monomorphize/src/collector.rs:1798-1833 收口：先 collect_roots，再用 par_for_each_in 从各个根节点走 mono item 图，最后因为遍历可能并行、结果集合天然无序，必须用 stable hashing context 排序，保证输出确定。这个“可并行遍历、后稳定排序”的细节很重要：rustc 在开启并行前端时要利用多核缩短收集时间，又不能让后续 codegen 因遍历顺序不同而生成不稳定产物。

收集到的图还不是最终后端输入。compiler/rustc_monomorphize/src/partitioning.rs:1131-1235 继续选择 Eager/Lazy 收集策略，运行 target-specific graph checks，然后 partition 到 Codegen Unit，并可在 -Zprint-mono-items 下输出每个 mono item 落在哪些 CGU。放置策略由 compiler/rustc_middle/src/mono.rs:27-48 的 InstantiationMode 表达：GloballyShared 表示全程序一份，LocalCopy 表示每个引用它的 CGU 可以有私有副本；mono.rs:131-233 再按入口函数、导出符号、drop glue、优化级别、inline 属性和增量编译需求做启发式选择。

这解释了一个常见误解：单态化的代价不只是“生成了几份泛型函数”。真正影响编译时间和二进制体积的是实例收集、依赖图、CGU 分区、inline 机会和符号可见性共同作用的结果。同一段泛型代码，在 debug、release、增量编译、LTO、#[inline] 属性不同的组合下，可能被放进不同数量的 CGU，也可能从 GloballyShared 变成 LocalCopy。优化泛型膨胀时，应该同时看 cargo llvm-lines、-Zprint-mono-items 和 CGU 划分，而不是只数源码里的 <T>。

6.13 总结

单态化是 Rust 类型系统和性能承诺之间的桥梁。它将编译期的泛型抽象转化为运行时的零成本具体代码，但代价是编译时间和二进制体积的膨胀。

从编译器实现的角度，单态化涉及三个核心组件：

1. 数据表示：Instance<'tcx> 将函数定义（InstanceKind）与具体类型参数绑定。InstanceKind 的十几个变体涵盖了用户代码和编译器生成代码的所有情况——从普通函数到 drop glue、vtable shim、闭包适配器
2. 收集算法：两阶段图遍历。第一阶段从 HIR 发现根节点（非泛型公开项、静态变量、入口函数），第二阶段从根节点出发遍历 MIR，递归发现所有可达的单态化实例。收集器支持并行遍历（默认构建中顺序执行），最终输出确定性排序的 mono item 集合
3. 放置策略：InstantiationMode 决定每个实例是 GloballyShared（整个程序一份，减小体积）还是 LocalCopy（每个 CGU 一份，允许内联）。这个决策平衡了 LLVM 优化效果和增量编译效率

在工程实践中，理解单态化的核心价值在于：

• 诊断能力：当项目编译慢或二进制过大时，知道用 cargo-bloat 和 cargo-llvm-lines 定位膨胀源
• 设计决策：在泛型和 dyn Trait 之间做出明智选择——性能热路径用泛型，非关键路径用动态分发
• 代码组织：将泛型函数中不依赖类型参数的逻辑提取为非泛型辅助函数，显著减少膨胀
• 依赖选择：意识到重泛型库（serde、diesel 等）对编译时间的放大效应

单态化没有银弹——编译时间和运行时性能是系统编程语言的本质权衡。但理解了它的全部机制，你就能在每个具体场景中做出最优的权衡。