代码之家 › 专栏 › 技术社区 › Martin Ba

为什么指针访问比vector::iterator访问慢?(编译器代码生成)

assembly compiler-construction debugging performance c++

Martin Ba · 技术社区 · 14 年前

好吧,题目有点蹩脚,但我真的不知道怎么说得更好。

我的问题是 std::vector<T> 对a T* + size_t count 我的编译器(Visual Studio 2005/VC++8)在指针上循环时实际上会生成比在向量上循环时更糟糕的代码。

也就是说,我有一个包含向量的测试结构和另一个包含指针+计数的测试结构。现在,当编写语义上完全相同的循环构造时,std::vector的版本是 明显地 (也就是说,>10%)比带指针的版本快。

下面您将找到代码以及生成的程序集。如果有人能解释这是怎么回事就好了。

如果查看程序集,可以注意到原始指针版本如何生成稍多的指令。如果有人能解释这些版本在汇编级别上的语义差异,这已经是一个很好的答案了。

以及拜托不要回答我不应该关心的问题,过早的优化,所有的邪恶根源等等不管怎样,我觉得这是一个相当有趣的谜题!:-)

编译器设置:

整个程序选择。=否

代码来了:

// Disable secure STL stuff!
#define _SECURE_SCL 0
#define _SECURE_SCL_THROWS 0
#include <iostream>
#include <iomanip>
#include <vector>
#include <mmsystem.h>

头文件

// loop1.h
typedef int PodType;

const size_t container_size = 3;
extern volatile size_t g_read_size;

void side_effect();

struct RawX {
    PodType* pData;
    PodType wCount;

    RawX()
    : pData(NULL)
    , wCount(0)
    { }

    ~RawX() {
        delete[] pData;
        pData = NULL;
        wCount = 0;
    }

    void Resize(PodType n) {
        delete[] pData;
        wCount = n;
        pData = new PodType[wCount];
    }
private:
    RawX(RawX const&);
    RawX& operator=(RawX const&);
};

struct VecX {
    std::vector<PodType> vData;
};

void raw_loop(const int n, RawX* obj);
void raw_iterator_loop(const int n, RawX* obj);
void vector_loop(const int n, VecX* obj);
void vector_iterator_loop(const int n, VecX* obj);

// loop1.cpp
void raw_loop(const int n, RawX* obj)
{
    for(int i=0; i!=n; ++i) {
        side_effect();
        for(int j=0, e=obj->wCount; j!=e; ++j) {
            g_read_size = obj->pData[j];
            side_effect();
        }
        side_effect();
    }
}

void raw_iterator_loop(const int n, RawX* obj)
{
    for(int i=0; i!=n; ++i) {
        side_effect();
        for(PodType *j=obj->pData, *e=obj->pData+size_t(obj->wCount); j!=e; ++j) {
            g_read_size = *j;
            side_effect();
        }
        side_effect();
    }
}

void vector_loop(const int n, VecX* obj)
{
    for(int i=0; i!=n; ++i) {
        side_effect();
        for(size_t j=0, e=obj->vData.size(); j!=e; ++j) {
            g_read_size = obj->vData[j];
            side_effect();
        }
        side_effect();
    }
}

void vector_iterator_loop(const int n, VecX* obj)
{
    for(int i=0; i!=n; ++i) {
        side_effect();
        for(std::vector<PodType>::const_iterator j=obj->vData.begin(), e=obj->vData.end(); j!=e; ++j) {
            g_read_size = *j;
            side_effect();
        }
        side_effect();      
    }
}

测试主文件

using namespace std;

volatile size_t g_read_size;
void side_effect()
{
    g_read_size = 0;
}

typedef size_t Value;

template<typename Container>
Value average(Container const& c)
{
    const Value sz = c.size();
    Value sum = 0;
    for(Container::const_iterator i=c.begin(), e=c.end(); i!=e; ++i)
        sum += *i;
    return sum/sz;

}

