4

当单个向量可以有不同时,我想填充一个向量向量size(),例如

std::vector<std::vector<big_data_type> > table;
std::vector<big_data_type> tmp;
for(auto i=0; i!=4242; ++i) {
  tmp = make_vector(i);              // copy elison; calls new[] only for i=0
  table.push_back(tmp);              // copy         calls new[] each time
}

我的主要问题是避免在未使用的容量上浪费内存。所以我的第一个问题是:

Q1副本(内部制作push_back)是否有capacity()== size()(我想要的),或者保留任何tmp有的东西,或者这个实现是否依赖/未定义?

我正在考虑将个人vectors 移动到table

  table.push_back(std::move(tmp));   // move

但这肯定会保留capacity并因此浪费内存。此外,这并不能避免分配每个单独的向量,它只会将其移动到另一个位置(内部make_vector而不是push_back)。

Q2我想知道省略变量有什么不同tmp,导致代码看起来更优雅(2 行而不是 5 行):

for(auto i=0; i!=4242; ++i)
  table.push_back(make_vector(i));   // move!

我最初的想法是,这将在每次迭代时构造和破坏另一个临时对象,因此会生成对new[]and的许多调用delete[](这将基本上重用相同的内存)。但是,此外,这将调用移动版本,push_back因此会浪费内存(见上文)。正确的?

Q3编译器是否有可能将我以前的代码“优化”为后一种形式,从而使用移动而不是复制(导致浪费内存)?

Q4如果我是正确的,在我看来,所有这些都意味着为临时对象自动移动数据是一件喜忧参半的事情(因为它可以防止压缩)。有什么方法可以明确禁止在最后一个代码中移动,即类似

for(auto i=0; i!=4242; ++i)
  table.push_back(std::copy(make_vector(i)));   // don't move!
4

6 回答 6

3

Q1 副本(在 push_back 中制作)是否有 capacity() == size() (我想要的),或者保留 tmp 的任何内容,或者这个实现是否依赖/未定义?

该标准从不设置容量的最大值,只设置最小值。也就是说,大多数实现将具有capacity() == size()新的向量副本或容量,略微向上舍入到分配器实现的块大小。

Q2 我想知道省略变量 tmp 有什么不同,从而使代码看起来更优雅。

结果是移动table而不是复制。

Q3 编译器是否有可能将我以前的代码“优化”为后一种形式,从而使用移动而不是复制(导致浪费内存)?

这是可能的,但可能性很小。编译器必须证明移动与复制没有明显不同,这具有足够的挑战性,据我所知,当前的编译器没有尝试过。

Q4 如果我是正确的,在我看来,所有这些都意味着为临时对象自动移动数据是一件喜忧参半的事情(因为它可以防止压缩)。

移动是速度优化,不一定是空间优化。复制可能会减少空间,但肯定增加处理时间。

如果您想优化空间,最好的办法是使用shrink_to_fit

std::vector<std::vector<big_data_type> > table;
for(auto i=0; i!=4242; ++i) {
  std::vector<big_data_type> tmp = make_vector(i); // copy elison
  tmp.shrink_to_fit();                             // shrink
  table.push_back(std::move(tmp));                 // move
}

编辑:深入分析。

假设:

  • table由于它的大小是已知的,因此将提前保留其空间,因此我们专注于vector<big_data_type>从 s 返回make_vector、临时存储在 s 中tmp、最后在s 中的 s 的分配和释放table
  • 的返回值make_vector(i)可能有也可能没有capacity == size。此分析视为make_vector不透明并忽略构建返回向量所需的任何分配。
  • 默认构造的向量的容量为 0。
  • reserve(n)将容量准确设置为n当且仅当n > capacity().
  • shrink_to_fit()capacity == size。它可能会或可能不会被实现为需要整个矢量内容的副本。
  • 向量复制构造函数设置capacity == size.
  • std::vector可能会或可能不会为复制分配提供强有力的例外保证。

我将对两个正整数的分析进行参数化:算法结束时N将出现的向量数(OP 中为 4242),以及:在过程中产生的所有向量中包含的对象总数算法。tableKbig_data_typemake_vector

