[Solved] Passing data to Trigger without race condition

[Kingz]

So currently i have a system using trackables in a way that you can attach any amount of triggers in any order to a trackables hit and track event.

Once it's event fires it loops through the triggers, passes needed data and then calls TriggerExecute(trig).

Currently it looks something like this:

        method onHit takes nothing returns nothing
            local integer i = 0
            local trigger t 
            loop
                exitwhen i >= triggerCount
                set t = LoadTriggerHandle(triggerData, this, i)
                
                call SaveInteger( dataTable, GetHandleId(t), GetTriggerExecCount(t)+1, playerId)
                call TriggerExecute(t)
                set i = i +1
            endloop
        endmethod

And in the executed trigger action:

local trigger t = GetTriggeringTrigger()
local integer playerId = LoadInteger( dataTable, GetHandleId(t), GetTriggerExecCount(t) )

I am using this to emulate a player firing an event for the trackable.

The system needs to be GUI friendly, that is the reason i am using lists of triggers to be executed, that way the user can just use custom scripts to load data for that trigger execution and then continue to use GUI.

The question is, does this suffer from race condition in any way, is it safe and would just setting a global be safe enough to not use the trigger execution trick with hashtable in a multiplayer enviorement (edge cases when two users click on a trackable which has the same triggers linked)

 

[Kingz]

After talking to IcemanBo he shared with me his understanding of warcraft 3 threading:

1. Threads do not run concurrently, only one thread is run at a time
2. Threads are queued in execution
3. No mid execution preemption happens between threads, thread preemption happens only if done explicitly within a thread or when the thread ends it's execution

If all of the above is true, race condition cannot apply unless i invalidate the data myself in one of the ran triggers and as such a global variable would be fine.

If anyone could share more info on the matter that would be nice.

 

[Bribe]

What is a race condition?

 

[PurgeandFire]

As IcemanBo mentioned, race conditions don't really apply to wc3. For the second part "would just be setting a global be safe enough"--I'm not quite sure what you're talking about. You would have to show your code.

You don't have to worry about race conditions for globals, but you should probably ensure that the value of a global is in sync between players. For example:

globals
    real x = 0
endglobals

...

if GetLocalPlayer() == Player(0) then
     set x = 100
endif

...

if (x == 100) then
    call CreateTrigger()
endif

The example above would desync even though it isn't immediately obvious. "x" is 100 for player 1 and 0 for everyone else. I doubt this applies to your situation though--trackable events are not ran locally, so unless you explicitly use GetLocalPlayer(), you don't have to worry.

EDIT: @Bribe: A race condition is just a common problem in programs that use multiple threads. In a single threaded environment, we can expect things to run in a somewhat "natural" order. For example:

for (int i = 0; i < 10; i++) {
    printf("%d, ", i);
}

That would print out 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

However, if you run that loop with multiple threads, then it could print those out in any order. Ultimately, with single threaded, you can expect a "natural" order. With multiple threads, the "order" is entirely dependent on the scheduler. This causes a plethora of issues when you're trying to write into memory. You have to share memory and instructions can run inbetween each other (this is usually where race conditions happen).

 

[Ceday]

I thought race condition is the situation where two threads use a common variable or object, not the order of execution.

 

[PurgeandFire]

I thought race condition is the situation where two threads use a common variable or object, not the order of execution.

This is what I was referring to specifically (this guy explains it better than I did):
http://stackoverflow.com/questions/34510/what-is-a-race-condition

The "order of execution" I was referring to was referring to the ability for one thread be writing at a certain PC in the code when another thread is reading at another PC. i.e. a race condition can occur when one thread writes to memory that may be simultaneously read by another thread.

The part of the code you'll want to look at is the part where the shared variable is being written to/read (and that is where you'll want to place your thread locks), but the reason a race condition occurs is due to the way multi-threaded code is actually executed.

 

[Dr Super Good]

would just setting a global be safe enough to not use the trigger execution trick with hashtable in a multiplayer enviorement (edge cases when two users click on a trackable which has the same triggers linked)

