[SHOW] Software Threads

I've been working on implementing a software threading framework for as3. The idea, since we're constrained to a single thread for our ActionScript, is to break apart processes, and allow them to be run in the background; ideally without disrupting the game/application/whatever.

The 2 things that first came to mind are what are in the demos. First was encoding a large (or many, or both!) images and the second was pathfinding. Both of these can totally lock up the player. You can see that in both cases the UI will totally freeze when executing linearly in one go on one frame, whereas the (admittedly slower) "green" thread method, does a fair job of keeping things responsive.

image encoding demo: http://lab.generalrelativity.org/thr...imageEncoding/

pathfinding demo:
http://lab.generalrelativity.org/threading/pathfinding/

In the image encoding demo, I'm encoding that same image 3 times in both cases. You can see, with the little diagnostic graphs, allocation opening up in the thread as other processes complete.

The API is pretty straightforward, you implement a simple interface that allows your process (usually a chunk of an algorithm) to be run. Then you create a thread and pass it a list of all processes to execute, a frequency and a percentage share of the processor. The thread will do its best to maintain the framerate by allocating only the constrained amount of time and policing misbehaving processes. Threads can yield to allow for other heavy-processing to take precedence and then pick back up right where they left off.

A verbose use of the framework would be:

Code:

---

//create the processes to execute
var process1:IRunnable = new SomeProcess();
var process2:IRunnable = new SomeOtherProcess();

//wrap them in an array to pass to the thread
var processes:Vector.<IRunnable> = Vector.<IRunnable>( [ process1, process2 ] );

//define frequency
var hertz:Number = stage.frameRate;

//allow the thread to occupy whatever percentage of player's processing
var share:Number = 0.3;

//create the thread
var thread:GreenThread = new GreenThread( processes, hertz, share );

//listen for process and thread complete events
thread.addEventListener( GreenThreadEvent.PROCESS_COMPLETE, processCompleteHandler );
thread.addEventListener( Event.COMPLETE, threadCompleteHandler );

//open the thread
thread.open();

---

But there are also utility methods to shorthand some of this:

Code:

---

ThreadUtil.openSingle( myProcess, callbackMethod );

---

I have some more work on it still, but will be releasing it shortly to anyone interested.

This is awsome. It seems it's not compatible with FP9, why ?

Let's say I want to precompute a couple of things in background before starting a game. The precompute method is of this kind :

PHP Code:

---

for (var i:int=0;i<1000000;i++){
//very heavy computations
} 


---

How do I turn this into a thread ?

the idea is interesting, the demos did not convinced me yet so far as there were still some minor hick ups esspecially at the beginning on older computers here- but I think the idea is very interesting.

I remember flash pathfinding demos (flash 5 days) from the past that devided A* operations into smaler elements so that it could be spanned over a frame event and take on each cycle little resources, so instead of using loops each iteration would take place once per frame event.

If I am not mistaken similar mechanics are used in realtime strategy games were complex pathfinding and resource simulation is handled into tiny pieces aside the engine execution.

@Sietjp: Yeah, I forgot to mention it's FP10. Sorry!
So it would be really simple to turn that into a thread. You'd create a class that implements 2 methods and that stores a reference to the index (i).

Code:

---

public class HeavyComputer extends AbstractProcess implements IRunnable
{

  private var i:int;

  public function HeavyComputer() {}

  override public function run() : void
  {
      //heavy computation
      //i++
  }

  override public function get percentage() : Number
  {
      return i / 1000000;
  }

}

---

Then you create and open the thread and pass your process:

Code:

---

var thread:GreenThread = new GreenThread( new HeavyComputer(), stage.frameRate );

thread.open();

---

Before you open it, you can listen for whichever events you need to know about: When the thread completes, when a single process completes, when a process times out, and every thread cycle.

I'm also going to create a proxy process that will allow you to pass a single method as opposed to creating a class.

@renderhjs: The image encoding hiccups when part of the bytearray gets compressed. So I could possibly get rid of that if I cared enough to write a compression algorithm in this form. That said, you can do a fairly good job of controlling processing by setting a lower percentage share.

I'm curious if you were seeing anything like that in the pathfinding demo though- each iteration is 0(n) and performs really well for me.

Thanks!

Hi,

sounds cool. I am interested in your scheduling strategy, if you don´t mind.
Did you use a common one, or did you implement your own strategy?

How do you handle critical regions? Do you offer synchronisation in your API?

Regarding the speed, I have to agree with render. I don´t see much difference between the single- and the multithreaded version.

regarding speed, it should be substantially slower than the normal method. Maybe your machine is better enough than mine that you don't see a hiccup? For the pathfinding demo, click opposite corners for the start and end nodes. When I do, and click run, the UI freezes (button hangs in over or selected state) and I might even get the spinning beach ball of death. I don't see any hit at all when running the multithreaded version.

