std :: vector가 일반 배열보다 훨씬 느립니까? {

저는 항상 std::vector“배열로 구현되는” 일반적인 지혜라고 생각했습니다 . 오늘 나는 그것을 내려 가서 테스트했지만 그렇지 않은 것 같습니다.

테스트 결과는 다음과 같습니다.

UseArray completed in 2.619 seconds
UseVector completed in 9.284 seconds
UseVectorPushBack completed in 14.669 seconds
The whole thing completed in 26.591 seconds

약 3-4 배 느립니다! ” vector몇 나노초 동안 속도가 느려질 수있다”라는 의견을 실제로 정당화하지는 않는다 .

그리고 내가 사용한 코드 :

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
    public:
        TestTimer(const std::string & name) : name(name),
            start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
        {
        }

        ~TestTimer()
        {
            using namespace std;
            using namespace boost;

            posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
            posix_time::time_duration d = now - start;

            cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
                " seconds" << endl;
        }

    private:
        std::string name;
        boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector()
{
    TestTimer t("UseVector");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPushBack");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        free(pixels);
    }
}

int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}

내가 잘못하거나 뭔가를하고 있습니까? 아니면 방금이 공연 신화를 파괴 했습니까?

Visual Studio 2005 에서 릴리스 모드를 사용하고 있습니다.


에서는 카메라 C ++ , #define _SECURE_SCL 0감소 UseVector절반 (4 초로 낮추기). 이것은 정말 거대합니다.



답변

다음을 사용하여 :

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray 2.196 초에 완료
4.412 초에 완료 UseVector
8.017 초에 완료 UseVectorPushBack
모든 것은이 14.626 초에 완료

따라서 배열은 벡터보다 두 배 빠릅니다.

그러나 코드를보다 자세히 살펴본 후에는 이것이 예상됩니다. 벡터를 두 번, 배열을 한 번만 실행하면 참고 : resize()벡터를 사용하면 메모리를 할당 할뿐만 아니라 벡터를 통해 실행하고 각 멤버에서 생성자를 호출합니다.

벡터가 각 객체를 한 번만 초기화하도록 코드를 약간 다시 정렬합니다.

 std::vector<Pixel>  pixels(dimensions * dimensions, Pixel(255,0,0));

이제 동일한 타이밍을 다시 수행하십시오.

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector가 2.216 초 안에 완료되었습니다.

벡터는 이제 어레이보다 약간 나빠질뿐입니다. IMO는이 차이가 중요하지 않으며 테스트와 관련되지 않은 많은 것들로 인해 발생할 수 있습니다.

또한 UseArrray()생성자 / 소멸자가 호출되지 않았으므로 메소드 에서 Pixel 객체를 올바르게 초기화 / 파괴하지 않는다는 것을 고려할 것입니다 (이 간단한 클래스에는 문제가되지 않지만 약간 더 복잡한 것은 (예 : 포인터 또는 멤버) 포인터가 있으면 문제가 발생합니다.


답변

좋은 질문입니다. 나는 벡터 테스트를 빠르게 할 수있는 간단한 수정을 기대하기 위해 여기에왔다. 예상대로 작동하지 않았습니다!

최적화가 도움이되지만 충분하지 않습니다. 최적화를 통해 UseArray와 UseVector의 성능 차이는 여전히 2 배입니다. 흥미롭게도 UseVector는 최적화없이 UseVectorPushBack보다 상당히 느 렸습니다.

# g++ -Wall -Wextra -pedantic -o vector vector.cpp
# ./vector
UseArray completed in 20.68 seconds
UseVector completed in 120.509 seconds
UseVectorPushBack completed in 37.654 seconds
The whole thing completed in 178.845 seconds
# g++ -Wall -Wextra -pedantic -O3 -o vector vector.cpp
# ./vector
UseArray completed in 3.09 seconds
UseVector completed in 6.09 seconds
UseVectorPushBack completed in 9.847 seconds
The whole thing completed in 19.028 seconds

아이디어 # 1-malloc 대신 new [] 사용

객체가 생성되도록 UseArray로 변경 malloc()을 시도했습니다 new[]. 개별 필드 할당에서 Pixel 인스턴스 할당으로 변경 내부 루프 변수의 이름을로 바꿉니다 j.

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        // Same speed as malloc().
        Pixel * pixels = new Pixel[dimension * dimension];

        for(int j = 0 ; j < dimension * dimension; ++j)
            pixels[j] = Pixel(255, 0, 0);

        delete[] pixels;
    }
}

놀랍게도 (나에게), 그러한 변화들 중 어느 것도 변화를 일으키지 않았습니다. new[]기본적으로 변경되어 모든 픽셀이 구성되는 것은 아닙니다 . gcc는를 사용할 때 기본 생성자 호출을 최적화 할 수 new[]있지만 사용할 때는 최적화 하지 않는 것 같습니다 vector.

