Prev: Function lookup as metaprogramming
Next: Why you should never use a const& parameter to initialize a const& member variable!
From: NL on 3 Feb 2010 05:41
Hi,

I'm thinking about changing some of my arrays of structures to
vectors, but it seems like it might be quite a bit slower. Can anybody
shed some light on the following example?
With the array method, when I want to add to the FooList, I call
GetNextFoo() which returns a pointer, and I can just fill in my foo
object directly.
With the vector method, it seems like I have to make a local copy of
the foo structure, fill it out, and then call vector.push_back, which
to me seems like it would have to make a copy to put in the vector.
This could be expensive since the foo object is quite large.
Are there ways to avoid the copying?

Thanks,
NL


struct Foo{
double x[1000];
double y[1000];
};

Array method :
class FooList {
Foo theFoos[5000];
int numFoo;
Foo* GetNextFoo() {
return &theFoos[numFoo++];
}
}

Vector method;
...
Foo f;
<fill out f>
fooVector.push_back(f) // I assume this makes a copy before adding the
object to the vector?



--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: nabulke on 3 Feb 2010 15:43
On 3 Feb., 23:41, NL <norv...(a)gmail.com> wrote:
> Hi,
>
> I'm thinking about changing some of my arrays of structures to
> vectors, but it seems like it might be quite a bit slower. Can anybody
> shed some light on the following example?

"Premature optimization is the root of all evil". Did you measure/
profile it?

> With the array method, when I want to add to the FooList, I call
> GetNextFoo() which returns a pointer, and I can just fill in my foo
> object directly.

You could just use a vector of pointers to Foo, or even better a
vector of smart pointers to foo so you don't get any issues with
memory allocation/deallocation.

> With the vector method, it seems like I have to make a local copy of
> the foo structure, fill it out, and then call vector.push_back, which
> to me seems like it would have to make a copy to put in the vector.
> This could be expensive since the foo object is quite large.
> Are there ways to avoid the copying?
>
> Thanks,
> NL
>
> struct Foo{
> double x[1000];
> double y[1000];
>
> };
>
> Array method :
> class FooList {
> Foo theFoos[5000];
> int numFoo;
> Foo* GetNextFoo() {
> return &theFoos[numFoo++];
> }
>
> }
>
> Vector method;
> ..
> Foo f;
> <fill out f>
> fooVector.push_back(f) // I assume this makes a copy before adding the
> object to the vector?
>

Yes, push_back uses the copy constructor to make one copy of the
element Foo. Using pointers would make this very cheap.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Goran on 3 Feb 2010 20:14
On Feb 3, 11:41 pm, NL <norv...(a)gmail.com> wrote:
> Hi,
>
> I'm thinking about changing some of my arrays of structures to
> vectors, but it seems like it might be quite a bit slower. Can anybody
> shed some light on the following example?
> With the array method, when I want to add to the FooList, I call
> GetNextFoo() which returns a pointer, and I can just fill in my foo
> object directly.
> With the vector method, it seems like I have to make a local copy of
> the foo structure, fill it out, and then call vector.push_back, which
> to me seems like it would have to make a copy to put in the vector.
> This could be expensive since the foo object is quite large.
> Are there ways to avoid the copying?

First question you need to answer, to yourself, is: does it matter, in
your code, the way it's supposed to run in at least some usage
scenarios? (IOW, did you conclude that it's slower through
measurement?). Because if not, you are in premature optimization land.

That said, not entirely, no. But note that vector and your array have
different capabilities. vector will grow as large as needed, or as
there is memory. Your array grow up to compile-time defined constant.
Note also that for small values of numFoo, you're mightily wasting
storage (that's IMO the number 2 reason why one should never use fixed-
size storage, number 1 being "what if you need element 5001 and there
__indeed is__ space for it on the heap?").

Mitigating factors:

1. you can use reserve() to minimize heap re-allocations (but the
price is wasted storage like with compile-time-fixed size).

2. you can also use resize() and numFoo (similar price as with above).

3. you can use vector<Foo*>, but expose reference-like semantics in
access to Foo-s from FooList (why "List", BTW? It's an array, or a
vector, and list is something else; I personally prefer to name
containers with a simple plural (Foos) whenever possible and use tools
to find out what operations on them are). That practically avoids
copying overhead, but needs more storage and possible fragmentation.

Goran.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Ralf Fassel on 4 Feb 2010 04:34
* NL <norvinl(a)gmail.com>
| Array method :
| class FooList {
| Foo theFoos[5000];
| int numFoo;
| Foo* GetNextFoo() {
| return &theFoos[numFoo++];
| }
| }
|
| Vector method;

class FooList {
FooList() : theFoos(5000) {};
std::vector<Foo> theFoos;
int numFoo;
Foo* GetNextFoo() {
return &theFoos[numFoo++];
}
};

There really should be no difference. Just init the vector the same
size as your array, then you don't need push_back().

R'

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: NL on 4 Feb 2010 04:34
Hi

First of all, thanks for the replies:

Regarding premature optimization, the creation and filling of the
vector is currently 90% of the execution time in the semi real time
system, so I'm just exploring what overhead I'm adding before jumping
in with both feet.

>
> You could just use a vector of pointers to Foo, or even better a
> vector of smart pointers to foo so you don't get any issues with
> memory allocation/deallocation.
>

I don't understand. What container are the actual Foo's stored in? If
a vector, then my issue still exists. (My issue is in creating and
filling the container of Foo objects. With the array, I currently fill
in an already existing chunk of memory, with a vector I'll need to do
the same, but then copy the memory to another location.)
The temporary object I'm creating and filling is local to the
function, so a pointer to it would be useless outside the function,
no? Or maybe smart pointers could help here?

Thanks,
Norvin

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2 3
Prev: Function lookup as metaprogramming
Next: Why you should never use a const& parameter to initialize a const& member variable!