Threading Notes (Papyrus)

From Creation Kit
Jump to: navigation, search

Papyrus is a threaded scripting language. In essence, this means that the game can run multiple scripts in parallel. This allows the Creation Engine to manage script processing more effectively. Papyrus scripters should have at least a cursory understanding of the ramifications this creates for them.

This article attempts to explain threads in layman's terms, in the context of scripting for Papyrus.

Threading

The Basic Rules of Papyrus Threading

  • Only one thread at a time can be doing anything with an instance of a script.
  • Whenever a thread first becomes active in a script, it "locks" that script, preventing other threads from accessing it.
  • When multiple threads try to manipulate the same instance of a script at the same time, a "queue" forms of all of those threads, which essentially wait in line for the script to become unlocked.
  • If the active thread releases its lock on the script, another thread from the queue may be let into the script to "take its turn" so-to-speak. The new thread will then work until it releases its own lock on the script instance. The chances of new threads being let in to an unlocked script, and the order in which they will gain access is unpredictable.
  • Any time a thread makes an external call (to a function on a different object, to a global function, or to a function in a script with a different self), its execution is suspended and will be resumed when the call is completed. Meanwhile the script instance it was working on will be "unlocked" so that other threads can potentially access and modify it.
  • If another thread does begin manipulating the script while the first thread is making its external call, the first thread will have to re-enter the queue once its external call is completed, and wait to regain entry to the script and continue its work.
  • The nature of the function does not matter: it can be native or non-native, latent or not, etc. Any external function call will potentially unlock the script instance. A function call is "internal" only if the function belongs to the the same script instance or one of its ancestors (in other words, if the function called shares the same self). All other function calls are "external". Even native non-delayed functions (like Debug.Trace) are external calls, and will cause their thread to potentially lose its lock on the script.
  • Reading or writing a property on another object is equivalent to an external function call. Reading or writing to a property defined in the same script is optimized to be a variable access, and thus is not an external call.

The reasons behind this

If a script performs an external call it lets in the next thing from the queue while the other thread is off doing that other thing. Then while the new thread is occupying the script, when the previous thread that was off doing its thing wants to come back and continue processing, now it has to wait in line until the new thread is done with the script (or it performs an external call).

You might be asking yourself why is this necessary. Simply put, the very thing that makes multi-threaded software beautiful is also the source of all its problems - simultaneous execution. Two threads could engage the same set of instructions at the same time. They could read a value at the same time and process it on their own and then write it back into memory. Since they pulled the same data at the same time, executed the same operations on it, a simple conclusion is that the result of these operations will be the same, and that result will be stored back into memory twice, making the other thread's work redundant and wrong. You never want two threads to compete for who will write to memory first or even read a piece of data at the same time, because it will basically do the same thing twice (because of the dependence on the initial conditions of the data while reading will affect all subsequent operations on that data or any other that is affected by it). Something is needed to prevent this from happening, a form of mutual exclusion. A thread gains the edge, invokes a lock and all other threads must wait for the "lucky" thread to say: "I'm done." and release the lock. Usually, a queue forms (FIFO structure, first in, first out, logical) of all the threads that have been coming in the meantime and patiently waiting. And then the second thread engages the lock and does its thing. This is an effective way for instructions to operate properly on good, valid data - without racing around.

The same concept is employed with Papyrus scripts, but scripts as a whole. As soon as an object activates something that possibly modifies data in the script, everyone else must queue and wait patiently until it has been cleared to proceed with that specific script. If another script is invoked that doesn't directly clash with data of other running scripts, it is free to run asynchronously. Locks are just necessary in places where it needs to be made sure that the data is intact and valid, synchronized. When two objects want to operate on a third object, a race ensues. Which is killed by synchronization, allowing awesomeness to continue.

