hierarchy of yield for distributing work load possible?

hi,
i want to spread heavy calculations (ai, production, movement) over several frames to avoid framerate problems. my problem is that the calculations are distributed over several objects of several classes. so i’m wondering if it is somehow possible to yield several functions at once. i have not used yield before and want to evaluate if i can use it for this purpose. pseudocode:

Calculate(); // in update of manager class

private IEnumerator Calculate()
{
  foreach (obj in array)
  {
    obj.calc1();	// one of this functions will yield somewhere and i need this function to continue in the next update at the last position, maybe return the return value of each of these?
    obj.calc2();
    obj.calc3();
  }
}

private IEnumerator obj.calc1()	// calc2 + calc3 have similar structure
{
  for(i < numberofsubobjects)
  {
    DoStuff();
    if(++staticcounter > operationsperframe)
    {
      staticcounter = 0;
      yield return;	// stop calculations here and resume in the next frame
    }
}

so what i want to achieve is do some calculations until a frameratedependent count criteria is triggered then yield everything and resume at the same position in the next frame. once all calculations are done start again.

if this is not directly possible do you know another aproach or some workaround for this problem? i have thought about threads but because of locks i would require to have 2 datasets one which is used for the calculations of the actual state and one (copy of the other) for querying the last state. that appears somehow dirty to me (in programming sense ;)) and drives me into memory problems.

could someone clarify this issue for me? i’m not sure about either of these.
thanks in advance.

Trying to treat coroutines as threads doesn’t really work, since they are very different things. You should use actual threads instead. I’m not sure why you would require two different sets of data for threads if you don’t need it for coroutines.

–Eric

I’m going to second using threads over coroutines for that sort of work.

When I get home I’ll post a code snippet of a simple system for offloading arbitrary work to a new thread (with a callback and WaitHandles, etc…) I can post it so you can get an idea.

That is my question if yield helps me with the calculation distributed over several frames.

thanks for that. i apreciate your opinion very much.

i thought when a thread manipulates data it should be locked to avoid inconsistent data. when i use a coroutine i can yield at a certain point where i’m sure the operations are atomar and the object is in a consistent state or objects dont depend on each other. if i use a thread the data can be queried anywhere and inconsistent states can happen. but i think i should make a small lock then to avoid this so i can use a thread for that (which also utilizes multicore cpu’s).

thanks for that. that will give me a start. i have not used the .net threads yet. and i need to think about the lock mechanism more deeply.

thanks again. but don’t hesitate to continue discussion ;).
regards

When using threads you want to avoid two threads accessing the same point in memory at the same time, generally. This has to do with the CPU caching that variable and in the end overwriting later processes with earlier ones. You can however use the volatile keyword when declaring a variable, which means it is not cached and designed to be accessed by multiple threads simultaneously (public volatile bool volatilebool;). You can A) use locking, if it requires repeated access from multiple threads, or B)If it’s the result you care about, don’t check the result until a completion flag is reached.

i.e. simplest case: have a volatile boolean that flags when the work in done. Do not allow access to the data used by the thread until the boolean says the work is completed, avoiding two threads working on the same data.

Take advantage of Coroutines with threads. Have the thread do the work, and the Coroutine waiting till the work is done, giving you a yield-like effect for your thread and a quick and easy way to perform any Unity-based operations on the work done by the separate thread (as the Unity API is not thread-safe). As I mentioned before I can show a code sample later today, which would probably demonstrate the ideas better.

Here it is(Note: quickly written prototype code lies ahead):

using System.Threading;

namespace ThreadUtils
{
    public class Job : IAsyncResult
    {
        Action jobTask;

        Exception exception = null;

        bool isCompleted;
        public bool IsCompleted
        {
            get
            {
                return isCompleted;
            }
        }

        AsyncCallback callback = null;

        object asyncState;
        public object AsyncState
        {
            get
            {
                return asyncState;
            }
        }

        ManualResetEvent waitHandle = null;
        public WaitHandle AsyncWaitHandle
        {
            get
            {
                return GetWaitHandle();
            }
        }

        public bool CompletedSynchronously
        {
            get
            {
                return false;
            }
        }

        public Job(Action workToDo, AsyncCallback asyncCallback = null, object stateObject = null)
        {
            jobTask = workToDo;
            callback = asyncCallback;
            asyncState = stateObject;
        }

        public void Run()
        {
            try
            {
                jobTask();
            }
            catch( Exception e)
            {
                exception = e;
            }
        }

        public void Completed()
        {
            if (exception != null)
            {
                throw exception;
            }
            if (callback != null)
            {
                callback(this);
            }
            isCompleted = true;
            if(waitHandle != null)
            {
                waitHandle.Set();
            }
        }

        object waitHandleLock = new object();

        WaitHandle GetWaitHandle()
        {
            lock(waitHandleLock)
            {
                if(waitHandle == null)
                {   
                    waitHandle = new ManualResetEvent(false);
                }
                if(isCompleted)
                {
                    waitHandle.Set();
                }
            }
            return waitHandle;
        }
    }