Using a global is the recommend and probably best approach. This is how vJASS does its interfaces and how in SC2 GUI implements its "new thread" actions. One can think of the global variables as registers, so as long as you treat them appropriately they will work.

I thought race condition is the situation where two threads use a common variable or object, not the order of execution.

A race condition is all about the order of execution. It need not even be with software, as race condition problems commonly occur in hardware design. Hardware has no concept of "variable" or "thread" and so those clearly are not part of its definition.

A good example is two threads incrementing a variable by 1 in parallel. If they each do this 1,000 times to a variable starting at 0 the result of the variable could be any number from 1,000 to 2,000 depending on the underlying memory model quirks. On a modern multi-core computer it will likely be 1,000 due to separate caching of the variable on each core and each core running the thread in parallel with the last to complete thread overwriting the value from the other thread completing. On an older single-core computer it could end up 2,000 since increment is a single instruction and there is only a single cache for the single execution unit so even if the thread is pre-empted by its partner it will still keep consistency.

From a state point of view this is what it could look like on an old single-core computer for 3 increments per thread.

J1 1 : 2 : 3 :   :   :  
J2 W : W : W : 4 : 5 : 6
Result is 6 so correct.

This is what it would look like on a modern multi-core computer.

J1 1 : 2 : 3
J2 1 : 2 : 3
Result is 3 so wrong.

To guarantee no race condition you need to use synchronization. In the case above an "atomic" variable could be used. Such variable can be incremented "atomically" so the changes each thread make appear instantly to other threads. This obviously comes at a cost as it cannot happen in parallel. Another approach is to "lock" the variable with a mutex preventing other threads from incrementing it at the same time one thread owns the lock to increment it. When locks are given up the state is synchronized so that threads future locking threads see all changes made to the state (making them appear atomic within the lock. Locking and atomic variables have overhead and can prevent parallel execution so should only be used when you need a certain sequence for proper execution.

Race conditions can only occur when state is changed in parallel with respect to time. As far as software is concerned this is when two threads are run on either parallel execution units or pre-emptive scheduling model. As such this does not apply to Warcraft III or StarCraft II triggers since only a single execution unit exists and there is no thread pre-emption. Threads in WC3/SC2 will execute from start to finish once started unless they explicitly yield (eg do something that fires an event, TriggerSleepAction, natives that synchronize state etc) in which case they execute in a stack like way (with top of stack being newest and executed first).

 

[Kingz]

Thanks for everyone and their responses, and for reaffirming IcemanBo's words about threading in wc3.

Now for a sub question, is there a list of natives which explicitly cause a thread to yield to another thread? (switch to another thread)
TriggerSleepAction and TriggerEvaluate are ones that come to mind, but if someone could link me to a page with all of them that would be nice.

IcemanBo told me that as far as he knows TriggerExecute won't cause a thread switch, but that even if it did it would be the one to finish next and then resume the previous one from which the TriggerExecute was called.
As in:

Thread 0:
begins
stuff
TriggerExecute(t) -> thread 1 starts

Thread 1 (executing trigger t):
begins
trigger action stuff
ends -> back to thread 0

Thread 0:
after trigger execute stuff
ends

Knowing that I do not have to worry about multiple thread synchronization really puts my mind at ease at least, less work to be done.

 

[Dr Super Good]

Now for a sub question, is there a list of natives which explicitly cause a thread to yield to another thread? (switch to another thread)

There is no list as far as I know.

That said some of them are pretty obvious. For example dealing damage can cause a damage event to fire, yielding the current thread to execute the response trigger.

Knowing that I do not have to worry about multiple thread synchronization really puts my mind at ease at least, less work to be done.

The reality is anything else would be impractical. With JASS being such a high level language any potential gains from multi-threading would be lost by synchronization overhead. Also it would become a real pain to write triggers then.

 

[Kingz]

Thanks to everyone for their input at this matter, as the question has been answered mods can now freely close this thread.