vector question
in [C++]
|
Prev: Function lookup as metaprogramming
Next: Why you should never use a const& parameter to initialize a const& member variable!
From: Francis Glassborow on 4 Feb 2010 17:35 NL wrote: > 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. I am finding it hard to imagine a useful program, which is time critical and has a single process of filling and array/vector take 90% of the time. However I wonder how you are creating your vector. If you know (even approximately) the eventual number of elements (well you must do if you could use an array) make sure that you declare the vector with sufficient size other wise the process of expanding the vector's storage (requiring copying and consequential additional ctor/dtors) can consume far more time than necessary. In general a vector need not significantly longer to create than does a dynamic array. Modern systems are becoming increasingly more efficient at dynamic allocation so a vector often compare reasonably with a static array when both are options. > >> 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? They aren't they are created dynamically with code such as: (assuming container is a container of a suitable smart_pointer) container[i] = new object; 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 > Sketch solution: std::vector<smart_pointer<object> > maker(int size){ std::vector<smart_pointer<object> > cont(size); for(int i(0); i != cont.size(); ++i){ cont[i] = new object; } return cont; } Now it may seem that this results in copying the vector on return from the function, however some compilers will manage to avoid that by constructing cont in the space allocated for the return. That is today. but any compiler that implements move semantics will avoid copying the contents anyway because it will just move the body to the returned version. However note that were you to just use an array you would still have problems with returning it and would lose the advantage of move semantics. That puts vectors way ahead when you are going to create the container in one place and use it in another. -- Note that robinton.demon.co.uk addresses are no longer valid. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Goran on 4 Feb 2010 17:35 On Feb 4, 10:34 pm, NL <norv...(a)gmail.com> wrote: > 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. That's more precise, but still not enough for e.g. me to give more precise answer. These 90%, that's 90% of what, of your target time for "filling the vector"? Also, is that 90% of your current solution? If answer to both is "yes", perhaps you have a lot of copying going on? If so, can you work on avoiding that instead? (I am asking this because one of best ways to get better performance __anywhere__ is to avoid copying). Here's what I also wonder: is your data max set size known at compile- time? If so, are you happy with memory usage? If so, there is no point in using a vector at all. If the answer to any of these two questions is "no", then you __should__ consider using a vector. Given that you have numFoo, number of elements is not fixed. Also, at least from the code shown, you don't ever remove them, and you can't remove stuff from the middle using what you've shown. So, how does "filling" look like? If you have a big fill somewhere at ramp-up, then having empty Foo() and using resize() instead of a push_back loop would give you pretty much same speed (difference is one trip to heap). If, on the other hand, GetNextFoo() happens occasionally while running, and you do want to minimize heap pressure, it's difficult to beat simple push_back. If you don't care much about heap usage, then reserve might give you better more speed. At any rate, all these questions are best answered by you, because you know your situation best, and you are not explaining it in great detail here, either. Also, STL containers have rather nicely defined performance characteristics, that should be your guide for these things. > > 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, To achieve similar with vector, use reserve(). > with a vector I'll need to do > the same, but then copy the memory to another location.) If that's your question, use empty Foo constructor and resize(), e.g. struct Foo { Foo() {} } typedef std::vector<Foo> Foos; .... Foos foos(some_initial_size); // resize() is here. for (Foos::iterator p=foos.begin(); p!=foos.end(); ++p) { Foo& foo = *p; foo.x = blah; foo.y = blahblah; //... } Goran. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Brian on 4 Feb 2010 17:34 On Feb 4, 7:14 am, Goran <goran.pu...(a)gmail.com> wrote: > 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?"). I think you're going overboard here. Fixed-size storage is one way to describe a uint32_t. I don't think you would suggest avoiding fixed-size integer types. In other cases where requirements give a specific number of some thing, it seems at least possibly, like a good idea to model that with some fixed-size storage. Brian Wood http://webEbenezer.net (651) 251-9384 -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Kirill_Lykov on 4 Feb 2010 17:35 On Feb 4, 4:41 am, 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? > > 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? { edits: quoted banner removed. please remove irrelevant text b4 posting. -mod } There are other containers in stl which may be more acceptable for your purposes. For instance, you may use deque instead of using vector. Due to deque implementation it doesn't need additional copying. In addition, you may use std::tr1::array, which is useful is you want to place your data in stack. Although you may decrease the time of copying while you use vector it is no way to escape copying. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Francis Glassborow on 5 Feb 2010 02:46
Goran wrote: > On Feb 4, 10:34 pm, NL <norv...(a)gmail.com> wrote: >> 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. > > That's more precise, but still not enough for e.g. me to give more > precise answer. These 90%, that's 90% of what, of your target time for > "filling the vector"? Also, is that 90% of your current solution? > > If answer to both is "yes", perhaps you have a lot of copying going > on? If so, can you work on avoiding that instead? (I am asking this > because one of best ways to get better performance __anywhere__ is to > avoid copying). > > Here's what I also wonder: is your data max set size known at compile- > time? If so, are you happy with memory usage? If so, there is no point > in using a vector at all. > > If the answer to any of these two questions is "no", then you > __should__ consider using a vector. > > Given that you have numFoo, number of elements is not fixed. Also, at > least from the code shown, you don't ever remove them, and you can't > remove stuff from the middle using what you've shown. So, how does > "filling" look like? If you have a big fill somewhere at ramp-up, then > having empty Foo() and using resize() instead of a push_back loop > would give you pretty much same speed (difference is one trip to > heap). > > If, on the other hand, GetNextFoo() happens occasionally while > running, and you do want to minimize heap pressure, it's difficult to > beat simple push_back. If you don't care much about heap usage, then > reserve might give you better more speed. Think that one through. Push_back is fine as long as there is an unused reserve but places a great deal more pressure on the heap when there isn't. > > At any rate, all these questions are best answered by you, because you > know your situation best, and you are not explaining it in great > detail here, either. Also, STL containers have rather nicely defined > performance characteristics, that should be your guide for these > things. > >>> 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, > > To achieve similar with vector, use reserve(). Well reserve is one way, another is to create a sufficiently large vector at declaration time (if you know how big it needs to be). -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |