Cargo 的调度器能否改进？

# Ada的博客 来源：https://spirali.github.io/blog/cargo-scheduler/ ## Cargo的调度器是否可以更好？ 2026年8月31日 过去大约10年里，我一直在研究各类调度器，最近为HyperQueue (https://github.com/it4innovations/hyperqueue) 添加了一个新调度器（**本文讨论的并非这个调度器**）。它基于MILP，实现使用了HiGHS (https://docs.rs/highs/latest/highs/)，这个crate在编译时间方面很快就变得相当庞大。于是我开始思考Cargo实际是如何调度工作的，以及是否有改进空间。 注1：我并不熟悉Cargo内部实现。本文所有分析均基于对外部行为的观察，而非深入源代码。 注2：所有实验均使用rustc 1.97.1版本，测试环境为16核Intel CPU笔记本电脑，Linux系统。 ## 基准测试与图表 首先进行基准测试。我选取了15个知名的Rust项目，加上我维护的两个项目：HyperQueue (https://github.com/it4innovations/hyperqueue) 和 FairyFlow (https://github.com/spirali/fairyflow)。 它们的构建时间差异较大，因此作为起点是合适的。为简化分析，我们始终考虑纯调试构建（`cargo build`），不涉及`cargo check`和发布版本构建。 为实验调度策略，我们需要记录各构建任务之间的依赖关系图（即`rustc`及相关工具的调用关系）。只有重建此依赖图，才能在不同调度策略下重现相同的构建过程。 Cargo有构建计时功能（`cargo build --timings`），但其输出不足以重建完整的依赖图。通过对Cargo及其子进程的系统调用进行追踪，我们可以获取每个`rustc`进程读写文件的时序关系，从而推导出依赖关系和精确的任务起止时间。 这里有个关键细节：编译一个crate时，不需要其依赖项**完全**编译完成，只需要它们的元数据（`.rmeta`）。通过系统调用追踪也能发现这一点（`.rmeta`文件会在编译完成前创建）。因此在我们的依赖图中，对单个crate运行`rustc`实际表示为两个节点：**"前端"**（生成元数据）和**"剩余部分"**（完成代码生成和链接）。依赖的crate只需等待"前端"完成。此外还存在**"强制延续"**：一旦"前端"完成，"剩余部分"必须在同一工作线程上立即运行，因为这是同一OS进程的延续；调度器对此无权干预。 以下简单示例说明这一点：crate `app`和`app-tests`都依赖`my-crate`，它们只需等待`my-crate`的前端完成，而`my-crate`自身的"剩余部分"节点必须紧跟其前端节点执行： 为展示规模，这是HyperQueue的依赖图：包含471个节点和821条边。 本文后续仅讨论并行度*n=16*和*n=4*的情况。16是我的笔记本核心数，4代表资源受限环境（如小型CI运行器）。注意在极端情况下调度很简单：单CPU时无需决策，只需顺序执行；无限CPU时所有就绪任务可立即执行。有趣的情况介于两者之间。 ## 调度器 Cargo自身调度决策的重放（我们的基准线）在下图中标记为"cargo"。实际构建的墙钟时间通常略高于重放时间，因为我们的模拟未考虑一些额外开销。但由于所有对比都基于相同的"cargo"重放，且唯一差异在于调度逻辑，这构成了公平的基准。 我首先尝试了**b-level**调度器。它表现出色，成为我测试过的最佳简单调度器，因此在此重点介绍。 对于每个任务，我们计算其"b-level"（底层）：从该任务开始沿依赖图到构建结束，需要执行的最长任务链长度。换句话说： （对于无子任务的情况，`blevel(t) = duration(t)`）。每当工作线程空闲，调度器选择b-level最高的就绪任务。原理很简单：优先处理位于关键路径或其附近的任务，因为延迟它们会影响所有后续依赖任务。 我还尝试了其他方法：扇出优先（优先处理能解锁最多任务的任务）、最短/最长作业优先、几种b-level与扇出结合的变体（"cp-misf"和带小ε打破平局的版本），以及从随机或b-level调度开始的局部搜索（模拟退火），采用多种移动策略（随机扰动、交换两个任务、交换相邻任务）并随机重启。总体而言，这些方法要么不如基础b-level，最好也只能与之持平。 ## 结果 上图展示了若干代表性项目在关键路径（最长依赖链的长度，代表无限CPU下的最佳理论时间）、实际测量时间、"cargo"重放调度和b-level调度在n=4与n=16时的构建耗时。 您可能注意到HyperQueue在n=4时，实际时间略**小于**"cargo"重放耗时。调查发现：17个项目中有3个在n=4时出现此现象（HyperQueue、tantivy、zola），但n=16时没有。说实话，我不确定原因。 简而言之：b-level获胜。毫不意外，它在资源更受限的n=4时帮助更大。在17个项目中，n=4时b-level在15个项目上优于cargo调度，中位节省约8%墙钟时间（最佳情况达16%）。n=16时仍能在14个项目上获胜，收益缩小至中位约2%（最高15%）；这合乎逻辑，因为当几乎所有任务都能并行时，错误决策的影响空间变小。 但距离实际最优解有多远？不幸的是，此调度问题是NP难问题。因此我们构建**"伪最优"**：在所有测试调度器（包括运行10,000次迭代的随机局部搜索及下文描述的10,000次随机平局打破运行）中，特定项目和CPU数量下的最佳结果。这不保证是真最优，但可能已非常接近。 图表将b-level和cargo与伪最优对比，比值1.0表示"达到我们找到的最佳调度"。n=4时，b-level中位数高于伪最优约1.3%（最差3.3%），cargo则高约9.6%（最差超20%）。n=16时，b-level中位数高0.4%（最差1.3%），cargo高2.3%（最差达17.5%）。因此，仅选择最高b-level任务的简单贪心启发式已非常接近昂贵搜索的结果。 ## 真的可行吗？ 该方法存在一个明显问题：假设我们预先知道每个任务的实际耗时。现实中我们只有历史估算值。 b-level对耗时估算误差的敏感性如何？我为调度器提供带噪声的"假设"耗时而非真实值进行测试： 调度器基于`assumed`做决策，但模拟仍使用真实记录的耗时推进时间，与估算有误时的真实构建行为一致。测试了三种噪声水平：σ=10%（合理校准估算）、σ=30%（较粗糙）、σ=60%（与猜测无异），每个项目重复10,000次。 具体示例如下，展示2秒短任务和20秒长任务的三组噪声生成器采样结果： | 实际耗时 | 假设耗时（σ=10%） | 假设耗时（σ=30%） | 假设耗时（σ=60%） | |----------|-------------------|-------------------|-------------------| | 2.0 s | 2.19, 2.26, 2.47 s | 2.57, 2.77, 3.40 s | 3.13, 3.55, 4.81 s | | 20.0 s | 17.21, 22.90, 18.67 s | 11.62, 28.70, 16.02 s | 3.24, 37.39, 12.05 s | 注意在σ=60%的第一组采样中，20秒任务的假设耗时（3.24s）反而**小于**2秒任务的（3.13s）；调度器会认为长任务更短。这就是"与猜测无异"的实际表现。 为清晰展示，下图放大显示1.0附近的箱线图（不含须线）： 橙色菱形标记"cargo"基准线；Y轴本身已对无噪声的精确b-level归一化。在所有噪声水平下，带噪声估算的b-level构建耗时与无噪声b-level保持接近；即使σ=60%，中位数仍维持在百分之零点几内。个别不幸运行会明显变差（偶发30-50%），但这是尾部情况；噪声运行的中位数仍轻松超越"cargo"基准。 这是好消息，意味着我们无需精确知道执行时间。甚至不需要真实时间单位，粗略的相对估算即可，因为调度质量不受执行时间按常数缩放影响。 ## 一个比特足够吗？ 那么实际需要多少信息？噪声实验显示估算可能严重偏离；自然的问题是估算可以**多粗糙**。我们极端测试：每个任务仅提供一个比特信息："短"或"长"。 具体定义：实际耗时≤3秒的任务显示为1个时间单位，更长的显示为12个时间单位。3秒是临界点；调度器仅看到两个标签。b-level仅基于这两个数字计算，而模拟仍使用真实记录耗时推进时间，如同噪声实验。注意12不是对任何耗时的估算，仅表示一个"长"任务相当于多少个"短"任务。 注：基准测试中仅约1.3%的任务为"长"，但这些任务承担约三分之一的总编译工作量。 在展示结果前说明：使用真实耗时计算b-level时不会出现平局。但仅设置两个常数会产生许多相同b-level。下图中"1b b-level"柱状图是10k次随机平局打破运行的中位数，黑色须线显示最佳到最差排序的完整范围。 n=4时，此"1b b-level"比伪最优高1.5%，而精确耗时b-level高1.3%，cargo高9.6%。n=16时三个数值分别为0.5%、0.4%和2.3%。因此，即使只保留一个比特信息，仍能在n=4时16个项目上、n=16时14个项目上超越cargo基准。 查看失效案例：n=4时的fd项目比伪最优高9.7%，是图中最差柱形。原因是fd完全没有超过3秒的任务。该比特恒定为0，调度器实际上被告知所有任务等长，b-level退化为"任务在依赖图中的深度"。hyperfine和tokei项目也出现此情况，且代价可忽略。 注：我仅测试了少数临界值和比例组合，很可能存在更优常数；此处展示的1比特信息只是众多选项之一。 ## 我们根本不需要时间信息吗？ 下一步自然是移除这一个比特。如果每个任务显示相同耗时，b-level就变为纯粹的图深度。这不需要时间数据，仅需依赖图的形状——Cargo在编译前已知此信息。 此处的平局问题比上一节更严重，因为所有任务假设耗时相同：13,144个任务中仅剩393个不同b-level。盲柱图采用相同处理：10,000次随机平局打破的中位数，黑色须线显示完整范围。 n=16时中位项目比伪最优高0.7%，接近精确耗时b-level（0.4%），仍优于cargo（2.3%）。n=4时中位数为3.2%，而精确b-level为1.3%，cargo为9.6%。即使完全盲调度，仍能在n=4时16个项目、n=16时12个项目上超越cargo基准。 问题出现在尾部：少数项目严重偏离。n=16时nushell和zola均比伪最优高19%，n=4时gitui高12%，nushell高10%。这些并非随机次优排序：gitui在n=4时整个范围为11.6%至13.1%，n=16时nushell的最佳10,000排序仍比伪最优高16%。 这也说明一个比特的实际价值。比较绿柱与红柱，该比特几乎未改变中位数（n=16时从0.7%到0.5%），但大幅压缩了最差情况（从19%到4.1%）。这是针对尾部风险的保险而非平均情况改进。在fd、hyperfine和tokei项目上，两者本质相同：这些项目无任务超过3秒临界值，故该比特始终未设置，无法提供信息。 ## 结论 如果我们对任务耗时有所了解，b-level调度器胜出。而"有所了解"可以非常有限：估算可能噪声很大，或粗糙到每个crate仅一个比特信息，大部分优势依然存在。如果仅关注平均值，甚至无需这一比特信息。 这使得该想法极具实用性。基于历史构建的小型本地耗时数据库已足够好，可从共享的全局crate构建时间数据库启动，使新机器的首次构建也有参考。从1比特实验看，此类数据库甚至无需存储精确耗时；每个crate的"快速"/"慢速"标签已足够有用。当完全无参考数据时，回退到纯粹图深度是合理默认方案。 另一个启示是：更智能的调度策略可能收益甚微。所有简单替代方案均不如基础b-level，或至多持平；昂贵搜索仅找到比b-level更优约1.3%（n=4）和0.4%（n=16）的调度方案。 ## 附录 以下部分回应Reddit (https://www.reddit.com/r/rust/comments/1w37hnh/could_cargos_scheduler_be_better/) 上的讨论评论。 讨论中提出两种无需测量即可估算编译时间的方法：使用crate源代码大小，或其依赖项数量。 ### 源代码大小 测试了两种度量： - crates.io上的压缩包大小 - crates.io报告的代码行数 + 我计算的C/C++/汇编代码行数（跳过测试路径代码） 我们在两种调度器中使用这些度量："size b-level"（压缩包大小）和"loc b-level"（Rust代码行数作为rustc运行时间估算，C/C++行数作为build.rs时间估算）。 为完整起见，先看Rust代码行数与Rust部分编译时间的关系：