Not much in the way of scheduling... just adjusting allocation based on how well or poorly each process behaves. basically, i penalize a process if it exceeds its allocation. allocation is, otherwise, evenly broken up amongst all processes. i plan to, in the case of too many processes to maintain the frame rate, simply push the remainder into a queue.

What exactly do you mean by synchronization?

Quote:

---

regarding speed, it should be substantially slower than the normal method. Maybe your machine is better enough than mine that you don't see a hiccup? For the pathfinding demo, click opposite corners for the start and end nodes. When I do, and click run, the UI freezes (button hangs in over or selected state) and I might even get the spinning beach ball of death. I don't see any hit at all when running the multithreaded version.

---

I actually get a hiccup.

I tested the pathfinding demo with opposite corners and it seemed that the multithreaded version is 20-30 percent slower than the single- one.

Quote:

---

Not much in the way of scheduling... just adjusting allocation based on how well or poorly each process behaves. basically, i penalize a process if it exceeds its allocation. allocation is, otherwise, evenly broken up amongst all processes. i plan to, in the case of too many processes to maintain the frame rate, simply push the remainder into a queue.

---

ok, thanks.

Quote:

---

What exactly do you mean by synchronization?

---

Usually threads share some data. Synchronization guarantees that you will get always a unique result. Just imagine following scenario:

ThreadA and ThreadB share the same variable c (=2):

Thread A: multiplies c by 2;
Thread B: adds 5 to c;

So the threads run interleaved (A and B need one cycle to calculate the value):

cycle thread result
-----------------------------
1 A 2
2 B 4 //result of A
3 A 9 //result of B
4 B 18
5 A 23
....

If B somhow executes the code faster than A (A needs 3 cycles, B 1 cycle), you will get a problem.

cycle thread result
-----------------------------
1 A 2
2 B 2
3 A 7//result of B
4 B 14//result of A
5 A 19
....

Now you have got two different results. Synchronisation (for example a semaphore) ensures that this won´t happen. You can only access the critical region (in this case c) with one thread, until the critical operation is executed. The other(s) will have to wait.

There is no synchronization necessary here since its not actually threaded.
All that is happening is a time consuming algorithm is broken down to allow execution across multiple frames.
This framework just controls how many steps each algorithm is allowed to run each frame.

Its an interesting concept, but the problem is that you must manually break the algorithm into finite steps which is often the most difficult part. Adapting a recursive function to be able to stop and restart itself will be far more complicated than choosing how much of it to run each frame.

You will also run into the issue of how finely to break down the algorithm. Seperating a pathfinding algorithm into performing a single iteration per function call will come at a substantial speed cost. Allowing it to perform 200 iterations per function call may make it too coarse and make it impossible to time properly.

I'm not sure if I would use the term threading to describe the process of executing an algorithm across several frames.

Quote:

---

Originally Posted by andreaskrenmair

I tested the pathfinding demo with opposite corners and it seemed that the multithreaded version is 20-30 percent slower than the single- one.

---

Yeah, it should be a LOT slower- but without the locking.

Quote:

---

Originally Posted by 691175002

There is no synchronization necessary here since its not actually threaded.

---

The idea is that it does emulate threading though; and so to answer andreas, no, i hadn't thought of handling that. It probably wouldn't involve too much to expand it to include semaphores/locking, but at the cost of making it harder to use. In other words, I think that might throw it overboard in terms of approachability.

Quote:

---

Originally Posted by 691175002

Its an interesting concept, but the problem is that you must manually break the algorithm into finite steps which is often the most difficult part. Adapting a recursive function to be able to stop and restart itself will be far more complicated than choosing how much of it to run each frame.

---

I thought the same thing when starting off on this, but it's actually been the case that I haven't even needed to consider writing it to restart. Because the algorithm becomes a datatype, its values are all stored whether it's executing or not. so stopping/restarting is as simple as not executing it. Recursion also ends up being incredibly simple to break apart. It's definitely a different kind of thinking and an interesting algorithmic exercise for sure, but not nearly as difficult as I expected/you assume(?)!

Quote:

---

Originally Posted by 691175002

I'm not sure if I would use the term threading to describe the process of executing an algorithm across several frames.

---

Totally agreed- when I say threading or multi-threading, I mean thread emulation. Everything runs linearly in case I wasn't clear enough about that in my first post. Wikipedia to do a better job than me: http://en.wikipedia.org/wiki/Green_threads It addresses some the problems associated with not being able to execute in a different thread.

That said, with ShaderJobs we are able to execute (pixel bender) code in a separate thread. I wouldn't be too surprised to see a proper threading api offered in the not-so-distant future.

Quote:

---

Originally Posted by 691175002

There is no synchronization necessary here since its not actually threaded.
All that is happening is a time consuming algorithm is broken down to allow execution across multiple frames.
This framework just controls how many steps each algorithm is allowed to run each frame.

---

Ahh, must have misunterstood something. I should have read the description more carefully. Thanks, for making that clear.