적어도이 경우에는 벡터가 항상 C 배열보다 느린 이유는 무엇입니까?

비교에는 차이를 설명하는 불일치가 포함되어 있으며 다른 요인은 충분한 최적화없이 컴파일 한 결과 일 수 있습니다. 일부 구현에는 STL의 디버그 빌드에 많은 추가 코드가 있습니다. 예를 들어 MSVC는 디버그 빌드에서 속도를 크게 감소시키는 벡터 요소 액세스에 대한 경계 검사를 수행합니다.

다음 코드는 둘 사이의 훨씬 더 가까운 성능을 보여 주며 차이점은 아마도 샘플이 부족하다는 것입니다 (ideone은 시간 제한이 5 초임).

#include <vector>
#include <cmath>
#include <cstring>

int countPrimes_vector(int n) {  
    int res = 0; 
    std::vector<bool> bitmap(n, true);
    for (int i = 2; i<n; ++i){
        if(bitmap[i])
          ++res;
        if(sqrt(n)>i)
        {
             for(int j = i*i; j < n; j += i) bitmap[j] = false;
        }
    }
    return res;
}

int countPrimes_carray(int n) {  
    int res = 0; 
    bool* bitmap = new bool[n];
    memset(bitmap, true, sizeof(bool) * n);
    for (int i = 2; i<n; ++i){

        if(bitmap[i])++res;
        if(sqrt(n)>i)
        {
             for(int j = i*i; j < n; j += i) bitmap[j] = false;
        }
    }
    delete []bitmap;
    return res;
}

#include <chrono>
#include <iostream>

using namespace std;

void test(const char* description, int (*fn)(int))
{
    using clock = std::chrono::steady_clock;
    using ms = std::chrono::milliseconds;

    auto start = clock::now();

    int a;
    for(int i=0; i<9; ++i)
        a = countPrimes_vector(8000000); 

    auto end = clock::now();
    auto diff = std::chrono::duration_cast<ms>(end - start);

    std::cout << "time for " << description << " = " << diff.count() << "ms\n";
}

int main()
{
    test("carray", countPrimes_carray);
    test("vector", countPrimes_vector);
}

라이브 데모 : http://ideone.com/0Y9gQx

time for carray = 2251ms
time for vector = 2254ms

일부 실행에서는 carray가 1-2ms 더 느 렸습니다. 다시 말하지만 공유 리소스에 대한 샘플이 충분하지 않습니다.

--- 편집하다 ---

주요 의견에서 "최적화가 차이를 만드는 이유"를 묻습니다.

std::vector<bool> v = { 1, 2, 3 };
bool b[] = { 1, 2, 3 };

3 개의 요소로 구성된 두 개의 "배열"이 있으므로 다음을 고려하십시오.

v[10]; // illegal!
b[10]; // illegal!

STL의 디버그 버전은 종종 런타임 (그리고 일부 시나리오에서는 컴파일 타임) 중에이를 포착 할 수 있습니다. 어레이 액세스로 인해 잘못된 데이터 또는 충돌이 발생할 수 있습니다.

또한 STL은 같은 것에 대한 많은 작은 멤버 함수 호출을 사용하여 구현 되며 클래스 size()이기 때문에 실제로 함수 호출 ( )을 통해 파사드됩니다 .vector[]operator[]

컴파일러는 이들 중 많은 것을 제거 할 수 있지만 이것이 최적화입니다. 최적화하지 않으면

std::vector<int> v;
v[10];

대략 다음과 같이합니다.

int* data() { return M_.data_; }

v.operator[](size_t idx = 10) {
    if (idx >= this->size()) {
        raise exception("invalid [] access");
    }
    return *(data() + idx);
}

데이터가 "inlinable"기능이기는하지만 디버깅을 더 쉽게하기 위해 최적화되지 않은 코드는 그대로 둡니다. 최적화를 통해 빌드 할 때 컴파일러는 이러한 함수의 구현이 너무 사소하여 호출 사이트로 구현을 대체 할 수 있음을 인식하고 위의 모든 작업을보다 배열 액세스와 같은 작업으로 빠르게 단순화합니다.

예를 들어, 위의 경우 먼저 다음과 같이 줄일 operator[]수 있습니다.

v.operator[](size_t idx = 10) {
    if (idx >= this->size()) {
        raise exception("invalid [] access");
    }
    return *(M_.data_ + idx);
}

디버깅하지 않고 컴파일하면 경계 검사가 제거되기 때문에

v.operator[](size_t idx = 10) {
    return *(M_.data_ + idx);
}

이제 인라이너가

x = v[1];

...에

x = *(v.M_.data_ + 1); // comparable to v.M_.data_[1];

이 인 작은 형벌. c-array는 메모리의 데이터 블록과 블록을 가리키는 레지스터에 맞는 단일 지역 변수를 포함하며 참조는 다음과 직접 관련됩니다.

그러나 벡터를 사용하면 데이터, 크기 및 용량 변수에 대한 포인터 인 벡터 객체가 있습니다.

vector<T>  // pseudo code
{
    T* ptr;
    size_t size;
    size_t capacity;
}

기계 명령어를 세는 경우 벡터에는 초기화 및 관리 할 3 개의 변수가 있습니다.

당신이 쓸 때

x = v[1];

위의 벡터 근사치가 주어지면 다음과 같은 라인을 따라 무언가를 말하고 있습니다.

T* ptr = v.data();
x = ptr[1];

그러나 컴파일러는 일반적으로 최적화를 통해 빌드 할 때 루프 앞의 첫 번째 줄을 수행 할 수 있다는 것을 인식 할 수있을만큼 똑똑하지만 레지스터 비용이 많이 드는 경향이 있습니다.

T* ptr = v.data(); // in debug, function call, otherwise inlined.
for ... {
    x = ptr[1];
}

따라서 테스트 기능을 반복하거나 최신 프로세서에서 1 나노초 또는 2 시간의 추가 벽 시간당 몇 가지 더 많은 기계 명령을보고있을 것입니다.