企业官网建设流程全解析

• 编程语言
• 编译器
• 语言运行时
• 标准库
• 开发工具

导读

本文围绕 Dart SDK 仓库中的SoundSplayTreeSieve基准测试展开，它复刻了 Golem 基准集中的sieve9（埃拉托斯特尼筛法），用于对比dart:collection标准库中的SplayTreeSet与一个为类型参数声明了**型变修饰符（variance modifiers，inout）**的自定义SoundSplayTreeSet在完全相同的算法负载下的运行时差异。通过阅读本文，你将掌握该基准的算法细节、两组数据结构的差异根源、variance实验特性在 Dart 2JS / DDC 下的开启方式，以及如何在本地复现并解读它的输出结果。

基准测试要回答的问题：型变修饰符是否有运行时开销

SoundSplayTreeSieve的设计意图非常直接：在dart:collection的SplayTreeSet旁边，提供一份逐行复刻但为所有类型参数显式声明了inout型变修饰符的SoundSplayTreeSet，然后在同一份筛法代码上分别计时。其核心关切是：

当 Dart 语言的variance实验特性（即“声音型变 / sound variance”，见 tools/experimental_features.yaml 中的variance: "Sound variance"）开启后，为泛型类型参数标注inout是否会引入额外的运行时开销，或者反过来带来消除隐式检查（implicit checks）的优化空间。

因此，benchmarks/SoundSplayTreeSieve/dart/README.md 给出的全部运行指令都围绕着两种编译器前端展开：Dart2JS（含开启--omit-implicit-checks的变体）和 DDC（ddb调试浏览器运行器），因为它们恰好是能观察到泛型擦除与隐式类型检查行为的场景。

被测的两个集合：SplayTreeSet与SoundSplayTreeSet

dart:collection中的SplayTreeSet

基准的第一个被测对象直接来自标准库：

final candidates = SplayTreeSet<int>.from(initialCandidates);

SplayTreeSet是dart:collection提供的基于自平衡二叉搜索树的Set，其关键特性是：最近被访问的元素会被“伸展（splay）”到树根，从而在摊还意义下以 O(log n) 完成插入、查找与删除；同时它要求元素可比较（默认使用Comparable.compare）。

带inout型变修饰符的SoundSplayTreeSet

第二个被测对象是本仓库内位于 benchmarks/SoundSplayTreeSieve/dart/sound_splay_tree.dart 的自定义实现。它与标准库SplayTreeSet的 API 几乎一一对应，唯一显著的区别是每个类型参数都显式标注了inout型变修饰符：

abstract class _SoundSplayTree<inout K> { ... } class _SoundSplayTreeNode<inout K> { ... } class SoundSplayTreeSet<inout E> extends _SoundSplayTree<E> with IterableMixin<E>, SetMixin<E> { ... } class SoundSplayTreeMap<inout K, inout V> extends _SoundSplayTree<K> with MapMixin<K, V> { ... }

inout是 Dart 实验性“声音型变”特性引入的三向修饰符之一（与in、out并列），表示该类型参数在协变与逆变位置上都会被使用。例如_SoundSplayTree<K>中既有返回K的读取位置（_root.key、first、last），也有把K作为方法参数传入的写入位置（add(E element)、_compare(K key1, K key2)、removeAll(Iterable<Object?> elements)中的_remove(element as E)），因此K/E必须声明为inout才能同时满足两个方向的位置约束。

从源码结构看，这个文件完整复刻了标准 splay 树的所有核心机制（见下节），因此它与SplayTreeSet的差异被压缩到“是否声明型变修饰符”这一最小变量上——这正是对照基准的严谨性所在。

筛法算法与基准封装：代码逐行解读

被测算法位于 benchmarks/SoundSplayTreeSieve/dart/SoundSplayTreeSieve.dart，它实现了经典的埃拉托斯特尼筛法：维护一个候选数集合，反复取出最小元素作为素数，并从集合中删除它的所有倍数。

List<int> sieve(List<int> initialCandidates) { final candidates = SplayTreeSet<int>.from(initialCandidates); final int last = candidates.last; final primes = <int>[]; while (true) { final int prime = candidates.first; if (prime * prime > last) break; primes.add(prime); for (int i = prime; i <= last; i += prime) { candidates.remove(i); } } return primes..addAll(candidates); }

SplayTreeSet的两个特性在此被反复利用：first总能以 O(log n) 拿到当前最小候选；remove(i)则以摊还 O(log n) 删除倍数。sieveSound是它的逐字副本，仅把集合类型换成SoundSplayTreeSet<int>：