The only "loophole" is that a Papyrus script might depend upon another script on another object and your thread might run off to some other script to do its thing. In this time, there is no race going on, the data is "fairly secure" as far as the system is concerned, so it removes the lock and allows the next thread from the queue to work. This could have consequences on the first thread because some data might change right underneath you and make your thread do unexpected things when it comes back because its operation depends on the initial conditions of all the related variables as they were when it first started processing that particular script (another thread could've changed some variables when the first one was running chores on another object's script). You can make sure nobody messes with an object (and its appended script) by enforcing states which redirect all other threads to a different part of the script, so the first thread can emerge victorious in its quest of object modification.

Example

ObjectA has script with a function: DoSomething()

ObjectB calls ObjectA.DoSomething()at the exact same time ObjectC calls ObjectA.DoSomething()

First ObjectB finishes running ObjectA's DoSomething() and then ObjectC runs it.

But if DoSomething() in a script on ObjecttA looks like this:

 Function DoSomething()
    SomeThing1() ;another function in ObjectA
    ObjectD.DoSomethingElse() ;a function in a script on ObjectD    
    Something2() ;Another function in ObjectA
 EndFunction

Then first ObjectB calls ObjectA.DoSomething(), and while ObjectA is busy calling Something1() for ObjectB, ObjectC waits in line, not yet processing ObjectA's DoSomething().

But as soon as ObjectB's thread calls ObjectD.DoSomethingElse() because it has called a function on a different script/object, ObjectA waves in ObjectC who was waiting patiently to call DoSomething().

Now while ObjectC's thread is processing SomeThing1(), ObjectB's thread is done with DoSomethingElse on ObjectD, but before it runs Something2() it now must wait in line until ObjectC's done with Something1() and itself moves out to ObjectD's DoSomethingElse(). As soon as ObjectC's thread heads out to DoSomethingElse() in ObjectD, ObjectA waves in ObjectB's thread who is returning from ObjectD's DoSomethingElse() and will now be allowed to continue on with Something2()... and so on...

Notes

  • Operations on arrays (reading or writing an element, length, find, rfind) are not external calls.
  • Strictly speaking, not all external calls will release the lock around an instance but those exceptions are not predictable. You should assume that all external calls may unlock your object and you should not assume that an unlock will always occur. Learn more
  • External calls are not slower than internal calls: native functions all return after at least one frame (the non-delayed functions excepted), other functions all return after a small time (the VM can process about a few thousands of calls per frame). Learn more
  • The VM behave as a multithreaded OS: if any script (a script, not an instance/object) takes too many time and prevents other scripts to run, it is put on hold so that other scripts can get their shares. As a result, if many objects have the same script attached and the CPU is saturated, some of those objects could behave as if the VM was granting them a low priority (this is just an analogy). source


Threading: A Basic Example

In the image below, the player is activating a lever. Because this is a nice and cooperative player, he's only activated it once. The game sends Papyrus a notification of the activate event. Because our script contains an onActivate() Event, the game creates a "Thread", which you can think of as a set of instructions copied from our script. The game queues this thread up, and will process it momentarily.

Threads01.jpg

Very soon - probably on the next frame - the game processes the thread. Let's pretend that the contents of our onActivate() event look like this:

; Note - this is a non-functional snippet
EVENT onActivate()
    wait(5.0)
    player.additem(gold001, 10)
endEVENT

The player activates the switch, which notifies Papyrus to create a thread containing those instructions - After five seconds, ten gold pieces are added to the player's inventory. All is well. What happens with a less cooperative player, though?
Threads02.jpg
Here the player has activated the lever several times in a short period of time. That's valid input, and our script is about to receive it. In comes the first activate event - a thread is created and begins processing. Here comes the second activation - and another thread is created shortly after the first. This continues as long as the player spams activations on the lever.

The trouble comes with the time-sensitive nature of our script and threads in general. Thread #1 knows nothing about Thread #2 and so on, so each one will wait for five seconds, then add gold to the player.

This can get messy fast. We need a way to keep things organized.
Threads03.jpg
The above example represents the script as we'd want to re-write it - blocking further activations after the first. There are several ways to get this result. This example will be solved using States.

