[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

#61 Post by tzlaine »

Geoff the Medio wrote:
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.
I find that to be a unpersuasive argument, given how easy it is to build Boost yourself these days.

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

Re: [PATCH] WithinStarlaneJumps implementation

#62 Post by Geoff the Medio »

tzlaine wrote:
Geoff the Medio wrote: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?
It does not, however I was able to get it to build by making these changes in Universe.cpp:

Code: Select all

Index: Universe.cpp
===================================================================
--- Universe.cpp	(revision 4306)
+++ Universe.cpp	(working copy)
@@ -98,7 +98,7 @@
         short m_value;
     };
 
-    short get(const constant_property& pmap, const boost::detail::edge_desc_impl<boost::undirected_tag, unsigned long>&) { return pmap.m_value; }
+    short get(const constant_property& pmap, const boost::detail::edge_desc_impl<boost::undirected_tag, unsigned int>&) { return pmap.m_value; }
 
 }
 
@@ -106,7 +106,7 @@
     template <>
     struct property_traits<constant_property> {
         typedef short value_type;
-        typedef boost::detail::edge_desc_impl<boost::undirected_tag, unsigned long> key_type;
+        typedef boost::detail::edge_desc_impl<boost::undirected_tag, unsigned int> key_type;
         typedef readable_property_map_tag category;
     };
Since we're distributing Boost ourselves in the SDK, can you just make the edit indicated in the ticket?
I suppose so.
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.
That seems to have worked.
There are probably a lot more, but I stopped the build.
I'm happy to help with the rest, as needed.
Turns out there aren't any more.

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

Re: [PATCH] WithinStarlaneJumps implementation

#63 Post by tzlaine »

Cool. I'll use the 1.47 Spirit feature I need then.

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

Re: [PATCH] WithinStarlaneJumps implementation

#64 Post by Geoff the Medio »

Geoff the Medio wrote:I was able to get it to build by making these changes in Universe.cpp:
Only one of those changes was needed:

Code: Select all

Index: Universe.cpp
===================================================================
--- Universe.cpp	(revision 4306)
+++ Universe.cpp	(working copy)
@@ -98,7 +98,7 @@
         short m_value;
     };
 
-    short get(const constant_property& pmap, const boost::detail::edge_desc_impl<boost::undirected_tag, unsigned long>&) { return pmap.m_value; }
+    short get(const constant_property& pmap, const boost::detail::edge_desc_impl<boost::undirected_tag, unsigned int>&) { return pmap.m_value; }
 
 }

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

Re: [PATCH] WithinStarlaneJumps implementation

#65 Post by cami »

Thank you for your trust in me, tzlaine! Have you committed your improvements already? Then I'd run another callgrind to see whether there's still some potential. I won't have time for programming anytime soon however, in fact I never had in the first place, but I needed a break and so FreeOrion was welcome ^^° Well, we'll see, noone can work 24/7.
Last edited by cami on Sat Oct 01, 2011 6:02 pm, edited 1 time in total.
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

#66 Post by cami »

I recommend the attached patch to fix the constant_property issue. It's a bit more straightforward by simply templating on the Key/Value type and let the compiler do the rest.
Attachments

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

Last edited by cami on Sat Oct 01, 2011 7:10 pm, edited 1 time in total.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

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

Re: [PATCH] WithinStarlaneJumps implementation

#67 Post by Geoff the Medio »

cami wrote:I recommend the attached patch to fix the constant_property issue.
Is there any reason to do that instead of my change from long to int?

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

Re: [PATCH] WithinStarlaneJumps implementation

#68 Post by cami »

Yep, it works in a generic way no matter what types the graph implementation actually uses, making the code slightly more flexible, and as a plus a bit more reusable. The effect in machine instructions should be perfectly the same.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

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

Re: [PATCH] WithinStarlaneJumps implementation

#69 Post by Geoff the Medio »

tzlaine wrote:
Geoff the Medio wrote:It's probably possible to arrange such a case, by doing something like...
If you could gin up a patch that you've tested and know works, I would really like to test it out.
I added the following effectsgroup to the cultural archives building:

Code: Select all

Index: buildings.txt
===================================================================
--- buildings.txt	(revision 4333)
+++ buildings.txt	(working copy)
@@ -5,7 +5,7 @@
     buildcost = 2000
     buildtime = 200
     location = Not All
-    effectsgroups =
+    effectsgroups = [
         EffectsGroup
             scope = And [
                 Planet
@@ -18,6 +18,14 @@
                 SetTargetMining Value + Target.Population * 0.5
                 SetTargetIndustry Value + Target.Population * 1.0
             ]
+        EffectsGroup
+            scope = And [
+                Planet
+                WithinDistance distance = LocalCandidate.Supply condition =
+                    OwnedBy TheEmpire RootCandidate.Owner
+            ]
+            effects = SetFarming Value + 1
+    ]
     graphic = "icons/building/archive.png"
 
 BuildingType
I then started a game with 500 stars, high for all galaxy setup settings, and 5 AIs (although this should work with 0 AIs). I just started the game; no turns were played, so the following indicates events happening on the server before the first turn starts. In the server log, there are a bunch of lines showing how long it takes to get target sets for various content's effectsgroups, including these lines:

Code: Select all