아이디어 # 2-반복되는 연산자 [] 호출 제거

또한 트리플 operator[]조회를 제거 하고에 대한 참조를 캐시 하려고 했습니다 pixels[j]. 실제로 UseVector 속도가 느려졌습니다! 죄송합니다.

for(int j = 0; j < dimension * dimension; ++j)
{
    // Slower than accessing pixels[j] three times.
    Pixel &pixel = pixels[j];
    pixel.r = 255;
    pixel.g = 0;
    pixel.b = 0;
}

# ./vector 
UseArray completed in 3.226 seconds
UseVector completed in 7.54 seconds
UseVectorPushBack completed in 9.859 seconds
The whole thing completed in 20.626 seconds

아이디어 # 3-생성자 제거

생성자를 완전히 제거하는 것은 어떻습니까? 그러면 gcc는 벡터가 생성 될 때 모든 객체의 구성을 최적화 할 수 있습니다. Pixel을 다음과 같이 변경하면 어떻게됩니까?

struct Pixel
{
    unsigned char r, g, b;
};

결과 : 약 10 % 더 빠릅니다. 배열보다 여전히 느립니다. 흠.

# ./vector 
UseArray completed in 3.239 seconds
UseVector completed in 5.567 seconds

아이디어 # 4-루프 인덱스 대신 반복자를 사용

어떻게 사용에 대한 vector<Pixel>::iterator대신 루프 인덱스의?

for (std::vector<Pixel>::iterator j = pixels.begin(); j != pixels.end(); ++j)
{
    j->r = 255;
    j->g = 0;
    j->b = 0;
}

결과:

# ./vector 
UseArray completed in 3.264 seconds
UseVector completed in 5.443 seconds

아뇨, 다르지 않습니다. 적어도 느리지 않습니다. 나는 이것이 Pixel&참조를 사용한 # 2와 비슷한 성능을 가질 것이라고 생각했다 .

결론

일부 스마트 쿠키는 벡터를 배열만큼 빠르게 루프하는 방법을 알아 내더라도의 기본 동작을 잘 설명하지 못합니다 std::vector. 컴파일러는 모든 C ++를 최적화하고 STL 컨테이너를 원시 배열만큼 빠르게 만들 수있을만큼 똑똑합니다.

결론은 컴파일러가를 사용할 때 no-op 기본 생성자 호출을 최적화 할 수 없다는 것 std::vector입니다. 일반을 사용하면 잘 new[]최적화됩니다. 그러나와는 아닙니다 std::vector. 코드를 다시 작성하여 만트라에 직면하는 생성자 호출을 제거 할 수 있다고해도 “컴파일러는 당신보다 똑똑합니다. STL은 평범한 C만큼 빠릅니다. 걱정하지 마십시오.”


답변

이것은 오래되었지만 인기있는 질문입니다.

이 시점에서 많은 프로그래머들이 C ++ 11에서 작업 할 것입니다. 그리고 C ++ 11에서 작성된 OP 코드는 UseArrayor에 대해 동일하게 빠르게 실행됩니다 UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

근본적인 문제는 동안이었다 Pixel구조가 초기화되지 않은 한, std::vector<T>::resize( size_t, T const&=T() )기본 건설 소요 Pixel복사합니다 . 컴파일러는 초기화되지 않은 데이터를 복사하라는 요청을받지 않았으므로 실제로 복사를 수행했습니다.

C ++ 11 std::vector<T>::resize에는 두 가지 과부하가 있습니다. 첫 번째는 std::vector<T>::resize(size_t)이고 다른 하나는 std::vector<T>::resize(size_t, T const&)입니다. 이것은 resize두 번째 인수없이 호출 할 때 단순히 기본 구성이며 컴파일러는 기본 구성이 아무 것도 수행하지 않는다는 것을 인식 할 수있을 정도로 똑똑하므로 버퍼를 통과하지 않습니다.

(이동식, 구성 가능 및 복사 불가능한 유형을 처리하기 위해 추가 된 두 개의 과부하-초기화되지 않은 데이터 작업시 성능 향상은 보너스입니다).

push_back솔루션은 펜스 포스트 검사도 수행하므로 속도가 느려지므로 malloc버전 보다 느립니다 .

라이브 예 (타이머를로 교체했습니다 chrono::high_resolution_clock).

일반적으로 초기화가 필요한 구조가 있지만 버퍼를 확장 한 후에 처리하려는 경우 사용자 지정 std::vector할당기로이 작업을 수행 할 수 있습니다 . 그런 다음 더 정상적인 것으로 옮기려면 std::vector신중하게 사용 allocator_traits하고 재정의하면 ==이를 벗어날 수 있다고 확신하지만 확실하지 않습니다.