    public class JobScheduler : MonoBehaviour
    {
        Queue<Job> workToBeDone = new Queue<Job>();
        Queue<Job> completedWork = new Queue<Job>();

        Thread workerThread;

        ManualResetEvent workerThreadResetEvent = new ManualResetEvent(false);

        static JobScheduler instance;
        public static JobScheduler Instance
        {
            get
            {
                return instance ?? (instance = new GameObject("JobScheduler").AddComponent<JobScheduler>());
            }
        }

        void Awake()
        {
            StartCoroutine(Run());
            //If you want this to run in Editor use this instead
            //IEnumerator coroutine = Run();
            //EditorApplication.update += delegate{ coroutine.MoveNext(); };
        }

        void OnDestroy()
        {
            if(workerThread != null)
            {
                workerThread.Abort();
            }
        }

        public Job AddJob(Action workToDo, AsyncCallback callback = null, object asyncState = null)
        {
            Job job = new Job(workToDo, callback, asyncState);
            lock (workToBeDone)
            {
                workToBeDone.Enqueue(job);
            }
            workerThreadResetEvent.Set();
            return job;
        }

        IEnumerator Run()
        {
            workerThread = new Thread(new ThreadStart(ProcessWork));
            workerThread.IsBackground = true;
            workerThread.Start();
            while (true)
            {
                while (completedWork.Count > 0)
                {
                    Job doneWork = null;
                    lock (completedWork)
                    {
                       doneWork = completedWork.Dequeue();
                    }
                    doneWork.Completed();
                }
                yield return null;
            }
        }

        void ProcessWork()
        {
            while (true)
            {
                if (workToBeDone.Count == 0)
                {
                    workerThreadResetEvent.Reset();
                    workerThreadResetEvent.WaitOne();
                }
                Job currentWork = null;
                lock (workToBeDone)
                {
                    currentWork = workToBeDone.Dequeue();
                }
                currentWork.Run();
                lock (completedWork)
                {
                    completedWork.Enqueue(currentWork);
                }
            }
        }
    }
}

It’s probably a bit daunting in one big block. The main idea behind it is the JobScheduler receives Jobs, which are simply a block of processing work to be done with a bit of wrapping structure. Then it works through them in a first in first out fashion, on a separate thread. Each job has an OnCompleted callback you can provide if you want to do anything on the main thread after the Job has completed (say pass the calculations to a Unity API). This example only uses 1 thread to process all tasks but it can be rearranged to do each task on a separate thread (though that would take more work).

Run() is on the main thread, and handles OnCompletion events. ProcessWork is on a separate thread and handles doing each Job in order and keeping track of which jobs to do next/mark jobs as completed.

You have 3 options to doing something at the end of a Job: Use the WaitHandle and pause the current thread until the work is completed (not common in Unity, because of the reliance on the main loop for Unity API stuff), poll the Job.IsCompletedproperty to know that the work was completed, or provide a callback delegate to do the finalization work.

Here is an example(I’ve chosen to use the OnCompleted Callback):

using namespace TheadUtils;

public class Curve : MonoBehaviour 
{
    struct MeshData
    {
        public Vector3[] verts;
        public int[] tris;
    }

    public void Awake()
    {
        MeshData visualMeshData = new MeshData();
        JobScheduler.Instance.AddJob(delegate { CreateMeshThreaded(ref visualMeshData); }, delegate(IAsyncResult result) { FinalizeMeshThreaded(visualMeshData); });      
    }

    void CreateMeshThreaded(ref MeshData data)
    {
        //Fill in MeshData struct here (this is off the main thread, and ideal for multi-frame resource intensive work).  This is cut out because it's a large example
    }

    void FinalizeMeshThreaded(MeshData data)
    {
        //This is on the main thread, and is safe to use Unity APIs, and is always called on the frame after the Job was completed
        meshFilter.mesh.Clear();
        meshFilter.mesh.vertices = data.verts;
        meshFilter.mesh.triangles = data.tris;
    }
}
}

This code is heavily truncated, but it shows a basic example of performing the mesh generation in a thread and then applying it to Unity back on the main thread once it’s completed. The ref keyword on the Creation function allows me to use a value-type struct and pass it into the threaded function, but still have a proper reference for the callback, rather than the normal behaviour.

The only elements I locked are A) The JobQueue only when Enqueueing and Dequeueing, and B) The Jobs WaitHandle because it’s only created if requested, and could cause issues if 2 threads request it at the same time.

Also the Exception object in Job is to make sure that any errors or exceptions are thrown on the main thread, which can help make them easier to catch and handle properly.

Also another nice feature with the WorkerThreadResetEvent, is that if the Job Queue is empty, it won’t do any work or check the queue until another job is added, meaning that if there is no work to be done, there is not processing done for that thread.

Ask any questions about it, As if you are unused to .NET threads there could be some strange stuff, but hopefully this helps you come up with a good system.

Edit: Added workaround for Editor not having Coroutines.

Ntero thanks for the detailed explanation and example.

i need the result but it is calculated again and again (ai, production, movement). thats why i thought to require 2 datasets one which is calculated and one which represents the result of the last calculation to work with.

