如何演示指令缓存限制的影响

Question

我的想法是给出一个优雅的代码示例,它将演示指令缓存限制的影响.我编写了以下代码,使用模板元编程创建了大量相同的函数.

volatile int checksum;
void (*funcs[MAX_FUNCS])(void);

template <unsigned t> 
__attribute__ ((noinline)) static void work(void) { ++checksum; }

template <unsigned t> 
static void create(void) { funcs[t - 1] = &work<t - 1>; create<t - 1>(); }

template <> void create<0>(void) {  }

int main()
{
    create<MAX_FUNCS>();

    for (unsigned range = 1; range <= MAX_FUNCS; range *= 2)
    {
        checksum = 0;
        for (unsigned i = 0; i < WORKLOAD; ++i)
        {
            funcs[i % range]();
        }
    }

    return 0;
}

外循环使用跳转表改变要调用的不同函数的数量.对于每个循环传递,WORKLOAD然后测量调用函数所花费的时间.现在有什么结果？下图显示了每个函数调用的平均运行时间与使用范围的关系.蓝线显示在Core i7机器上测量的数据.由红线描绘的比较测量在Pentium 4机器上进行.然而,当谈到解释这些界限时,我似乎在某种程度上挣扎......

分段恒定红色曲线的唯一跳转恰好发生在范围内所有函数的总内存消耗超过测试机器上的一个高速缓存级别的容量的位置,该机器没有专用指令高速缓存.但是,对于非常小的范围(在这种情况下低于4),运行时间仍会随着功能的数量而增加.这可能与分支预测效率有关,但由于在这种情况下每个函数调用都减少为无条件跳转,因此我不确定是否应该存在任何分支惩罚.

蓝色曲线表现完全不同.对于小范围,运行时间是恒定的,并且之后增加对数.然而对于更大的范围,曲线似乎再次接近恒定的渐近线.两条曲线的定性差异究竟如何解释？

我目前正在使用GCC MinGW Win32 x86 v.4.8.1 g++ -std=c++11 -ftemplate-depth=65536并且没有编译器优化.

任何帮助,将不胜感激.我也对如何改进实验本身感兴趣.提前致谢!

Answer 1

首先，我要说的是，我真的很喜欢你解决这个问题的方式，这是针对故意代码膨胀的一个非常巧妙的解决方案。但是，您的测试可能仍然存在几个可能的问题 -

1. 您还可以测量预热时间。你没有显示你把时间检查放在哪里，但如果它只是在内部循环周围 - 那么第一次直到你达到 range/2 你仍然会享受上一个外部迭代的热身。相反，仅测量热性能 - 多次运行每个内部迭代（在中间添加另一个循环），并仅在 1-2 轮后获取时间戳。

2. 您声称测量了多个缓存级别，但您的 L1 缓存只有 32k，这就是您的图表的终点。即使假设这按照“范围”进行计算，每个函数也约为 21 个字节（至少在我的 gcc 4.8.1 上），因此您最多将达到 256KB，这才触及 L2 的大小。

3. 你没有指定你的CPU型号（i7现在市场上至少有4代，Haswell、IvyBridge、SandyBridge和Nehalem）。差异相当大，例如，自 Sandybrige 以来，附加的 uop 缓存具有复杂的存储规则和条件。您的基线也使事情变得复杂，如果我没记错的话，P4 有一个跟踪缓存，这也可能会导致各种性能影响。如果可能的话，您应该检查一个选项来禁用它们。

4. 不要忘记 TLB - 尽管它可能在组织如此紧密的代码中不起作用，但唯一 4k 页面的数量不应超过 ITLB（128 个条目），甚至在此之前您可能会开始发生冲突如果您的操作系统没有很好地分散物理代码页来避免 ITLB 冲突。