Vector Capacity
Author
I'm running into vector resize problems. I created an instancing engine for my objects, but the problem is that the animations on all my objects reset to their initial states when the vector resizes. ( I have heard about Vector speed problems with push_backs lagging when they are called hundreds of times per frame, but unfortunately it seems the only true dynamic array). Anyway, When I vector resizes, what happens? Does it invoke copy constructors to transfer the data over from one memory chunk to another? That would explain why this is happening (it would mean I would need a better copy constructor. Or does it use operator=?
Either way, is it a bad thing to declare a large size in advance? That might help.
(Also, is anything faster than a vector. So far I am happy with it( since my program still runs at about 300fps with 1077 objects animating), but I remember reading something about system optimization and it said to stay away from anything stl since it is very slow... which surprised me.
Thanks for the advice!
Types used with std::vector must have both valid assignment operators and copy constructors. When the capacity of a std::vector changes, the values in the existing vector will be copy constructed in the new storage.
When a vector resizes due to .resize or .push_back (or .pop_back):
1) If the new size() is less than the existing capacity() (i.e. the memory it already has is sufficient to hold that many elements), the only thing that happens is any relevant constructors or destructors for elements are called, and the pointer/size variable is adjusted. No reallocation on behalf of std::vector.
2) If the new size() is greater than the existing capacity() (i.e. needs more memory), it will resize it's existing memory amount by some factor of the existing amount (common sizes are 1.5x or 2x). This means that adding elements is an amortized constant time operation.
3) When this change of capacity() occurs, yes, the copy constructor will be called once for each element.
4) The Standard C++ Library of which the STL is now a part of has taken many performance considerations into it's very design. 95% of the "oh noes STL is slow~~" people have no clue while they're talking about. And frankly, until you can know for yourself as fact the various reasons you might want to avoid STL components in certain situations, you're not going to be able to do better than it.
(There is a lot of outdated fearmongering about the STL, some of which was valid some 10, 20 years ago, when C++ was new and optimizers weren't where they are today, and even a good bit of that was plain wrong even then.)
1) If the new size() is less than the existing capacity() (i.e. the memory it already has is sufficient to hold that many elements), the only thing that happens is any relevant constructors or destructors for elements are called, and the pointer/size variable is adjusted. No reallocation on behalf of std::vector.
2) If the new size() is greater than the existing capacity() (i.e. needs more memory), it will resize it's existing memory amount by some factor of the existing amount (common sizes are 1.5x or 2x). This means that adding elements is an amortized constant time operation.
3) When this change of capacity() occurs, yes, the copy constructor will be called once for each element.
4) The Standard C++ Library of which the STL is now a part of has taken many performance considerations into it's very design. 95% of the "oh noes STL is slow~~" people have no clue while they're talking about. And frankly, until you can know for yourself as fact the various reasons you might want to avoid STL components in certain situations, you're not going to be able to do better than it.
(There is a lot of outdated fearmongering about the STL, some of which was valid some 10, 20 years ago, when C++ was new and optimizers weren't where they are today, and even a good bit of that was plain wrong even then.)
Author
Basically what I'm hearing here is
Make copy constructors, follow the rules of three and singular responsibility, and don't worry about stl efficiency?
Sounds good to me.
Make copy constructors, follow the rules of three and singular responsibility, and don't worry about stl efficiency?
Sounds good to me.
<offtopic importance="utterly-low" canskip="true" lang="en-US">
I would say that fear of the STL 20 years ago was probably less stronger than what one would imagine (first presentation of the C++ version seemed to have occurred in 1992-1993; presentation to the C++ committee took place in 94 or 95 IIRC).
Now, I'm going to hide under the table to avoid your wrath [grin].
Anyway, 10 years ago, the C++ language was not even considered as a valid language to develop application. The whole language was deemed as "too slow" by a lot of (fearful?) professionals.
</offtopic>
Quote:Original post by MaulingMonkey
(There is a lot of outdated fearmongering about the STL, some of which was valid some 10, 20 years ago, when C++ was new and optimizers weren't where they are today, and even a good bit of that was plain wrong even then.)
I would say that fear of the STL 20 years ago was probably less stronger than what one would imagine (first presentation of the C++ version seemed to have occurred in 1992-1993; presentation to the C++ committee took place in 94 or 95 IIRC).
Now, I'm going to hide under the table to avoid your wrath [grin].
Anyway, 10 years ago, the C++ language was not even considered as a valid language to develop application. The whole language was deemed as "too slow" by a lot of (fearful?) professionals.
</offtopic>
Can you post the syntactic definition of your vector, and how you use it.
You shouldn't be doing any push_backs during execution. If you are, you might be using the wrong structure.
Vector is an array. Nothing more. As such, there's little to be gained from optimizing things there. If anything, the problem is with the algorithm.
Also, the resizing and copy constructor sound suspicious. There should be no need whatsoever to do that per frame. During initialization, but not during rendering.
You shouldn't be doing any push_backs during execution. If you are, you might be using the wrong structure.
Vector is an array. Nothing more. As such, there's little to be gained from optimizing things there. If anything, the problem is with the algorithm.
Also, the resizing and copy constructor sound suspicious. There should be no need whatsoever to do that per frame. During initialization, but not during rendering.
Usually when putting any entities in containers, I use pointers (shared or bare) in them. Copying pointers around is fast and cheap.
This is especially true if you need a reference to the object somewhere else. If not, you can store boost::shared_ptr<> objects of you animations in your container.
Also keep in mind which container is good for what. std::set is fast for look-ups and "random" insertions and removals. std::vector is only fast when appending and removing the last element (but you incur a copy overhead if the internal structure is resized).
This is especially true if you need a reference to the object somewhere else. If not, you can store boost::shared_ptr<> objects of you animations in your container.
Also keep in mind which container is good for what. std::set is fast for look-ups and "random" insertions and removals. std::vector is only fast when appending and removing the last element (but you incur a copy overhead if the internal structure is resized).
Quote:Original post by Plasmarobo
Basically what I'm hearing here is
Make copy constructors, follow the rules of three and singular responsibility, and don't worry about stl efficiency?
Sounds good to me.
Following the rule of singular responsibility usually results in not having to put any effort into the rule of three, though, due to things like smart pointers.
Could we have a look at your class as it stands?
<offtopic importance="utterly-low" canskip="true" lang="en-US">
August 1994.
Not really. I recall that C++ was widely used for Windows application development at least as early as '93 or '94, with frameworks like MFC and OWL. By 1997, C++ definitely was widespread for application development in the business domain. Not so much in the game development arena admittedly.
</offtopic>
Quote:Original post by Emmanuel Deloget
presentation to the C++ committee took place in 94 or 95 IIRC).
August 1994.
Quote:
Anyway, 10 years ago, the C++ language was not even considered as a valid language to develop application. The whole language was deemed as "too slow" by a lot of (fearful?) professionals.
Not really. I recall that C++ was widely used for Windows application development at least as early as '93 or '94, with frameworks like MFC and OWL. By 1997, C++ definitely was widespread for application development in the business domain. Not so much in the game development arena admittedly.
</offtopic>
Author
Quote:Original post by Zahlman
Could we have a look at your class as it stands?
My class as it stands is basically an encapsulation for an std::vector of loaded objects, with a separate vector for instances. I can't use pointers because they caused instancing problems (I was using them before, but I found that I had to reload the object every time I wanted to instance it). Here is the header for this particular class, but without my other code it won't make much sense:
class cObjects { protected: std::map<int, cObject2d*> m_objects; std::vector<cInst2d> m_instances; long m_size; public: cObjects() { m_objects.clear(); m_size = 0; } ~cObjects() { std::map<int, cObject2d*>::iterator iter; for(iter = m_objects.begin(); iter != m_objects.end(); iter++) { delete iter->second; iter->second = NULL; } m_objects.clear(); m_size = 0; } bool Load(LPCSTR dir, int id, cGraphics *graphics); //Load an object and register it bool LoadAll(LPCSTR dir, cGraphics *graphics); //Load the object list and register each object bool Save(LPCSTR dir); //Save the object list void Draw(int id, cGraphics *graphics); //Draw an object by name void AddObject(cObject2d* obj, int id, cGraphics *parent); //A pointer to a allocated object (nulls pointer) void AddObject(cObject2d* obj, cGraphics *parent) { AddObject(obj, m_size +1, parent); } void CreateObject(std::string anim, std::string texture, CORE::cGraphics *parent); void CreateObjectVerbose(std::string anim, std::string texture,float x, float y, int z, int index, int width, int height, float sx, float sy, float r, cGraphics *parent); void DrawAllLoaded(cGraphics *graphics); void AnimateAllLoaded(float now); void CopyObject(cObject2d *obj,cGraphics *parent); int CreateInstance(int id); bool ShowInstance(int id); bool HideInstance(int id); void Process(cGraphics *graphics, float now); //Send instance data to the rendering core int CopyInstance(int id); cObject2d *AccessInstance(int id) { return &m_instances[id].obj; } cObject2d *GrabObject(int id) { return m_objects.find(id)->second; } int Debug_Capacity() {return m_instances.capacity();} };That's it. It works well for me. I might need to redesign it when I make my move into the world of three dimensions, but as it stands... I'm pretty happy with it.
I'm more worried about automating it :(
Here are the Object and Instance classes, just so you can get a look at my copy constructors:
class cObject2d : public cBase2d { protected: friend class cObjects; int m_id; //Information for loading and registering std::string m_animdir; public: cObject2d() : cBase2d() { m_id = 0; m_animdir.clear(); } cObject2d(const CORE::cObject2d &rhs) { m_animdir = rhs.m_animdir; m_animation = new cAnimation2d; m_id = rhs.m_id; m_cx = rhs.m_cx; m_cy = rhs.m_cy; m_dir = rhs.m_dir; m_h = rhs.m_h; m_index = rhs.m_index; m_r = rhs.m_r; m_sc = rhs.m_sc; m_sx = rhs.m_sx; m_sy = rhs.m_sy; m_w = rhs.m_w; m_x = rhs.m_x; m_y = rhs.m_y; m_z = rhs.m_z; m_animation->Load(rhs.m_animdir); m_animation->SetFrame(m_index,m_animation->GetCurrentFrame(m_index),m_animation->GetCurrentRow(m_index)); } ~cObject2d() { m_animdir.clear(); delete m_animation; m_animation = NULL; m_id = 0; } virtual void Clone(const cObject2d &rhs); virtual bool Register(cGraphics *graphics); virtual bool Save(std::ofstream &file); //Write this to a file virtual bool Load(std::ifstream &file); //Load this from a file, and aquire animation data virtual bool Load(std::ifstream &file, unsigned long offset); virtual bool LoadAnimation(LPCSTR dir) { m_animdir = dir; m_animation->Zero(); return m_animation->Load(m_animdir); } virtual bool LoadAnimation() { return m_animation->Load(m_animdir); } void operator=(const cObject2d &rhs) { m_animdir = rhs.m_animdir; delete m_animation; m_animation = NULL; m_animation = new cAnimation2d; m_id = rhs.m_id; m_cx = rhs.m_cx; m_cy = rhs.m_cy; m_dir = rhs.m_dir; m_h = rhs.m_h; m_index = rhs.m_index; m_r = rhs.m_r; m_sc = rhs.m_sc; m_sx = rhs.m_sx; m_sy = rhs.m_sy; m_w = rhs.m_w; m_x = rhs.m_x; m_y = rhs.m_y; m_z = rhs.m_z; m_animation->Load(rhs.m_animdir); m_animation->SetFrame(m_index,m_animation->GetCurrentFrame(m_index),m_animation->GetCurrentRow(m_index)); } }; struct cInst2d { CORE::cObject2d obj; //Actual object, since it must hold it's own data bool draw; //The draw flag. cInst2d() { draw = false; } cInst2d(const cObject2d &object) { obj.Clone(object); draw = false; } ~cInst2d() { draw = false; ZeroMemory(&obj, sizeof(CORE::cObject2d)); } cInst2d(const cInst2d &rhs) { obj = rhs.obj; draw = rhs.draw; } void operator=(const cInst2d &rhs) { obj = rhs.obj; draw = rhs.draw; } void operator=(const cObject2d &object) { obj.Clone(object); draw = false; } }; //and instance + flags structure Those are my classes. I'm not quite sure why it resets on every resize. I'm explicitly copying the frame over in both the operator = and copy constructor;
[Edited by - Plasmarobo on July 11, 2007 6:31:56 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
