Skip to main content
GameDev.net gamedev.net
🔒 Locked

Which would be better? for a renderlist vector or list

Started by MARS_999 Jun 21, 2012 at 12:14 AM 2 replies 1.2k views
Original Post
MARS_999
MARS_999
I am not sure which way is faster, but I populate a std::list to be rendered. The list just holds the pointer as a main std::list<> holds the actual dynamic allocated memory objects. So each frame I check the main list against the viewing frustum and push() the object on that list and after each frame clear() the render list and populate again based on whats visible...

So would it be faster to use a vector or list based on this method? I am assuming not much difference? What I don't know is there much overhead for pushing just a pointer without "new" in a container class? Wouldn't it be just as fast a a normal variable?

Thanks!
_the_phantom_
_the_phantom_
The problem with a list isn't the pushing of the object - it is the cost of pulling data out of that list as you walk along it.
(well, ok, the holding would also be a problem as I'm pretty sure the container would have to 'new' a piece of memory the size of a pointer to hold the data + list book keeping information for each 'push' which could cost as well).

Memory allocated to hold elements in a list can be 'anywhere' in memory, which means right away access it is going to cost you a cache miss. You then have to use that pointer to grab another chunk of data, again 'anywhere' in memory and going to cost you. Memory access is basically very slow when compared to ALU speed - CPUs try to compensate by reading ahead but when bouncing all over memory as you'll do in this system you don't help them one bit.

A better system would be a vector of pointers : the pointers themselves would be contiguous in memory although you'd still take a hit to go and find the memory to work with.

The 'best' system would involve using small structures to store JUST the rendering information required - that way the rendering part isn't reading redundant data, the CPU can happily read ahead and pre-fetch things into cache for you and things should generally be faster.

However as stop gap I'd go with a vector of pointers - not ideal but it'll cost you less in memory problems in the short term and remove the constant 'new' problem as you'd only have to 'clear' the vector and not release all the nodes and reclaim memory as with the list method.
Krohm
Krohm
I put drawcall information in [font=courier new,courier,monospace]std::vector[/font]. Each entry contains stuff going to DrawIndexedPrimitive+some additional data for stream and shader setup, I guess it's about 100+ bytes each, where copy can be performed by [font=courier new,courier,monospace]memcpy[/font]. Because of the way std::vector works, each [font=courier new,courier,monospace]push_back [/font]is essentially a memcpy (re-allocations are amortized on multiple calls) and thus very fast.
Back when I used renderables, I had to go with a vector of shared pointers. Pretty much like [font=courier new,courier,monospace]std::vector[/font], which is what phantom suggests above. As the current drawcall information references some external structures as well, I guess getting the data is relatively similar in performance.In general, it didn't matter to me: nothing of this ever showed up in the profiler (I stopped looking at stuff taking less than 0.5% of samples).

Personally I am quite surprised you managed to work with generic objects being pushed to a list of [font=courier new,courier,monospace]Renderable [/font]objects. I experienced quite some stir with this approach in the past. I'm currently allowing only drawcalls to be queued, each component provides them and once they are them, they are supposed to be rendered (the filter happens before adding).
Previously "Krohm"
MARS_999
MARS_999
Yeah so far works great! I just have a main std::list that holds all the master list of dynamic allocated objects for the game, and then I use a vector now was a list based on phantoms suggestion to hold the copy of the pointer to render the objects in view. So far no notice in speed but I never profiled the code before to see, just figured this was some common knowledge on which one would faster.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.