template<typename T>
struct Data: public boost::intrusive::list_base_hook<>
{
Data(T _data): data(_data) {};
~Data() {};
T data;
friend bool operator<(const Data<T>& a, const Data<T>& b) { return a.data < b.data; }
};
Data<int> randomInts() { return Data<int>(std::rand()%100); }
template<typename T>
struct TestList
{
TestList(std::vector< Data<int> >& _data)
{
for(std::vector< Data<int> >::iterator it(_data.begin()), itend(_data.end()); it != itend; ++it)
{
data.push_back(*it);
}
};
void operator()()
{
data.sort();
};
T data;
};
int main( int argc, const char* argv[] )
{
std::srand(static_cast<unsigned int>(std::time(0)));
std::vector< Data<int> > data;
std::generate_n(std::back_inserter(data), 10000, randomInts);
TestList< std::list< Data<int> > > stlTest(data);
TestList< boost::intrusive::list< Data<int> > > boostTest(data);
std::clock_t start_time;
start_time = std::clock();
stlTest();
std::cout << "Time: " << static_cast<double>(std::clock() - start_time) / CLOCKS_PER_SEC << std::endl;
start_time = std::clock();
boostTest();
std::cout << "Time: " << static_cast<double>(std::clock() - start_time) / CLOCKS_PER_SEC << std::endl;
return 0;
}
boost intrusive containers - slow?
Author
I've been looking for a good container to hold a dynamic scene in my engine. Since the container will be iterated each frame, fast iteration is key. Further, I want to be able to insert and remove objects at any time. Finally I want the container to be sorted by material/geometry in order to reduce state changes during rendering.
Sofar, I have used STL containers (holding pointers) for this. After looking at boost intrusive containers I was wondering whether they might better suited for performance critical code. They certainly sound promising. However, after a couple of quick tests (iterating, inserting, sorting random integers), I have yet to see one case of a boost intrusive container outperforming an STL container. I'm not claiming that my tests are perfect and I'm certainly no expert at benchmarking. But I'm starting to doubt that intrusive containers would improve performance. This is surprising. I'm wondering if someone around here has experience with intrusive containers and can share his opinion on this.
Before anyone asks, this is the kind of code I used for testing. (But I would rather have an discussion about the containers than the test.)
[Edited by - kloffy on October 13, 2008 11:55:27 AM]
Quote:Original post by kloffy
I've been looking for a good container to hold a dynamic scene in my engine. Since the container will be iterated each frame, fast iteration is key. Further, I want to be able to insert and remove objects at any time. Finally I want the container to be sorted by material/geometry in order to reduce state changes during rendering.
As such, any choice of list<> will be sub-optimal.
To get optimal performance, use some continuous storage, vector or fixed-size array. Pre-allocate them to maximum number of elements, although in case of vector, that might not be needed.
Additionally, in test, list will behave quite well. But in practice, nodes will not be allocated close to each other, so performance will degrade.
Quote:I'm not claiming that my tests are perfect
You didn't post the actual benchmarking functions, but clock() tends to have too low resolution. How long does your test run take? Unless it's a second or more, then the benchmark is likely inaccurate.
Author
Thanks for your input. In the simplest version that I've been playing around with, I am using a set<>, because it is sorted. That is also what keeps me from using a vector<>. As far as I understand sorting a vector<> is relatively expensive. A more complicated setup that I have tried is a map<> with the state information as a key and vector<> as values.
(map{"red cube" -> [instance1 of red cube with transforms, instance2 of red cube with transforms, etc...]})
I can see though, that fast iteration will probably outweigh the benefits of a sorted container, so I am not ruling out switching to vector<>.
I've used mach timing functions in the tests, but I've switched to std::clock when posting the code for brevity.
I'm still interested to hear what experiences users had with intrusive containers.
(map{"red cube" -> [instance1 of red cube with transforms, instance2 of red cube with transforms, etc...]})
I can see though, that fast iteration will probably outweigh the benefits of a sorted container, so I am not ruling out switching to vector<>.
I've used mach timing functions in the tests, but I've switched to std::clock when posting the code for brevity.
I'm still interested to hear what experiences users had with intrusive containers.
I haven't seriously looked at boost's implementation but the point of intrusive containers is that they allow you to do certain things which would be impossible (or simply be disallowed) with non-intrusive containers. But for normal tasks the equivalent STL containers are likely to be far better tuned than boost's half-hearted intrusive containers, so I would've been surprised if the STL hadn't fared better. That is assuming the benchmark function doesn't take advantage of the benefits of these specialized container?
You were talking about trying to decide between storing your objects in a vector for fast iteration, or as a binary tree for sorted access. Well, with intrusive containers you wouldn't have to choose. Simply keep a normal std::vector of objects for fast iteration as well as a separate intrusive set (or hash table, or splay tree) in which you store the same objects.
I'm not saying that it's necessarily a good idea, that would depend on what you're doing with the list as well as when and why it needs to be sorted, but it's a classic example of something you can do with intrusive containers which would be impossible with the traditional containers (without an extra level of indirection anyway.)
You were talking about trying to decide between storing your objects in a vector for fast iteration, or as a binary tree for sorted access. Well, with intrusive containers you wouldn't have to choose. Simply keep a normal std::vector of objects for fast iteration as well as a separate intrusive set (or hash table, or splay tree) in which you store the same objects.
I'm not saying that it's necessarily a good idea, that would depend on what you're doing with the list as well as when and why it needs to be sorted, but it's a classic example of something you can do with intrusive containers which would be impossible with the traditional containers (without an extra level of indirection anyway.)
Why not have a list of object types. Each object type then has a list of associated objects.
You then can sort the object type list once (so all your state changes are minimal) then each object list can just be a vector<> of objects of that type that are active in the level. Since it doesn't have to be sorted, fast O(1) insertion and removal are possible.
You then can sort the object type list once (so all your state changes are minimal) then each object list can just be a vector<> of objects of that type that are active in the level. Since it doesn't have to be sorted, fast O(1) insertion and removal are possible.
Author
@implicit: The boost documentation lead me to believe that intrusive containers offer better performance in general. Like I already said, I'm not sure if it's my benchmark, but I've tried different scenarios and on average intrusive containers required twice the time (or more) as their STL counterparts. One reason for posting this thread was to find out if others would confirm these results. The idea of mixing STL and intrusive containers is interesting, I'll look into that.
@KulSeran: That sounds similar to the solution I tried using a map<>. Actually that is the best solution I have so far, so I may end up using something like this. Thank you for your suggestion!
@KulSeran: That sounds similar to the solution I tried using a map<>. Actually that is the best solution I have so far, so I may end up using something like this. Thank you for your suggestion!
While looking for another presentation on same topic, I stumbled onto relveant discussion about the actual problem of scene sorting (not the container implementation).
Author
Quote:Original post by Antheus
While looking for another presentation on same topic, I stumbled onto relveant discussion about the actual problem of scene sorting (not the container implementation).
That link is very interesting! If you find the other presentation make sure to post it as well.
Here's a test that I ran that had different results than yours:
Re: intrusive container performance example
I wonder if that was because I was using an early version of the library.
Re: intrusive container performance example
I wonder if that was because I was using an early version of the library.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
