vector :: push_back性能 [英] vector::push_back performance

问题描述

正如我在档案中看到的那样，在vector :: push_back期间由内存引起的性能问题是一个常见的问题。我的第一个C ++

程序正在遭受这样的困扰：根据剖析器，在20次重新分配中产生了30万次push_backs，

;这20个重新分配

占3.6秒（Celeron 1.3G），占总执行时间的40％。


我不明白：为什么重新分配代码如此复杂？我

研究了图书馆的来源，我很难理解它，

但它似乎是逐个复制矢量项目

重新分配。为什么不是realloc足够吗？


而且，鉴于我事先并不知道矢量大小，那么除了尝试deqeue或者其他任何东西我都可以做其他事情吗？猜猜

vector :: reserve？


如果重要的话，我正在使用gcc 3.3及其标准的c ++库

a Debian sarge，但便携性也是一个问题。


谢谢！

Hi,

As I read in the archives, the performance problem caused by memory
reallocations during vector::push_back is a common one. My first C++
program is suffering from it: 300 thousand push_backs result,
according to the profiler, in 20 reallocations; these 20 reallocations
account for 3.6 seconds (Celeron 1.3G), which is 40% of total
execution time.

What I don''t understand: why is the reallocation code so complex? I
studied the library source and I have a hard time understanding it,
but it seems to be copying the vector item by item in each
reallocation. Why wouldn''t a "realloc" suffice?

And, given that I don''t know the vector size beforehand, is there
anything else I can do other than trying deqeue or a guessed
vector::reserve?

In case it matters, I''m using gcc 3.3 with its standard c++ library on
a Debian sarge, but portability is also an issue.

Thanks!

推荐答案

Antonios Christofides写道：

Antonios Christofides wrote:

当我在档案中读到时，在vector :: push_back期间由内存重新分配引起的性能问题是常见的。我的第一个C ++
程序正在遭受它的影响：根据剖析器，在20次重新分配中产生了30万次push_backs;这20个重新分配
占3.6秒（Celeron 1.3G），占总执行时间的40％。

我不明白：为什么重新分配代码如此复杂？我研究了图书馆资源，我很难理解它，
但似乎是在每次重新分配时逐项复制矢量。为什么不是realloc满足？


这就是realloc的含义。也是。你通常不能轻易地将已经分配的内存块更大（你之后用数据做什么？），所以必须分配一个

的新块，数据被复制到它，然后旧的

一个被销毁。

并且，鉴于我事先不知道矢量大小，是否有除了尝试deqeue或猜测
vector :: reserve之外我还能做什么？


不多。

如果重要的话，我正在使用gcc 3.3及其标准的c ++库来进行Debian sarge，但是可移植性也是一个问题。

Hi,

As I read in the archives, the performance problem caused by memory
reallocations during vector::push_back is a common one. My first C++
program is suffering from it: 300 thousand push_backs result,
according to the profiler, in 20 reallocations; these 20 reallocations
account for 3.6 seconds (Celeron 1.3G), which is 40% of total
execution time.

What I don''t understand: why is the reallocation code so complex? I
studied the library source and I have a hard time understanding it,
but it seems to be copying the vector item by item in each
reallocation. Why wouldn''t a "realloc" suffice?
That''s what a "realloc" does, too. You usually can''t easily make an already
allocated memory block bigger (what would you do with data after it?), so a
new block must be allocated and the data be copied over to it, then the old
one destroyed.
And, given that I don''t know the vector size beforehand, is there
anything else I can do other than trying deqeue or a guessed
vector::reserve?
Not much.
In case it matters, I''m using gcc 3.3 with its standard c++ library on
a Debian sarge, but portability is also an issue.

Antonios Christofides写道：

Antonios Christofides wrote:

当我在档案中看到，表演内存导致的问题在vector :: push_back期间重新分配是一个常见的问题。我的第一个C ++
程序正在遭受它的影响：根据剖析器，在20次重新分配中产生了30万次push_backs;这20次重新分配占据3.6秒（Celeron 1.3G），占总执行时间的40％。


