FreeOrion

Forums for the FreeOrion project
It is currently Mon Dec 11, 2017 6:44 pm

All times are UTC




Post new topic Reply to topic  [ 22 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Sun Jan 29, 2017 6:45 pm 
Offline
Dyson Forest

Joined: Tue Sep 30, 2014 10:01 am
Posts: 212
So a while ago I was figuring out how to use extra PP from the imperial stockpile in the production queue.
What struck me as odd was that actual calculation and simulation for future turns was using different code.
What is the reasoning behind this and is it really necessary?

The way it is now, future simulation can be a lot more wrong than it has to be.
I also need to add simulation for the imperial stockpile anyway, so I'd like to clean up if possible.

I imagine a unified function which gets an extra parameter for the state of the current turn and calculates the next turn. For simulation you just use the result as input to the next call until all projects are funded.

Edit: rename thread so one can see its a imperial stockpile thing, was called: Why is production queue calculation not used for simulation?
Edit: added link to dilvish imperial stockpile thread

_________________
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.


Last edited by Ophiuchus on Fri Jun 09, 2017 8:34 am, edited 2 times in total.

Top
 Profile  
 
PostPosted: Sun Jan 29, 2017 7:13 pm 
Offline
Programming, Design, Admin
User avatar

Joined: Wed Oct 08, 2003 1:33 am
Posts: 12040
Location: Munich
Ophiuchus wrote:
What struck me as odd was that actual calculation and simulation for future turns was using different code.
What is the reasoning behind this and is it really necessary?
Can you be more specific? What calculation? What code?


Top
 Profile  
 
PostPosted: Sun Jan 29, 2017 9:05 pm 
Offline
Dyson Forest

Joined: Tue Sep 30, 2014 10:01 am
Posts: 212
Geoff the Medio wrote:
Ophiuchus wrote:
What struck me as odd was that actual calculation and simulation for future turns was using different code.
What is the reasoning behind this and is it really necessary?
Can you be more specific? What calculation? What code?


Starting from Empire.cpp#994
Code:
void ProductionQueue::Update() {

Calculates how much PP progress each project in the production queue gets.

Starting from Empire.cpp#1061 to #1281, future turns are simulated to find out when projects are finished.

_________________
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.


Top
 Profile  
 
PostPosted: Wed Feb 01, 2017 9:21 am 
Offline
Dyson Forest

Joined: Tue Sep 30, 2014 10:01 am
Posts: 212
I am looking for the person who did the simulation - i think maybe it was too slow and somebody rewrote it so it becomes acceptable.

I probably need to rewrite quite a bit for imperial stockpile and i would like to refactor first (which I think is very necessary - code is not easy to maintain). But I need to know what were the main reasons why it was to slow, so I do not run into the wrong direction.

The problem for imperial supply is that at the moment for each supply group the whole simulation is done (depth-first turnwise). With a source of PP which spans multiple supply groups (like the stockpile), these can't be calculated independently anymore - PP from stockpile are distributed first come first serve in the order in the production queue.

I probably could do a minimal change to simulation which would for work some typical situations but would be off in other cases. So at the moment there are the following implementation ideas:

A) minimal change (simulation not correct) - first do supply groups, then distribute PP from stockpile

B) small change (simulation not correct) - collect all queue items which may use imperial stock PP and add each time a queue item gets PP

C) bigger change - for each turn; calculate for each queue item; add PP from supply group and stockpile; (for this it makes most sense to unify current turn distribution and future simulation first)

So who did the work on the future turn simulation :?:

_________________
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.


Top
 Profile  
 
PostPosted: Wed Feb 01, 2017 1:43 pm 
Offline
Dyson Forest

