我一直认为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倍!这并不能证明“向量可能会慢几纳秒”的评论是正确的。

我使用的代码是:

#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中的发布模式。


在Visual c++中,#define _SECURE_SCL 0将UseVector减少了一半(减少到4秒)。在我看来,这真的是件大事。


当前回答

当我第一次看您的代码时,这很难说是一个公平的比较;我还以为你不是在比较苹果和苹果。所以我想,让构造函数和析构函数在所有测试中都被调用;然后比较。

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

这显然是减速的根源,因为vector使用复制构造函数从默认构造的对象初始化元素。

这意味着,以下伪操作顺序发生在向量的构造过程中:

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

所以默认像素保持未初始化,而其余的初始化使用默认像素的未初始化值。

与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实现都不会因为某些未知的原因而变慢,它只是完全按照你的要求去做;希望你能明白。

其他回答

好问题。我来这里是希望能找到一些简单的方法来加快矢量测试的速度。结果跟我想象的不太一样!

优化有帮助,但这还不够。通过优化,我仍然看到UseArray和UseVector之间的2X性能差异。有趣的是,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 -使用new[]代替malloc

我尝试在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 -删除重复的操作符[]调用

我还尝试摆脱三重运算符[]查找,并缓存对像素[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可以在创建向量时优化所有对象的结构。如果我们把像素改为:

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

没有什么不同。至少没有变慢。我认为这将具有类似于#2的性能,其中我使用了Pixel&引用。

结论

即使一些聪明的cookie找到了如何使vector循环和数组循环一样快的方法,这也不能说明std::vector的默认行为。编译器足够聪明,可以优化所有c++特性,并使STL容器像原始数组一样快。

底线是,当使用std::vector时,编译器无法优化掉无操作的默认构造函数调用。如果你使用普通的new[],它就能很好地优化它们。但不是std::vector。即使你可以重写你的代码,以消除构造函数调用,在这里的咒语:“编译器比你聪明。STL和普通c一样快,不用担心。”

我只是想提一下vector(和smart_ptr)只是原始数组(和原始指针)上的一个薄层。 实际上在连续存储器中向量的访问时间比数组快。 下面的代码显示了初始化和访问向量和数组的结果。

#include <boost/date_time/posix_time/posix_time.hpp>
#include <iostream>
#include <vector>
#define SIZE 20000
int main() {
    srand (time(NULL));
    vector<vector<int>> vector2d;
    vector2d.reserve(SIZE);
    int index(0);
    boost::posix_time::ptime start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        vector2d.push_back(vector<int>(SIZE));
    }
    boost::posix_time::ptime start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            vector2d[index][index]++;
        }
    }
    boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time();
    boost::posix_time::time_duration msdiff = end - start_total;
    cout << "Vector total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Vector access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 


    int index(0);
    int** raw2d = nullptr;
    raw2d = new int*[SIZE];
    start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        raw2d[i] = new int[SIZE];
    }
    start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            raw2d[index][index]++;
        }
    }
    end = boost::posix_time::microsec_clock::local_time();
    msdiff = end - start_total;
    cout << "Array total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Array access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 
    for (int i = 0; i < SIZE; i++) {
        delete [] raw2d[i];
    }
    return 0;
}

输出结果为:

    Vector total time: 925milliseconds.
    Vector access time: 4milliseconds.
    Array total time: 30milliseconds.
    Array access time: 21milliseconds.

所以如果使用得当,速度几乎是一样的。 (正如其他人提到的使用reserve()或resize())。

下面是vector中的push_back方法的工作原理:

vector在初始化时分配X个空间。 如下所述,它检查当前底层数组中是否有空间用于该项。 它复制push_back调用中的项。

调用push_back X项后:

vector将kX的空间重新分配到第二个数组中。 它将第一个数组的项复制到第二个数组。 丢弃第一个数组。 现在使用第二个数组作为存储,直到它达到kX项。

重复。如果你没有预留空间,它肯定会变慢。更重要的是,如果复制项目的成本很高,那么像这样的“push_back”会让你生吞活剥。

至于向量和数组的区别,我同意其他人的观点。在发布版中运行,打开优化,并放入更多的标志,这样微软的友好人员就不会为你而烦恼了。

还有一件事,如果你不需要调整大小,使用Boost.Array。

这是一个古老而流行的问题。

在这一点上,许多程序员将使用c++ 11。在c++ 11中,OP的代码对于UseArray或UseVector运行得同样快。

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

基本的问题是,当你的像素结构未初始化时,std::vector<T>::resize(size_t, T const&=T())接受一个默认构造的像素并复制它。编译器没有注意到它被要求复制未初始化的数据,所以它实际执行了复制。

在c++ 11中,std::vector<T>::resize有两个重载。第一个是std::vector<T>::resize(size_t),另一个是std::vector<T>::resize(size_t, T const&)。这意味着当调用resize而不带第二个参数时,它只是默认构造,而编译器足够聪明,可以意识到默认构造什么也不做,因此它跳过了缓冲区的传递。

(添加这两个重载是为了处理可移动、可构造和不可复制类型——处理未初始化数据时的性能提升是一个额外的好处)。

push_back解决方案还执行fencepost检查,这降低了它的速度,因此它仍然比malloc版本慢。

现场示例(我还用chrono::high_resolution_clock替换了计时器)。

注意,如果你有一个通常需要初始化的结构,但你想在增加缓冲区后处理它,你可以使用自定义std::vector分配器来做到这一点。如果你想把它移动到一个更正常的std::vector,我相信仔细使用allocator_traits和重写==可能会成功,但我不确定。

试试这个:

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

我得到了和数组几乎完全一样的性能。

The thing about vector is that it's a much more general tool than an array. And that means you have to consider how you use it. It can be used in a lot of different ways, providing functionality that an array doesn't even have. And if you use it "wrong" for your purpose, you incur a lot of overhead, but if you use it correctly, it is usually basically a zero-overhead data structure. In this case, the problem is that you separately initialized the vector (causing all elements to have their default ctor called), and then overwriting each element individually with the correct value. That is much harder for the compiler to optimize away than when you do the same thing with an array. Which is why the vector provides a constructor which lets you do exactly that: initialize N elements with value X.

当你使用它时,向量和数组一样快。

所以,你还没有打破性能神话。但是你已经证明了只有当你最优地使用向量时它才成立,这也是一个很好的观点。:)

好的一面是,它确实是最简单的用法,但却是最快的。如果您将我的代码片段(一行)与John Kugelman的答案进行对比,其中包含大量的调整和优化,但仍然不能完全消除性能差异,很明显,vector的设计非常巧妙。你不必费尽周折才能得到等于数组的速度。相反,您必须使用最简单的解决方案。