List<int> sieveSound(List<int> initialCandidates) { final candidates = SoundSplayTreeSet<int>.from(initialCandidates); // ...与 sieve 完全相同的循环体 }

基准入口（main）将两个算法封装进Base（继承自package:benchmark_harness的BenchmarkBase），先执行 10 轮“热身 + 实测”，最后统一report()：

final benchmarks = [ Base(sieve, 'CollectionSieves-SplayTreeSet-removeLoop'), Base(sieveSound, 'CollectionSieves-SoundSplayTreeSet-removeLoop'), ];

需要注意两个细节：

• 输入规模固定：Base.input = range(2, 5000)，即 2 到 5000 的整数序列（4999 个候选数）；
• 结果正确性校验：run()中会断言筛出的素数个数必须等于669，否则抛出'Wrong result for $name: ${primes.length}'。2 到 5000 之间恰好有 669 个素数，这一断言保证了两条实现路径产出完全一致的结果，避免“跑得快但算错了”的无效测量。

此外，main每轮实测前都会调用busyWork()（位于同一文件的 62-92 行）：它用String.codeUnits、Uint16List、Uint32List、UnmodifiableListView、asMap().values等多种集合形态反复执行map/where/toList/List.from/Set.from，并校验长度断言。正如源码注释所写，其目的是“以一定程度的多态性确保核心库被使用”，避免测试对象独占 CPU 缓存或让 JIT 针对单一形态过度特化，从而让两组数据结构的对比更贴近真实场景。

基准输出格式解读

README 给出了基准打印结果的典型形态（运行时间会随机器波动）：

CollectionSieves-SplayTreeSet-removeLoop(RunTime): 4307.52688172043 us. CollectionSieves-SoundSplayTreeSet-removeLoop(RunTime): 4344.902386117137 us.

每一行由基准名(RunTime)与微秒（us）单位的耗时组成。-removeLoop后缀来自 Golem 基准的命名惯例，强调该负载以“循环内反复删除”为主要操作形态（即每次迭代都执行candidates.remove(i)的删除热点，而非单纯遍历）。两个数值的差即反映了型变修饰符在当前编译配置下的开销。

在本地运行基准（三种编译方式）

以下命令均假设你在sdk仓库根目录执行。基准源码与配置文件位于 benchmarks/SoundSplayTreeSieve/dart/，其中 analysis_options.yaml 已经声明了该目录需要开启variance实验特性。

方式一：Dart2JS + V8（d8）

将基准编译为 JavaScript，再用 V8 独立 shelld8执行：

$ sdk/bin/dart2js_developer benchmarks/SoundSplayTreeSieve/dart/SoundSplayTreeSieve.dart --enable-experiment=variance --out=soundsplay_d2js.js $ third_party/d8/linux/d8 soundsplay_d2js.js

• --enable-experiment=variance：显式开启variance实验特性，否则inout修饰符会触发编译错误；
• --out=：指定输出的 JS 文件；
• d8是仓库第三方依赖中捆绑的 V8 独立执行器（third_party/d8），路径前缀按实际平台（这里是 linux）选择。

方式二：Dart2JS 并省略隐式检查

这是该基准最值得关注的一种运行方式：

$ sdk/bin/dart2js_developer benchmarks/SoundSplayTreeSieve/dart/SoundSplayTreeSieve.dart --enable-experiment=variance --omit-implicit-checks --out=soundsplay_d2js_omit.js --lax-runtime-type-to-string $ third_party/d8/linux/d8 soundsplay_d2js_omit.js

• --omit-implicit-checks：指示 Dart2JS 不生成运行时的隐式类型检查代码（如as转换、泛型实例化检查等），这正是声音型变在编译器层面可能带来的收益点——如果inout声明的型变信息能让编译器在编译期静态证明类型安全，那么运行时检查就可以被省略；
• --lax-runtime-type-to-string：允许toString()等方法采用更宽松的（非完整泛型类型的）字符串表示，减少编译产物体积与运行开销。

对照“方式一”与“方式二”两组输出的差值，可以间接评估隐式检查在该负载中的占比。

方式三：DDC（Dart Dev Compiler）调试运行器

使用pkg/dev_compiler自带的ddb工具，在 Chrome 浏览器中直接运行基准：

$ pkg/dev_compiler/tool/ddb -d -r chrome --enable-experiment=variance -k benchmarks/SoundSplayTreeSieve/dart/SoundSplayTreeSieve.dart

• -d：debug 模式；
• -r chrome：以 Chrome 作为运行时；
• -k <文件>：指定要编译运行的入口 Dart 文件。

DDC 保留更完整的类型信息，与 Dart2JS 的产物形成对照，可用于判断测量结果是否受具体编译器后端影响。

深入源码：SoundSplayTreeSet 如何工作

若想理解该基准到底在测什么，值得沿 sound_splay_tree.dart 的源码追踪其核心机制：

1. 节点结构与哑节点（dummy node）：_SoundSplayTreeNode<inout K>持有key与左右子树指针。_DummySoundSplayTreeNode用于在_splay算法中充当左右“哨兵”，复用同一节点避免了每次伸展都重新分配，见 21-32 行与 106-164 行。
2. 顶层伸展算法：_splay(K key)实现了 Sleator 与 Tarjan《Self-adjusting Binary Search Trees》中描述的简化自顶向下伸展，旋转（rotate）与“链接（link）”交替进行，最后将搜索路径上的节点重组到树根，并把_dummy的左右指针复位。每次伸展都会递增_splayCount。
3. 并发修改检测：_modificationCount在键集合变化时递增，_splayCount在树结构重组时递增。迭代器（_SoundSplayTreeIterator）据此抛出ConcurrentModificationError（见 592-597 行、632-652 行），保证遍历安全。
4. 删除与最小/最大：_remove先_splay(key)定位，若根节点没有左子树则直接把右子树提升为根，否则对左子树执行_splayMax后再接回原右子树（197-216 行）；_first/_last则分别通过_splayMin/_splayMax把极值元素旋到根（243-253 行）——这正对应筛法中高频使用的candidates.first与candidates.last。
5. 比较器与键校验：构造时若未提供compare，则优先复用Comparable.compare（当compare is Comparator<K>时零开销直用），否则退化为动态分派 + 强转的_dynamicCompare（262-273 行）；isValidKey默认实现为(v) => v is E，用于在contains/remove/lookup等方法接受任意Object?时先过滤非法键（758-760 行）。
6. 辅助类型：iterable.dart 提供了EfficientLengthIterable（声明length是 O(1) 高效实现）与IterableElementError（统一构造No element/Too many elements/Too few elements的StateError），键/值迭代器与toSet等操作依赖它们。

可见，SoundSplayTreeSet并不是简化玩具实现，而是功能完整、含并发检测与完整迭代器支持的工业级副本。整个文件刻意保留与标准库SplayTreeSet相同的算法骨架，唯一系统性差异就是inout修饰符，从而保证基准结果能归因于型变声明本身。

为什么用variance实验特性：背景与限制

当前 Dart SDK 中，variance（声音型变）仍是实验特性：在 tools/experimental_features.yaml 中，其条目为variance: "Sound variance"。这意味着：

• 源码中直接书写inout/in/out修饰符，必须在所有涉及编译与静态分析的环节（dart2js_developer、ddb、analyzer）都显式传入--enable-experiment=variance或在analysis_options.yaml的analyzer.enable-experiment中声明，否则会报实验特性未启用错误；
• 该特性尚未默认开放，因此其运行时成本、编译期优化空间与语义边界仍处于评估阶段——这正是SoundSplayTreeSieve这类专门为特性“度量”而生的基准存在的意义；
• 结合 docs/process/experimental-flags.md 与 docs/Experimental-Flags.md 对实验开关流程的说明，可以理解该基准需要随语言版本与编译器演进持续回归，用于决策variance能否转正、以及转正后是否需要为SplayTreeSet等标准库集合补充型变修饰符。

结语：如何把基准结果用于决策

SoundSplayTreeSieve的完整价值链是：最小差异对照（同一份筛法代码 + 仅差型变声明的两棵 splay 树）→多后端测量（Dart2JS 常规 / Dart2JS 省略隐式检查 / DDC）→结果自校验（669 个素数的硬断言）。任何一条运行路径产出的两条RunTime数据，都直接服务于“声音型变为现有集合类带来多少开销或收益”这一语言设计问题。

复现方法总结：在仓库根目录依次执行 README 中的 Dart2JS 或 DDC 命令（务必保留--enable-experiment=variance），对比CollectionSieves-SplayTreeSet-removeLoop与CollectionSieves-SoundSplayTreeSet-removeLoop两行的微秒数值即可。若你希望修改输入规模或筛法细节，请编辑 SoundSplayTreeSieve.dart 中的Base.input与断言阈值，并保持busyWork()热身逻辑不变，以维持测量的可比性。

• 编程语言
• 编译器
• 语言运行时
• 标准库
• 开发工具