2011-10-02 12:15:10,303 DEBUG Server : Universe::GetEffectsAndTargets for BUILDINGS
2011-10-02 12:15:10,305 DEBUG Server : ... ... Universe::StoreTargetsAndCausesOfEffectsGroups get target set time: 2
2011-10-02 12:15:10,305 DEBUG Server : ... Universe::StoreTargetsAndCausesOfEffectsGroups done processing source 2149 cause: BLD_CULTURE_ARCHIVES effects group 1 time: 2
2011-10-02 12:15:11,404 DEBUG Server : ... ... Universe::StoreTargetsAndCausesOfEffectsGroups get target set time: 1098
2011-10-02 12:15:11,427 DEBUG Server : ... Universe::StoreTargetsAndCausesOfEffectsGroups done processing source 2149 cause: BLD_CULTURE_ARCHIVES effects group 2 time: 1122
2011-10-02 12:15:11,430 DEBUG Server : ... ... Universe::StoreTargetsAndCausesOfEffectsGroups get target set time: 3
2011-10-02 12:15:11,430 DEBUG Server : ... Universe::StoreTargetsAndCausesOfEffectsGroups done processing source 2150 cause: BLD_IMPERIAL_PALACE effects group 1 time: 3
2011-10-02 12:15:11,432 DEBUG Server : ... Universe::StoreTargetsAndCausesOfEffectsGroups done processing source 2150 cause: BLD_IMPERIAL_PALACE effects group 2 time: 2
2011-10-02 12:15:11,434 DEBUG Server : ... ... Universe::StoreTargetsAndCausesOfEffectsGroups get target set time: 2
2011-10-02 12:15:11,434 DEBUG Server : ... Universe::StoreTargetsAndCausesOfEffectsGroups done processing source 2150 cause: BLD_IMPERIAL_PALACE effects group 3 time: 2
2011-10-02 12:15:11,436 DEBUG Server : ... ... Universe::StoreTargetsAndCausesOfEffectsGroups get target set time: 2
The important measure is the number after "time:". As can be seen, the cultural archives 2nd effects group - the new one in the patch - is quite slow at 1098 ms compared with the other effectsgroup for that building or another similar building (imperial palace) at 2 or 3 ms each.

Switching from "distance = LocalCandidate.Supply" to "distance = 3" produces similar results.

Also switching from "RootCandidate.Owner" to "Source.Owner" reduces the times for that target set to 3 ms.

Switching back to "distance = LocalCandidate.Supply" but leaving "Source.Owner" makes the time 2 ms.

This may not be a completely fair comparison, as the set of objects matched by the OwnedBy condition will be different, but the sets will be about the same size for each owner, and given the short distance, it's unlikely there will be a significant difference in the number of objects' distances that need to be checked before one is found or all are checked.

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

Re: [PATCH] WithinStarlaneJumps implementation

#70 Post by tzlaine »

Nice. A 3-orders-of-magnitude slowdown! Let's hope we can do better somehow.

Carsten, if you have time, can you do a callgrind run with Geoff's patch?

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

Re: [PATCH] WithinStarlaneJumps implementation

#71 Post by cami »

sure, callgrinds can run in the background easily. Each one takes a few hours though, the tool is very precise at the expense of a tremendous slowdown.

Update: The callgrind with Geoffs Patch (gzipped, 3.1MB) is done. Like him, I only generated a universe (500 systems, mature spiral 3-arm, high densities, human, 5AI). The callgrind reveals Condition::WithinDistance as a major bottleneck, which resorts to the poor double-loop implementation of ConditionBase::Eval(). This confirms Geoffs's earlier suspect. The second major bottleneck it reveals is Condition::Contains, that I already mentioned in another thread.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

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

Re: [PATCH] WithinStarlaneJumps implementation

#72 Post by Geoff the Medio »

I think there might be a problem with the present WithinhStarlaneJumps code. There are a few cases where stuff is happening for no apparent reason: eleazar reported a reproducible (for him) issue with his species being replaced by a different one than selected at the start of the game, and I'm getting natives spawning in my home system, both of which could happen if the withinstarlanejumps condition used to select acceptable systems to add natives was not working properly. I haven't tested or investigated thoroughly, but it seems plausible, and I can't immediately think of another reason this would be happening.

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

Re: [PATCH] WithinStarlaneJumps implementation

#73 Post by tzlaine »

All the more reason for us to have regression tests for ValueRefs, Conditions, and Effects.

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

Re: [PATCH] WithinStarlaneJumps implementation

#74 Post by Geoff the Medio »

tzlaine wrote:All the more reason for us to have regression tests for ValueRefs, Conditions, and Effects.
I think a good way to implement that would be to have a Python-scripting interface for universe generation (that we should have anyway), and create a regression-test script that sets up universe configurations and runs ValueRef, Condition, and Effects on them, checks the results, and reports in the log or messages window.

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

Re: [PATCH] WithinStarlaneJumps implementation

#75 Post by Geoff the Medio »

Geoff the Medio wrote:I think there might be a problem with the present WithinhStarlaneJumps code.
In Universe::JumpDistance why is 1 subtracted from the number looked up in m_system_jumps? With it there, I get natives in the wrong places, and few elsewhere, and without it, things look correct...

Post Reply