如何避免使用容器中的引用来取消引用指针的开销？

Question

我遇到了设计挑战.有一个巨大的std::vector<int>称为O大小10000的说,有类型的两个许多对象Foo,f_1... f_n.每个Foo都有一个内部std::vector<int>的子目录O.例如:

O = 1, 2, ..., 100000
f_1.order = 1, 2, 3
f_2.order = 1, 4, 16
f_3.order = 100, 101, 102
// ...

主要要求是更新其值更改O时的相应f_n值.所有Foo物体的长度和含量在施工时都知道,并且在其使用寿命期间不应该改变.例如,已知它f_1包含第一,第二和第三元素O.

显而易见的解决方案当然是使用指针.Foo可以保存std::vector<int*>每个元素指向原始order(O)的基础数据.

另一方面,我的程序使用Foo对象进行一些繁重的计算.所以我正在寻找一种方法来消除指针解除引用的开销.如果设计允许我使用某种类型std::vector<int&>但这是不可能的(我猜因为vector<T>需要存在T*).

一位同事建议使用boost::ptr_vector.另一位建议持有指数vector<size_t>......

Answer 1

我会说优化指针解除引用开销是没有意义的.我们来看一些示例代码:

void bar(int i);

void foo(int* p, int i)
{
    bar(*p);
    bar(i);
}

现在让我们来看看它的组装:

void foo(int* p, int i)
{
                      push   rbx
                      mov    ebx, esi

    bar(*p);
                      mov    edi, DWORD PTR [rdi]
                      call   a <foo+0xa>

    bar(i);
                      mov    edi, ebx
                      call   11 <foo+0x11>
}

有一个内存读取的"开销".

至于使用引用,它不会做任何有用的事情.引用可能与指针有不同的语义,但在下面,它们仍然是指针:

void foo(int& r)
{
    bar(r);
                      mov    edi,DWORD PTR [rbx]
                      call   20 <_Z3fooPiiRi+0x20>
}

发生了相同的内存读取.

我不确定这是否算作"答案",但严重的是:不要打扰.

Answer 2

这个问题不够强调 - 在您知道自己遇到问题之前不要优化代码.指针解除引用并不昂贵,并且通常不是程序中的主要瓶颈.

请注意,引用是使用指针解除引用实现的,因此即使您可以这样做std::vector<int&>,也无济于事.

如果你真的,真的觉得你必须做点什么 - 即使我真的,完全确定它不可能在任何有意义的意义上帮助你的表现 - 你可以尝试覆盖记忆.也就是说,你可以像这样定义它(请注意,我并没有以任何方式支持这一点 - 我只是指出它,这样你就不会做更糟糕的事情):

std::vector<int> O;

struct Foo {
   int *myData;
   int &operator[](int offset) { return myData[offset]; }
};

O.resize(1000000, 0);
Foo f_1, f_2, ...;
f_1.myData = &(O[0]);
f_2.myData = &(O[3]);

O[0] = 5;
cout << f_1[0]; // prints 5

另外,BTW - 拜托,拜托,请不要将名称O用作变量.请.它看起来像零.