间接成本 ~ 浮点乘法的 3 倍，真的吗？（带演示）

Question

我刚刚发现间接寻址的开销大约是浮点乘法的 3 倍！
这是可以预料的吗？我的测试错了吗？

背景

读完How much does pointer indirection affect efficiency?后，我对间接成本感到恐慌。

Going through a pointer indirection can be much slower because of how a modern CPU works.

在我过早地优化我的真实代码之前，我想确保它真的像我担心的那样花费很多。

我做了一些技巧来找到粗略的数字 (3x)，如下所示：-

第 1 步

Test1 ：没有间接 -> 计算一些东西
Test2：间接 -> 计算一些东西（相同）

我发现 Test2 比 Test1 花费更多的时间。
这里没有什么奇怪的。

第 2 步

Test1 : 没有间接 -> 计算昂贵的东西
Test2 : 间接 -> 计算便宜的东西

我尝试将我在 calculate something expensive 中的代码更改为逐渐变得更昂贵，以使 Test 的成本接近相同。

结果

最后，我发现使两个测试使用相同时间量（即收支平衡）的可能函数之一是：-

Test1：无间接 -> return float*float*... 3 次
Test2 ：间接 -> 简单地 return a float

这是我的测试用例 (ideone demo) :-

class C{
    public: float hello;  
    public: float hello2s[10];  
    public: C(){
        hello=((double) rand() / (RAND_MAX))*10;
        for(int n=0;n<10;n++){
            hello2s[n]= ((double) rand() / (RAND_MAX))*10;
        }
    }
    public: float calculateCheap(){
        return hello;
    }
    public: float calculateExpensive(){
        float result=1;
        result=hello2s[0]*hello2s[1]*hello2s[2]*hello2s[3]*hello2s[4];
        return result;
    }
};

这是主要内容：-

int main(){
    const int numTest=10000;
    C  d[numTest];
    C* e[numTest];
    for(int n=0;n<numTest;n++){
        d[n]=C();
        e[n]=new C();
    }
    float accu=0;
    auto t1= std::chrono::system_clock::now();
    for(int n=0;n<numTest;n++){
        accu+=d[n].calculateExpensive();  //direct call
    }
    auto t2= std::chrono::system_clock::now();
    for(int n=0;n<numTest;n++){
        accu+=e[n]->calculateCheap();     //indirect call
    }
    auto t3= std::chrono::system_clock::now();
    std::cout<<"direct call time ="<<(t2-t1).count()<<std::endl;
    std::cout<<"indirect call time ="<<(t3-t2).count()<<std::endl;
    std::cout<<"print to disable compiler cheat="<<accu<<std::endl;
}

直接调用时间和间接调用时间调整为与上述类似（通过编辑calculateExpensive ).

结论

间接成本 = 3x 浮点乘法。
在我的桌面上（Visual Studio 2015 with -O2），它是 7x。

问题

是否可以预期间接成本约为浮点乘法的 3 倍？
如果不是，我的测试怎么错了？

（感谢enhzflep提出改进建议，已编辑。）

Answer 1

您的问题没有简单的答案。这取决于硬件的功能和特性（CPU、RAM、总线速度等）。

在过去，浮点乘法可能需要数十个甚至数百个周期。内存访问的速度类似于 CPU 频率（这里想想兆赫兹），浮点乘法比间接乘法需要更长的时间。

从那时起，情况发生了很大变化。现代硬件可以在一两个周期内执行浮点乘法，而间接（内存访问）可能只需要几个周期到数百个周期，具体取决于要读取的数据所在的位置。可以有多个级别的缓存。在极端情况下，通过间接访问的内存已交换到磁盘，需要重新读入。这将有数千个周期的延迟。

通常，获取浮点乘法操作数和解码指令的开销可能比实际乘法花费的时间更长。

Answer 2

简而言之，您的测试非常不具有代表性，实际上并没有准确衡量您可能认为的结果。

请注意，您调用了 new C() 100'000 次。这将在你的内存中创建 100'000 个 C 实例，每个实例都非常小。如果您的内存访问是有规律的，现代硬件非常擅长预测。由于每次分配、每次调用 new 都是独立发生的，因此内存地址不会很好地组合在一起，从而使这种预测变得更加困难。这会导致所谓的缓存未命中。

分配为数组 (new C[numTest]) 可能会产生完全不同的结果，因为在这种情况下地址再次非常可预测。将内存尽可能紧密地组合在一起并以线性、可预测的方式访问它通常会提供更好的性能。这是因为大多数缓存和地址预取器都希望在常见程序中出现这种模式。

次要补充：像这样初始化C d[numTest] = {}; 将在每个元素上调用构造函数

Answer 3

间接成本主要由缓存未命中决定。因为老实说，缓存未命中比您正在谈论的任何其他事情都要昂贵得多，其他一切最终都是舍入错误。

缓存未命中和间接访问的代价可能比您的测试表明的要高得多。

这主要是因为您只有 100,000 个元素，而 CPU 缓存可以缓存每个这些浮点数。顺序堆分配将趋于聚集。

你会得到一堆缓存未命中，但不是每个元素都有一个。

你的两个案例都是间接的。 "indirect" 的情况必须遵循两个指针，而 "direct" 的情况必须执行一个指针运算实例。 "expensive" 情况可能适用于某些 SIMD，特别是如果您放宽了浮点精度（允许乘法重新排序）。

正如所见here, or this image（不是内联，我没有权利），主内存引用的数量将支配上述代码中的几乎所有其他内容。 2 Ghz CPU 的周期时间为 0.5 ns，主存储器引用为 100 ns 或 200 个周期的延迟。

与此同时，桌面 CPU 每个周期可以进行 8 次以上的浮点运算，如果您可以提取矢量化代码。这可能是比单个缓存未命中快 1600 倍的浮点运算。

间接会使您无法使用矢量化指令（速度减慢 8 倍），如果一切都在缓存中，仍然需要比替代方法更频繁地引用 L2 缓存（速度减慢 14 倍）。但与 200 ns 的主内存引用延迟相比，这些减速很小。

请注意，并非所有 CPU 都具有相同级别的矢量化，正在努力加快 CPU/main 内存延迟，FPU 具有不同的特性，以及无数其他并发症。

间接成本 ~ 浮点乘法的 3 倍，真的吗？（带演示）

indirection cost ~ 3x of float multiplication, really? (with demo)

c++

optimization

indirection

c++14

背景

第 1 步

第 2 步

结果

结论

问题

间接成本 ~ 浮点乘法的 3 倍，真的吗？ （带演示）

indirection cost ~ 3x of float multiplication, really? (with demo)

c++

optimization

indirection

c++14

背景

第 1 步

第 2 步

结果

结论

问题

间接成本 ~ 浮点乘法的 3 倍，真的吗？（带演示）