我却始终认为这是常规的智慧, std::vector "实现为一个数组,"blah blah blah。今天我关闭了测试它,和它看起来是不是这样︰

下面是一些测试结果︰

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可能要慢一些 nanosecs 的"意见。

然后我使用的代码︰

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

正在执行其错误或其他?或我有只 busted 此性能神话?

我使用Visual Studio 2005年发布模式.


Visual C++#define _SECURE_SCL 0 UseVector减少一半 (将它带到 4 秒)。这是真正的大,IMO。

2010-09-08 02:38:41
问题评论:

某些版本的向量,当您在调试模式下添加额外的说明检查您不访问数组的末尾之外,类似的东西。要获得真正的计时必须在发布模式下生成并启用优化。

很好的测量而不是相信您在 Internet 上听说过的索赔。

矢量作为一个数组来实现。这并不是"传统智慧",这是事实。您已经发现该vector是一般用途的可调整大小的数组。祝贺您。如同所有一般用途的工具,就可以拿出特殊的情况下是最优。这是为什么世故是对开始一个vector并考虑替代方案,如有必要。

lol,"到一个接收器引发脏盘子"和"引发到一个接收器脏盘子和检查是否他们没有破坏"的速度差异是什么?

在 VC2010 上至少似乎主要区别是该 malloc() 比 resize() 更快。计时从删除的内存分配、 编译与 _ITERATOR_DEBUG_LEVEL = = 0 和结果都是相同。

回答:

使用以下︰

g + +-O3 Time.cpp-我 < 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-我 < MyBoost >
。 /a.out
UseVector 在 2.216 秒内完成

仅略糟数组向量现在性能。IMO 这种差异并不显著,可能由一整套与测试无关的事情。

我也会考虑在内,则是不正确地初始化/Destroying UseArrray()方法中的像素对象如不调用任何构造函数/析构函数 (这可能不是问题,对于这个简单的类,但稍微更复杂 (ie 随指针或具有指针成员) 会导致问题。

@kizzx2︰ 您需要使用reserve()而不是resize()这为对象分配空间 (也就是说,更改向量容量) 但不创建对象 (即留向量的大小不变)。

您正在执行的 1 000 000 000 数组访问。时差是 0.333 秒。或每个数组访问 0.000000000333 的差别。假定的 2.33 g h z 处理器像我这样 0.7 指令管道阶段每个数组的访问。因此矢量看起来像使用访问每一个额外的指令。

在我看来,从-1 因为此答案试图给我隐藏的 c + + 的真正弱点︰ 初始化是笨拙,经常会不必要地效率。我喜欢 c + + 和我很高兴看到在 C + + 1x,要解决这些问题,但我们应 fess 最真实现状的批评。

@j_random_hacker︰ 不完全是我说的是什么?我认为我已非常清楚,只reserve更改矢量,不是其大小的容量。

好了,去想一想。没有大量的矢量方法中的异常相关才。添加/EHsc编译开关到清理的和assign()实际上现在胜过数组。Yay。

问得好。我就在这里应找到右上的执行速度矢量测试一些简单修复。问题解决得不很像我需要的 !

优化可帮助,但还不够。使用优化的我仍然能看到 2x UseArray 和 UseVector 之间的性能差异。有趣的是,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 使用新的]

我已尝试改为malloc() UseArray 中的new[]以便将构造的对象。并从单个字段分配更改为指定的像素实例。哦,和重内部循环变量命名为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 可以优化出的所有对象的构造创建向量时。如果我们更改为像素,则会发生什么︰

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

结果︰ 有关 10%更快。比数组仍然较慢。Hm。

# ./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 容器。

底线是,编译器就无法进行优化以去除 no op 默认构造函数调用时使用std::vector如果您使用普通new[]它优化掉的只是罚款。但不是能与std::vector即使您可以重新编写代码以消除构造函数调用,这里要诀换飞:"编译器是比您更明智。STL 是的纯 c。 不要担心它一样快。

再次感谢您实际运行的代码。有时很容易获得原因不 bashed,当有人试图挑战流行观点。

"这么多编译器被足够智能,优化出所有 C + + 等,并使 STL 容器作为原始数组快。"很好的注释。我已经从理论上讲,这"编译器是智能的"只是神话-c + + 分析是极难,并且编译器只需一台计算机。

我不知道。当然,他是能够降低阵列测试,但是他没有加速的媒介之一。在中编辑上面我构造函数从像素,使其简单的结构,而且它仍运行缓慢。这就是坏消息的任何用户使用简单的类型,如vector<int>.

