[Threading] findPath

[FRex]

It is true for visual studios before 2010, because they have foolproof checked iterators enabled by default even in release, unless you #define them to be off.

[binary1248]

I just did some analysis of the asm code GCC produced from the same loop using iterators and indexing. It is true that the difference if any is negligible, but this really depends on what the loop body looks like. When it is a simple arithmetic operation the iterator is compiled out and the asm code is identical (besides that the iterator loop adds 4 and the index loop increments). When the loop bodies become more complex however, the difference between the loops grows. I don't know why this happens because they are semantically the same but I guess the compiler has a harder time to detect what you really want and is just playing it safe.

Maybe I should rephrase that a bit: Try to avoid using iterators when you have a complex loop body, don't need any special iterator functionality and care about every bit of performance. If using indexing makes your code 10x uglier then you really should use iterators because the performance gain isn't worth the headache every time you have to read your code .

As for deque, actually the code for both loops are also similar and have the same amount of memory accesses. The same applies here as for vector though and it really depends on the loop body how optimized the iterators can get.

This was done on GCC 4.7.0. I suspect that there are already many loop optimization hacks built into the newer compilers that should already be mostly C++11 ready. Maybe on older compilers the difference was so big it would have even been noticeable .

[Nexus]

It is true for visual studios before 2010, because they have foolproof checked iterators enabled by default even in release, unless you #define them to be off.

Yes, but when going for maximal performance one has to be aware of such compiler settings.

Let's continue here...

[tavrin]

OK, here are a few things you might want to look at:

• Use (const) references more. They help avoid unnecessary copies since you only read many of your data structures.
• Avoid making temporary objects if you intend to just pass them to some function and let them go out of scope. If you are using a C++11 compatible compiler, just construct the object within the argument list and it will invoke the Rvalue reference variant of said function.
• Move your integrity checking outside of your main loop. Doing it every iteration can become quite expensive.
• If you don't intend to make use of the exceptions that .at() can throw use operator[] instead. This saves time since you make sure that you will never access any element out of bounds anyway.
• Try to use "more efficient" data structures. Instead of using the implicit ordering of a std::set, you can try to use std::vector or std::deque and sort it yourself when needed. This saves a lot of time when inserting and deleting.
• If you take my advice and use std::vector or std::deque, don't insert and erase so much. It is expensive no matter what data structure you use. Rather try to use boolean values to mark nodes as done or not.
• Try to avoid using iterators where possible. Traversing a container with an iterator is more expensive than using direct array indexing if you don't intend to modify the container.
• You might want to experiment with using the A* algorithm instead of plain old Dijkstra's. With a decent heuristic it can be much faster in most cases.

I estimate that the majority of the time that your path finding algorithm is running, the CPU is actually busy with allocating and freeing memory. In any performance critical case such as this it is really worth-while to open up your profiler tool and gather performance data, it will help you optimize out the hotspots if you didn't already do it from static code analysis.

Awsome tips, I started working on my project again, starting with the Dijkstra with these things in mind. Also, we have to use Dijkstra :c, so I'm not allowed to implement A* algorithm.

Thanks for the tips!
And thanks to everyone for replying, I'll post the result!

[tavrin]

OK, here are a few things you might want to look at:

• If you take my advice and use std::vector or std::deque, don't insert and erase so much. It is expensive no matter what data structure you use. Rather try to use boolean values to mark nodes as done or not.

I see what you mean, but I just adjusted the algorithm and I'm kind of stuck now.
In my while-loop, I don't erase the least weighted element now, instead mark it as "scanned". But now I have to make sure I select the non-scanned least weighted element of the vector. But I'm not sure if looping through the vector to check is efficient.[/list]

[binary1248]

It's still more efficient than a container that implicitly sorts every time it is modified. If you use std::set, you don't notice but the library iterates many more times over the data structure than you might need. If you use std::vector, yes you have to iterate over it too, but because you yourself do it, you are sure it isn't done more times than necessary.

[tavrin]

It's still more efficient than a container that implicitly sorts every time it is modified. If you use std::set, you don't notice but the library iterates many more times over the data structure than you might need. If you use std::vector, yes you have to iterate over it too, but because you yourself do it, you are sure it isn't done more times than necessary.

I've updated my code and the speed has indeed increased! the game is now much more playable, still a little lag, but it's okay, I think I've done as much improving as I can.
Thanks for your help!!