c - SpMV 算法的大小与时间图中的不规则时间跳跃

Question

我正在测试尺寸为 1 到 1000 的代码，并且正在测量每次迭代所需的时间，我注意到时间上存在很大差异，即使尺寸相差一倍。

我进行了 7 个测试，但这里只粘贴 3 个。图片中的 x 轴代表矩阵大小(N x N)，y 轴代表时间(以微秒为单位)。

这是我正在测试的代码片段:

QueryPerformanceFrequency(&frequency);
QueryPerformanceCounter(&start);

for (i = 0; i < size; i++) 
{
    for (j = row_ptr[i]; j < row_ptr[i + 1]; j++) 
    {
        result[i] += val[j] * x[col_idx[j]];
    }
}
QueryPerformanceCounter(&end);
// Stop time measurement

interval = (double) (end.QuadPart - start.QuadPart) / frequency.QuadPart;

我尝试找到解决方案，例如找到填充 L3 缓存的大小并使用这些大小进行测试，但没有任何结果。

为什么我会遇到这些违规行为？另外，为什么对于一些较大尺寸的矩阵，我的时间会减少？

PS 这是完整的 code如果有人感兴趣:

Answer 1

虽然这个名字可能会让您相信 QueryPerformanceCounter 正在测量任务的性能，但它实际上测量的是耗时，而不是与当前任务关联的 CPU 时间。

即使它正在测量 CPU 时间，也有很多事情可能会分散 CPU 几微秒(或者在其他正在运行的任务抢占 CPU 的情况下是几毫秒)，包括中断处理(例如，网络)流量)、页面错误和 TLB 刷新。所有这些不同的事件都会给基准测试带来一些噪音；标准建议是多次运行基准测试并在分析数据之前删除异常值。

此外，在开始运行基准测试之前，CPU 缓存中不会有任何有用的内容，并且分支预测将不准确。因此，随着缓存和分支预测“预热”，前几次基准测试运行通常会逐渐加快。 (您需要特别小心地通过在同一基准程序中连续运行两种不同的算法来比较它们。如果您不考虑内存中数据的缓存预热，则第一个基准可能会比第二个慢即使它们是完全相同的算法。)

最后，多核芯片中的核心性能之间通常存在微小差异，因此从一个核心切换到另一个核心可能会导致基准图中的垂直位移，例如您在第一个中看到的大约 N=400 的情况图表。