Archived

This topic is now archived and is closed to further replies.

Subconscious

Speed of std::list?

Recommended Posts

Is std::list made for speed at all? Is it reasonable to create a linked list of 100+ pointers every single frame when you''re running hundreds of frames a second, or would this significantly slow the game down?

Share this post


Link to post
Share on other sites
What are you going to be using the list for?


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
std::list is faster then any list you''d write yourself. The slowest part is the memory allocation for the nodes. You might consider a vector - so long as the vecter is persistent and you only use clear() and push_back(), it will only allocate memory during your first frame, or whenever theres an object-spike. This is too micro though.

The best solution to any ''efficiency'' issue is, of course, to step away from the problem and make the algorithm itself better.

Share this post


Link to post
Share on other sites
It depends on the list implementation. The MSVC++ 6.0 implementation is a good deal slower than stlport''s implementation. I''m using an std::list (the stlport implementation) for my render queue, which creates and clears a list of over 1000 objects, and I haven''t had a noticeable slowdown at all.

Share this post


Link to post
Share on other sites
Well, I'm redesigning my directx 2d engine and I want to batch together all the triangles that use the same texture so I can make less calls to SetTexture and DrawPrimative. Now that my engine is using a bunch of different objects, some having multiple textures, I can't simply sort the list of objects by texture to render them in that order. So, I thought maybe I could make each object in my engine spit out what they need to draw, triangle by triangle, and then I will make a list of triangles, sorting them by what texture they use as the list is being made. Then render the list of triangles, batching as many together as possible.

This would take place every frame though, so basically I would be creating a huge list of pointers every frame.

Edit: What I'm really wondering is whether the slowdown from creating and destroying a huge linked list every frame would be worse than the slowdown from rendering each object by itself with no kind of batching.

[edited by - Subconscious on April 3, 2004 4:23:55 PM]

Share this post


Link to post
Share on other sites
Eeeyike. An element per-triangle in pretty much any STL container is going to be something of a slowdown.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
The slowdown from drawing individual triangles will far outweigh the slowdown from switching textures, especially as it prevents you from using things like triangle lists.

Now; if you had the object stick a pointer to a triangle list into the list, and sorted by texture, you might gain a couple FPS, but only if you have hundreds of texture switches each frame.

Share this post


Link to post
Share on other sites
Deyja, I''m not going to be drawing the triangles individually, I''m just sorting them individually so that I can push all the ones using the same texture into a vertex buffer and draw at once with one DrawPrimitive and one SetTexture

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The minimum permissable speeds of the STL containers is specified in the C++ standard using the O notation (if you''re not familiar with it the number in brackets tells you roughly how many times the operations (not opcodes!) must be performed to complete the required task in the worst case). What I have listed is from memory - but I''m sure it''s about right.

For std::list :
insert anywhere into the chain (front, back or middle) - O( 1 )
find any particular element - O( n * log( n ) )

For std::vector :
insert to the start of the list: O( n )
insert at the end of the list: O( 1 ) if the vector doesn''t need to be enlarged, else O( n )
look up a numbered element: O( 1 )

For either if you have a list of items you want to work through sequentially then you can use iterators that will give you O(1) time to access the next/previous element. If you have a large list you are more likely to get hit with a speed penalty by the vector as it initially allocates some memory for elements, when that''s filled up it allocates a larger chunk & copies what was already in the smaller chunk into the larger chunk and deletes the old chunk of memory. On the other hand a list allocates a new chunk of memory for every insertion. If you have a reasonable idea of the ammount of elements required when you initialise a vector you could specify the number of elements that it should start with, then you could avoid the need for it to expand

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The only cases ever when a linked list has been faster than a vector for me, were special algorithms in which the algorithm traversed the list back and forth, inserting and/or deleting nodes. But I can tell you that that kind of algorithms are RARE and vector is a much better general purpose container (e.g. a vector of pointers, if you need to delete from the middle every not-so-often and you want the elements to stay in fixed memory locations).

Share this post


Link to post
Share on other sites
Heheh... I wrote my own container class, and used it for batching. It worked well, but I could have saved three days if I had just used a superior, already-made one.

Share this post


Link to post
Share on other sites
If it''s just 2d, how many objects do you have? I render thousands of quads every frame, using direct-mode in opengl (glvertex3f and it runs blazingly fast...

Share this post


Link to post
Share on other sites
Bear in mind that big-O notation doesn''t tell you how efficient an algorithm is, only its time complexity.

So it only expresses, by a factor of what, does the time taken increase as the size of the problem increases.

It''s sometimes better to have an algorithm with a worse big-O, if you know the size of the problem in advance (and it will never increase beyond a known limit), if the "worse" algorithm is a lot faster in a particular case.

An algorithm with a better "big-O" will of course scale better as you tend towards infinity, but a lot of problems don''t tend towards infinity

My best guess as to where the time is spent with std::list, would be inside the memory allocator which it uses to allocate its nodes. As other posters have mentioned, vector gets around this problem by reusing the same nodes (although of course it doesn''t handle random insertion / deletion efficiently).

Mark

Share this post


Link to post
Share on other sites
quote:
It depends on the list implementation. The MSVC++ 6.0 implementation is a good deal slower than stlport''s implementation

No it isn''t. Which isn''t surprising, really, since for the most part their implementations are identical.

Share this post


Link to post
Share on other sites
The slow part of MSVC containers is the memory allocator. It''s design for maximum efficency of memory use, whereas some allocators today are tweaked for speed of (de)allocation.

In this case vector will undoubtably out-perform the list due to the locality of reference rule.

Share this post


Link to post
Share on other sites
Yeah, you can plug in your own allocation scheme with std::list, look at the interface for std::allocator<> or google for a tutorial.

Share this post


Link to post
Share on other sites