你的技术

std::vector<std::vector<big_data_type> > table;
table.reserve(N);
std::vector<big_data_type> tmp;
for(auto i=0; i!=N; ++i) {
  tmp = make_vector(i); // #1
  table.push_back(tmp); // #2
}
// #3

对于 C++11

在#1,由于tmp已经构建,RVO/复制省略不会发生。每次通过循环时,返回值都分配给tmp. 赋值是一个移动:旧数据tmp将被销毁(第一次迭代时tmp为空除外)并且返回值的内容从 make_vector移动到tmp不发生复制。tmp具有capacity == size 当且仅当make_vector的返回值具有该属性。

在 #2 处,tmp被复制到table. 新构建的副本table具有 capacity == size所需的内容。在#3tmp大概离开范围并且它的存储被释放。

总分配/解除分配:N。#2 处的所有分配,# N - 11 处的释放,以及#3 处的一个。

big_data_type(对象的)总副本: K.

对于 C++11 之前的版本

在#1,由于tmp已经构建,RVO/复制省略不会发生。每次通过循环时,返回值都分配给tmp. tmp如果 (a) 实现提供了强保证,或者 (b)太小而无法包含返回向量中的所有元素,则此分配需要分配和解除分配。在任何情况下,元素都必须单独复制。在完整表达式的末尾,保存返回值的临时对象make_vector被销毁,导致释放。

在 #2 处,tmp被复制到table. 新构建的副本table具有 capacity == size所需的内容。在#3tmp大概离开范围并且它的存储被释放。

总分配/解除分配:N+ 1 到 2 * N。1 到N#1、#2 的分配NN2 * N- 1 次在 #1 处释放,1 次在 #3 处。

总份数:2 * K. K在#1 和K#2。

我的技术(仅限 C++11)

std::vector<std::vector<big_data_type> > table;
table.reserve(N);
for(auto i=0; i!=N; ++i) {
  auto tmp = make_vector(i);          // #1
  tmp.shrink_to_fit();                // #2
  table.emplace_back(std::move(tmp)); // #3
}

在 #1tmp是从 的返回值新构建的make_vector,因此 RVO/复制省略是可能的。即使实施make_vector 阻碍了 RVO,tmp也将被移动构造,导致没有分配、释放或复制。

在 #2shrink_to_fit可能需要也可能不需要单个分配和解除分配,这取决于来自的返回值是否make_vector已经具有该capacity == size属性。如果发生分配/解除分配,则可能会或可能不会复制元素,具体取决于实现的质量。

在 #3 的内容tmp被移动到新构建的向量中 table。不执行分配/解除分配/复制。

总分配/解除分配:0 或N, 全部在 #2 当且仅当make_vector不返回带有 的向量capacity == size。副本总数:0 或K,当且仅当shrink_to_fit被实现为副本时,全部位于 #2。

如果实现者make_vector生成具有该属性的向量capacity == size 并且标准库以shrink_to_fit最佳方式实现,则没有新闻/删除和副本。

结论

My Technique 的最坏情况表现与 Your Technique 的预期情况表现相同。我的技术有条件地是最优的。

于 2013-08-12T14:32:05.887 回答
1

除了凯西帖子,我还有以下几点说明。

正如jrok在这里的评论中所说,shrink_to_fit不保证会做任何事情。但是,如果shrink_to_fit为精确数量的元素分配内存size(),复制/移动元素并释放原始缓冲区,那么这正是 OP 所要求的。

我对 Q4 的确切回答是,

有什么方法可以显式抑制在最后一个代码中的移动 [...]?

是:是的,你可以做到

for(auto i=0; i!=4242; ++i)
  table.push_back(static_cast<const std::vector<big_data_type>&>(make_vector(i)));

OP建议的copy功能可以写成如下。

template <typename T>
const T& copy(const T& x) {
    return x;
}

代码变成了

for(auto i=0; i!=4242; ++i)
  table.push_back(copy(make_vector(i)));

但是,老实说,我不认为这是一个明智的做法。

