c++ - 如何避免指针的取消引用开销，在容器中使用引用？

Question

我遇到了设计挑战。有一个巨大的std::vector<int>叫做Osay，大小为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在 af_n更改其值时更新相应的值。所有对象的长度和内容Foo在构造时都是已知的，并且在它们的生命周期内不应该改变。例如，已知f_1包含 的第一个、第二个和第三个元素O。

显而易见的解决方案当然是使用指针。Foo可以保存一个std::vector<int*>每个元素指向原始顺序的基础数据（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

另外，顺便说一句 - 请，请，请不要将名称O用作变量。请。它看起来像一个零。

Answer 3

It sound as premature optimization. Dereference a pointer is ridiculously cheap.

The obvious solution is to use pointers of course. Foo may hold a std::vector which each element points to underlying data of original order (O).

Here a solution, deducting what you need, not using pointers, using std::reference_wrapper and std::ref:

struct Foo
{
    Foo(std::vector<int>& _data) : dataFull(_data)
    { ; }

    void add(int index)
    {
        assert(index < dataFull.size());

        if(index < references.size())
        {
            // replace
            references[index] = std::ref(dataFull[index]);
        }
        else
        {
            // add n times, need sync with index
            while(index >= references.size())
            {
                references.push_back(std::ref(dataFull[index]));
            }
        }

        // mark as valid index
        indexes.push_back(index);
        // sort for can find with binary_search
        std::sort(indexes.begin(), indexes.end());
    }

    int* get(int index)
    {
        if(std::binary_search(indexes.begin(), indexes.end(), index))
        {
            return &references[index].get();
        }
        else
        {
            return NULL;
        }
    }

protected:
    std::vector<int>& dataFull;
    std::vector<std::reference_wrapper<int> > references;
    std::vector<int> indexes;
};

int main()
{
    const int size = 1000000;
    std::vector<int> O;
    O.resize(1000000, 0);

    Foo f_1(O);
    f_1.add(1);
    f_1.add(2);
    f_1.add(3);

    Foo f_2(O);
    f_2.add(1);
    f_2.add(4);
    f_2.add(16);

    Foo f_3(O);
    f_3.add(100);
    f_3.add(101);
    f_3.add(102);

    // index 1 is changed, it must affect to all "Foo" that use this index (f_1 and f_2)
    O[1] = 666;

    // checking if it changed
    assert( *f_1.get(1) == 666 );
    assert( *f_2.get(1) == 666 );
    assert(  f_3.get(1) == NULL );

    return 0;
}

EDIT: Performance is same that if you use pointer, but std::reference_wrapper can be integrated best in templated code because you have T& and don't need have code for T* and T&.

Have indexes in other vector, only is useful if your struct is ordered by multiple criteria.

I show a example with a vector, where T is a struct complex with two fields. I can reorder this vector with 2 criterias, without touch the original.

template <typename T>
struct Index
{
    typedef typename bool(*Comparator)(const T&, const T&);

    Index(std::vector<T>& _data, Comparator _comp)
        : dataFull(_data)
        , comp(_comp)
    {
        for(unsigned int i = 0; i < dataFull.size(); ++i)
        {
            add(i);
        }
        commit();
    }

    void commit()
    {
        std::sort(references.begin(), references.end(), comp);
    }

    std::vector<std::reference_wrapper<T> >& getReference() {return references;}

protected:

    void add(int index)
    {
        assert(index < dataFull.size());
        references.push_back(std::ref(dataFull[index]));
    }

protected:
    std::vector<T>& dataFull;
    std::vector<std::reference_wrapper<T> > references;
    Comparator comp;
};

int main()
{
    struct ComplexData
    {
        int field1;
        int field2;
    };

    // Generate vector
    const int size = 10;
    std::vector<ComplexData> data;
    data.resize(size);
    for(unsigned int i = 0; i < size; ++i)
    {
        ComplexData& c = data[i];
        c.field1 = i;
        c.field2 = size - i;
    }

    // Vector reordered without touch original
    std::cout << "Vector data, ordered by field1" << std::endl;
    {
        Index<ComplexData> f_1(data, 
            [](const ComplexData& a, const ComplexData& b){return a.field1 < b.field1;});
        auto it = f_1.getReference().begin();
        auto ite = f_1.getReference().end();
        for(; it != ite; ++it)
        {
            std::cout << "-> " << it->get().field1 << " - " << it->get().field2 << std::endl;
        }
    }

    // Vector reordered without touch original
    std::cout << "Vector data, ordered by field2" << std::endl;
    {
        Index<ComplexData> f_2(data, 
            [](const ComplexData& a, const ComplexData& b){return a.field2 < b.field2;});
        auto it = f_2.getReference().begin();
        auto ite = f_2.getReference().end();
        for(; it != ite; ++it)
        {
            std::cout << "-> " << it->get().field1 << " - " << it->get().field2 << std::endl;
        }
    }

    return 0;
}