Sign in to follow this  

Vector Capacity

This topic is 3813 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
<offtopic importance="utterly-low" canskip="true" lang="en-US">
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>

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
<offtopic importance="utterly-low" canskip="true" lang="en-US">
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>

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
This should work if
Quote:
m_animation->SetFrame(m_index,m_animation->GetCurrentFrame(m_index),m_animation->GetCurrentRow(m_index));
does what it should do.

Are you sure SetFrame() works properly?

Share this post


Link to post
Share on other sites
Quote:
Original post by Plasmarobo
My class as it stands is basically an encapsulation for an std::vector of loaded objects, with a separate vector for instances.


This is already sounding strange. To OOP folk, "instance" and "object" are synonymous.

Quote:
Here is the header for this particular class, but without my other code it won't make much sense:
*** Source Snippet Removed ***
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 assume the map "owns" the pointed-at objects. Your object class shouldn't have to know about the containing "objects" class. Also, you shouldn't be tracking a size yourself, because vectors and maps already know their size. Oh, and it's actually very unusual to need .clear() on standard library containers. Certainly it's pointless to do in a constructor, because members of the class are default-constructed by default (oddly enough), and a default-constructed map or vector doesn't contain anything to be .clear()ed out. Oh, and PLEASE get rid of all these leading 'c's on your class names. Calling code should not care that the thing in question is a class; it cares only about the interface.

I'm also worried about this:

void AddObject(cObject2d* obj, int id, cGraphics *parent); //A pointer to a allocated object (nulls pointer)


If you set the pointer to null within the function, the calling code WILL NOT see that. You need to pass the pointer by reference to get that effect. Although I think you're already doing strange things here anyway. Why not just pass the constructor arguments to AddObject, and have the container create the new object to add?

Quote:

Here are the Object and Instance classes, just so you can get a look at my copy constructors


OK, it looks like you're trying to use the virtual clone idiom, but getting it completely wrong. The way this normally works is:

- Think of "object" as an implementation helper for "instance". The instance holds a *pointer* to an object, and either owns the pointed-at object, or shares it via boost::shared_ptr or equivalent. The interface of the instance simply delegates to the object.

- The object::clone() accepts no arguments, and returns a pointer to a new (in the keyword sense) object that is a clone of the object that was clone()d.

Share this post


Link to post
Share on other sites

This topic is 3813 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this