What is the point of the ObjectSets, that are passed arround during evaluation?
Why are there matches and non_matches?
Why was this design chosen over a predicate design (pass in the object under evaluation and return if the condition applies as boolean value)?
FOCS Condition implementation
Moderator: Committer
- adrian_broher
- Programmer
- Posts: 1156
- Joined: Fri Mar 01, 2013 9:52 am
- Location: Germany
FOCS Condition implementation
Resident code gremlin
Attached patches are released under GPL 2.0 or later.
Git author: Marcel Metz
Attached patches are released under GPL 2.0 or later.
Git author: Marcel Metz
Re: FOCS Condition implementation
Not the authorative answer: i guess performance
non_matches and matches allow for shortcutting of calculation.
You can handle multiple objects at once instead of handling each object separately.
Also because it is breadth first instead of depht first, putting the most significant condition first will reduce computation time.
non_matches and matches allow for shortcutting of calculation.
You can handle multiple objects at once instead of handling each object separately.
Also because it is breadth first instead of depht first, putting the most significant condition first will reduce computation time.
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!
Look, ma... four combat bouts!
- Geoff the Medio
- Programming, Design, Admin
- Posts: 13603
- Joined: Wed Oct 08, 2003 1:33 am
- Location: Munich
Re: FOCS Condition implementation
The main purpose of conditions is to filter a set of candidate objects, not to match single objects independently. Passing, working on, and returning sets of (potential) matches is thus more fitting for the purpose.
Matching sets rather than each object independently also allows optimizations. Many conditions have parameters or sub-conditions that control how they match candidates. In some cases, those parameters or subconditions can be evaluated once and applied for all candidate objects. If each candidate was matched independently, then the parameters or subconditions would have to be evaluated again for each candidate. For example, a condition might match objects if they have a stealth meter less the sum of all the population meters of planets owned by an empire. That sum doesn't need to be calculated separately for each candidate as long as it doesn't directly refer to the candidate object in its script.
Conditions often do use a predicate system: the Match functions. For many of the conditions, especially simpler ones like ObjectType (Planet, System, Ship, etc.), there are Match functions that are used by the default base-class condition Eval function as a predicate that is applied to candidate objects to filter them for transfer between the matches and non_matches sets. But for some cases, using a predicate doesn't make sense or would be inefficient, in which case the overridden Eval function might not use a Match function.
The reason for having both matches and non_matches set is for evaluation of conditions like And, Or, and Not when they are composed as subconditions to eachother. Not And [Ship Unowned] doesn't need to propagate the negation into the subcondition(s), since it remembers all of the candidates at each step. All candidates would be put into the matches set and checked if they are ships. Those that aren't would be moved to non_matches. Then all remaining matches would be checked if they are unowned. Those that aren't would also be moved into non_matches. Then the matches and non_matches sets would be swapped due to the negation. For the Or condition, it puts candidates in matches, then filters matches with the first subcondition, whereas all additional subcondition are used to filter non_matches to see if they should be moved into matches. Anything already in matches after the first filter doesn't need to be tested again with any other subconditions.
Matching sets rather than each object independently also allows optimizations. Many conditions have parameters or sub-conditions that control how they match candidates. In some cases, those parameters or subconditions can be evaluated once and applied for all candidate objects. If each candidate was matched independently, then the parameters or subconditions would have to be evaluated again for each candidate. For example, a condition might match objects if they have a stealth meter less the sum of all the population meters of planets owned by an empire. That sum doesn't need to be calculated separately for each candidate as long as it doesn't directly refer to the candidate object in its script.
Conditions often do use a predicate system: the Match functions. For many of the conditions, especially simpler ones like ObjectType (Planet, System, Ship, etc.), there are Match functions that are used by the default base-class condition Eval function as a predicate that is applied to candidate objects to filter them for transfer between the matches and non_matches sets. But for some cases, using a predicate doesn't make sense or would be inefficient, in which case the overridden Eval function might not use a Match function.
The reason for having both matches and non_matches set is for evaluation of conditions like And, Or, and Not when they are composed as subconditions to eachother. Not And [Ship Unowned] doesn't need to propagate the negation into the subcondition(s), since it remembers all of the candidates at each step. All candidates would be put into the matches set and checked if they are ships. Those that aren't would be moved to non_matches. Then all remaining matches would be checked if they are unowned. Those that aren't would also be moved into non_matches. Then the matches and non_matches sets would be swapped due to the negation. For the Or condition, it puts candidates in matches, then filters matches with the first subcondition, whereas all additional subcondition are used to filter non_matches to see if they should be moved into matches. Anything already in matches after the first filter doesn't need to be tested again with any other subconditions.
- adrian_broher
- Programmer
- Posts: 1156
- Joined: Fri Mar 01, 2013 9:52 am
- Location: Germany
Re: FOCS Condition implementation
So that's the reason for the clunkyness. However why shouldn't subconditions not store their evaluation result, if the do not depend on the candidate? That's the whole point of the invariances parameters, right? Adding a value cache to the condition and an epoche for identifying the validity for the cached value would achieve the same.Matching sets rather than each object independently also allows optimizations. Many conditions have parameters or sub-conditions that control how they match candidates. In some cases, those parameters or subconditions can be evaluated once and applied for all candidate objects. If each candidate was matched independently, then the parameters or subconditions would have to be evaluated again for each candidate. For example, a condition might match objects if they have a stealth meter less the sum of all the population meters of planets owned by an empire. That sum doesn't need to be calculated separately for each candidate as long as it doesn't directly refer to the candidate object in its script.
Resident code gremlin
Attached patches are released under GPL 2.0 or later.
Git author: Marcel Metz
Attached patches are released under GPL 2.0 or later.
Git author: Marcel Metz
- Geoff the Medio
- Programming, Design, Admin
- Posts: 13603
- Joined: Wed Oct 08, 2003 1:33 am
- Location: Munich
Re: FOCS Condition implementation
Conditions could be made to cache their results, but currently, in some cases, the code that evaluates a condition caches the results. The extra context the calling code has makes deciding when to do this easier, I think. As noted, within a containing condition, effect, or valueref, invariance tests are used to decide whether to evaluate once or per-candidate. Also, Universe::GetEffectsAndTargets stores a cache of condition results during its evaluation, keyed by source object.
If you are proposing a more-persistent cache, that would be difficult to keep current, I think. Determining when a cached condition result would become invalid would be complicated for arbitrary conditions, if there is to be any level of specificity beyond any time the gamestate changes.
If you are proposing a more-persistent cache, that would be difficult to keep current, I think. Determining when a cached condition result would become invalid would be complicated for arbitrary conditions, if there is to be any level of specificity beyond any time the gamestate changes.
- adrian_broher
- Programmer
- Posts: 1156
- Joined: Fri Mar 01, 2013 9:52 am
- Location: Germany
Re: FOCS Condition implementation
> If you are proposing a more-persistent cache
I'm currently still trying to grasp the setup so I propose nothing yet.
The problem is that I see the current implementation it makes my toe nails curls, nothing more, nothing less.
I'm currently still trying to grasp the setup so I propose nothing yet.
The problem is that I see the current implementation it makes my toe nails curls, nothing more, nothing less.
Resident code gremlin
Attached patches are released under GPL 2.0 or later.
Git author: Marcel Metz
Attached patches are released under GPL 2.0 or later.
Git author: Marcel Metz