Which container is most efficient both for iteration and key-value access?
Hello, I have a veriable number of pointers that point to instances of a certain class.
Each instance has a unique ID, and it has to be possible to access all of them by this ID (like an std::map).
However, I also have to iterate over these pointers and call their update(float) method at every frame. (about 60 fps).
What is the most efficient container for these pointers?
Each instance has a unique ID, and it has to be possible to access all of them by this ID (like an std::map).
However, I also have to iterate over these pointers and call their update(float) method at every frame. (about 60 fps).
What is the most efficient container for these pointers?
Use two containers, perhaps?
This assumes that deletions of objects are infrequent.
std::vector< pointer / smart_pointer > to iteratestd::unordered_map< ID_type, pointer / smart_pointer > to look up.This assumes that deletions of objects are infrequent.
I don't really think that will do anything for you. Iterating over maps isn't really slow. At least, I don't think it's any slower than dereferencing a pointer.
I would just use a map and do some profiling if it turns out to be slow (which I doubt it will be). No sense in premature optimization... especially when it makes you do error-prone stuff like keep two independent containers in sync.
I would just use a map and do some profiling if it turns out to be slow (which I doubt it will be). No sense in premature optimization... especially when it makes you do error-prone stuff like keep two independent containers in sync.
Iterating over a
There are two reasons for this:
a. A
http://blogs.microsoft.co.il/blogs/pavely/archive/2009/06/22/cache-locality-for-performance.aspx
a. A
http://www.multicoreinfo.com/prefetching-multicore-processors/
std::list<> or std::map<> is typically three to four times slower than iterating over a std::vector<> of the same size.There are two reasons for this:
a. A
std::vector<> elements have spatial cache locality, while std::list<> or std::map<> does not.http://blogs.microsoft.co.il/blogs/pavely/archive/2009/06/22/cache-locality-for-performance.aspx
a. A
std::vector<> elements have no pref-fetch data dependencies and data pre-fetching is always possible. With a std::list<> or std::map<> we need to follow a pointer to go from one element to the next - until element at position n has been fetched and evaluated, the processor does not know where the element at position n+1 is, and until the element at n+1 has has been fetched and evaluated, the processor does not know where the element at n+2 is. The typical three stage pre-fetch is stalled at stage one.http://www.multicoreinfo.com/prefetching-multicore-processors/
I don't doubt that it will be slower, I just doubt if it will make a significant impact on the overall performance of the program.
It seems to be like he should just use a map first, and if it ends up being too slow (which I find very doubtful), then worry about coming up with a more optimized solution.
There's not much point in greatly complicating your code and opening possibilities for bugs for a speed improvement so small you'll never notice.
It seems to be like he should just use a map first, and if it ends up being too slow (which I find very doubtful), then worry about coming up with a more optimized solution.
There's not much point in greatly complicating your code and opening possibilities for bugs for a speed improvement so small you'll never notice.
> It seems to be like he should just use a map first, and if it ends up being too slow ... a more optimized solution.
Agreed.
Though, IMHO, start off with an unordered_map rather than a map.
> for a speed improvement so small you'll never notice.
If the number of objects is not trivial, the speed improvement would be not just noticeable; it would be glaring.
"iterate over these pointers and call their update(float) method at every frame. (about 60 fps)."
Agreed.
Though, IMHO, start off with an unordered_map rather than a map.
> for a speed improvement so small you'll never notice.
If the number of objects is not trivial, the speed improvement would be not just noticeable; it would be glaring.
"iterate over these pointers and call their update(float) method at every frame. (about 60 fps)."
Last edited on
Seems like you could just have a sorted array.
My only thought is that you may want to reconsider the way you are approaching this problem. Graphics APIs have built in functions to rotate/translate points. You might also want to check out binding data to the graphics card, as well as instancing models.
My only thought is that you may want to reconsider the way you are approaching this problem. Graphics APIs have built in functions to rotate/translate points. You might also want to check out binding data to the graphics card, as well as instancing models.
> Seems like you could just have a sorted array.
Yes. A
Yes. A
std::vector<> kept sorted on unique object ID would work wonderfully well if insertions/removals of objects are infrequent - say once every minute or so. 3600 iterations, insert/remove keeping the sequence sorted, 3600 iterations, insert/remove etc. And for the lookup, the O(log N) std::lower_bound() with a predicate.
:) One hell of a game with different objects 60 times per second.
(Sorry to assume game btw, "60" seems a giveaway though)
(Sorry to assume game btw, "60" seems a giveaway though)
Last edited on
Topic archived. No new replies allowed.