Joined: Tue Sep 30, 2014 10:01 am
Posts: 212
D) medium change (crazy; maybe possible; but correct) - change the simulation loop to something parallel coroutinish thingy (like generators in python).
The idea is to process the supply groups in parallel and halt the execution when an item would be need PP from the imperial stockpile. When all those are halted you figure out which items get imperial PP first and doing so you restart those (until all processing is halted again). Do this until all items are funded or all PP are spend. So in pseudocode:
Code:
while calculation is not finished
  start parallel partial calculation for all supply groups, wait until all subcalculations yield
    each supply group gets calculated independently, calculation stops and yields the current queue item and the current simulated turn if one of the following happens
       1) queue item is completed
       2) maximum simulation turn reached
       3) an item can not be fully funded by the supply group and eligible for imperial stockpile PP (and stockpile has PP)
   with all those subcalculations partially finished, of all returned turns choose the lowest one
   fund all those items in the lowest turn using the imperial stockpile (in the order of items in the production queue)
   restart all those subcalculations in the lowest turn

This could speed up production queue processing because of parallelism and correctly calculate group and imperial PP distribution. I just dont know if there is a suitable library to support this.

_________________
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.


Top
 Profile  
 
PostPosted: Wed Feb 01, 2017 10:20 pm 
Offline
Programmer

Joined: Sun Feb 14, 2016 12:08 am
Posts: 359
Ophiuchus wrote:
So who did the work on the future turn simulation :?:

git blame or history are great sources for this kind of info, github even provides a feature for them.


Top
 Profile  
 
PostPosted: Thu Feb 02, 2017 9:09 pm 
Offline
Dyson Forest

Joined: Tue Sep 30, 2014 10:01 am
Posts: 212
dbenage-cx wrote:
Ophiuchus wrote:
So who did the work on the future turn simulation :?:

git blame or history are great sources for this kind of info, github even provides a feature for them.

History I checked before posting, but didnt really help.
Blame is really helpful, never used it before, thanks.
Geoff mostly exclusively has written the simulation, yay.

_________________
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.


Top
 Profile  
 
PostPosted: Thu Feb 02, 2017 9:10 pm 
Offline
Programming, Design, Admin
User avatar

Joined: Wed Oct 08, 2003 1:33 am
Posts: 12040
Location: Munich
Ophiuchus wrote:
Geoff mostly exclusively has written the simulation, yay.
I think I was just applying patches from someone else, at least if it's a version that has the "dp" sim stuff. Blame doesn't help if a line has been modified since the important change you're trying to find.


Top
 Profile  
 
PostPosted: Fri Feb 03, 2017 10:48 pm 
Offline
Vacuum Dragon
User avatar

Joined: Sun Sep 25, 2011 2:51 pm
Posts: 500
Geoff the Medio wrote:
Ophiuchus wrote:
Geoff mostly exclusively has written the simulation, yay.
I think I was just applying patches from someone else, at least if it's a version that has the "dp" sim stuff. Blame doesn't help if a line has been modified since the important change you're trying to find.

In cases like this, one needs to apply blame in iterations. First, find the latest change to the line with blame, then use this commit's id to find its parent and apply the blame to the parent commit, which will give you the author of a previous change to the line. Repeating this is tedious, but can give the information you need.

_________________
[...] for Man has earned his right to hold this planet against all comers, by virtue of occasionally producing someone totally batshit insane. - Randall Munroe, title text to xkcd #556


Top
 Profile  
 
PostPosted: Sun Feb 05, 2017 3:53 am 
Offline
AI Lead, Programmer
User avatar

