std :: vector比普通数组慢得多吗？

Question

我一直认为这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中使用Release模式.

---

在Visual C++中,#define _SECURE_SCL 0减少UseVector一半(将其降低到4秒).这真是巨大的,IMO.

Answer 1

使用以下内容:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray
在2.196秒
内完成UseVector 在4.412秒内完成UseVectorPushBack 在8.017秒内完成
整件事在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这种差异是微不足道的,可能是由一大堆与测试无关的事情引起的.

我还会考虑到你没有正确地初始化/销毁方法中的Pixel对象,UseArrray()因为没有调用构造函数/析构函数(这可能不是这个简单类的问题,但是任何稍微复杂的东西(即指针或成员)用指针)会引起问题.

Answer 2

好问题.我来到这里期待找到一些简单的修复,可以加快矢量测试的速度.这没有像我预期的那样成功!

优化有所帮助,但还不够.通过优化,我仍然看到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 - 使用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 - 删除重复的operator []调用

我还试图摆脱三重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

不,没有什么不同.至少它并不慢.我认为这会有类似#2的性能,我使用了一个Pixel&参考.

结论

即使一些智能cookie计算出如何使向量循环与数组一样快,这也不能说明默认行为std::vector.因为编译器足够聪明,可以优化所有C++,并使STL容器与原始数组一样快.

底线是编译器在使用时无法优化无操作默认构造函数调用std::vector.如果你使用普通的new[]话就可以优化它们.但不是std::vector.即使你可以重写你的代码来消除面对这里的咒语的构造函数调用:"编译器比你聪明.STL和普通的C一样快.不要担心它."

Answer 3

这是一个古老而又受欢迎的问题.

在这一点上,许多程序员将使用C++ 11.在C++ 11中,OP编写的代码运行速度相同UseArray或者为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解决方案还执行fencepost检查,这会减慢它,因此它仍然比malloc版本慢.

实例(我也更换了计时器chrono::high_resolution_clock).

请注意,如果您的结构通常需要初始化,但是您希望在增长缓冲区后处理它,则可以使用自定义std::vector分配器执行此操作.如果你想把它变成一个更正常的std::vector,我相信小心使用allocator_traits和压倒==可能会把它拉下来,但我不确定.

Answer 4

公平地说,您无法将C++实现与C实现进行比较,因为我将其称为malloc版本.malloc不会创建对象 - 它只分配原始内存.然后你将内存视为对象而不调用构造函数是可怜的C++(可能无效 - 我会把它留给语言律师).

也就是说,简单地将malloc更改为new Pixel[dimensions*dimensions]free 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

使用Pixel的非内联构造函数,std :: vector现在胜过原始数组.

看起来通过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

我们可以从中学到的是,性病::矢量相当于原始阵列进行访问,但如果你需要创建和删除矢量/阵列多次,创建一个复杂的对象将是更费时,创建一个简单的数组当元素的构造函数没有内联时.我不认为这是非常令人惊讶的.

Answer 5

试试这个:

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毕竟设计得非常巧妙.你不必跳过箍来获得等于阵列的速度.相反,您必须使用最简单的解决方案.

Answer 6

当我第一次看你的代码时,这不是一个公平的比较; 我当然认为你不是在比较苹果和苹果.所以我想,让我们在所有测试中调用构造函数和析构函数; 然后比较.

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实现并不慢,它只是完全按照你的要求执行; 希望你更清楚.

Answer 7

尝试禁用已检查的迭代器并在发布模式下构建.你不应该看到很多性能差异.