Re: Lua and preemptive scheduling for coroutines

[Leo Romanoff <romixlev@...>]

----- Ursprüngliche Message -----
> Von: Thomas Jericke <tjericke@indel.ch>
> An: Leo Romanoff <romixlev@yahoo.com>; Lua mailing list <lua-l@lists.lua.org>
> CC: 
> Gesendet: 12:54 Sonntag, 31.März 2013
> Betreff: Re: Lua and preemptive scheduling for coroutines
> 
>>  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. 

Thanks a lot for your feedback! It is very interesting. 

>Just with the difference, that I wrote my Hook functions in C.

Yep. I was also playing with this idea. But I wanted to have a flexibility of defining hooks in Lua.

> 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.

Yes, I haven't listened and just implemented it ;-)

> 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)

Exactly, I also changed the code in lvm.c.

I'm not sure you really need to call your hook at any instruction. Simple arithmetic opcodes, access to variables and the like is not so interesting for interception. They never consume a lot of time.
I could be enough to intercept only CALLs (i.e. control flow opcodes and something that may result in invocations of (long lasting) functions) and in addition every N instructions probably (for a very long linear code or for tight loops without any calls).

> -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 agree that instruction counts are not very good estimates. But of course with my solution I can mimic yours. I would simply check the used-time in the posthook and decide if I need to yield or not.

> - 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.

Sure. As I indicated, in my example code I haven't implemented a real scheduler and used a stupid while loop which alternates between two specific threads. In a real world scenario, one would keep a set of threads to be scheduled and decide after each yield which thread should be resumed next.

> - 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.

This is a very good point and hint how to solve it! Thanks! I'll definitely look into it.

> 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.

Makes sense. This is how my posthook could look like.

> 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 :-)

Yes, thanks. This is very informative!

-Leo