我想我真的无法 upvote 您的答案两次。智能的观点,尝试 (即使没有真正所起的作用),我不能甚至想到的 !

只是想记 (即 insanely 是复杂的是的)分析c + + 的复杂性与优化的质量无关。后者通常发生在阶段分析结果已经为更低级别的表示形式转换很多次的地方。

公平地说,不能为我将调用 malloc 版本比较对 C 实现,一个 c + + 实现。malloc 不会创建对象-它只分配原始内存。然后为对象将该内存,不用的情况下调用的构造函数 (可能的无效-我会的到语言律师) 较差的 c + +。

尽管如此,只需更改对 mallocnew Pixel[dimensions*dimensions]和免费的delete [] pixels不会使您具有的像素的简单实现太大差异。下面是我框 (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 现在节拍的原始数组。

它将显示分配通过 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),然后覆盖的每个元素分别为正确的值。这就是编译器优化掉比当您做与数组相同的要困难得多。因此,矢量提供一个构造函数,这样就可以实现此目的︰ 初始化值X N个元素.

并且,使用时,矢量数组一样快。

这样不对,没有 busted 性能误区。但有显示,才真正是否使用向量的理想,这也是一个很好的点。:)

好的一面,它实际上是证明是最快的最简单用法。如果对比我的代码段 (单线) John Kugelman 的答案,包含堆和堆的调整和优化,仍没有完全消除的性能差异,则相当清楚毕竟非常巧妙而设计的vector您无需通过圈来获得速度等于数组跳转。相反,您必须使用最简单的可能解决方案。

我仍然怀疑这是否是一个公平的比较。如果您正在消除内部循环则是等效数组构造一个单个像素对象然后位块,跨整个数组。

使用new[]执行同一默认构造函数是vector.resize() ,但却要快得多。new[] + 内部循环应该是相同的速度为vector.resize() + 内层循环,但它不是,是几乎两倍速度一样快。

@John︰ 它是一个公平的比较。在原始的代码中,该数组分配使用malloc未初始化或构造任何内容,因此它有效的单通道算法只是喜欢我vector的示例。并与new[]回答显然是,两者都需要两个周期,但new[]的情况下,编译器能够优化该额外的开销,它不在vector的情况下做到这一点。但我看不到为何有趣的是在不理想的情况下会发生什么情况。如果您关心的性能时,您不像这样编写代码。

@John︰ 有趣的评论。如果我想位块跨整个数组,我猜测数组再次是最佳的解决方案,因为我不能给我一块 contingous 内存而不浪费时间没用的调用构造函数的vector::resize()

@kizzx2: 是和否。在 c + + 通常也初始化数组。在 C 中,而使用malloc哪些不能执行初始化,但是,不会使用 c + + 中非 POD 类型。因此,在一般情况下,c + + 数组应该是同样糟糕。可能的问题是,如果您打算经常执行此平面闪不会重复使用同一个数组向量?并且,如果做到这一点,然后只需付费"无用构造函数"的成本一次,在最开始。毕竟,实际平面闪是一样快。

当我第一次看代码;,它是几乎不是一个公平的比较我确实认为没有比较苹果与苹果。因此我认为,我们获取构造函数和析构函数被调用的所有测试;然后进行比较。

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 有一切在头中,因此它应已能了解一切所需的编译器。

我的想法是它处于循环方式 initialises 的默认构造函数的所有值。因此我执行一个测试︰

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
Copy Constructed: %i
", 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保持不 initialised,而其余程序初始化的默认Pixel非 initialised值。

相比于使用New[]替代的情况 /Delete[]:

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

    printf("Default Constructed: %i
Copy Constructed:%i
", Tester::count, Tester::count2);

    delete[] myvec;

    return 0;
}

Default Constructed: 300
Copy Constructed: 0

它们是所有留下为其取消 initialised 的值,而双迭代序列。

有了这些信息,如何可以我们测试它?让我们尝试覆盖的隐式复制构造函数。

Pixel(const Pixel&) {}

和结果?

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

在摘要,因此,如果您要经常做数百个向量︰重新思考您的算法.

在任何情况下,不慢STL实现是由于某种未知的原因,只是恰好在要求;希望更好地了解。

判断从有趣我们 (您和我和其他聪明的人在此处) 有,STL 实现"希望"实际上是一个相当苛刻︰ P 从根本上说,我们可以夸大并结束它希望我已阅读并分析所有其源代码。是否仍要︰ P

Awsome !在 VS 2013 这进行矢量比数组快。尽管似乎性能关键系统需要测试 STL 大量能够有效地使用它。

请输入您的翻译

Is std::vector so much slower than plain arrays?

确认取消