Joined: Sat Sep 22, 2012 6:25 pm
Posts: 4390
Heyas, I am the person who wrote the current production queue projections code. It sounds like you are asking why did I do this (kinda complicated) approach instead of just repeatedly calling the more basic turn update version? It used to be be done in pretty much that fashion, but that is a not-so-efficient way to handle this task, which has to be done many many times in any given turn (taking into account the AI's). The old approach was so CPU costly that (to my recollection) there had been a limit of something like 20 imposed on the number of items that could be placed on the build queue, and it could not do projections for very many turns in the future, either..

I am tight on time these days, but can try to help you sort out your issue here. Could you point me to a thread that describes in detail the imperial stockpile that you are trying to have the projections take into account?

_________________
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0


Top
 Profile  
 
PostPosted: Thu Feb 09, 2017 5:36 pm 
Offline
AI Lead, Programmer
User avatar

Joined: Sat Sep 22, 2012 6:25 pm
Posts: 4390
OK well I have now found your thread discussing the imperial stockpile, and also looked over the code in your PR a bit. I am pretty sure that the primary (probably only significant) snag is that the current code loops over the supply-connected resource groups, fully simulating the projections for each one before moving on to the next, which is not really compatible with an imperial stockpile that gets allocated to the items at the top of the queue even if they span multiple resource groups. Handling the groups sequentially instead of in parallel had allowed using some smaller data structures and saving memory, but I don't think it is important for the time savings, and the amount of memory involved is fairly minor also.

I am game to harmonize the projections code with your stockpile, and could submit it as a PR to your branch, if you'd like.

_________________
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0


Top
 Profile  
 
PostPosted: Wed Mar 01, 2017 1:36 pm 
Offline
Dyson Forest

Joined: Tue Sep 30, 2014 10:01 am
Posts: 212
Dilvish wrote:
OK well I have now found your thread discussing the imperial stockpile, and also looked over the code in your PR a bit. I am pretty sure that the primary (probably only significant) snag is that the current code loops over the supply-connected resource groups, fully simulating the projections for each one before moving on to the next, which is not really compatible with an imperial stockpile that gets allocated to the items at the top of the queue even if they span multiple resource groups.

Agreed

I started an implementation using boost coroutine2 https://github.com/agrrr3/freeorion/tree/imperial-supply-stockpile-with-coroutine2, but it crashes and im not sure i can debug it.
Quote:
I am game to harmonize the projections code with your stockpile, and could submit it as a PR to your branch, if you'd like.


And now I got really swamped by life so I'm not sure i will be able to finish.
So I'd gladly accept your PR, would be great.

_________________
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.


Top
 Profile  
 
PostPosted: Mon May 22, 2017 7:55 pm 
Offline
Dyson Forest

Joined: Tue Sep 30, 2014 10:01 am
Posts: 212
Dilvish wrote:
I am game to harmonize the projections code with your stockpile, and could submit it as a PR to your branch, if you'd like.

Hi @Dilvish, any news?

_________________
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.


Top
 Profile  
 
PostPosted: Tue May 23, 2017 7:00 am 
Offline
AI Lead, Programmer
User avatar

Joined: Sat Sep 22, 2012 6:25 pm
Posts: 4390
@Ophiuchus heya. Now that we've got 0.4.7 out and have had some time to relax since then, it does seem like the right time to get back to this. I'll try to get something ready over the next few days or so. (heads-up, though, I don't plan to pursue this coroutine path you are trying out now).

_________________
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0


Top
 Profile  
 
PostPosted: Tue May 23, 2017 7:42 am 
Offline
Dyson Forest

Joined: Tue Sep 30, 2014 10:01 am
Posts: 212
Dilvish wrote:
@Ophiuchus heya. Now that we've got 0.4.7 out and have had some time to relax since then, it does seem like the right time to get back to this. I'll try to get something ready over the next few days or so.

Thats great news. :)

Quote:
(heads-up, though, I don't plan to pursue this coroutine path you are trying out now).

Whatever works is fine for me.
The coroutine implementation would be more like a learning/research project for myself. I want to know if the problem is suited for coroutines and I'd like to know the performance implications if I can make it work. Is there a unit test framework in use in the project? I would be willing to write some tests for the production queue to speed up testing.

_________________
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 22 posts ]  Go to page 1, 2  Next

All times are UTC


Who is online

Users browsing this forum: Linkdex, Yahoo [Bot] and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group