[PATCH] WithinStarlaneJumps implementation

tzlaine · **Joined:** Thu Jun 26, 2003 1:33 pm **Posts:** 1092

Geoff the Medio wrote:

tzlaine wrote:

Ugh. I'll have to tackle this tomorrow. Sorry for the breakage.

Commenting out the include line, and the line where the johnson stuff is used seems to get it to build. (I didn't try just one or the other).
Edit: Although FreeOrion is crashing for me at startup after doing that... although that may be related to unrelated changes I've made locally... /Edit

I have two things for you to try:

1) boost::johnson_all_pairs_shortest_paths() -> boost::floyd_warshall_all_pairs_shortest_paths() (and the associated #include)
2) try it with Boost 1.47.

The latter is a preferable permanent solution if it works, since Johnson is supposed to be a lot faster for sparse graphs.

cami · **Joined:** Tue Sep 20, 2011 10:32 pm **Posts:** 49

tzlaine wrote:

What bothers me though is that you keep the double loop forall (source,target) get distance(source,target) in WithinStarlaneJumps::Eval. This scales quadratically with the number of objects, not systems, which grows quite a bit higher (the example game has few colonized systems yet). I got the closest object "on the way", but now that we have the distances in constant time, isn't there a more efficient way to perform this check? If the closest subcondition match is within the #subcondition_matches closest objects to the target (in fact it needs to be one step closer than this allows), or if there are less objects at most jump_limit-1 steps away than there are subcondition matches, a simple BFS search for any subconditon match starting at the target will take at most the time of scanning through all the subcondition matches, the less the closer the object is (in fact you have to apply a correction factor here as scanning a list item is faster than testing set membership of a vertex). I think it is worthwhile to use this alternative method in most cases for a jump limit of 1 (this is actually used). To verify when its actually useful we'd have to keep the d-neighbourhood sizes for each vertex and small distances d in memory and compare them to the subcondition match list size. Then again, hardware evolution will quickly render this effort moot within the next few years, so...

There's no way of getting away from the O(N*N) performance of doing this kind of search. We have implemented a greedy system where possible (we only search from previous search results in an And for instance). The only fix that can get rid of this is to memoize results for later reuse. For this to work, we need to have a better understanding of when the universe is constant and when it is not (and so we must throw out our memos). This is what I've been planning for some time. I hope it's even possible.[/quote]

True, and still untrue. In theory, you cannot improve the worst case. In practice, you can improve most realistical cases, especially at such radically short jump limits as 1. Still, I've abandoned that idea myself as it's likely not worth the effort.

Sidenote: do you know the simplex algorithm? It is proven to run in worst case exponential time. However, it is also proven to run in expected polynomial time on arbitrary inputs, provided you add some small random error. Algorithms can be bad in the worst case and still good in practice.

cami · **Joined:** Tue Sep 20, 2011 10:32 pm **Posts:** 49

tzlaine wrote:

A couple of notes about your original patch, Carsten.

First, this:

Code:

@@ -4294,16 +4402,15 @@
 
         ObjectSet& from_set = search_domain == MATCHES ? matches : non_matches;
         ObjectSet& to_set = search_domain == MATCHES ? non_matches : matches;