답변

공정하게 말하면 malloc 버전이라고 부르는 것처럼 C ++ 구현과 C 구현을 비교할 수 없습니다. malloc은 객체를 생성하지 않습니다-원시 메모리 만 할당합니다. 그런 다음 생성자를 호출하지 않고 해당 메모리를 객체로 취급한다는 것은 C ++이 좋지 않습니다 (아마도 유효하지 않습니다-언어 변호사에게 맡길 것입니다).

즉, malloc을 new Pixel[dimensions*dimensions]무료로 변경 하고 무료로 변경하는 delete [] pixels것은 간단한 Pixel 구현과 크게 다르지 않습니다. 내 상자의 결과는 다음과 같습니다 (E6600, 64 비트).

UseArray completed in 0.269 seconds
UseVector completed in 1.665 seconds
UseVectorPushBack completed in 7.309 seconds
The whole thing completed in 9.244 seconds

그러나 약간의 변화로 테이블이 바뀌 었습니다.

Pixel.h

struct Pixel
{
    Pixel();
    Pixel(unsigned char r, unsigned char g, unsigned char b);

    unsigned char r, g, b;
};

Pixel.cc

#include "Pixel.h"

Pixel::Pixel() {}
Pixel::Pixel(unsigned char r, unsigned char g, unsigned char b)
  : r(r), g(g), b(b) {}

main.cc

#include "Pixel.h"
[rest of test harness without class Pixel]
[UseArray now uses new/delete not malloc/free]

이 방법으로 컴파일 :

$ g++ -O3 -c -o Pixel.o Pixel.cc
$ g++ -O3 -c -o main.o main.cc
$ g++ -o main main.o Pixel.o

우리는 매우 다른 결과를 얻습니다.

UseArray completed in 2.78 seconds
UseVector completed in 1.651 seconds
UseVectorPushBack completed in 7.826 seconds
The whole thing completed in 12.258 seconds

std :: vector는 Pixel에 대해 인라인되지 않은 생성자를 사용하여 원시 배열보다 우선합니다.

std :: vector 및 std : allocator를 통한 할당의 복잡성이 너무 단순하여 효과적으로 최적화되지 않는 것으로 보입니다 new Pixel[n]. 그러나 루프 외부로 이동하여 벡터 / 배열을 한 번 생성하기 위해 몇 가지 테스트 함수를 조정하여 벡터 액세스가 아닌 할당에 문제가 있음을 알 수 있습니다.

