Re: Lua and preemptive scheduling for coroutines

["Thomas Jericke" <tjericke@...>]

> From: Leo Romanoff <romixlev@yahoo.com>
> To: "lua-l@lists.lua.org" <lua-l@lists.lua.org> 
> Date: 4:20 2013-3-29
> Subject: Lua and preemptive scheduling for coroutines
>I'd like to report about a progress on this topic:

>- I implemented the solution with pre and post hooks that I proposed above. To do this, I tweaked a bit the Lua VM. >Specifically, I tweaked the place where hooks are invoked currently and added a code to invoke a  pre-hook and a >post-hook, if they are provided. Pre and post hooks are just normal Lua functions and they are invoked by Lua VM as >Lua functions, as if they would be directly called from the user code. (BTW,  this approach could be generalized to >dynamically invoke Lua functions at any place in the user-code without changing the generated bytecodes and >injecting any CALL instructions into it. This can be pretty interesting for implementing something like debuggers, >profilers, aspect-oriented programming, etc)

>- The implementation is very small and introduces just minor changes into the Lua VM, IMHO. 

>- I compared the speed of this solution with a speed of a solution, where coroutines would explicitly call yield >every N operations of a tight loop.  So far, the pre- and post-hook based solution seems to outperform the >explicitly yielding solution by a factor of 2 on my tests, which is not bad ;-) I was actually surprised to see >that it makes things faster and not slower. I think the reason for the explicitly yielding solution to be slow is >that it needs to check on each loop iteration if a certain flag is set. And this check is a Lua code, i.e. it needs >to be interpreted/executed by the Lua VM. The hooks based solution does perform similar checks in C, which is very >efficient.

- I don't post the implementation yet, as I want to clean up it a bit first. I also would like to see if I can do a similar thing for LuaJIT.
> 
> - TODOs: 
> - I need to test that I don't break any existing code with my Lua VM modifications. Are there any test suits/unit tests for Lua that I could use for it?
> - I need to check what would happen in a solution where Lua and C calls are mixed together
> - My solution seems to swallow and not propagate errors that happen in the prehooks or posthooks. This is not such a big problem, but may be I could fix it
> - My solution may have some problems with the way how LuaVM handles RETURN bytecode instructions. If assertions are enabled, it may run into problems, because Lua VM checks that instruction which invoked current frame was a CALL instruction. But since my code just mimics the CALL of a Lua function without having a real CALL instruction in the user bytecode,  such a check would fail.
> 
> - And finally, here is some code to see how the code using this solution looks like:
> 
> local posthookCalls = 0
> local prehookCalls = 0
> local explicitYieldCalls = 0
> 
> local function hook() 
> 
> end
> 
> 
> 
> local function posthook()
>     posthookCalls = posthookCalls + 1
> 
>     coroutine.yield()
> end
> 
> 
> local function prehook()
>     prehookCalls = prehookCalls + 1
> 
>     coroutine.yield()
> end
> 
> 
> 
> local MAX_ITER = 100000000
> 
> local function task1()
> local sum = 0
> for i=1, MAX_ITER do
>     sum = sum + i
> 
> end
> print("Sum1=", sum)
> end
> 
> local function task2()
> local sum = 0
> for i=1,MAX_ITER do
>     sum = sum + i
> 
> end
> print("Sum2=", sum)
> end
> 
> 
> -- Test implicit cooperative multitasking
> local coro1 = coroutine.create(task1)
> local coro2 = coroutine.create(task2)
> 
> 
> -- New special functions for setting prehooks and posthooks
> --print ("Prehook coro1:", debug.getprehook(coro1))
> --print ("Prehook coro2:", debug.getprehook(coro2))
> --print ("Posthook coro1:", debug.getposthook(coro1))
> --print ("Postook coro2:", debug.getposthook(coro2))
> --debug.setprehook(coro1, prehook)
> --debug.setprehook(coro2, prehook)
> -- Register post-hooks, which should perform implicit yielding
> debug.setposthook(coro1, posthook)
> debug.setposthook(coro2, posthook)
> --print ("Prehook coro1:", debug.getprehook(coro1))
> --print ("Prehook coro2:", debug.getprehook(coro2))
> --print ("Posthook coro1:", debug.getposthook(coro1))
> --print ("Posthook coro2:", debug.getposthook(coro2))
> 
> -- Invoke the hook every 200 instructions for coro2
> debug.sethook(coro2, hook, "", 200)
> 
> -- Invoke the hook every 100 instructions for coro1
> debug.sethook(coro1, hook, "", 100)
> 
> 
> while(coroutine.status(coro1) == "suspended" or coroutine.status(coro2) == "suspended") do
>    coroutine.resume(coro1)
>    coroutine.resume(coro2)
> end
> 
> print ("Posthook calls using yield = ", posthookCalls)
> print ("Prehook calls using yield = ", prehookCalls)
> 
> 
> As you can see, the code is pretty simple and can be easily generalized to create a preemptive scheduler in pure Lua without any need for C code to achieve this goal.
>   
> -Leo

Hello Leo I just wanted add my two cents too even you already have a solution. Just in case you might want to know that I did almost the same thing. Just with the difference, that I wrote my Hook functions in C.

This  project now runs for over a year and we actually have a lot of machines  in the field. So don't listen to those who say that this won't work. It  is just a question whether you like to have per-emptive threads.

A few things you might want to consider that I did in my solution:
I added a new hook which is always called, at any instruction (in lvm.c)
-In  the hook I compare runtime and not number of instructions. Of course you need to have a ways to calculate runtime of your tasks to do this, a  simple os.clock comparison might be not enough. In my case I check how much time the C task that runs the interpreter used since the current Lua task was resumed.
I do this because I think that the used time is  a better indication than number of instructions (especially if you have  C calls involved).

- I check if there are other tasks and if they need time before I yield. For this you need to have some place where you store all your task that need to be scheduled.

- Very important: Yielding is not possible at all places in Lua. Lua 5.2 is a huge improvement over 5.1 when it comes to this but there are some places left. For example within  a _tostring call.
What I did was the  following. I checked how the interpreted decides if a yield is possible  (L->nny == 0) and made a function that provides me this information:

LUA_API int lua_canyield (lua_State *L) {
  return L->nny == 0;
}
Now all you have to do is to make this available in Lua as well.

As I said my hook is in C and uses a lot of calls to functions of our system, but in Lua it would look like this:
 local post_warning = true
local function instuctionhook()
  if get_elapsed_time() > time_slice and #tasks > 1 then
    if canyield() then
       post_warning = true
      coroutine.yield()
   else 
      print "Warning: Tried to yield unyieldable task."
      post_warning = false 
   end
end

The  post_warning is just used to print a warning once if you run into a situation where a yield was not possible. And to avoid spamming it is only posted once.

As I see it, the main difference is that you are using Lua in the hook, and this could then of course lead you into problems I don't have. (Like hook inside hook situations). 

Hope this helps :-)

-- Thomas