4

我正在编写一些需要尽可能快的代码，而不会占用我所有的研究时间（换句话说，没有手动优化的汇编）。

我的系统主要由一堆 3D 点（原子系统）组成，因此我编写的代码进行了大量的距离比较、最近邻搜索以及其他类型的排序和比较。这些是大型、百万或十亿点系统，嵌套 for 循环的天真 O(n^2) 不会削减它。

对我来说，只使用 astd::vector来保存点坐标是最简单的。起初我认为它可能会和数组一样快，所以太好了！然而，这个问题（Is std::vector so much faster than plain arrays?）让我有一种非常不安的感觉。我没有时间使用数组和向量编写所有代码并对其进行基准测试，因此我现在需要做出正确的决定。

我确信知道背后详细实现std::vector的人可以使用这些功能而速度损失很小。但是，我主要用 C 编程，所以我不知道std::vector幕后在做什么，我不知道push_back每次调用它时是否要执行一些新的内存分配，或者我可能会陷入什么其他“陷阱”这样做使我的代码非常慢。

数组很简单；我确切地知道什么时候分配内存，我所有算法的顺序是什么，等等。没有我可能不得不忍受的黑盒未知数。然而，我经常看到有人批评在互联网上使用数组而不是向量，我不禁想知道我是否遗漏了更多信息。

编辑：为了澄清，有人问“你为什么要用数组或向量来操作这么大的数据集”？好吧，最终，一切都存储在内存中，因此您需要选择一些底层抽象。例如，我使用 kd-trees 来保存 3D 点，但即便如此，kd-tree 也需要从数组或向量中构建。

另外，我并不是说编译器不能优化（我知道最好的编译器在很多情况下可以胜过人类），只是说它们的优化不能比它们的约束允许的更好，而且我可能只是因为我的无知而无意中引入了约束向量的实现。

4

7 回答 7

2

一切都取决于你如何实现你的算法。std::vector是这样一个通用的容器概念，它给了我们灵活性，但让我们有自由和责任去刻意构建算法的实现。我们将观察到的大部分效率开销std::vector来自于复制。std::vector提供了一个构造函数，可以让你用值 X 初始化 N 个元素，当你使用它时，向量和数组一样快。

我做了一个测试与这里std::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);
    }
}
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));
    }
}

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

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

    return 0;
}

以下是结果（在 Ubuntu amd64 上使用 g++ -O3 编译）：

UseArray 在0.325秒
内完成 UseVector 在 1.23 秒内
完成 UseConstructor 在 0.866 秒
内完成 UseVectorPushBack 在 8.987 秒内完成
整个事情在 11.411 秒内完成

显然push_back这里不是一个好的选择，使用构造函数仍然比数组慢 2 倍。现在，为 Pixel 提供空副本 Tor：

Pixel(const Pixel&) {}

给我们以下结果：

UseArray 在0.331秒
内完成 UseVector 在 0.306 秒内
完成 UseConstructor 在 0 秒内
完成 UseVectorPushBack 在 2.714 秒内完成
整个事情在 3.352 秒内完成

总而言之：重新考虑您的算法，否则，可能会求助于 New[]/Delete[] 周围的自定义包装器。在任何情况下，STL 实现并没有因为某些未知原因而变慢，它只是按照您的要求执行；希望你知道得更好。在您刚开始使用向量的情况下，它们的行为可能会令人惊讶，例如以下代码：

class U{
    int i_;
public:
    U(){}
    U(int i) : i_(i) {cout << "consting " << i_ << endl;}
    U(const U& ot) : i_(ot.i_) {cout << "copying " << i_ << endl;}
};

int main(int argc, char** argv)
{   
    std::vector<U> arr(2,U(3));
    arr.resize(4);
    return 0;
}

结果：

构造 3

复制 3

复制 3

复制 548789016

复制 548789016

复制 3

复制 3

于 2013-04-13T21:13:37.970 回答
1

发明 STL，然后将其纳入 C++ 标准库的人，被骂得精明。甚至不要让自己想象一下，由于您对传统 C 数组的丰富知识，您可以超越他们。（如果您知道一些 Fortran，您将有机会）。

使用std::vector，您可以一次性分配所有内存，就像使用 C 数组一样。您也可以增量分配，就像使用 C 数组一样。您可以控制每次分配发生的时间，就像使用 C 数组一样。与C 数组不同，您也可以忘记这一切，让系统为您管理分配，如果这是您想要的。这都是绝对必要的基本功能。我不确定为什么有人会认为它丢失了。

说了这么多，如果您发现数组更容易理解，请使用数组。

于 2013-04-13T21:00:55.800 回答
1

我并不是真的建议您选择数组或向量，因为我认为它们可能不完全适合您的需求。

您需要能够有效地组织数据，以便查询不需要扫描整个内存范围来获取相关数据。因此，您希望将更有可能被选中的点彼此靠近地分组。

如果您的数据集是静态的，那么您可以离线进行排序，并使您的数组在应用程序启动时加载到内存中，并且向量或数组都可以工作（前提是您预先reserve调用vector，因为默认分配增长方案会在底层数组变满时将其大小加倍，并且您不希望仅将 16Gb 的内存用于 9Gb 的数据）。

但是，如果您的数据集是动态的，则很难使用向量或数组在您的集合中进行有效的插入。回想一下，数组中的每个插入都会创建一个位置的所有后继元素的移位。当然，索引，如您提到的 kd 树，将有助于避免对数组进行全扫描，但如果所选点分散在数组中，对内存和缓存的影响基本上是相同的。这种转变也意味着需要更新索引。

