Sign in to follow this  
extraneus

Collecting objects with STL fast?

Recommended Posts

Hello! Each frame I want to collect a number of objects fast. The problem is that i dont know the actual number of objects and i dont want to allocate new memory for the vector each time of a new loop. I have written my own dynamic vector class of pointers which allocates a bigger array each time the array is full. I have a counter which i set at the beginning of each frame to 0. The good thing is that no new memory gets allocated for each frame i just set the counter to 0. Appending this way is very fast... The problem is that i now want to move to the STL but i cannot figure out how to make this very easy task with the STL. For example with lists each insertion would allocate a new node, would set pointers etc. Using vectors I dont know how to set the size to 0 without resitzing the whole array which i dont want to do. I just wanted to set the size of the vector to 0 without resizing the vector. How could i do that? Thank you a lot!!!

Share this post


Link to post
Share on other sites
Presumably your counter is to count the number of objects you've added to the array? The equivalent for the STL vector is the size() method which returns the number of items in the vector.

Now when you say that you set the counter to 0, do you mean you want to empty the array but without releasing the allocated memory? If so then then the clear() method will do this.

Share this post


Link to post
Share on other sites
std::vector.resize(0) just resets the size to 0, the capacity remains, no memory is freed. don't use clear(), as it is commonly implemented to free the allocated memory. In msvc2003 .clear() didn't free the memory, but that changed in msvc2005, where it now does, and I believe gcc and other implementations also commonly free memory with clear(), resize(0) is what you want.

filling and resize(0) a vector is about the fastest option.

Share this post


Link to post
Share on other sites
Quote:
Original post by DrEvil
std::vector.resize(0) just resets the size to 0, the capacity remains, no memory is freed. don't use clear(), as it is commonly implemented to free the allocated memory. In msvc2003 .clear() didn't free the memory, but that changed in msvc2005, where it now does, and I believe gcc and other implementations also commonly free memory with clear(), resize(0) is what you want.

filling and resize(0) a vector is about the fastest option.

In VC++2005 Express calling clear doesn't deallocate the memory.
In-fact I believe that clear is meant to call erase( begin(), end()) and erase will not deallocate memory thus neither does clear.
However resize may actually allocate/deallocate memory.
I'm no standards guru though.

Share this post


Link to post
Share on other sites
It's been a while, I think I got it backwards. 2003 freed the memory and 2005 doesn't I think. The point still stands though, that it is implementation defined, and resize(0) I think is the more commonly accepted way to do that.

Edit: Yes just confirmed. 2003 frees the memory 2005 doesn't. I believe someone else has mentioned before that some other platform, I want to say some version of GCC frees the memory as well, but I don't recall specifically.

Share this post


Link to post
Share on other sites
Hmm, I'm still not convinced.
I think the standard semantics of clear() are that the capacity remains the same and the size will equal 0.
Whereas for resize(N) the capacity is atleast equal to N and size is at most equal to N.

If so, and 2003 releases the memory during a clear, then it's not being standards compliant.

Share this post


Link to post
Share on other sites
You may be right. Moreso than whether or not msvc2003 was compliant or not it's been discussed and documented in several optimization papers, such as a presentation at GDC2004 about stl misuse in games, that resize(0) seems to be the most accepted method. clear() may be equally acceptable if properly implemented, which may be safe to assume these days.

Share this post


Link to post
Share on other sites
Contrary to what I said before, I do not think resize will ever deallocate memory, meaning that resize(0) should preserve the capacity as intended.

That said, if clear() is implemented correctly - by that I mean it calls erase(begin(), end()); (whether that is standards defined or not I don't know) - it would be marginly more efficient than resize(0) due to it not needing to check for growth.

For reference: VC++2008 behaves as VC++2005 and the capacity is preserved upon a clear. [smile]

Share this post


Link to post
Share on other sites
Surprisingly, getting the standard C++ vector to release memory is nontrivial. The common idiom to do so is the "swap trick": myVector.swap(vector<int>()) to clear the vector and release its memory, or myVector.swap(vector<int>(myVector)) to trim the capacity to the current size.

Share this post


Link to post
Share on other sites
Quote:
Original post by extraneus
Hello!

Each frame I want to collect a number of objects fast. The problem is that i dont know the actual number of objects and i dont want to allocate new memory for the vector each time of a new loop.

I have written my own dynamic vector class of pointers which allocates a bigger array each time the array is full.


To me, this sounds like:

"I'm worried about performance. I don't want std::vector to allocate new memory on every iteration of the loop, so I made my own custom class that allocates new memory on every iteration of the loop. I am, meanwhile, unaware that the normal, simple usage of std::vector would not allocate new memory on every iteration."

Or were you talking about the outer (per-frame) loop?

Share this post


Link to post
Share on other sites
Quote:
Each frame I want to collect a number of objects fast. The problem is that i dont know the actual number of objects and i dont want to allocate new memory for the vector each time of a new loop.

I think, std::list suits here better then std::vector

Share this post


Link to post
Share on other sites
Quote:
Original post by Ocelot
Quote:
Each frame I want to collect a number of objects fast. The problem is that i dont know the actual number of objects and i dont want to allocate new memory for the vector each time of a new loop.

I think, std::list suits here better then std::vector


std::list allocates every time an object is added. If avoiding excessive allocation is what you want, std::list is not the way to go.

Share this post


Link to post
Share on other sites
In some cases you are able to use a list that doesn't allocate memory at all. You can achieve this by storing the next/prev pointers in the objects themselves. The trade-off is that such an object can only be at one list at any given time (although it might be possible to extend this).

An example:


// This class is only for convinience, FastList
// will work fine without it
template <class T>
class ListObject {
public:
ListObject():next(NULL), prev(NULL) {}

T *next;
T *prev;
};

template <class T>
class FastList {
public:
FastList():head(NULL), tail(NULL), count(0) {}

void add(T &obj) {
if (!tail)
tail = &obj;

if (head) {
obj.prev = head;
head->next = &obj;
}
head = &obj;

++count;
}

void remove(const T &obj) {
if (obj.next)
obj.next->prev = obj.prev;
if (obj.prev)
obj.prev->next = obj.next;

--count;

if (tail == &obj)
tail = obj.next;
}

const T* first() const { return tail; }

int size() const { return count; }

private:
T *tail; // Points to first element
T *head; // Points to last element added
int count;
};



Here's a small program to test this class:


class Obj : public ListObject<Obj> {
public:
explicit Obj(int val):id(val) {}

void print() const { cout << id << endl; }

private:
int id;
};

template <class T>
void print(const FastList<T> &list) {
for (const T *head = list.first(); head != NULL; head = head->next)
head->print();

cout << endl;
}

void testFastList() {
FastList<Obj> list;

Obj a(1), b(2), c(3);
list.add(a);
list.add(b);
list.add(c);
print(list);
list.remove(b);
print(list);
}



This was quickly thrown together just now, so it might be buggy, inefficient or use poor style, but it illustrates the concept.

If anyone has any comments or caveats about this class, I'll be happy to hear them.

Share this post


Link to post
Share on other sites
Quote:
Original post by Gage64
If anyone has any comments or caveats about this class, I'll be happy to hear them.


Storing pointers to stack based objects. Unless you are very careful where you use this, it will blow up in your face. It isn't suitable here because the OP doesn't have all the objects preallocated anywhere so they must allocate space for them somewhere.

Share this post


Link to post
Share on other sites

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