三十万推送到没有保留的矢量？似乎

不合理。

我不明白：为什么重新分配代码如此复杂？我研究了图书馆资源，我很难理解它，
但似乎是在每次重新分配时逐项复制矢量。为什么不是realloc满足？


'realloc'会做什么？将每个对象放在不同的内存

位置而不让对象知道？那是不对的。对象

可能需要知道它们的构造位置。他们可能想要

让其他类或对象知道他们的位置等等。

而且，鉴于我事先并不知道矢量大小，那么<除了尝试deqeue或猜测
vector :: reserve之外我还能做什么？


不。使用标准容器需要承认权衡。

如果你需要快速推回而你不知道它的大小，你应该

可能使用''std ::列出''或'''std :: deque''。如果你之后需要随机访问

，不要在没有保留的情况下推迟。我打赌标准容器上任何体面的书

谈论如何选择适合您任务的容器

。当然，这假设你知道你的任务是什么。

如果它很重要，我正在使用gcc 3.3及其标准的c ++库来进行Debian sarge，但是可移植性是也是一个问题。

As I read in the archives, the performance problem caused by memory
reallocations during vector::push_back is a common one. My first C++
program is suffering from it: 300 thousand push_backs result,
according to the profiler, in 20 reallocations; these 20 reallocations
account for 3.6 seconds (Celeron 1.3G), which is 40% of total
execution time.
Three hundred thousand push_backs into a vector without reserve? Seems
unjustified.
What I don''t understand: why is the reallocation code so complex? I
studied the library source and I have a hard time understanding it,
but it seems to be copying the vector item by item in each
reallocation. Why wouldn''t a "realloc" suffice?
What would ''realloc'' do? Place the objects each at a different memory
location without letting the object know? That''s not right. Objects
may need to know where they have been constructed. They might want to
let other classes or objects know of their location, etc.
And, given that I don''t know the vector size beforehand, is there
anything else I can do other than trying deqeue or a guessed
vector::reserve?
Nope. Using standard containers requires acknowledging the trade-offs.
If you need fast push_back and you don''t know the size, you should
probably use ''std::list'' or ''std::deque''. If you need random access
afterwards, don''t push-back without reserving. I bet any decent book
on Standard containers talks about how to pick the container well-suited
for your task. Of course, that assumes that you know what your task is.
In case it matters, I''m using gcc 3.3 with its standard c++ library on
a Debian sarge, but portability is also an issue.

没关系，至少不在这里。


V

It doesn''t matter, at least not here.

V

Antonios Christofides写道：

Antonios Christofides wrote:

当我在档案中读到时，在vector :: push_back期间由内存重新分配引起的性能问题是一个普通的。我的第一个C ++
程序正在遭受它的影响：根据剖析器，在20次重新分配中产生了30万次push_backs;这20次重新分配占据3.6秒（Celeron 1.3G），占总执行时间的40％。


你认为你可以去一个你少推回的算法吗？

我不明白：为什么重新分配代码如此复杂？我研究了图书馆资源，我很难理解它，
但似乎是在每次重新分配时逐项复制矢量。为什么不是realloc足够吗？

As I read in the archives, the performance problem caused by memory
reallocations during vector::push_back is a common one. My first C++
program is suffering from it: 300 thousand push_backs result,
according to the profiler, in 20 reallocations; these 20 reallocations
account for 3.6 seconds (Celeron 1.3G), which is 40% of total
execution time.
Do you think you could go to an algorithm where you push less back?
What I don''t understand: why is the reallocation code so complex? I
studied the library source and I have a hard time understanding it,
but it seems to be copying the vector item by item in each
reallocation. Why wouldn''t a "realloc" suffice?

阅读Herb Sutter的酷炫GOTW系列和他的书籍/ Exceptional C ++ /。他打击选择的容器类通常应该是std :: deque<>，而不是
推送到开头和结尾。


- -

Phlip
http： //industrialxp.org/community/bi...UserInterfaces

这篇关于vector :: push_back性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！