为什么在排序数组中较大搜索值的实际运行时间小于较低搜索值？

Question

我对包含范围 [1, 10000] 中所有唯一元素的数组执行了线性搜索，按所有搜索值（即从 1 到 10000）按递增顺序排序，并绘制了运行时与搜索值图，如下所示：

仔细分析放大版本的情节如下：

我发现一些较大搜索值的运行时间小于较低搜索值，反之亦然

我对这种现象的最佳猜测是，它与 CPU 如何使用主内存和缓存处理数据有关，但没有明确的可量化理由来解释这一点。

任何提示将不胜感激。

PS：代码是用 C++ 编写的，并在 linux 平台上执行，该平台托管在 Google Cloud 上具有 4 个 VCPU 的虚拟机上。运行时间是使用 C++ Chrono 库测量的。

Answer 1

CPU 缓存大小取决于 CPU 型号，有多个缓存级别，因此您的实验应考虑所有这些因素。L1 缓存通常为 8 KiB，比您的 10000 阵列小约 4 倍。但我不认为这是缓存未命中。L2延迟在100ns左右，比最低和二线的差值小很多，大约5usec。我想这（第二行云）是由上下文切换贡献的。任务越长，上下文切换发生的可能性就越大。这就是为什么右侧的云层更厚的原因。

现在为放大图。由于 Linux 不是实时操作系统，因此时间测量不是很可靠。IIRC 它的最小报告单位是微秒。现在，如果某个任务正好需要 15.45 微秒，那么它的结束时间取决于它的开始时间。如果任务在精确的零时钟开始，则报告的时间将为 15 微秒。如果它在内部时钟为 0.1 微秒时启动，那么您将获得 16 微秒。您在图中看到的是模拟直线到离散值轴的线性近似。所以你得到的任务持续时间不是实际的任务持续时间，而是实际值加上任务开始时间到微秒（均匀分布~U[0,1]）和所有四舍五入到最接近的整数值。