ARTICLE DETAIL

资讯详情

深耕网站建设与运营推广的一线实战洞察。

Dart SDK 基准测试解析:用 SoundSplayTreeSet 验证声音型变(Sound Variance)对 Splay 树性能的影响

Dart SDK 基准测试解析:用 SoundSplayTreeSet 验证声音型变(Sound Variance)对 Splay 树性能的影响 编程语言编译器语言运行时标准库开发工具【免费下载链接】sdkThe Dart SDK, including the VM, JS and Wasm compilers, analysis, core libraries, and more.项目地址https://gitcode.com/gh_mirrors/sdk1/sdk点击查看免费下载导读本文围绕 Dart SDK 仓库中的SoundSplayTreeSieve基准测试展开它复刻了 Golem 基准集中的sieve9埃拉托斯特尼筛法用于对比dart:collection标准库中的SplayTreeSet与一个为类型参数声明了**型变修饰符variance modifiersinout**的自定义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的变体和 DDCddb调试浏览器运行器因为它们恰好是能观察到泛型擦除与隐式类型检查行为的场景。被测的两个集合SplayTreeSet与SoundSplayTreeSetdart:collection中的SplayTreeSet基准的第一个被测对象直接来自标准库final candidates SplayTreeSetint.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 _SoundSplayTreeinout K { ... } class _SoundSplayTreeNodeinout K { ... } class SoundSplayTreeSetinout E extends _SoundSplayTreeE with IterableMixinE, SetMixinE { ... } class SoundSplayTreeMapinout K, inout V extends _SoundSplayTreeK with MapMixinK, V { ... }inout是 Dart 实验性“声音型变”特性引入的三向修饰符之一与in、out并列表示该类型参数在协变与逆变位置上都会被使用。例如_SoundSplayTreeK中既有返回K的读取位置_root.key、first、last也有把K作为方法参数传入的写入位置add(E element)、_compare(K key1, K key2)、removeAll(IterableObject? elements)中的_remove(element as E)因此K/E必须声明为inout才能同时满足两个方向的位置约束。从源码结构看这个文件完整复刻了标准 splay 树的所有核心机制见下节因此它与SplayTreeSet的差异被压缩到“是否声明型变修饰符”这一最小变量上——这正是对照基准的严谨性所在。筛法算法与基准封装代码逐行解读被测算法位于 benchmarks/SoundSplayTreeSieve/dart/SoundSplayTreeSieve.dart它实现了经典的埃拉托斯特尼筛法维护一个候选数集合反复取出最小元素作为素数并从集合中删除它的所有倍数。Listint sieve(Listint initialCandidates) { final candidates SplayTreeSetint.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是它的逐字副本仅把集合类型换成SoundSplayTreeSetintListint sieveSound(Listint initialCandidates) { final candidates SoundSplayTreeSetint.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 V8d8将基准编译为 JavaScript再用 V8 独立 shelld8执行$ sdk/bin/dart2js_developer benchmarks/SoundSplayTreeSieve/dart/SoundSplayTreeSieve.dart --enable-experimentvariance --outsoundsplay_d2js.js $ third_party/d8/linux/d8 soundsplay_d2js.js--enable-experimentvariance显式开启variance实验特性否则inout修饰符会触发编译错误--out指定输出的 JS 文件d8是仓库第三方依赖中捆绑的 V8 独立执行器third_party/d8路径前缀按实际平台这里是 linux选择。方式二Dart2JS 并省略隐式检查这是该基准最值得关注的一种运行方式$ sdk/bin/dart2js_developer benchmarks/SoundSplayTreeSieve/dart/SoundSplayTreeSieve.dart --enable-experimentvariance --omit-implicit-checks --outsoundsplay_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()等方法采用更宽松的非完整泛型类型的字符串表示减少编译产物体积与运行开销。对照“方式一”与“方式二”两组输出的差值可以间接评估隐式检查在该负载中的占比。方式三DDCDart Dev Compiler调试运行器使用pkg/dev_compiler自带的ddb工具在 Chrome 浏览器中直接运行基准$ pkg/dev_compiler/tool/ddb -d -r chrome --enable-experimentvariance -k benchmarks/SoundSplayTreeSieve/dart/SoundSplayTreeSieve.dart-ddebug 模式-r chrome以 Chrome 作为运行时-k 文件指定要编译运行的入口 Dart 文件。DDC 保留更完整的类型信息与 Dart2JS 的产物形成对照可用于判断测量结果是否受具体编译器后端影响。深入源码SoundSplayTreeSet 如何工作若想理解该基准到底在测什么值得沿 sound_splay_tree.dart 的源码追踪其核心机制节点结构与哑节点dummy node_SoundSplayTreeNodeinout K持有key与左右子树指针。_DummySoundSplayTreeNode用于在_splay算法中充当左右“哨兵”复用同一节点避免了每次伸展都重新分配见 21-32 行与 106-164 行。顶层伸展算法_splay(K key)实现了 Sleator 与 Tarjan《Self-adjusting Binary Search Trees》中描述的简化自顶向下伸展旋转rotate与“链接link”交替进行最后将搜索路径上的节点重组到树根并把_dummy的左右指针复位。每次伸展都会递增_splayCount。并发修改检测_modificationCount在键集合变化时递增_splayCount在树结构重组时递增。迭代器_SoundSplayTreeIterator据此抛出ConcurrentModificationError见 592-597 行、632-652 行保证遍历安全。删除与最小/最大_remove先_splay(key)定位若根节点没有左子树则直接把右子树提升为根否则对左子树执行_splayMax后再接回原右子树197-216 行_first/_last则分别通过_splayMin/_splayMax把极值元素旋到根243-253 行——这正对应筛法中高频使用的candidates.first与candidates.last。比较器与键校验构造时若未提供compare则优先复用Comparable.compare当compare is ComparatorK时零开销直用否则退化为动态分派 强转的_dynamicCompare262-273 行isValidKey默认实现为(v) v is E用于在contains/remove/lookup等方法接受任意Object?时先过滤非法键758-760 行。辅助类型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-experimentvariance或在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-experimentvariance对比CollectionSieves-SplayTreeSet-removeLoop与CollectionSieves-SoundSplayTreeSet-removeLoop两行的微秒数值即可。若你希望修改输入规模或筛法细节请编辑 SoundSplayTreeSieve.dart 中的Base.input与断言阈值并保持busyWork()热身逻辑不变以维持测量的可比性。赞分享编程语言编译器语言运行时标准库开发工具【免费下载链接】sdkThe Dart SDK, including the VM, JS and Wasm compilers, analysis, core libraries, and more.项目地址https://gitcode.com/gh_mirrors/sdk1/sdk点击查看免费下载相关推荐Bilibili-EvolvedCSS变量性能影响基准测试结果Bilibili EvolvedCSS变量性能影响基准测试结果 测试背景与方法 在Bilibili Evolved项目中CSS变量被广泛应用于主题切换和组件前端音视频Kitex拦截器性能影响基准测试对比Kitex拦截器性能影响基准测试对比 你是否在生产环境中遇到过RPC调用延迟突增的问题是否怀疑过那些看似无害的拦截器Interceptor或中间件Mi后端RPC框架微服务服务注册发现负载均衡revanced-patches性能基准测试量化补丁对应用的影响revanced patches性能基准测试量化补丁对应用的影响 还在为应用卡顿、耗电快而烦恼ReVanced Patches作为一个强大的Android应移动开发创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表