-        ObjectSet::iterator it = from_set.begin();
-        ObjectSet::iterator end_it = from_set.end();
-        for ( ; it != end_it; ) {
-            ObjectSet::iterator temp = it++;
+        std::map<const UniverseObject *, std::pair<const UniverseObject *, int> > object_distances(BuildDistanceMap(subcondition_matches, from_set, jump_limit));
+        
+        for (ObjectSet::iterator it = from_set.begin(), end_it = from_set.end(); it != end_it; ++it) {
             // does candidate object contain any subcondition matches?
-            bool match = WithinStarlaneJumpsSimpleMatch(*temp, subcondition_matches, jump_limit);
+            bool match = WithinStarlaneJumpsSimpleMatch(*it, subcondition_matches, jump_limit, object_distances);
             // transfer
             if ((search_domain == MATCHES && !match) || (search_domain == NON_MATCHES && match)) {
-                to_set.insert(*temp);
-                from_set.erase(temp);
+                to_set.insert(*it);
+                from_set.erase(it);
             }
         }
     } else {

breaks things. Do you see why now that I've pointed it out?

Yes, the iterator is invalidated by erase.
Once we're at it: if you change ObjectSet to std::vector erase will invalidate ALL iterators.

tzlaine wrote:

Also, your implementation changed some logic from:

determining the shortest path for fleets in deep space by looking at both possible paths through the systems on either end of its starlane (accurate but slow)

with this:

Code:

+        if (!system_one && result < MANY_JUMPS) ++result; // object one isn't in a system, so add a jump
+        if (!system_two && result < MANY_JUMPS) ++result; // object two isn't in a system, so add a jump // TZL

This is probably wrong 50% of the time. We need to optimize, but we must also preserve correctness.

I know this is different, and I explicitly asked whether min(system1_distance, system2_distance) + 1 is ok instead of max(system1_distance, system2_distance). It's different, but it even makes more sense IMHO, as the fleet is at neither end but something away from both. It would have been possible to compute max using two separate precomputations, but I was told this simpler version is ok. I admit I didnt ask whether +2 is ok if both objects are fleets, but is the same argument as when only one object is a fleet.
Note that the +1 isn't executed when the fleet is inside a system.

tzlaine · **Joined:** Thu Jun 26, 2003 1:33 pm **Posts:** 1092

cami wrote:

It may look dangerous, but it's precisely the same.
-both oldfile and newfile begin by saving begin and end of from_set
-although newfile does not save "it", neither "it" nor from_set is modified until "it" is dereferenced
-neither distances, nor subcondition matches change during the loop in oldfile, so precomputation in newfile is ok.

The problem with your change happens after "from_set.erase(it);", which invalidates "it". When the loop cycles again, the behavior of "++it" is undefined. It may work by accident, it may crash. It is necessary to copy "it" into "temp", then increment "it" before "it" might ever be erased.

cami · **Joined:** Tue Sep 20, 2011 10:32 pm **Posts:** 49

Yup, saw it and edited the post while you were replying. Thanks for the hint =)
Before it gets overlooked, I'll repeat that if you make ObjectSet std::vector erase() will invalidate ALL iterators.

eleazar · **Posted:** Thu Sep 29, 2011 6:05 pm

So for the less technical of us-- generally what kind of speedup for the time between turns are we looking at here?

tzlaine · **Joined:** Thu Jun 26, 2003 1:33 pm **Posts:** 1092

eleazar wrote:

So for the less technical of us-- generally what kind of speedup for the time between turns are we looking at here?

About 4 times faster for very large galaxies. Not sure if the speedup will be the same for smaller galaxies.

Geoff the Medio · **Posted:** Thu Sep 29, 2011 11:39 pm

cami wrote:

...if you make ObjectSet std::vector erase() will invalidate ALL iterators.

This can be resolved by swapping the item to be erased with the last item in the vector, and then removing the (new) last item, which only invalidates an iterator to the last item. A disadvantage of this is that it reorders the items in the vector, which might be undesirable when dealing with ObjectSet (although the ordering is effectively arbitrary with a std::set anyway).

Alternatively, while iterating through the source vector, push copies of the items that are to be saved into a temporary, and then swap the source and temp when done.

Geoff the Medio · **Posted:** Fri Sep 30, 2011 2:13 am

tzlaine wrote:

boost::johnson_all_pairs_shortest_paths() -> boost::floyd_warshall_all_pairs_shortest_paths() (and the associated #include)

Using floyd gives me more errors of this sort:

Code:

boost_1_46_1\boost/graph/floyd_warshall_shortest.hpp(127): error C2664: 'boost::multi_index::get' : cannot convert parameter 2 from 'boost::detail::edge_desc_impl<Directed,Vertex>' to 'const boost::detail::edge_desc_impl<Directed,Vertex> &'

tzlaine · **Joined:** Thu Jun 26, 2003 1:33 pm **Posts:** 1092

Geoff the Medio wrote:

tzlaine wrote:

Ugh. I'll have to tackle this tomorrow. Sorry for the breakage.

Commenting out the include line, and the line where the johnson stuff is used seems to get it to build. (I didn't try just one or the other).
Edit: Although FreeOrion is crashing for me at startup after doing that... although that may be related to unrelated changes I've made locally... /Edit

cami wrote:

freeorion is currently unable to fully utilize my 8-way parallel configuration.

Determining effect target sets (Universe::GetEffectsAndTargets) might be a good case for parallelization efforts, as the relevant data does not change while this is occurring, and the results of each condition are independent.

Good idea.

tzlaine · **Joined:** Thu Jun 26, 2003 1:33 pm **Posts:** 1092

Geoff the Medio wrote:

tzlaine wrote:

boost::johnson_all_pairs_shortest_paths() -> boost::floyd_warshall_all_pairs_shortest_paths() (and the associated #include)

Using floyd gives me more errors of this sort:

Code:

boost_1_46_1\boost/graph/floyd_warshall_shortest.hpp(127): error C2664: 'boost::multi_index::get' : cannot convert parameter 2 from 'boost::detail::edge_desc_impl<Directed,Vertex>' to 'const boost::detail::edge_desc_impl<Directed,Vertex> &'

Well, that sucks. Can you upgrade to Boost 1.47 and see if that has any effect?

tzlaine · **Joined:** Thu Jun 26, 2003 1:33 pm **Posts:** 1092

While I'm waiting on that, I thought I'd try replacing the storage of ObjectMap (std::map<int, UniverseObject*>) with boost::unordered_map<int, UniverseObject*>. It doesn't break the binary file format, and it shaves off another 0.2 seconds. Patch attached.

From here out, I'm going to let Carsten lead the way on this turn update optimization work. That is, if you're interested, Carsten. FWIW, I was going to tackle this real soon, so it's great that you've stepped in when you did.

I'm going to go back to mainly working on the new Spirit 2 parser now. I am investigating options for speeding up ValueRef evaluations as I work on the parser.

Geoff the Medio · **Posted:** Fri Sep 30, 2011 5:42 am

tzlaine wrote:

Can you upgrade to Boost 1.47 and see if that has any effect?

I switched to Boost 1.47, and it definitely had an effect, but I don't think it was an upgrade...

Some of that is a known problem: https://svn.boost.org/trac/boost/ticket/5722

There are probably a lot more, but I stopped the build.

tzlaine · **Joined:** Thu Jun 26, 2003 1:33 pm **Posts:** 1092

Geoff the Medio wrote:

tzlaine wrote:

Can you upgrade to Boost 1.47 and see if that has any effect?

I switched to Boost 1.47, and it definitely had an effect, but I don't think it was an upgrade...

Do we know if it at least steps around our Boost.Graph compiler bug?

Quote:

Some of that is a known problem: https://svn.boost.org/trac/boost/ticket/5722

This is only an issue on the Windows platform. Since we're distributing Boost ourselves in the SDK, can you just make the edit indicated in the ticket?

You also need to add "#include <boost/array.hpp>" near the top of networking/ServerNetworking.h to fix the rest of the errors in the log.

Quote:

There are probably a lot more, but I stopped the build.

I'm happy to help with the rest, as needed.

I'd like to use 1.47 to make the parser a bit easier to write as well, so this upgrade would be useful for that reason as well.

Geoff the Medio · **Posted:** Fri Sep 30, 2011 6:43 pm

tzlaine wrote:

I'd like to use 1.47...

I doubt it will sway you, but I'm reluctant to require the latest release of Boost, as there are often posters trying to compile on Linux who can't seem to get the latest version of Boost easily on their systems. Then again, not that many people seem to be compiling on Linux right now anyway.

FreeOrion

[PATCH] WithinStarlaneJumps implementation

Who is online