i think your example will be quite helpfull especially because it directly works with unity. i will integrate this in my game and see if it does what i want. but im quite optimistic ;). many thanks.

for a more detailed explanation what i want to do.
i have a gamedata which consists of arrays of objects which are not handeled by unity. it contains stars and they contain planets, bases, fleets etc. and factions, missions etc… this data should be updated every second so i require gamedata.update be called in a thread as it contains too many objects to be done without framerate problems. but at the same time i need one of the starsystems to be accessible (where player is in) and it needs to be updated every frame (at least movement). is this possible with this threading solution? or is the data “out of scope” once given to a thread so i need to use 2 datasets (at least for the current system).

i have read all the day about .net threading mainly here. but one question has not been resolved yet for me.

i have a data class with an array of objects which need to be calculated (these having sub-objects) in an update method in a thread.
consider a loop iterating over 100 objects. every object is possible to be changed so the loopblock contains a lock. is this lock exclusively for the current object? so when object 23 is changed currently can i read-access all other objects from mainthread without having to wait for the lock finishing the whole loop? or does the lock also block the whole array/dataclass from beeing accessed (read only)?

void Update()
{// this is done in a worker thread
 for( i < 100)
 {
   lock
   {
     // change actual object here but access all others read only from main thread?
   }
 }
}

In that case you would call lock with an object. For example: lock(this) will block all other lock calls that reference ‘this’. You can use strings or blank object types (as used in the Job class), and use that reference to sort of lock a group of objects(though strings have the problem in big projects of potentially being reused).

for(int i = 0; i < objects.Length; i++)
{
lock(objects[i])
{
//Do Stuff with objects[i]
}
}

But there is some inherent danger here. If the main thread and the processing thread update the objects in the same order, then you could cause a very heavy slowdown as the processing thread would be working on the next object each time, and so the main thread would stop on every single lock in the loop. You may want some way to either A) skip by, or B) only lock the object when setting say, it’s transform settings, or C) Run the processing and main thread loops in opposite orders (that way you are guaranteed to only get 1 clash per frame. but you will almost always get one clash).

Also with regards to

There is only a very minute amount of time when you would be setting those variables, and on the processing thread you can keep them within function scope. Especially when using Value Types, as the will copy on assignation, you can handle it with only 1 set of class scoped variables, and just copy the required ones at the start of the job function, and assign at the end.

It sounds like you are going to have to play around with locking and multiple threads accessing the same data, as it may end up very particular to you setup on what can be accessed and when, As you want to minimize the amount of times the main thread and processing hit a lock at the same time, and the amount of stalling locks the main thread hits could cause some performance issues. Sometimes it can just be easier to check a volatile boolean and skip updating that object, so the main thread never stops.

The main thread does not manipulate/change the objects. it shall only read them randomly when required and when the object of interest is not modified currently by the workerthread. when an object is locked by the worker thread for manipulation and the main thread accesses it is it secure this way? does lock prevent another thread from reading the object?

the worker thread will update over several frames (once every 1 second probably) because the stuff is not visible to the player and can run in a coarse approximation. so i dont need it to run the same speed as the maingame. production and ai are not required to run/update in real time.

i think dual datasets are not required here because only one thread manipulates the objects and the other only reads (and can wait for a rare short lock).

you mean one volatile boolean per locked object?

you have been a big help for me. slowly it shapes in my head. many thanks.

The issue I was talking about would be say, having two threads to this (even if one is just reading):

for(int i = 0; i < objects.Length; i++)
{
lock(objects[i])
{
//Do Stuff with objects[i]
}
}

Because there is no time between locks, if the slower of the two processes starts ahead (and causes the faster one to stop at a lock), then what’s going to happen is that the slow one will move at it’s own pace, but the faster process can’t get ahead of it, because the next element it’s working on is always locked. This causes the normally faster process to run at almost identical speed to the slower process.

What the lock does is make sure only one thread is processing work within a lock. So when code hits a lock it A) checks if someone else is using that lock object, B) if someone is, will suspend it’s processing until the other lock is completed C) Lock the object itself, preventing other threads from using that lock object, D) do it’s work E) release it’s lock, allowing any waiting threads to continue. Locking the smallest amount of processing possible is good, because it allows other threads to work on all sorts of other work without having to suspend and wait on someone else. If you don’t use the lock keyword on both threads accessing the object it won’t work, as it only checks locks/suspends on a lock call. From your learning resource: Threading in C# - Part 2 - Basic Synchronization (This is a great threading resource too, as it goes from beginner to advanced and is well written). The object choosen isn’t really important, what’s important is that the object is shared for code blocks that access the same variables.

And yeah, one volatile boolean per locked object(as opposed to locking), can be a way to check a sort of .IsBusy and then skip it and update it’s state on the main thread on the next frame sort of design. Then the main thread will never suspend(keeping the framerate consistent), it’ll just skip an object.

Edit: With the JobScheduler above, on AddJob, it returns a reference to the newly assigned Job object. You can then store that somewhere and use it’s OnCompleted variable to know when it’s done (although currently with that code you can’t check if it’s started :S, but that can be added pretty easily (check if the ToBeDone queue contains that Job).