[PATCH] WithinStarlaneJumps implementation

Programmers discuss here anything related to FreeOrion programming. Primarily for the developers to discuss.

Moderator: Committer

Message
Author
tzlaine
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: [PATCH] WithinStarlaneJumps implementation

#46 Post by tzlaine »

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.

User avatar
cami
Space Dragon
Posts: 411
Joined: Tue Sep 20, 2011 10:32 pm
Location: Halle (Saale)

Re: [PATCH] WithinStarlaneJumps implementation

#47 Post by cami »

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.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

User avatar
cami
Space Dragon
Posts: 411
Joined: Tue Sep 20, 2011 10:32 pm
Location: Halle (Saale)

Re: [PATCH] WithinStarlaneJumps implementation

#48 Post by cami »

tzlaine wrote:A couple of notes about your original patch, Carsten.

First, this:

Code: Select all

@@ -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: Select all

+        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.
Last edited by cami on Thu Sep 29, 2011 5:40 pm, edited 1 time in total.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

tzlaine
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: [PATCH] WithinStarlaneJumps implementation

#49 Post by tzlaine »

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.

User avatar
cami
Space Dragon
Posts: 411
Joined: Tue Sep 20, 2011 10:32 pm
Location: Halle (Saale)

Re: [PATCH] WithinStarlaneJumps implementation

#50 Post by cami »

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.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

User avatar
eleazar
Design & Graphics Lead Emeritus
Posts: 3858
Joined: Sat Sep 23, 2006 7:09 pm
Location: USA — midwest

Re: [PATCH] WithinStarlaneJumps implementation

#51 Post by eleazar »

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

tzlaine
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: [PATCH] WithinStarlaneJumps implementation

#52 Post by tzlaine »

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.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: [PATCH] WithinStarlaneJumps implementation

#53 Post by Geoff the Medio »

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.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: [PATCH] WithinStarlaneJumps implementation

#54 Post by Geoff the Medio »

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: Select all

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
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: [PATCH] WithinStarlaneJumps implementation

#55 Post by tzlaine »

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
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: [PATCH] WithinStarlaneJumps implementation

#56 Post by tzlaine »

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: Select all

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
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: [PATCH] WithinStarlaneJumps implementation

#57 Post by tzlaine »

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.
Attachments

[The extension patch has been deactivated and can no longer be displayed.]


User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: [PATCH] WithinStarlaneJumps implementation

#58 Post by Geoff the Medio »

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.
Attachments
FO_Build_Errors_Sample_with_Boost_1.47.txt
FreeOrion server build errors (selected) with Boost 1.47.
(8.65 KiB) Downloaded 65 times

tzlaine
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: [PATCH] WithinStarlaneJumps implementation

#59 Post by tzlaine »

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?
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.
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.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: [PATCH] WithinStarlaneJumps implementation

#60 Post by Geoff the Medio »

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.

Post Reply