void take_timings()
{
    const int x = 10;
    const int n = 10*1000*1000;

    VecX vobj;
    vobj.vData.resize(container_size);
    RawX robj;
    robj.Resize(container_size);

    std::vector<DWORD> raw_times;
    std::vector<DWORD> vec_times;
    std::vector<DWORD> rit_times;
    std::vector<DWORD> vit_times;

    for(int i=0; i!=x; ++i) {
        const DWORD t1 = timeGetTime();
        raw_loop(n, &robj);
        const DWORD t2 = timeGetTime();
        vector_loop(n, &vobj);
        const DWORD t3 = timeGetTime();
        raw_iterator_loop(n, &robj);
        const DWORD t4 = timeGetTime();
        vector_iterator_loop(n, &vobj);
        const DWORD t5 = timeGetTime();
        raw_times.push_back(t2-t1);
        vec_times.push_back(t3-t2);
        rit_times.push_back(t4-t3);
        vit_times.push_back(t5-t4);
    }

    cout << "Average over " << x << " iterations for loops with count " << n << " ...\n";
    cout << "The PodType is '" << typeid(PodType).name() << "'\n";
    cout << "raw_loop: " << setw(10) << average(raw_times) << " ms \n";
    cout << "vec_loop: " << setw(10) << average(vec_times) << " ms \n";
    cout << "rit_loop: " << setw(10) << average(rit_times) << " ms \n";
    cout << "vit_loop: " << setw(10) << average(vit_times) << " ms \n";
}

int main()
{
    take_timings();
    return 0;
}

下面是visual studio调试器显示的生成的程序集(用于带有“迭代器”的两个函数)。

*原始迭代器循环*

void raw_iterator_loop(const int n, RawX* obj)
{
    for(int i=0; i!=n; ++i) {
00  mov         eax,dword ptr [esp+4] 
00  test        eax,eax 
00  je          raw_iterator_loop+53h (4028C3h) 
00  push        ebx  
00  mov         ebx,dword ptr [esp+0Ch] 
00  push        ebp  
00  push        esi  
00  push        edi  
00  mov         ebp,eax 
        side_effect();
00  call        side_effect (401020h) 
        for(PodType *j=obj->pData, *e=obj->pData+size_t(obj->wCount); j!=e; ++j) {
00  movzx       eax,word ptr [ebx+4] 
00  mov         esi,dword ptr [ebx] 
00  lea         edi,[esi+eax*2] 
00  cmp         esi,edi 
00  je          raw_iterator_loop+45h (4028B5h) 
00  jmp         raw_iterator_loop+30h (4028A0h) 
00  lea         esp,[esp] 
00  lea         ecx,[ecx] 
            g_read_size = *j;
00  movzx       ecx,word ptr [esi] 
00  mov         dword ptr [g_read_size (4060B0h)],ecx 
            side_effect();
00  call        side_effect (401020h) 
00  add         esi,2 
00  cmp         esi,edi 
00  jne         raw_iterator_loop+30h (4028A0h) 
        }
        side_effect();
00  call        side_effect (401020h) 
00  sub         ebp,1 
00  jne         raw_iterator_loop+12h (402882h) 
00  pop         edi  
00  pop         esi  
00  pop         ebp  
00  pop         ebx  
    }
}
00  ret

*向量迭代器循环*

void vector_iterator_loop(const int n, VecX* obj)
{
    for(int i=0; i!=n; ++i) {
00  mov         eax,dword ptr [esp+4] 
00  test        eax,eax 
00  je          vector_iterator_loop+43h (402813h) 
00  push        ebx  
00  mov         ebx,dword ptr [esp+0Ch] 
00  push        ebp  
00  push        esi  
00  push        edi  
00  mov         ebp,eax 
        side_effect();
00  call        side_effect (401020h) 
        for(std::vector<PodType>::const_iterator j=obj->vData.begin(), e=obj->vData.end(); j!=e; ++j) {
00  mov         esi,dword ptr [ebx+4] 
00  mov         edi,dword ptr [ebx+8] 
00  cmp         esi,edi 
00  je          vector_iterator_loop+35h (402805h) 
            g_read_size = *j;
00  movzx       eax,word ptr [esi] 
00  mov         dword ptr [g_read_size (4060B0h)],eax 
            side_effect();
00  call        side_effect (401020h) 
00  add         esi,2 
00  cmp         esi,edi 
00  jne         vector_iterator_loop+21h (4027F1h) 
        }
        side_effect();      
00  call        side_effect (401020h) 
00  sub         ebp,1 
00  jne         vector_iterator_loop+12h (4027E2h) 
00  pop         edi  
00  pop         esi  
00  pop         ebp  
00  pop         ebx  
    }
}
00  ret

8 回复 | 直到 14 年前

AnT stands with Russia 14 年前

虽然我生成的机器代码版本与您的版本(MSVC++2005)不同,但这两个变体之间的一个区别与您的代码中的差别几乎相同:

在矢量版本的代码中,“结束迭代器”值是预先计算并存储为 std::vector 对象,因此内部循环只加载容易获得的值。
lea 用于实现乘法的指令),这意味着外循环的每次迭代都会一次又一次地执行该计算。

如果你重新实施 raw_iterator_loop 如下所示(即,将结束指针的计算从外循环中拉出)