我的解决方案是在页面中切割数组（列表链接或数组索引）并将数据存储在页面中。这样，就可以将相关元素组合在一起，同时仍然保持页面内连续内存访问的速度。然后索引将引用一个页面和该页面中的偏移量。页面不会被自动填充，这就为插入相关元素留下了空间，或者使轮班操作变得非常便宜。

请注意，如果页面总是满的（最后一页除外），在插入的情况下，您仍然必须移动每一个页面，而如果您允许不完整的页面，您可以将移动限制为单个页面，如果该页面已满，请在其后插入一个新页面以包含补充元素。

需要记住的一些事项：

  • 数组和向量分配有上限，这取决于操作系统（这些限制可能不同）

在我的 32 位系统上，3D 点向量的最大允许分配约为 1.8 亿个条目，因此对于更大的数据集，必须找到不同的解决方案。当然，在 64 位操作系统上，这个数量可能要大得多（在 Windows 32 位上，一个进程的最大内存空间是 2Gb - 我认为他们在更高级的操作系统版本上添加了一些技巧来扩展这个数量）。诚然，对于像我这样的解决方案，内存将更加成问题。

  • 调整向量的大小需要分配堆的新大小，将元素从旧内存块复制到新内存块。

因此，如果只向序列中添加一个元素，则在调整大小期间将需要两倍的内存。这个问题可能不会出现普通数组，可以使用临时操作系统内存函数重新分配（realloc例如在 unices 上，但据我所知，该函数不能保证相同的内存块将被重用） . 如果使用将使用相同函数的自定义分配器，则向量中也可以避免该问题。

  • C++ 不对底层内存架构做任何假设。

向量和数组旨在表示分配器提供的连续内存块，并用接口包装该内存块以访问它。但是 C++ 不知道操作系统如何管理该内存。在大多数现代操作系统中，该内存实际上是按页面切割的，这些页面映射进出物理内存。所以我的解决方案是以某种方式在流程级别重现该机制。为了使分页高效，我们的页面必须适合操作系统页面，因此需要一些操作系统相关的代码。另一方面，对于基于向量或数组的解决方案，这根本不是问题。

因此，从本质上讲，我的答案是关注以有利于彼此靠近的聚类点的方式更新数据集的效率。它假设这样的聚类是可能的。如果不是这样，那么只需在数据集的末尾推送一个新点就可以了。

于 2013-04-13T21:55:12.467 回答
1

向量保证底层数据是内存中的一个连续块。保证这一点的唯一合理方法是将其实现为数组。

推送新元素时可能会发生内存重新分配，因为向量无法提前知道要添加多少元素。但是，当您提前知道时，您可以使用适当数量的条目调用reserve，以避免在添加它们时重新分配。

向量通常比数组更受欢迎，因为它们允许在使用.at(). 这意味着访问向量之外的索引不会像数组那样导致未定义的行为。然而，这种边界检查确实需要额外的 CPU 周期。当您使用[]-operator访问元素时，不会进行边界检查，访问速度应该与数组一样快。但是，当您的代码有错误时，这会导致未定义的行为。

于 2013-04-13T20:11:08.927 回答
0

对于向量和数组之间常见的操作（因此不是 push_back 或 pop_back，因为数组的大小是固定的），它们的执行完全相同，因为 - 按照规范 - 它们是相同的。

矢量访问方法是如此微不足道，以至于更简单的编译器优化将把它们消灭掉。如果您事先知道向量的大小，只需通过指定大小或调用来构造它resize，您将得到与使用new [].

如果您不知道大小，但您知道需要增长多少，只需调用reserve，并且您不会在 push_back 上受到任何惩罚，因为所有必需的内存都已分配。

无论如何，重定位并不是那么“愚蠢”：向量的容量和大小是两个截然不同的东西，容量通常会在耗尽时翻倍，因此大量重定位的频率越来越低。

此外，如果您了解有关大小的所有信息，并且您不需要动态内存并且想要相同的矢量接口，请考虑使用std::array.

于 2013-04-13T20:32:45.070 回答
0

虽然我不知道 std:vector 的确切实现，但大多数像这样的列表系统比数组慢，因为它们在调整大小时分配内存，通常是当前容量的两倍，尽管情况并非总是如此。

因此，如果向量包含 16 个项目并且您添加了另一个，则它需要另外 16 个项目的内存。由于向量在内存中是连续的，这意味着它将为 32 个项目分配一个实心内存块并更新向量。您可以通过构造 std:vector 来获得一些性能改进，其初始容量与您认为数据集的大小大致相同，尽管这并不总是一个容易得出的数字。

于 2013-04-13T20:14:15.153 回答
0

听起来你需要大量的 RAM，所以你不需要分页。我倾向于同意@Philipp 的回答，因为您真的很想确保它不会在后台重新分配

但

一棵需要重新平衡的树是怎么回事？你甚至在考虑编译器优化？

请参加如何优化软件的速成课程。我敢肯定你对 Big-O 了如指掌，但我敢打赌你习惯于忽略常数因素，对吧？它们可能会出现 2 到 3 个数量级的异常，做一些你从未认为代价高昂的事情。如果这转化为几天的计算时间，也许它会变得有趣。

并且没有编译器优化器可以为您解决这些问题。

如果你有学术倾向，这篇文章会更详细。

于 2013-04-14T00:36:41.250 回答