Imperial stockpile and production queue future simulation

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

Moderator: Committer

Message
Author
Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Imperial stockpile and production queue future simulation

#1 Post by Ophiuchus »

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
Last edited by Ophiuchus on Fri Jun 09, 2017 8:34 am, edited 2 times in total.
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.

Look, ma... four combat bouts!

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

Re: Why is production queue calculation not used for simulat

#2 Post by Geoff the Medio »

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?

Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Re: Why is production queue calculation not used for simulat

#3 Post by Ophiuchus »

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

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.

Look, ma... four combat bouts!

Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Re: Why is production queue calculation not used for simulat

#4 Post by Ophiuchus »

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.

Look, ma... four combat bouts!

Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Re: Why is production queue calculation not used for simulat

#5 Post by Ophiuchus »

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

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.

Look, ma... four combat bouts!

dbenage-cx
Programmer
Posts: 389
Joined: Sun Feb 14, 2016 12:08 am

Re: Why is production queue calculation not used for simulat

#6 Post by dbenage-cx »

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.

Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Re: Why is production queue calculation not used for simulat

#7 Post by Ophiuchus »

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.

Look, ma... four combat bouts!

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

Re: Why is production queue calculation not used for simulat

#8 Post by Geoff the Medio »

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.

User avatar
em3
Vacuum Dragon
Posts: 630
Joined: Sun Sep 25, 2011 2:51 pm

Re: Why is production queue calculation not used for simulat

#9 Post by em3 »

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.
https://github.com/mmoderau
[...] 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

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: Why is production queue calculation not used for simulat

#10 Post by Dilvish »

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

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: Why is production queue calculation not used for simulat

#11 Post by Dilvish »

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

Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Re: Why is production queue calculation not used for simulat

#12 Post by Ophiuchus »

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/tre ... coroutine2, but it crashes and im not sure i can debug it.
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.

Look, ma... four combat bouts!

Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Re: Why is production queue calculation not used for simulat

#13 Post by Ophiuchus »

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.

Look, ma... four combat bouts!

User avatar
Dilvish
AI Lead and Programmer Emeritus
Posts: 4768
Joined: Sat Sep 22, 2012 6:25 pm

Re: Why is production queue calculation not used for simulat

#14 Post by Dilvish »

@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

Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Re: Why is production queue calculation not used for simulat

#15 Post by Ophiuchus »

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. :)
(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.

Look, ma... four combat bouts!

Post Reply