void UseVector()
{
    TestTimer t("UseVector");

    int dimension = 999;
    std::vector<Pixel> pixels;
    pixels.resize(dimension * dimension);

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseArray()
{
    TestTimer t("UseArray");

    int dimension = 999;
    Pixel * pixels = new Pixel[dimension * dimension];

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
    delete [] pixels;
}

결과는 다음과 같습니다.

UseArray completed in 0.254 seconds
UseVector completed in 0.249 seconds
UseVectorPushBack completed in 7.298 seconds
The whole thing completed in 7.802 seconds

이것으로부터 배울 수있는 것은 std :: vector는 액세스를 위해 원시 배열과 비교할 수 있지만 벡터 / 배열을 여러 번 작성하고 삭제해야하는 경우 복잡한 객체를 작성하면 간단한 배열을 작성하는 데 더 많은 시간이 소요됩니다 요소의 생성자가 인라인되지 않은 경우 나는 이것이 매우 놀라운 것이라고 생각하지 않습니다.


답변

이것으로 시도하십시오 :

void UseVectorCtor()
{
    TestTimer t("UseConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));
    }
}

배열과 거의 동일한 성능을 얻습니다.

중요한 것은 vector배열보다 훨씬 일반적인 도구라는 것입니다. 그리고 그것은 당신이 그것을 어떻게 사용 하는지 고려해야한다는 것을 의미 합니다. 어레이에는없는 기능을 제공하여 다양한 방식으로 사용될 수 있습니다. 목적에 “잘못”사용하면 많은 오버 헤드가 발생하지만 올바르게 사용하면 기본적으로 오버 헤드가없는 데이터 구조입니다. 이 경우 문제는 벡터를 개별적으로 초기화 한 후 (모든 요소가 기본 ctor를 호출하도록 함) 정확한 값으로 각 요소를 개별적으로 덮어 쓰는 것입니다. 배열에서 같은 일을 할 때보 다 컴파일러가 최적화하기가 훨씬 어렵습니다. 이것이 바로 벡터가 생성자를 제공하는 이유입니다.NX.

그리고 그것을 사용할 때 벡터는 배열만큼 빠릅니다.

그래서, 당신은 성능 신화를 파열시키지 않았습니다. 그러나 벡터를 최적으로 사용하는 경우에만 해당되는 것으로 나타났습니다. 🙂

밝은면에서는 실제로 가장 간단한 사용법이 가장 빠릅니다. 내 코드 스 니펫 (한 줄)을 John Kugelman의 답변과 비교하면 힙과 힙의 조정 및 최적화가 포함되어 성능 차이가 여전히 제거되지는 않지만 결국에는 vector영리하게 디자인 된 것이 분명 합니다. 어레이와 동일한 속도를 얻기 위해 후프를 뛰어 넘을 필요가 없습니다. 반대로 가장 간단한 솔루션을 사용해야합니다.


답변

내가 당신의 코드를 처음 보았을 때 그것은 공정한 비교가 아니 었습니다. 나는 당신이 사과와 사과를 비교하지 않았다고 생각했습니다. 그래서 모든 테스트에서 생성자와 소멸자가 호출되도록했습니다. 그런 다음 비교하십시오.

const size_t dimension = 1000;

void UseArray() {
    TestTimer t("UseArray");
    for(size_t j = 0; j < dimension; ++j) {
        Pixel* pixels = new Pixel[dimension * dimension];
        for(size_t i = 0 ; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
        delete[] pixels;
    }
}

void UseVector() {
    TestTimer t("UseVector");
    for(size_t j = 0; j < dimension; ++j) {
        std::vector<Pixel> pixels(dimension * dimension);
        for(size_t i = 0; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
    }
}

int main() {
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();

    return 0;
}

내 생각은이 설정을 사용하면 정확히 동일 해야한다는 것 입니다. 내가 틀렸다는 것이 밝혀졌다.

UseArray completed in 3.06 seconds
UseVector completed in 4.087 seconds
The whole thing completed in 10.14 seconds

그렇다면이 30 %의 성능 손실이 발생한 이유는 무엇입니까? STL에는 헤더에 모든 것이 포함되어 있으므로 컴파일러가 필요한 모든 것을 이해할 수 있어야합니다.

내 생각은 루프가 모든 값을 기본 생성자로 초기화하는 방법에 있다는 것입니다. 그래서 테스트를 수행했습니다.

class Tester {
public:
    static int count;
    static int count2;
    Tester() { count++; }
    Tester(const Tester&) { count2++; }
};
int Tester::count = 0;
int Tester::count2 = 0;

int main() {
    std::vector<Tester> myvec(300);
    printf("Default Constructed: %i\nCopy Constructed: %i\n", Tester::count, Tester::count2);

    return 0;
}

결과는 내가 의심 한 것입니다.

Default Constructed: 1
Copy Constructed: 300

이것은 벡터가 복사 생성자를 사용하여 기본 생성 된 객체에서 요소를 초기화한다는 사실의 감속 원인입니다.

이는 벡터를 구성하는 동안 다음 의사 연산 순서가 발생 함을 의미합니다.

Pixel pixel;
for (auto i = 0; i < N; ++i) vector[i] = pixel;

컴파일러에 의해 작성된 암시 적 복사 생성자로 인해 다음과 같이 확장됩니다.

Pixel pixel;
for (auto i = 0; i < N; ++i) {
    vector[i].r = pixel.r;
    vector[i].g = pixel.g;
    vector[i].b = pixel.b;
}

따라서 기본값 Pixel은 초기화되지 않은 상태로 유지되고 나머지 기본값 Pixel초기화되지 않은으로 초기화 됩니다.

New[]/로 대체 상황과 비교 Delete[]:

int main() {
    Tester* myvec = new Tester[300];

    printf("Default Constructed: %i\nCopy Constructed:%i\n", Tester::count, Tester::count2);

    delete[] myvec;

    return 0;
}

Default Constructed: 300
Copy Constructed: 0

그것들은 모두 초기화되지 않은 값으로 남겨졌으며 시퀀스에 대한 이중 반복이 없습니다.

이 정보로 무장하면 어떻게 테스트 할 수 있습니까? 암시 적 복사 생성자를 덮어 쓰겠습니다.

Pixel(const Pixel&) {}

그리고 결과는?

UseArray completed in 2.617 seconds
UseVector completed in 2.682 seconds
The whole thing completed in 5.301 seconds

요약하면 수백 개의 벡터를 매우 자주 만드는 경우 알고리즘을 다시 생각하십시오 .

어쨌든 STL 구현은 알려지지 않은 이유로 느리게 진행되지 않으며 요청한 내용 만 수행합니다. 더 잘 알기를 바라고 있습니다.


답변

확인 된 반복자를 비활성화 하고 릴리스 모드에서 빌드하십시오. 성능 차이가 크지 않아야합니다.