void raw_iterator_loop(const int n, RawX* obj)
{
    PodType *e = obj->pData+size_t(obj->wCount);

    for(int i=0; i!=n; ++i) {
        side_effect();
        for(PodType *j=obj->pData; j!=e; ++j) {
            g_read_size = *j;
            side_effect();
        }
        side_effect();
    }
}

(甚至在类中存储和维护结束指针)您应该以更“公平”的比较结束。

Steve Townsend 14 年前

产生指令差异的一个具体原因是VisualC++ vector 有个成员 _Myfirst 和 _Mylast (对应于 begin() 和 end()

在原始情况下,编译器必须进行实际的指针计算以设置所需的开始和结束局部变量。

矢量 编码更快。

Paul Groke Chronial 14 年前

编译器无法知道 side_effect() 不会改变的 obj->pData .

p、 S.:这会影响 raw_loop 和 vector_loop . 原始回路 可以通过使用局部变量来“修复”, 矢量环路 不能。不能,因为会有一个数组指针向量,编译器也无法知道任何东西都不会改变向量内的数组指针。毕竟, side_effect 可以打电话给。 push_back() . 当然,如果编译器可以内联任何循环函数,它可能会优化得更好。E、 g.如果使用的向量是一个局部变量,其地址在函数外部未知,并且只传递给循环函数。然后编译器可以再次知道 副作用 无法更改向量(因为它不知道它的地址),因此无法更好地进行优化。->如果要针对非内联情况对函数进行优化,请确保编译器无法内联该函数。

Joe Valenzuela 14 年前

您的计时可能反映了这样一个事实:初始raw_循环支付加载缓存的成本。如果重新排序测试以首先执行向量测试(或者可以抛出第一个迭代,或者使每个测试成为一个单独的程序),会得到类似的计时吗。

Community CDub 8 年前

看看为内部循环生成的程序集,它们基本上是相同的,除了一个寄存器更改。我不希望在这个基础上有任何时间上的差异。

            g_read_size = *j; 
00  movzx       ecx,word ptr [esi]  
00  mov         dword ptr [g_read_size (4060B0h)],ecx  
            side_effect(); 
00  call        side_effect (401020h)  
00  add         esi,2  
00  cmp         esi,edi  
00  jne         raw_iterator_loop+30h (4028A0h)

            g_read_size = *j;  
00  movzx       eax,word ptr [esi]   
00  mov         dword ptr [g_read_size (4060B0h)],eax   
            side_effect();  
00  call        side_effect (401020h)   
00  add         esi,2   
00  cmp         esi,edi   
00  jne         vector_iterator_loop+21h (4027F1h)

我有一个关于代码计时的类似问题,我无法解释两段代码之间的差异。我从来没有得到一个明确的答案,虽然最后我说服自己,这是一个代码对齐的情况。 How can adding code to a loop make it faster?

Yakov Galka 14 年前

尝试更改播客类型 int 到 size_t . 那里的转换使循环初始化代码复杂化。

Ben Voigt 14 年前

我本来希望优化器足够聪明,可以消除任何差异,但通常减量和与零的比较比与非零指针的比较快。

void countdown_loop(int n, RawX* obj)
{
    if (!n) return;
    size_t const wc = obj->wCount;
    if (!wc) return;
    PodType* const first = obj->pData;
    do {
        side_effect();
        size_t i = wc;
        PodType* p = first;
        do {
            g_read_size = *p;
            side_effect();
            ++p;
        } while (--i);
        side_effect();
    } while (--n);
}

user1295785 12 年前

我知道这很晚了,但有一个快速的观察:未签名的指令可以稍微快一点。据我所知,硬件实现稍微简单一点,因为没有符号位可以随增量或减量而改变。对于P6微架构CPU来说,这只是一个时钟周期,但这些都是累积起来的。

我希望大小是无符号的,因为没有负的“大小”。

您必须使用“芯片制造商档案器”(英特尔VTUNE—30天试用版;AMD代码分析器是免费的)进行档案分析,因为有太多的东西可以发挥作用:管道暂停、缓存未命中、数据未对齐、存储加载依赖性。。。

这件事比44年前我在高中写第一个Fortran程序时复杂得多。再也没有人在汇编程序中编程了。一个真正让人头疼的是,从C程序生成的PA Risc(90年代的HP Unix系统芯片)指令。。。这些操作不是我所期望的顺序,因为代码生成器理解PA Risc CPU的内部操作。指令的顺序很有趣,因为它们在CPU中是有意义的,但在我的纸上是没有意义的。