States are very useful for creating a script that reacts to events differently based on different circumstances. The pseudo-script example below shows an example.

; Note - this is a non-functional snippet
STATE readyState
    EVENT onActivate()
       gotoState("emptySTATE")
       wait(5.0)
       player.additem(gold001, 10)
       ; want to allow subsequent activatiosn after the 5 sec delay?  add a "gotoState("readyState") here.
    endEVENT
endSTATE
 
STATE emptySTATE
    ; This state contains no events
    ; Note that other scripts attached to this reference will still process their activate events
endSTATE

Note about tracing "GoToState()"

In the previous example, take note of where goToState() is called. Why? Because additem() is in an external script (as is the setValue() in the example below), it creates an opportunity for another thread to start processing your script before you go to the state you expect it to be in. Therefore, go to your desired state first. Your thread will complete the instructions below the gotoState() call just fine, and future threads will treat the script as being in the state - "XYZ" in the example below - when they encounter it.

In other words - Don't do this:

 gigawatts.setValue(1.21)
 GoToState("XYZ")

Instead, do this:

 GoToState("XYZ")
 gigawatts.setValue(1.21)

Another example

From an email to Jeff asking if calling IncrementMyProperty from an external script multiple times in a row was "thread safe."


...assuming that all functions and the property itself are in the same script.

 Function IncrementMyProperty
   myProperty += 1
 endFunction

100% “thread safe”. myProperty will correctly increment. Right now it resolves to two function calls and as far as you should ever know, will always resolve that way.

 Function IncrementMyProperty
   myProperty += 1
      if myProperty == 5
         ;do something
      endif
 endFunction

myProperty is guaranteed to be 5 when “do something” executes. If “do something” performs an external call, myProperty may change.

Function IncrementMyProperty
   myProperty += 1
   if myProperty == 5
      myQuest.setStage(10)
   endif
 endFunction
 
 ;Elsewhere In MyQuest’s stage 10 fragment:
 If myProperty == 5
   ;do something
 endif

SetStage is external, therefore myProperty may change, even if you just use “SetStage(10)” and your script extends Quest and is attached to the quest.

In the case of the fragment – it is entirely likely that myProperty will no longer equal 5 by the time the fragment runs. Remember: you called setStage, NOT a function. Fragments execute “some time in the future” (which happens to be very soon in most cases). This is one case where a function call is much more useful than a fragment.

