Faster Triggers

[Nestharus]

I discovered something rather interesting about triggers.

Given a set of boolean expressions, that set of boolean expressions is a list and each boolean expression is a tree. Therefore, TriggerAddCondition will add to the trigger's list one tree.

When the trigger is evaluated, every boolean expression in the trigger's list will be evaluated, and by being evaluated, the trees will be walked.


The more balanced the trees are, the less overhead there is.

I performed 3 tests

Test 1: many single boolean expression trigger conditions
Result: 10 fps

Test 2: 1 trigger condition with a very unbalanced boolean expression tree built via

Or(expr, func)
Or(expr, func) //etc

Result: 5 fps (similar to trigger actions)

Test 3: 1 trigger condition with a perfectly balanced boolean expression tree built similarly to a heap

Result: 15 fps


This allows for a few things. Firstly, because there is only 1 trigger condition in the trigger's list, that trigger condition may be removed at any point without breaking the trigger's evaluation. TriggerRemoveCondition was unsafe as if the trigger condition being removed was the one being currently evaluated, the trigger wouldn't evaluate next trigger condition, it would simply terminate. Timers and so forth had to be used, which gave bad behavior. Allowing the use of TriggerRemoveCondition gives correct behavior and reduces overhead.

Next, a single boolean expression allows triggers to be mixed. Consider priorities, like in PriorityEvent. Suppose that you have one PriorityEvent that is global for everything in the map and another PriorityEvent that is specific to 1 unit in the map. If you can't mix them and they have this format:

Global Priorities: 0, 5, 10
Local Priorities: 0, 5, 10

Then it would run in this order

G0, G5, G10, L0, L5, L10

Where G is Global and L is Local

By being able to mix triggers, it will correctly run in this order

L0, G0, L5, G5, L10, G10


But wait? If the entire trigger is just 1 boolean expression, won't the same problem remain? If they are put together via Condition(localExpression, globalExpression), the result is just

L0, L5, L10, G0, G5, G10

By storing a list of trees, each list being a priority, and each tree being a boolean expression, then iterating over the local list and the global list will correctly merge the trees.

Local List:
Priority 0: Boolean Expression Tree
Priority 5: Boolean Expression Tree
Priority 10: Boolean Expression Tree

Global List:
Priority 0: Boolean Expression Tree
Priority 5: Boolean Expression Tree
Priority 10: Boolean Expression Tree

From here, iterate over the local tree first

loop
     exitwhen globalNode == 0

     loop
         exitwhen localNode.priority > globalNode.priority
         set expr = Or(expr, localNode.expr)
     endloop

     set expr = Or(expr, globalNode.expr)

     set globalNode = globalNode .next
endloop

The final result, after applying the above, is

L0, G0, L5, G5, L10, G10

You may notice that the tree will probably not be perfectly balanced, but each subtree that makes up the larger tree will be perfectly balanced, so there is a significant performance gain.

 

[Magtheridon96]

You should totally write a system for this thing ;O
Heck, maybe we can integrate it into RegisterPlayerUnitEvent somehow.

 

[Bribe]

So what you're saying is... that Or is faster than a bunch of trigger add conditions... but what is the big difference that makes it run at 5 VS 15, in plain English (i don't understand your lingo)? is it because you add the ors in one thread instead of one by one?

 

[chobibo]

Sorry but I'm not as well versed as you guys so here is how I interpret this:

G1 = { boolValA , boolValB , boolValC }

        [BoolExp: {G0}]
              /\
[BoolExp: {G1}] [BoolExp: {G2}]

1. I just want to know why it executes faster, is it because it iterates through a list and not a list of lists?

CondList = { L0, G0, L5, G5, L10, G10 }

2. If so, is this what makes it safe to remove the said condition?
-------------------

I think this is a good find.

EDIT: sorry about the weird chart lol.

 

[Nestharus]

1. I just want to know why it executes faster, is it because it iterates through a list and not a list of lists?

Try list of trees. Not sure why, it could be something that wc3 does between each triggercondition as opposed to just evaluating a boolean expression. Each trigger condition evaluates the boolean expression inside of it, and then that boolean expression will evaluate the left, the current, and then the right.

2. If so, is this what makes it safe to remove the said condition?

The thing that broke TriggerConditions was removing a currently evaluating node from the trigger condition list in the trigger. If you removed it, then it lost it's .next, meaning that the rest of the list doesn't get evaluated. By only using 1 boolean expression, you have only 1 node in the list, which means that nothing gets ruined =).

 

[chobibo]

Thanks for the info, I think I understand it a bit now.