← 揭开黑盒:理解系统的调查课堂

第二章 · 计算机选择的数学 / 第六单元 · 计算与搬运

怎样相信一次快慢比较?

我们已经有了三种实现。如果某次计时里分块最快,可以宣布它就是更好的算法吗?先像第一章核查“已保存”一样,核查“更快”的承诺范围。

预计用时:45 分钟。打开 真实计时,保持浏览器页面在前台。

在运行前固定问题

页面要求先写一句预测。至少说明:比较什么输入、哪种顺序可能更快,以及哪一种结果会迫使你修改解释。第一次可选择边长 48、块边长 8。

输入是两份确定生成的小整数 Float64Array。在本课允许的规模内,乘积和部分和都在 binary64 能精确保存的整数范围内。页面用 BigInt 独立计算每一个参考输出,再逐项核对三种结果。

这样安排是为了先隔开舍入差异。它不能替代通用浮点误差分析,换成实数数据后要重新定义验收。

计时器围住了哪些步骤

本次顺序比较包含:调用函数、检查输入、分配并清零输出、执行循环。输入生成和 BigInt 参考计算在计时外;每种实现先预热一次,再轮换先后顺序测量五次。

预热能减少一部分首次运行影响,但一次预热不保证浏览器已经达到稳定优化状态。轮换顺序能减轻某种实现总是先跑的偏差,也不能消除温度、后台负载和垃圾回收等变化。

结果显示各次原始样本、中位数和最小到最大范围。较小输入可能接近计时分辨率;范围高度重叠时,不能仅凭中位数末位选赢家。

用规模变化区分解释

现在保留 tile=8,把边长改为 96,再到 192。可能有两种解释:“一个循环写法本身永远更快”;“输入规模改变后,数据复用、循环开销和浏览器优化的相对贡献会变”。

把同一个实现跨规模的变化、不同实现同规模的差别放在一起看。若顺序改变,单次排名的解释就需要收紧。若排序未变,也不能因此断言所有机器与更大规模都会如此。

下一步只改 tile,保持 n 不变。不要同时改输入、块大小、浏览器与计时范围,然后把差别全部归给缓存。

结果与解释之间,还有一段距离

“这个实现的五次中位数较低”是一次观察。“因为更少的缓存未命中”是原因解释。我们的教学模型能说明后者可能发生,但没有直接观测本机 CPU 的事件。

要进一步定位,可以在适当环境使用性能剖析、硬件计数器、原生内核及更严格的基准设计。当前浏览器实验足以比较给定环境中的这几段实现,还不能排除 JIT、边界检查消除等其他原因。

也不能把手写 Python 循环与原生矩阵库的差距全部叫作“算法差距”:语言运行时、数据表示、库实现和线程数都可能一并改变。比较的层次要写清楚。

第六单元交付

导出页面记录,附上三部分说明:原预测、真实样本、你的解释与一个尚未排除的原因。至少包含两个输入规模,以及一组只改块大小的对照。

报告的结论应像这样有范围:“在记录的浏览器、这些输入与计时边界内,方案 A 的样本表现为……;模型提示……可能有关;尚未测量……。”保留没有显著差别或与预测相反的结果。

停止条件是获得足以支撑当前选择的比较。如果目标程序只处理很小的表,简单实现已满足延迟与正确性要求,继续调块大小可能不值得。

下一单元增加一个条件:如果机器上有多个执行者,怎样让他们一起计算?