컨테이너의 참조를 사용하여 포인터의 참조 해제 오버 헤드를 방지하려면 어떻게해야합니까?

Question

디자인 문제가 발생했습니다. 크기 10000의 거대한 std::vector<int>라고 O 말은 유형 Foo, f_1 ... f_n 두 가지 많은 개체가 있습니다. 각 Foo에는 O의 하위 주문 인 std::vector<int> 내부가 있습니다. 예를 들어

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

주요 요건은 f_n 그 값을 변경할 때 O의 해당 값을 업데이트한다. 모든 Foo 개체의 길이와 내용은 작성시 알고 있으며 수명 동안 변경되지 않아야합니다. 예를 들어, f_1에는 O의 첫 번째, 두 번째 및 세 번째 요소가 들어있는 것으로 알려져 있습니다.

명백한 해결책은 물론 포인터를 사용하는 것입니다. Foo은 각 요소가 원래 순서 (O)의 기본 데이터를 가리키는 std::vector<int*>을 보유 할 수 있습니다. 한편

, 내 프로그램은 Foo 개체를 사용하여 몇 가지 무거운 계산을 할. 그래서 포인터 역 참조의 오버 헤드를 제거하는 방법을 찾고 있습니다. 설계가 std::vector<int&> 일종의 사용을 허용한다면 좋겠지 만, vector<T>이 존재해야하기 때문에 T*이 존재합니다.

동료

는 boost::ptr_vector를 사용하도록 제안. 코드를 최적화하지 않습니다 당신이 문제가 알기도 전에 - 또 다른이 충분히 강조되지 않을 수

Answer 1

조숙 한 최적화라고 생각합니다. 포인터를 어설프게 싸구려를 참조하십시오.

명백한 해결책은 물론 포인터를 사용하는 것입니다. Foo는 각 요소가 원본 오더 (O)의 기본 데이터를 가리키는 std :: vector를 보유 할 수 있습니다. 여기

솔루션

는, 표준 : reference_wrapper 및 표준을 사용하여 포인터를 사용하지 않는, 당신이 필요로 공제 :: 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; 
} 

편집 : 성능이 동일하면 포인터를 사용하는 경우 있음 , 그러나 표준 : reference_wrapper는 T &을 가지며 T *와 T &에 대한 코드를 필요로하지 않기 때문에 템플릿 기반 코드에서 가장 잘 통합 될 수 있습니다.

다른 벡터에 인덱스가있는 경우 구조가 여러 조건에 의해 정렬 된 경우에만 유용합니다.

벡터를 사용하여 예제를 보여줍니다. 여기서 T는 두 필드가있는 struct complex입니다. 원판을 만지지 않고 두 가지 기준으로이 벡터를 재정렬 할 수 있습니다.

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; 
} 

Answer 2

... vector<size_t>에 인덱스를 잡고 제안했다. 포인터 역 참조는 비용이 많이 들지 않으며 일반적으로 프로그램의 주요 병목 현상이 아닙니다. 참조 포인터 역 참조를 사용하여 구현된다, 그래서 당신은 std::vector<int&>을 할 수있는 경우에도 도움이되지 것

는

참고.

당신은 정말, 정말 당신이 뭔가를해야 느끼는 경우에 - 나는 그것이 아마도 의미있는 의미에서 성능을 도울 수 없어요 정말 완전히 확신에도 불구하고 - 메모리를 오버레이 시도 할 수 있습니다. BTW, 또한

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을 사용하지 마십시오. 부디. 그것은 0처럼 보입니다.

Answer 3

나는 포인터 역 참조 오버 헤드를 최적화하는 것이 무의미하다고 말합니다.

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> 
} 

있다 동일한 메모리가 일어나고 읽어 보시기 바랍니다.

"대답"으로 간주할지 여부는 확실하지 않지만 심각하게 생각하지 않습니다.