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

Question

好吧，问题标题有点蹩脚，但我真的不知道如何更好地表达这个问题。

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

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

您将在下面找到代码以及生成的程序集。如果有人可以解释这里发生了什么，那就太好了。

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

并且请不要回答告诉我我不应该关心、过早优化、万恶之源等。在这种特定情况下，我确实关心，无论如何我认为这是一个相当有趣的谜题! :-)

---

编译器设置:

• 全面优化 (/Ox)
• 整个计划选项。 =否

代码如下:

stdafx.h

// 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 调试器显示的生成的程序集(对于带有“迭代器”的 2 个函数)。

*原始迭代器循环*

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              

*vector_iterator_loop*

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          

Answer 1

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

• 在代码的 vector 版本中，“结束迭代器”值被预先计算并存储为 std::vector 对象的成员，因此内部循环仅加载现成可用的值(value)。

• 在原始指针版本中，“结束迭代器”值在内循环的 header 中明确计算(通过用于实现乘法的 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();
    }
}

(或者甚至在你的类中存储和维护结束指针)你应该得到一个更“公平”的比较。