Please note:
If myProperty is NOT in your local script, then “myProperty += 1” may not increment. This is because it resolves to “myProperty.set(myProperty.get() + 1)”, and myProperty’s value may change between the get and set calls since it isn’t on your own script. [Editor's note: Which is why you would write a IncrementMyProperty() function in that other script -- JPD ]

-Jeff

Alternative concurrent strategies

While the use of states presented before is a very efficient one, it is not always enough for every situation. Here we present alternative strategies.

Locks

A spin lock ensures that a thread cannot start running a code before another one completes. Locks can be easily achieved that way:

bool locked = false
function SomeLockedFunction()
    while locked
        wait(1.0) ; using a latent call that actually takes time, otherwise the lock may not have a chance to be freed and reduces strain on the VM
    endwhile
    locked = true
 
    wait(5.0)
    player.additem(gold001, 10)
 
    locked = false
endfunction

If thread A and B both try to run this function and thread A is the first one to run, it will set locked to true, then start waiting. Thread B then barges in while A is asleep but since locked is true, it calls wait and is suspended for a real-world second. From then on, B will be resumed every second to recheck whether locked is still true. A is finally resumed and sets locked to false. Then the next time B is resumed it will jump out of the loop and continue running.

Warning: using locks can lead to deadlocks. Deadlocked functions can be identified through the "dps" console command. They can be prevented by defining a convention that rules out which lock should be locked first when you want to lock N locks.

Versioning

Versioning is useful in many situations, for example when you only want to let the last caller proceed and you are willing to cancel older, still ongoing, operations when a new call occurs.

int version = 0
function SomeLockedFunction()
    version += 1
    int localVersion = version
 
    wait(5.0)
    if version == localVersion
         player.AddItem(gold001, 10) 
    endif
endfunction

If thread A and B both try to run this function and thread A is the first one to run, it will have a localVersion equals to N. B will have version N + 1. So when A will be resumed, it will not add the item since it is not the most recent caller. Integers can go up to 2 billions, so in a 200 hours game you're fine as long as you do not call this more often than 2500 times per second.

Double Buffering

Multiple buffering allows a reader to read a given data set while a writer generates the next data set, those two sets being independent. Syncrhonization will be needed at some point but not during the most part of the work. A typical example is the video buffers: the GPU renders a scene to buffer A, while buffer B is sent to the screen to be displayed. Once one has done its job, it enters a wait state until both are done. The buffers are then swapped, the GPU now renders to B, while A is sent to the screen. This is what is called double-buffering. In the papyrus context, as long as the buffers are local or self variables only, we're guaranteed that the swap will be protected by the implicit locking mechanism.

; There must never be more than ONE simultaneous ongoing call to GenerateNextSet. That is, this function is never called again before it has finished.
; There must never be more than ONE simultaneous ongoing call to ProcessCurrentSet. That is, this function is never called again before it has finished.
; However, the calls to GenerateNextSet and ProcessCurrentSet can be ran in parallel.
int[] nextData
int[] currentData
 
function GenerateNextSet()
    ; Modify nextData here, with external functions calls that release the implicit lock on self.
endfunction
 
function ProcessCurrentSet()
    ; "self" stays locked during those three lines
    int[] tmp = currentData
    currentData = nextData
    nextData = tmp
 
    ; Now we can call any external function as long as we only work on currentData.
endevent

Agent model and messages passing

The agent model (sometimes called "actor model" in the literature) relies on the idea that a single, unique thread, is ever allowed to manipulate a given set of data. An agent typically encapsulates internal data, a thread and a messages queue. When the agent is called, it stores a message in the queue and the thread will later dequeue it and process it. While it is possible for the agent to wait for the answer in order to make the call synchronous, the architecture shines when asynchronicity is the rule rather than the exception. Papyrus makes difficult to store messages, however this architecture may still be very useful for complex concurrent problems where other methods are all worse.

int MsgHelloWorld = 0
 
; msgArgsS1[i] stores the first string argument of the i-th message. Initialize them to 128.
int[] msgCodes        
string[] msgArgsS1
string[] msgArgsS2
; Once we reach the end of the arrays, we start over.
int firstMsg          
int msgCount
 
bool isRunning
 
; This function never release the lock on "self"
function EnsurePumpIsRunning()
    if !isRunning
        isRunning = true
        RegisterForSingleUpdate(0.1) ;<-- this function has the same self as this script, so calling RegisterForSingleUpdate()
    endif                            ;will not unlock the script. (However, once the EnsurePumpIsRunning() function has finished,
endfunction                          ;other threads CAN sneak in during the wait time before the update).
 
 
; This function never release the lock on "self"
function PushHelloWorld(string hello, string world)
    int index = (firstMsg + msgCount) % 128
    msgCount += 1
    msgCodes[index] = MsgHelloWorld
    msgArgsS1[index] = hello
    msgArgsS2[index] = world
    EnsurePumpIsRunning()
endfunction
 
event OnUpdate()
     ; The following six lines never release the lock on "self"
     while msgCount != 0
         int index = firstMsg
         firstMsg += 1
         msgCount -= 1
         int code = msgCodes[index]
         if code == MsgHelloWorld
             ; However this line may (and usually will) release the lock on "self"
             debug.trace(msgArgsS1[index] + " " + msgArgsS2[index])
 
         elseif code = ...
             ...
         endif
     endwhile
     isRunning = false
endevent

See Also


Language: English  • français