大型矢量空间高效的C++矢量分配器？

我正在使用一些C++代码来实现一个使用很多小块内存（gSpan的相对值，但并不重要）的图算法。代码以C++实现，并使用std :: vectors存储许多小元素（每个元素大小为64字节）。但是，我在比原作者更大的数据集上使用这个数据集，而且我的内存不足。大型矢量空间高效的C++矢量分配器？

它的出现，但是，我跑出来的内存过早。不成？我怀疑这是因为std :: vectors在每次需要更多内存时都尝试增加大小，并且载体坚持连续内存。我有8GB的内存和18GB的交换，但是当std :: bad_alloc被抛出时，我只使用6.5GB驻留和〜8GB虚拟。我抓住了bad_alloc的调用和打印出来的矢量大小和这里就是我看到：

size: 536870912 
capacity: 536870912 
maxsize: 1152921504606846975 
terminate called after throwing an instance of 'std::bad_alloc' 
    what(): std::bad_alloc

因此，很明显，我们已经打了载体的最大规模和库试图分配更多，失败。

所以我的问题是：

上午我在假设正确的问题是什么？
什么是解决方案（除了“购买更多的RAM”）。我愿意将CPU时间换成内存。
我应该转换整个代码使用std ::列表（并以某种方式实现operator []的地方代码使用它？）..会甚至是更多的内存效率？至少它会允许列表元素不连续......对吗？
是否有更好的分配，在那里，我可以用它来覆盖对用于该用途的情况下，载体的标准？
我错过了哪些其他解决方案？

由于我不知道最终会使用多少内存，我知道即使我进行了更改，仍然可能没有足够的内存来执行我的计算，但我怀疑我至少可以得到一个现在我越来越多了，这似乎很快就放弃了。

来源

2013-04-05 clemej

我要澄清，作为新的元件试图与的push_back待添加的bad_alloc的抛出（）。 – clemej 2013-04-05 19:10:41

如果算法需要随机访问（而不仅仅是顺序访问），那么用链接列表替换向量可以保证*糟糕的性能。获取M元素链表的第n个元素需要解除引用“min {n，M-n}”指针的次数。对于你的情况，对'operator []'的单个调用将需要数百，甚至数千，甚至数百万条指令（每个指令本身相对较慢）。有了这样庞大的数据集，实际上可以确保您的程序永远持续下去。 – delnan 2013-04-05 19:12:42

如果矢量需要增长，它*暂时*需要大约两倍的RAM，因为矢量总是存储在连续的内存块中。如果它增长，它将分配一个更大的元素，移动所有元素，然后释放前一个元素。你有可能知道元素的上限吗？如果是这样，请尝试在开始处使用['reserve（）']（http://en.cppreference.com/w/cpp/container/vector/reserve）。 – 2013-04-05 19:13:38

我会尝试使用std::deque作为直接下拉为vector。有可能是因为它（经常）使用一组块，所以扩展deque可能会比扩展vector便宜（就所需的额外内存而言）。

来源

2013-04-05 19:29:40

（阅读deque）似乎接近我在找什么！我会试试看。可能无法解决问题，但可能会更接近。 – clemej 2013-04-05 19:56:00

很酷。 deque并没有让程序工作，但至少给了我半可预测的行为，并在用完之前使用了更多的内存。正是我在找什么。它是一个简单的“sed -i's/vector/deque/g'”的双加奖励点。 – clemej 2013-04-05 20:49:51

在这个用例中，Deque也不会比矢量慢得多。 – clemej 2013-04-05 20:50:40

大型矢量空间高效的C++矢量分配器？

回答

相关问题