벡터 대 배열 성능

Question

다른 스레드에서 나는 버튼을 누르기 위해 주로 악마의 옹호자 역할을하는 벡터 및 배열에 대한 토론을 시작했습니다. 그러나이 과정에서 나는 다소 당혹스러워하는 테스트 케이스에 넘어졌고, 나는 악마의 옹호자 역할을하기 위해 얻는 "학대"에 대해 진짜 토론을하고 싶다. 그 실에 대한 토론은 이제 불가능합니다. 그러나이 특별한 예는 나에게 흥미로웠다. 그리고 나 자신에게 만족스럽게 설명 할 수는 없다.

동적 요소를 무시하고 Vector vs Arrays의 일반적인 성능에 대해 설명합니다. 예 : 분명히 벡터에서 push_back()을 계속 사용하면 속도가 느려질 것입니다. 벡터와 배열에는 데이터가 미리 채워져 있다고 가정합니다.

#include <iostream> 
#include <vector> 
#include <type_traits> 
using namespace std; 

const int ARRAY_SIZE = 500000000; 

// http://stackoverflow.com/a/15975738/500104 
template <class T> 
class no_init_allocator 
{ 
public: 
    typedef T value_type; 

    no_init_allocator() noexcept {} 
    template <class U> 
     no_init_allocator(const no_init_allocator<U>&) noexcept {} 
    T* allocate(std::size_t n) 
     {return static_cast<T*>(::operator new(n * sizeof(T)));} 
    void deallocate(T* p, std::size_t) noexcept 
     {::operator delete(static_cast<void*>(p));} 
    template <class U> 
     void construct(U*) noexcept 
     { 
      // libstdc++ doesn't know 'is_trivially_default_constructible', still has the old names 
      static_assert(is_trivially_default_constructible<U>::value, 
      "This allocator can only be used with trivally default constructible types"); 
     } 
    template <class U, class A0, class... Args> 
     void construct(U* up, A0&& a0, Args&&... args) noexcept 
     { 
      ::new(up) U(std::forward<A0>(a0), std::forward<Args>(args)...); 
     } 
}; 

int main() { 
    srand(5); //I use the same seed, we just need the random distribution. 
    vector<char, no_init_allocator<char>> charArray(ARRAY_SIZE); 
    //char* charArray = new char[ARRAY_SIZE]; 
    for(int i = 0; i < ARRAY_SIZE; i++) { 
     charArray[i] = (char)((i%26) + 48) ; 
    } 

    for(int i = 0; i < ARRAY_SIZE; i++) { 
     charArray[i] = charArray[rand() % ARRAY_SIZE]; 
    } 
} 

내 컴퓨터에서이 프로그램을 실행할 때, 나는 다음과 같은 터미널 출력을 얻을 : I 제시, 이후 스레드의 개별 의해 수정의 예는 다음이었다. 첫 번째 실행은 벡터 라인의 주석 처리가 제거 된 상태이고 두 번째 실행은 주석 처리되지 않은 배열 라인입니다. 벡터를 성공의 가장 좋은 기회를주기 위해 가장 높은 수준의 최적화를 사용했습니다. 아래는 제 결과입니다. 첫 번째 두 줄은 배열 줄의 주석 처리를 제거하고 두 번째 줄은 벡터 줄을 사용합니다. 배열이 50 %의 순서가 나는 그들이 무시할 수있을 것이라고 기대, 나를 매우 놀라게의 차이는, 그러나, 나를 놀라게하지 않습니다 벡터를 능가하고, 나는이의 성격 같은 느낌 그건

//Array run # 1 
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out 

real 0m20.287s 
user 0m20.068s 
sys 0m0.175s 

//Array run # 2 
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out 

real 0m21.504s 
user 0m21.267s 
sys 0m0.192s 

//Vector run # 1 
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out 

real 0m28.513s 
user 0m28.292s 
sys 0m0.178s 

//Vector run # 2 
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out 

real 0m28.607s 
user 0m28.391s 
sys 0m0.178s 

테스트 케이스 내가 결과의 성격을 모호하게합니다. 더 작은 어레이 크기에서이 테스트를 실행하면 성능 차이가 크게 줄어 듭니다.

내 설명 : 벡터

추가 구현 지침 아마도 예, 2 개의 다른 "블록"에 정말 나쁜 지점에서 분할에, 벡터 지침을 제대로 메모리에 정렬하는 원인이된다. 이로 인해 캐시 대 데이터 캐시와 명령어 캐시 사이에서 예상보다 자주 메모리가 앞뒤로 이동하게됩니다. 또한 LLVM 컴파일러가 새로운 C++ 11 요소로 인해 약점을 과장하고 최적화하지 않을 수도 있다고 생각합니다. 그러나 가설과 추측 외에도 이러한 설명이 필요하지 않습니다.

A : 누군가가 내 결과를 복제 할 수 있고 B : 컴퓨터가이 특정 벤치 마크를 실행하는 방법에 대한 더 나은 설명이있는 경우와 벡터가이 인스턴스에서 실적이 저조한 배열이있는 이유에 관심이 있습니다.

내이 설정 : http://www.newegg.com/Product/Product.aspx?Item=N82E16834100226

Answer 1

(전혀 최적화 사실에있는 경우) 나는 LLVM이 가리키고 misoptimize의 표준 : : 벡터를한다는 것을 보장 할 수있다, 적어도 지금의로. 관련된 많은 함수 호출을 정확하게 인라인하지 않습니다. GCC를 사용하면 성능이 향상됩니다.

Answer 2

더 간단한 설명 : 최적화가 비활성화 된 상태에서 구축 중입니다. -O3이 아니라 -o3이 필요합니다.

나는 정확히 테스트를 재현 사용할 수 연타를 가지고 있지 않지만, 다음과 같이 내 결과는 다음과 같습니다

//Array run # 1 
$ g++ -std=c++11 -O3 test.cpp -o b.out && time ./b.out 

real 0m25.323s 
user 0m25.162s 
sys 0m0.148s 

//Vector run #1 
$ g++ -std=c++11 -O3 test.cpp -o b.out && time ./b.out 

real 0m25.634s 
user 0m25.486s 
sys 0m0.136s