Hi,
As I read in the archives, the performance problem caused by memory
reallocations during vector::push_ba ck 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!
Jul 22 '05
30 4510
"Andrew Koenig" <ar*@acm.org> wrote in message news:<do******* **************@ bgtnsc04-news.ops.worldn et.att.net>... "Antonios Christofides" <an*****@itia.n tua.gr> wrote in message news:dc5.4159da 31.d0edf@voltai re...
As I read in the archives, the performance problem caused by memory reallocations during vector::push_ba ck 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.
I'm skeptical.
Here's a little program:
#include <vector>
int main() { std::vector<int > v; for (std::vector<in t>::size_type i = 0; i != 1000000; ++i) v.push_back(i); return 0; }
When I run this program on my machine (admittedly faster than 1.3G, but no more than twice as fast), it runs in three *hundredths* of a second. And it calls push_back a million times, not 300,000 times.
Just for the records: Are you sure it _does_ call push_back at all?
Since your program doesn't produce any observable effect, the compiler
has licence to transfer it into something like
int main()
{
}
which should probably run quite fast, shouldn't it?
Have fun,
Uwe
Uwe Schnitker wrote: "Andrew Koenig" <ar*@acm.org> wrote in message news:<do******* **************@ bgtnsc04-news.ops.worldn et.att.net>...
"Antonios Christofides" <an*****@itia.n tua.gr> wrote in message news:dc5.4159 da31.d0edf@volt aire...
As I read in the archives, the performance problem caused by memory reallocation s during vector::push_ba ck 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.
I'm skeptical.
Here's a little program:
#include <vector>
int main() { std::vector<int > v; for (std::vector<in t>::size_type i = 0; i != 1000000; ++i) v.push_back(i); return 0; }
When I run this program on my machine (admittedly faster than 1.3G, but no more than twice as fast), it runs in three *hundredths* of a second. And it calls push_back a million times, not 300,000 times.
Just for the records: Are you sure it _does_ call push_back at all?
Since your program doesn't produce any observable effect, the compiler has licence to transfer it into something like
int main() { }
which should probably run quite fast, shouldn't it?
Good point, one should always be carefull with drawing conclusions from
test like this.
I compiled Andrew program on MSVC 6.0 with full optimization and checked
the assembly output. On this compiler the loop isn't optimized away.
push_back() is inlined, but the function that inserts elements into the
vector is still called one million times. Nevertheless this program
completed in 0.10 seconds on a Pentium III @ 700Mhz.
But I can imagine when the objects in the vector are expensive to copy
the story changes quite a bit.
--
Peter van Merkerk
peter.van.merke rk(at)dse.nl
"Uwe Schnitker" <sc************ ********@sigma-c.com> wrote in message
news:30******** *************** ***@posting.goo gle.com... Just for the records: Are you sure it _does_ call push_back at all?
Since your program doesn't produce any observable effect, the compiler has licence to transfer it into something like
int main() { }
which should probably run quite fast, shouldn't it?
If I insert the statement
std::cout << v.size() << std::endl;
in the appropriate place, it prints 1000000 and still runs in 0.03 seconds.
Uwe - do you know who yoe are questioning?
I guess not...
Have fun yourself
Hi again,
after several experiments, I see that, indeed, when vector::push_ba ck
needs to reallocate memory, it does construct a copy of the object and
destruct the old object. When I recompiled my program without
optimization, I saw that the reallocation routines don't actually take
much time, but the constructor of the contained class does; with
optimization, it is apparently inlined and the profiler indicates that
the time is spent in the reallocation routines. If I call
vector::reserve prior to performing the 306 thousand push_backs, the
constructor is called 306 thousand times; if I don't, it is called 830
thousand times (likewise for the destructor).
Why don't just memmove the objects? I understand that in the general
case this is not possible; for example, if the constructor registers
the object's address in some global vector object. But this would not
be a problem for my class, which does not do such things. Furthermore,
my examination with the debugger indicates that when I copy an
instance of it, the copy is identical, byte by byte; even a string
member points to the same memory location as the original. So is it
just that the compiler/stl can't know, and we can't hint it, that a
memmove would suffice?
Here's the class, for your reference:
struct Record {
Record(const Date& t, bool n, double v, string f):
timestamp(t), null(n), value(v), flags(f) { }
Date timestamp;
bool null;
double value;
string flags;
};
("Date" is a user class internally represented as a struct tm.)
"algorithm" <bo*********@ya hoo.com> wrote in message news:<0d******* *************** ********@localh ost.talkaboutpr ogramming.com>. .. Uwe - do you know who yoe are questioning? I guess not... Have fun yourself
I'm not sure when I first read something either about or by AK, but it
must have been in the previous century ...
Questioning (well-earned) authority is not a matter of refusal to
learn from it. Quite the contrary.
Antonios Christofides wrote: [...] Why don't just memmove the objects? I understand that in the general case this is not possible; for example, if the constructor registers the object's address in some global vector object. But this would not be a problem for my class, which does not do such things. Furthermore, my examination with the debugger indicates that when I copy an instance of it, the copy is identical, byte by byte; even a string member points to the same memory location as the original. So is it just that the compiler/stl can't know, and we can't hint it, that a memmove would suffice? [...]
Try implementing the copy c-tor for your class in terms of 'memmove'.
If you succeed, remember that it's not portable. If you don't succeed,
read up on "move semantics" for return values and temporaries (IIRC),
the discussion was in comp.lang.c++.m oderated somewhere in the past
couple of years.
Victor
On Wed, 29 Sep 2004 07:37:21 +0000 (UTC), Antonios Christofides
<an*****@itia.n tua.gr> wrote: > All the texts I have read state that, when a dynamic array needs > to be extended, it is better/faster to 'realloc' instead of > creating a new array and copying the elements manually. > > So why is 'realloc' more efficient?
Except for what was already said, I believe that even in the cases when realloc needs to allocate a new memory block rather than extend the existing one, it uses memmove or some similar operation which will be faster than manually copying the elements if its implementation uses specialized mass-byte-copying CPU instructions.
std::vector will also typically use memmove or memcpy for built in
types like int. The easiest way to see this is to trace into the
push_back calls in a debugger - working out the code path can be
difficult otherwise.
For object types with copy constructors, the language currently
contains no better way of moving them that copying them and then
destroying the original. However, move constructors are a future
solution to this problem.
Tom
On Sun, 03 Oct 2004 18:52:16 -0000, Antonios Christofides
<an*****@itia.n tua.gr> wrote: Hi again,
after several experiments, I see that, indeed, when vector::push_ba ck needs to reallocate memory, it does construct a copy of the object and destruct the old object. When I recompiled my program without optimization , I saw that the reallocation routines don't actually take much time, but the constructor of the contained class does; with optimization , it is apparently inlined and the profiler indicates that the time is spent in the reallocation routines. If I call vector::reserv e prior to performing the 306 thousand push_backs, the constructor is called 306 thousand times; if I don't, it is called 830 thousand times (likewise for the destructor).
Right. Unfortunately the std::allocator interface doesn't include any
kind of try_realloc method, so it always has to allocate a new block
and copy, even when there is free space after the current storage.
Why don't just memmove the objects? I understand that in the general case this is not possible; for example, if the constructor registers the object's address in some global vector object. But this would not be a problem for my class, which does not do such things. Furthermore, my examination with the debugger indicates that when I copy an instance of it, the copy is identical, byte by byte; even a string member points to the same memory location as the original. So is it just that the compiler/stl can't know, and we can't hint it, that a memmove would suffice?
Yes, exactly. Strictly speaking, you can't use memmove portably on any
non-POD type, but in practice it works well with many types.
Here's the class, for your reference:
struct Record { Record(const Date& t, bool n, double v, string f): timestamp(t), null(n), value(v), flags(f) { } Date timestamp; bool null; double value; string flags; };
("Date" is a user class internally represented as a struct tm.)
Well, I can think of reasonable implementations of std::string that
wouldn't be memmoveable (e.g. using a COW based lock-free pointer XOR
reference linked list implementation) , so the copy-destroy cycle is
the best you can do until this comes to be: http://www.open-std.org/jtc1/sc22/wg...ve%20Semantics
Tom
On Thu, 30 Sep 2004 14:03:10 GMT in comp.lang.c++, "Andrew Koenig"
<ar*@acm.org> wrote, If I insert the statement
std::cout << v.size() << std::endl;
in the appropriate place, it prints 1000000 and still runs in 0.03 seconds.
But perhaps the compiler is determining statically what the size of the
vector would be at that point and encoding only that string in the
executable. I think you have to read the initial 1000000 from a file
that is unknown at compile time. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Hitesh Bhatiya |
last post by:
Hi all,
I have written a small program to accept some socket connections, which are
then added to a vector (using push_back). But after a few calls to the
push_back function, it deleted the object that was added last.
Could someone please tell me why this happens ? Am I doing something wrong
here ?
|
by: Mark P |
last post by:
Say I have objects of class C which are fairly large. Then consider:
vector<C> vc;
vc.push_back(C());
Naively this would seem to construct a temporary object C(), copy it
into the space owned by the vector, and then delete the temporary object.
I realize this is implementation dependent, but will most modern
compilers optimize away the creation of the temporary object, or is
|
by: whocares |
last post by:
hi everyone.
i'm currently experiencing a strange problem under vc++ 2005 express. i hope
someone has a hint for me, i'm kind of lost atm.
i'm using a vectors of pointers in my code.
using the release build i can add and remove elements aslong as i stay below
a certain vector size (13 in this case, no joke). as soon as the vector tries
to add element 14 i get a runtime error.
|
by: Al |
last post by:
What is the problem with this code? It always crashes at the
'push_back'. I found that thanks to debugging. Any Ideas?
Other question: what is a faster way to convert a string to an integer?
Is there a built-in function to do that?
Here's the code:
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
|
by: ma740988 |
last post by:
Consider the source snippet
int main()
{
std::vector<double> vec_push( 0x10 );
size_t const SZ = vec_push.size();
std::cout << vec_push.size() << std::endl;
if ( SZ != 0x10 ) {
cout << " something's amiss " << endl;
| |
by: Siam |
last post by:
Hi,
I'm a little new to stl so bear with me...Say I have the following
code:
vector<intvec;
int i = 3;
vec.push_back(i);
i=4;
cout<<vec.at(0)<<endl;
|
by: jmsanchezdiaz |
last post by:
CPP question: if i had a struct like "struct str { int a; int b };"
and a vector "std::vector < str test;" and wanted to push_back a
struct, would i have to define the struct, fill it, and then push_back
it, or could i pushback the two ints directly somehow?
Thanks for all.
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
| |
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |