Sign in to follow this  
Ehrys

std::vector vs Linked List

Recommended Posts

Which is faster? I am currently implementing a manager class containing 300+ objects of the same class with a draw method. Would it be faster to contain all 300+ objects in an std::vector<> and iterate through each one. Or should I create a linked list that returns a pointer to the next object? Speed is of the essence so everything down to compiler optimisation is a bonus. Example of first method:
std::vector<Object*>::iterator ObjectIterator;
for(ObjectIterator = ObjectVector.begin(); ObjectIterator != ObjectVector.end(); ++ObjectIterator)
{
ObjectIterator->draw();
}




Example of second method
Object* Object::draw()
{
// Code to do drawing of VBO/Vertex List
return _nextObject;
}

// Assume ObjectManager holds a pointer to the First object of the LL
void ObjectManager::Draw()
{
currentObject = firstObject->draw();
while(currentObject)
{
currentObject = currentObject->draw();
}
}




Thanks for any advice EDIT: Just realised I didn't fully explain. Obviously with the second method, you would presume ObjectManager wouldn't contain any information regarding other Objects than the first. However I will need access to them. Therefor, I'm already storing a vector of the Objects. So memory management is not a deciding factor. [Edited by - Sneftel on November 25, 2008 8:41:43 AM]

Share this post


Link to post
Share on other sites
std::vector would probably be very very slightly faster, since it's more likely that the objects will stay in the cache.

However, the main reason you'd choose one over the other is if you need random access (std::list doesn't have it), or fast insertion (std::vector is only fast to insert elements at the end).

Share this post


Link to post
Share on other sites
If you're not sure how to benchmark this yourself, the proper question is not about std::vector vs. your own linked list, but rather std::vector vs. std::list. Try both yourself and see how they behave in your particular application. If one of them was universally better than the other, there would be no reason for the other to exist... But it does. In other words, there's no general answer to your question.

Share this post


Link to post
Share on other sites
I wouldn't be using the std::list objects. I would be storing pointers to the previous object and the next object on each object themselves.

Example:
Assume I have three objects that are linked 1->2->3
Object1::_nextObject = *Object2;
Object2::_nextObject = *Object3;
Object3::_nextObject = NULL;


More like that :)

Obviously they would have _previousObject which would point the other way also.

Ideally I want the compiler to optimise the code best as possible and increase the possibility of success of branch prediction on the CPU.

I know how to benchmark, but I wanted an idea before I set to coding one or the other.

Share this post


Link to post
Share on other sites
  • The standard library already has a linked list: std::list - use that in preference to your own.
  • Iterating over a vector is faster than a list (contiguous memory, simple increment to advance).
  • Adding and removing elements anywhere except the end of a vector is *very* expensive, so make sure you don't need to do this.
  • You say it needs to be very fast, but 300 is not very many objects, so either iteration will be fast, and the time taken to actually draw the objects should overshadow the iteration cost by a huge amount.
Edit: No need to mark topics as closed.

Share this post


Link to post
Share on other sites
In my game engine I opted to use std::list for rendering tasks. Each task is inherited from a generic RenderTask interface which is set up as a tree.
Each task has a list of sub tasks that are executed and can be dynamically added/removed (note that their also reference counted too) at runtime based on how the actor manager/event system defines. Since I was unaware of the potential number of sub-tasks for any given Task I was able to use std::vector:reserve, so std::list was the best solution in my case.

My Engine Rendering Example:
Task #0 - Setup Shadow Textures
- SubTask #0 - Setup Render Target
- SubTask #1 - Setup Camera
- SubTask #2 - Draw Scene
- SubTask #3 - Apply Post FX
Task #1 - Render In Game
- SubTask #0 - Setup Camera Task (Shared with Task #0/SubTask #1)
- SubTask #1 - Draw Scene (Shared with Task #0/SubTask #2)
Task #2 - Render UI
- SubTask #0 - Draw UI

Share this post


Link to post
Share on other sites
Quote:
Original post by Ehrys
std::vector<Object*>::iterator ObjectIterator;
for(ObjectIterator = ObjectVector.begin(); ObjectIterator != ObjectVector.end(); ++ObjectIterator)
{
ObjectIterator->draw();
}


You mean (*ObjectIterator)->draw();, right? Because you have to dereference the iterator and the pointer. Anyway, here is real C++ code that replaces your manual iteration:
#include <algorithm>
#include <functional>

std::for_each(ObjectVector.begin(), ObjectVector.end(), std::mem_fun(&Object::draw));

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Iterating over a vector is faster than a list (contiguous memory, simple increment to advance).

Unfortunately that comparison only works when comparing iteration when storing objects by value in the both a vector and a list. That, however, is not what he's doing. Instead it's iteration of a vector<Object *> versus iterating over an intrusive list, which is much more like comparing a std::vector<Object *> to a std::list<Object>.

Either way, we're the wrong people to be asking. You should be asking this question of your profiler.

Share this post


Link to post
Share on other sites
Could you recommend a good profiler that I can get under either Academic license or for free?

I personally have an Intel processor, however, the target machine will be an AMD X2 4800+

So I'm not sure exactly how useful profiling it with a specific Intel one will be.

Share this post


Link to post
Share on other sites
I don't see what the fuss is about...
When iterating over even 3000 pointers-to-objects, I just can't see you noticing a difference of using any kind of list or vector. If you had millions than maybe it'd be worth worrying about. At this point the question isn't important.

What matters is what will you need to do with these lists? Are you just drawing? Then pick the container that will be easiest to use. Will an event (say a collision or something) possibly cause one of these objects to be deleted? Maybe you'll want to use a list in this case since removing an object in the midst of iterating over a vector is cause for many issues needing workarounds.

I think right now the correct question is what do you need, not which is fastest.

Cheers
-Scott

Share this post


Link to post
Share on other sites
What compiler are you using? Your compiler may already have a profiler (e.g. some editions of MSVC do). If using the GNU toolchain, you can use gprof as a profiler.

Share this post


Link to post
Share on other sites
Ooo thanks, I had no idea MSVS had a profiler. Hah, I am blind sometimes, been using MSVS for about 4 years :D


And to answer your question pops, i could be using 300, 3,000 or 3,000,000. The numbers used are irrelevant. I simply have to use the fastest method possible, taking into account any optimisation ability in the compiler and taking advantage of CPU's branch prediction. This is vital, even if I only save a matter of 20-30ns :)

Share this post


Link to post
Share on other sites
It's highly doubtful that the iteration itself is going to be a bottleneck in your program, meaning that no matter how much you optimize it you'll never see a performance difference because there's something else that's much slower which hides any different in performance. As a matter of fact, I'm willing to bet that you're going to spend enough time stalled in your draw method to mask any differences between containers.

In other words, don't sweat it :) Use the container which makes your code easiest to write and let the profiler worry about the performance when the time comes.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ehrys
I simply have to use the fastest method possible, taking into account any optimisation ability in the compiler and taking advantage of CPU's branch prediction. This is vital, even if I only save a matter of 20-30ns :)


Why? Is someone going to pay you large sums of money if you can prove that your method is fastest?

Have you considered the possibility that what is fastest for 300 elements might not be fastest for 3,000,000?

(Also, insert jokes here about the "madness" of optimizing for a collection of 300 elements. Sparta, etc.)

Share this post


Link to post
Share on other sites
Why do you worry so much about the performance of the surrounding iteration? The interesting part is what happens inside the loop:
std::for_each(ObjectVector.begin(), ObjectVector.end(), std::mem_fun(&Object::draw));

As others have already pointed out, that is where you should put your optimization efforts.

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