如果可能的话,制作这样的每个元素的最佳位置v是在。(正如凯西所说,该标准没有对容量设置任何上限。)然后将结果移动到将在两个意义上(内存和速度)都是最佳的。OP的剪断可能应该照顾好。tablev.size() == v.capacity()make_vector() make_vector()tabletable.size()

总之,该标准没有提供任何强制容量匹配大小的方法。Jon Kalb有一个(明智的,恕我直言)建议std::vector::shrink_to_fit至少与shrink_to_fit 习语(也不能保证任何事情)一样高效(在内存使用方面)。然而,委员会的一些成员对此并不热衷,并建议人们宁愿向他们的供应商投诉,或者实现自己的容器和分配功能。

于 2013-08-12T18:41:49.753 回答
1

以下是一些运行时测试,其中包含计算创建、移动和复制的辅助类型:

#include <vector>
#include <iostream>

struct big_data_type {
  double state;
  big_data_type( double d ):state(d) { ++counter; ++create_counter; }
  big_data_type():state(0.) { ++counter; }
  big_data_type( big_data_type const& o ): state(o.state) { ++counter; }
  big_data_type( big_data_type && o ): state(o.state) { ++move_counter; }
  big_data_type& operator=( big_data_type const& o ) {
    state = o.state;
    ++counter;
    return *this;
  }
  big_data_type& operator=( big_data_type && o ) {
    state = o.state;
    ++move_counter;
    return *this;
  }
  static int counter;
  static int create_counter;
  static int move_counter;
};
int big_data_type::move_counter = 0;
int big_data_type::create_counter = 0;
int big_data_type::counter = 0;

std::vector<big_data_type>& make_vector( int i, std::vector<big_data_type>& tmp ) {
  tmp.resize(0);
  tmp.reserve(1000);
  for( int j = 0; j < 10+i/100; ++j ) {
    tmp.emplace_back( 100. - j/10. );
  }
  return tmp;
}
std::vector<big_data_type> make_vector2( int i ) {
  std::vector<big_data_type> tmp;
  tmp.resize(0);
  tmp.reserve(1000);
  for( int j = 0; j < 10+i/100; ++j ) {
    tmp.emplace_back( 100. - j/10. );
  }
  return tmp;
}
enum option { a, b, c, d, e };
void test(option op) {
  std::vector<std::vector<big_data_type> > table;
  std::vector<big_data_type> tmp;
  for(int i=0; i!=10; ++i) {
    switch(op) {
      case a:
        table.emplace_back(make_vector(i, tmp));
        break;
      case b:
        tmp = make_vector2(i);
        table.emplace_back(tmp);
        break;
      case c:
        tmp = make_vector2(i);
        table.emplace_back(std::move(tmp));
        break;
      case d:
        table.emplace_back(make_vector2(i));
        break;
      case e:
        std::vector<big_data_type> result;
        make_vector(i, tmp);
        result.reserve( tmp.size() );
        result.insert( result.end(), std::make_move_iterator( tmp.begin() ),std::make_move_iterator( tmp.end() ) );
        table.emplace_back(std::move(result));
        break;
    }
  }
  std::cout << "Big data copied or created:" << big_data_type::counter << "\n";
  big_data_type::counter = 0;
  std::cout << "Big data created:" << big_data_type::create_counter << "\n";
  big_data_type::create_counter = 0;
  std::cout << "Big data moved:" << big_data_type::move_counter << "\n";
  big_data_type::move_counter = 0;
  std::size_t cap = 0;
  for (auto&& v:table)
    cap += v.capacity();
  std::cout << "Total capacity at end:" << cap << "\n";
}

int main() {
  std::cout << "A\n";
  test(a);
  std::cout << "B\n";
  test(b);
  std::cout << "C\n";
  test(c);
  std::cout << "D\n";
  test(d);
  std::cout << "E\n";
  test(e);
}

活生生的例子

输出:

