EffectsGroup priorities

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

Moderator: Committer

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

Re: EffectsGroup priorities

#61 Post by cami »

The code is simplified. As printed above, the effects within the same effectsgroup indeed would not stack. This could easily be fixed by iterating over effects instead of effect groups. Different effect groups however already stack in the simplified code, even if they shouldn't (because they belong to the same stacking group - I left out that check also for readability)
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: EffectsGroup priorities

#62 Post by Geoff the Medio »

Ah, so effectsgroups would be processed serially, but effects within would be in parallel?

That seems like a very limited form of parallelism, given that many effectsgroups have only a single effect and target, and could be executed simultaneously without complication.

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

Re: EffectsGroup priorities

#63 Post by cami »

No, targets are executed in parallel. It works a bit like SIMD on modern GPU's, each thread does the same thing at the same time, just on different data. I.e., One effect is executed after the next, and each thread gets a share of the targets. This is indeed very limited parallelism, but as there are very few threads, it pays off for every moderately complex effect. It definitely seems a better strategy than running the simple effects in parallel with complex scheduling and little gain, while running the expensive effects (namely: statistics) without parallelism.
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: EffectsGroup priorities

#64 Post by Geoff the Medio »

What would EvaluateValues do exactly? What values would it be storing?

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

Re: EffectsGroup priorities

#65 Post by cami »

The idea is to resolve ValueRefs in EvaluateValues() and store the resulting values. Then wait until all threads are done with that, and start executing the effects, using those values instead of resolving ValueRefs. This idea is kind of stolen from the way the scope evaluation of effects groups is separated-off into GetEffectsTargets(). The difference between GetEffectsTargets() and EvaluateValues() is that all scopes can be evaluated using the same universe, while ValueRefs need to be careful which effects have already been applied and which not, thus, EvaluateValues() can only be called for the "current effect" in the global effects sequence. The remaining parallelism comes from the number of targets the effect needs to be applied to.
Note that, eventually, we don't need to make the threads completely independent of each other, we only need to achieve that they can share the workload. Unless the majority of the effects applies to just one single target, we are already speeding up by at least 50% if only two threads can share workload for the majority of effects.
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: EffectsGroup priorities

#66 Post by Geoff the Medio »

Some effects (I think just the ones that move objects around) also contain Conditions that determine what they do... Presumably you'd need to cache the results of those as well?

Would a good first step / test be to just parallelize the execution of SetMeter effects, particularly when not target invariant?

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

Re: EffectsGroup priorities

#67 Post by cami »

Yes, basicly "everything that needs (only) read access". Ideally all the computations that depend on object states are completed before the barrier and only the final step that actually modifies the object is done after the barrier. Probably, it's not even worth parallelizing that last step.
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: EffectsGroup priorities

#68 Post by Geoff the Medio »

A lot of effects are going to be things like

Code: Select all

                SetTargetResearch Value + 5
                SetTargetIndustry Value + Target.Population / 2
In those, the processing required to get the new meter (or whatever else) value seems fairly small. I wonder whether it will be very useful to parallelize those computations when it then will be necessary to do thread-safe storage and retrieval of the results as well...

Do you have a sense / measurements of what actually takes a lot of time during effect executions? Is calculating statistics a dominant contribution, or is it an aggregate of many such simple ValueRef calculations?

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

Re: EffectsGroup priorities

#69 Post by cami »

I noticed that, too. I had (hopefully still have) a valgrind file somewhere. Could have a look at it again. My suspects are the effects with conditions.
Oh, and we don't need thread-safe storage and retrieval more than in condition evaluation, if we do it in the barrier style i proposed.
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: EffectsGroup priorities

#70 Post by Geoff the Medio »

cami wrote:Oh, and we don't need thread-safe storage and retrieval more than in condition evaluation, if we do it in the barrier style i proposed.
I suppose you can pre-allocate storage for results of ValueRef and Condition and pass a reference to that storage to the work thread? I just meant that if you're computing all that in parallel, the storage for the results presumably needs to work with mult-threaded write access.

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

Re: EffectsGroup priorities

#71 Post by cami »

Yes, exactly. The valueref Evaluation can be a complex calculation only a single result value of which is actually used, so like in GetEffectsTargets, we can run the evaluation mostly without locks and only lock for the final storage, and/or prepare a thread-private storage that can be accessed safely (GetEffectsTargets uses a mix of both)
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: EffectsGroup priorities

#72 Post by cami »

Geoff the Medio wrote:Do you have a sense / measurements of what actually takes a lot of time during effect executions? Is calculating statistics a dominant contribution, or is it an aggregate of many such simple ValueRef calculations?
Dammit, I forgot to take the cachegrind file with me. Will have to wait until next week. I remember that in inverse perspective, the contribution of effects execution to condition evaluation was significant, although small (I think about 5%). Maybe I can calculate it from that. Effects execution takes between 50% and 200% of the time that scope evaluation does on my machine, so lets assume 100%. It runs one one cpu, scope evaluation runs on 8 cpu on my machine, so Execution has about 12% of the computational cost of scope evaluation. Comparing that to the 5%, we have 5%*105%/12% = about 40% of the effects execution attributed to condition evaluation.
Those aren't the only effects that can benefit from the "single effect multiple targets" parallel approach. Any effects with a significant number of targets do as well. And we have quite some effects that say "all planets in empire" or "all planets in supply range", or say "all ships with part X", which is easily several hundreds in larger, or late games.
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: EffectsGroup priorities

#73 Post by Geoff the Medio »

I'm a bit concerned about major changes to the interface of Effects and EffectsGroup that these changes would require. Would it be less disruptive to the existing code and effect execution structure if the changes were contained within the Execute functions of individual effects? (Requiring doing the outer loop over effects, not effectsgroups...)

Ideally the existing behaviour would remain as a default, and individual Effects could be modified separately to use the evaluate-and-store-in-parallel then execute-in-parallel instead of evaluate-and-execute-in-series. Different effects will require different types of caching anyway...

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

Re: EffectsGroup priorities

#74 Post by cami »

Yes, that would be possible and actually a good idea IMO as well.
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: EffectsGroup priorities

#75 Post by cami »

Ok, so here are the facts from my last callgrind run in January. After that run I switched to oprofile because the valgrind overhead was no longer bearable. Unfortunately, oprofile's support for single-program analysis is inferior to callgrind, and I got drawn away from profiling trying to overcome that.
I took the datafrom freeoriond, because it has much more data to process than the clients. It appears condition evaluation takes up almost all the execution cost if we eleminate an apparantly unfortunate use of std::find.
30% of Effects execution is spent in std::find (called directly from Universe::ExecuteEffects)
55% of Effects execution is spent actually in effects groups processing
45% of Effects execution is spent in Effect::SetDestination(4/5 of all effects computation!)
40% of Effects execution is spent in condition evaluation (calls dominated by SetDestination)

The following are dominated by or excclusive to condition evaluation:
20% of Effects execution is spent in WithinStarlaneJumps evaluation
8.0% of Effects execution is spent in the TemporaryPtr copy constructor
(calls half/half JumpsBetweenObjects and Initial Candidates)
7.5% of Effects execution is spent in Containment evaluation
6.5% of Effects execution is spent in GetSystem() (calls dominated by JumpsBetweenObjects)
6.0% of Effects execution is spent in constructing default candidates from type-specialized object maps
4.5% of Effects execution is spent in Object Type evaluation
3.5% of Effects execution is spent in shortest path search
3.0% of Effects execution is spent in Universe::JumpDistance (only 1/7 of WithinStarlaneJumps!)
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

Post Reply