I want to know which is the best way to store and store the objects in my engine.
Ive got a scene manager class, and I dont know how many objects there will be in my game to I create a std::list of objects and keep adding the object I need.
To sort the objects I calculate the distance between the object and and eye position.
Is it ok to use an std::list or should I store the objects differently?
Storing and sorting objects on my engine
No, it's really not ok to use a list for your scene manager. Too much overhead and way too slow because of memory fragmentation. Use a std::vector of pointers to your game objects. Reserve some space up front (vector.reserve()). A vector will be enormously faster thanks to contiguous memory allocation. Now, for sorting, you can use std::sort on the vector. The STL algorithms work well! Use them. You'll need to make a function that takes two pointers to your game object class and returns the Boolean value of a depth-comparison between them. You'll need to pass that function to the sort function so that the algorithm knows how to compare depths.
Hope that gives you an idea of how to approach it!
Hope that gives you an idea of how to approach it!
Quote:
...and way too slow because of memory fragmentation. Use a std::vector of pointers to your game objects.
A vector of pointers is bad for fragmentation too.
At least use something like boost::pool for allocating those pointers to help reduce fragmentation.
Quote:Original post by KulSeranQuote:
...and way too slow because of memory fragmentation. Use a std::vector of pointers to your game objects.
A vector of pointers is bad for fragmentation too.
At least use something like boost::pool for allocating those pointers to help reduce fragmentation.
Of course, if the pointers are allocated carelessly. I should have been more clear - use a memory pool!
Still, lists have more overheard regardless.
Author
so I will use a std::vector, my question now is:
I created a vector of elements of this structure:
And I want to sort the elements of the vector by distanceToCameraPosition;
So how do I use the sort() function in a std::vector<Object> and sort it the distanceToCameraPosition?
I created a vector of elements of this structure:
struct Object{ ID3DX10Mesh* mesh; D3DXVECTOR3 position; float distanceToCameraPosition;}And I want to sort the elements of the vector by distanceToCameraPosition;
So how do I use the sort() function in a std::vector<Object> and sort it the distanceToCameraPosition?
std::sort. It takes a range to sort on, and optionally, a comparison operator.
If it makes sense in context, you can overload operator < and std::sort will just work. If that doesn't make sense, or you need more information at the time of comparison, wrap everything into a comparison function object.
If it makes sense in context, you can overload operator < and std::sort will just work. If that doesn't make sense, or you need more information at the time of comparison, wrap everything into a comparison function object.
class CompareObjects{ CompareObjects() {} bool operator ()( const Object &a, const Object &b ) { return a.distanceToCameraPosition < b.distanceToCameraPosition; }};//...std::vector<Object> vec;//...std::sort( vec.begin(), vec.end(), CompareObjects() );
Hi,
i want to hear more arguments as to why not using list (of pointers) for this "thing".
i was reading from this page (among others) and have concluded that list have all
"attributes" that i need vs. vector witch i have found to be difficult for me to
use/implement into my test projects (i am beginner so i might overlooked some things).
i want to hear more arguments as to why not using list (of pointers) for this "thing".
i was reading from this page (among others) and have concluded that list have all
"attributes" that i need vs. vector witch i have found to be difficult for me to
use/implement into my test projects (i am beginner so i might overlooked some things).
What are all of the use cases that you intend to use the collection for? Different containers are good for different things. In most cases, sorting a vector will be faster than sorting a list just because of memory continuity which helps leverage the cache better. It is however possible to also get similar performance from a list if you privide a memory pool allocator to the list. Ultimately even in the best case the list would still being doing just an ounce more work during the sort since it has to assign next/previous pointers asside from just the data. It's pretty easy to throw together a sort test with roughly the same size data and same number of objects as you expect and see how the two options compare. The results might be interesting.
You might have other goals for the collection that you didn't list here which could ultimately result in different recomendations. Problems in isolation often have different solutions than what results in real world scenarios.
You might have other goals for the collection that you didn't list here which could ultimately result in different recomendations. Problems in isolation often have different solutions than what results in real world scenarios.
After some research/testing i have realized that you are right.
Found some performance measure code on this forum and used it
in my test project:
output from console:
btw. is this "valid" way to do performance analisis?
EDIT: this results are from Debug build, with Release (Full Optimization /Ox
and Favore Fast code /Ot) i got similar result where vector is almost 2.5x faster.
[Edited by - brega on October 13, 2010 5:13:32 AM]
Found some performance measure code on this forum and used it
in my test project:
#define _CRT_RAND_S#include <vector>#include <list>#include <iostream>#include <algorithm>#include <functional>#include <windows.h>using namespace std;class Object{private: float DistToCam;public: Object() { DistToCam = 0.0f; } ~Object() { } explicit Object(float d) { Set(d); } Object(const Object& other) { *this = other; } Object& operator = (const Object& other) { if(this != &other) { Set(other.DistToCam); } return *this; } void Set(float d) { DistToCam = d; } bool operator > (const Object& other) const { return DistToCam > other.DistToCam; } bool operator < (const Object& other) const { return DistToCam < other.DistToCam; } struct BackToFront : public binary_function<Object*,Object*,bool> { bool operator () (Object* left, Object* right) { return (*left > *right); } }; struct FrontToBack : public binary_function<Object*,Object*,bool> { bool operator () (Object* left, Object* right) { return (*left < *right); } };};float Random(float maxf){ float numOut(1.0f); UINT num(1); errno_t err = rand_s(&num); if(0 == err) { numOut = (float)num / (float)UINT_MAX * maxf; } return numOut;}int main(){ const UINT NumObjects = 5000; LARGE_INTEGER before, after, frequency; list<Object*> lObj; list<Object*>::iterator iLObj; for(UINT i = 0; i < NumObjects; i++) { Object* pObj = new Object(Random((float)NumObjects * 2.0f)); lObj.push_back(pObj); } QueryPerformanceCounter(&before); lObj.sort(Object::BackToFront()); QueryPerformanceCounter(&after); after.QuadPart -= before.QuadPart; QueryPerformanceFrequency(&frequency); cout << "list sort time: " << (double)after.QuadPart / (double)frequency.QuadPart << "s" << endl; for(iLObj = lObj.begin(); iLObj != lObj.end(); iLObj++) { Object* pObj = *iLObj; delete (pObj); pObj = 0; } vector<Object*> vObj; vector<Object*>::iterator iObj; for(UINT i = 0; i < NumObjects; i++) { Object* pObj = new Object(Random((float)NumObjects * 2.0f)); vObj.push_back(pObj); } QueryPerformanceCounter(&before); sort(vObj.begin(), vObj.end(), Object::BackToFront()); QueryPerformanceCounter(&after); after.QuadPart -= before.QuadPart; QueryPerformanceFrequency(&frequency); cout << "vector sort time: " << (double)after.QuadPart / (double)frequency.QuadPart << "s" << endl; for(iObj = vObj.begin(); iObj != vObj.end(); iObj++) { Object* pObj = *iObj; delete (pObj); pObj = 0; } cin.get(); return 0;}output from console:
list sort time: 0.300784svector sort time: 0.126097sbtw. is this "valid" way to do performance analisis?
EDIT: this results are from Debug build, with Release (Full Optimization /Ox
and Favore Fast code /Ot) i got similar result where vector is almost 2.5x faster.
[Edited by - brega on October 13, 2010 5:13:32 AM]
The main thing about performance analysis is telling what it's worst case complexity is using an induction proof. O(n) might be slower than O(n lg n) for default sizes but O(n^2) as a worst case is dangerous even for small collections. I use in place heap sort with O(n lg n) complexity.
Linked lists are one of the worst datastructures for sorting because most sorting algorithms (Quick sort for example) require random access in constant time.
I use a padded dynamic array of pointers for my graphics engine and it can do insertion and deletion in constant time. There is no fragmentation from deleting because pointers have the same size and can swap places to fill any gaps. I only reallocate new memory when I run out of memory, and that only occur when loading a larger level.
Insert:
By increasing the counter, allocating if needed and filling the last space.
Delete:
By swaping place between the removed pointer and the last pointer, free the last element and decrease the counter.
Delete all:
By freeing all pointers and set the counter to 0.
Linked lists are one of the worst datastructures for sorting because most sorting algorithms (Quick sort for example) require random access in constant time.
I use a padded dynamic array of pointers for my graphics engine and it can do insertion and deletion in constant time. There is no fragmentation from deleting because pointers have the same size and can swap places to fill any gaps. I only reallocate new memory when I run out of memory, and that only occur when loading a larger level.
Insert:
By increasing the counter, allocating if needed and filling the last space.
Delete:
By swaping place between the removed pointer and the last pointer, free the last element and decrease the counter.
Delete all:
By freeing all pointers and set the counter to 0.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