+ g++ -O4 -Wall -pedantic -pthread -std=c++11 main.cpp
+ ./a.out
A
Big data copied or created:200
Big data created:100
Big data moved:0
Total capacity at end:100
B
Big data copied or created:200
Big data created:100
Big data moved:0
Total capacity at end:100
C
Big data copied or created:100
Big data created:100
Big data moved:0
Total capacity at end:10000
D
Big data copied or created:100
Big data created:100
Big data moved:0
Total capacity at end:10000
E
Big data copied or created:100
Big data created:100
Big data moved:100
Total capacity at end:100

E是一个例子,当你的大数据可以移动时,这通常是行不通的。

created refers to only explicitly created data (ie, from the double) -- data "created on purpose". Copied or created refers to any time that any big data is duplicated in a way that the source big data cannot be "discarded". And moved refers to any situation where big data is moved in a way that the source big data can be "discarded".

Case a and b, which are identical in result, are probably want you are looking for. Note the explicit use of the tmp vector as an argument to make_vector: elision won't let you reuse the buffer, you have to be explicit about it.

于 2013-08-14T14:09:52.203 回答
1

The vector of vectors construct brings a lot of unnecessary overhead in cases where data is only ever added at the end of the top level vector (as appears to be the case here).

The main issue is the separate buffer allocations and management for each individual entry in the top level vector.

It's much better to concatenate all the sub-entries together into a single contiguous buffer, if possible, with a separate buffer to index into this for each top level entry.

See this article (on my blog), for more discussion about this, and for an example implementation of a 'collapsed vector vector' class to wrap this kind of indexed buffer setup up in a generic container object.

As I said before, this only applies if data only ever gets added at the end of your data structure, i.e. you don't come back later and push entries into arbitrary top level sub vectors, but in cases where this technique applied it can be quite a significant optimisation..

于 2013-11-26T13:35:24.393 回答
0

一般来说,如果你想要容量相等,你可以使用 vector::shrink_to_fit() http://www.cplusplus.com/reference/vector/vector/shrink_to_fit/

于 2013-08-12T14:29:13.217 回答
0

好的,我想我学到了一点,但找不到完整的答案。因此,让我们首先澄清一下任务

我们有一个填充向量的函数。为了避免争论是否可能复制省略,我们假设它的定义是

void fill_vector(std::vector<big_data_type>& v, int i)
{
  v.clear();
  v.reserve(large_number);       // allocates unless v.capacity() >= large_number
  for(int done=0,k=0; k<large_number && !done; ++k)
    v.push_back(get_more_big_data(i,done));
  // v.capacity() == v.size() is highly unlikely at this point.
}

此外,我们要填写表格

std::vector<std::vector<big_data_type>> table;

使用N条目,每个条目都fill_vector()以以下方式生成:(1)最大限度地减少表中的内存使用,但(2)避免不必要的分配/取消分配。在一个简单的 C 代码中,会有N+2分配和取消分配,并且只会分配实际提供1的总数K。我们不应该需要更多的 C++。这是一个可能的 C++答案big_data_typefill_vector()

table.reserve(N);                         // allocates enough space for N vectors
size_t K=0;                               // count big_data_types in table
std::vector<big_data_type> tmp;
for(int n=0; n!=N; ++n) {
  fill_vector(tmp,i);                     // allocates at first iteration only
  K += tmp.size();
  table.push_back(tmp.begin(),tmp.end()); // allocates tmp.size() big_data_type
}
                                          // de-allocates tmp

因此,我们可以根据需要进行N+2分配和1取消分配,并且不会浪费内存(不超过K big_data_type分配的内存table)。push_back调用 的构造函数(std::vector不传递有关容量的信息tmp)并暗示每个 的副本big_data_type。(如果big_data_type可以移动,我们可以使用make_move_iterator(tmp.begin())等)

请注意,无论我们如何编码,我们都必须至少N+1进行分配(为其table及其每个元素)。这意味着使用 ofshrink_to_fit无济于事,因为充其量它只进行一次分配和一次取消分配(除非capacity==size我们不希望以任何可能性发生),彼此取消(因此分配不能贡献于所需的总和) ) N+1。这就是为什么其他一些答案是不可接受的。

于 2013-08-14T13:59:40.773 回答