Re: Lua and light threads

[Bret Mogilefsky <mogul@...>]

On Fri, Oct 20, 2000 at 12:28:49PM +0200, Stefano Lanzavecchia wrote:
> 1) it is possible (the way Bret did years ago) to unwind the stack (i.e.:
> not rely on C recursive calls) at least for pure Lua-to-Lua function
> invocation, but it would mean a lot of work and a lot of changes to the
> various files in the source code to implement the same thing for all the tag
> methods, since all of them are implemented as calls to different C routines
> eventually calling luaD_call or friends. Because all the implementations of
> OO paradigms on Lua are based on tag methods (index, settable, setglobal,
> getglobal and so on) if this wasn't done, the scheduler would be very very
> jumpy; I don't know now how to reconcile this fact with the perceived need
> to maintain the set of changes to a minimum, and not to manually inline into
> luaVM_execute all the external C calls so that the VM becomes (almost)
> stackless;

I spent last night looking through the code, and the code is laid out in
much the same way it was in 3.1alpha, with the nice addition that all global
variables are now contained in the lua_Stat structure.  Thank you, Tecgraf
guys, for making this change, which I'm sure was tedious.

As a result of this work, only two files (really two functions!) need to be
modified to get the same results I did for Grim.  You are correct in that
there are many, many possible ways for luaD_call() to be recursed into as a
result of tag methods, lineHooks, callHooks, garbage collection, etc.... I
will refer to these as "indirect" calls to Lua functions.  ("Direct" calls,
then, are those caused by OP_CALL and OP_TAILCALL.)  The important
realization is that you don't want to "sleep" during an indirect call
anyway!  Not only is it unlikely that you would want to, but it's easy to
enforce this restriction; I kept a static "recursion count" inside
luaD_call() that was incremented on entry and decremented on exit.  (Side
note: Now this counter needs to go into the state structure in order to
maintain Lua's thread-safety.)  If a sleep was called, I checked this
count.  If it indicated a nested luaD_call, it must be a result of an
indirect call.  At this point I would throw out a message to warn that
sleeping was not allowed in this context and was ignored, then simply
continue execution.  It was frustrating to have this as a run-time rather
than compile-time message, but after you see the message a couple of times,
it becomes very obvious when a sleep is allowed and when it's not.

I guess I've misled you all if I said I completely eliminated the
recursion... I eliminated it for the common ("direct") case, where it was
necessary in order to support an explicit sleep.  Where that's not
necessary, I still let it happen.

> 2) it would be easy to stop the scheduler from intruding in the case of a
> Lua->C->Lua sequence of calls, so that's not an issue;

People seem to think I had a scheduler deep inside Lua handing off between
the tasks.  Not true: in 4.0's terms, I had a list of lua_States right at
the very top of the API.  "Scheduling" just meant they were run one after
the next, where they might stop part way through execution, and they might
finish execution.  If they finished they got recycled (since they probably
already had a stack that had been realloc'd a few times), and otherwise I
just kept traversing the list.  (I called my "update and draw the world"
function each time I reached the end of the list.) This is easily doable on
top of 4.0's API.

I should mention I also provided some appropriate meta-functions for
manipulating tasks/states, which were all pretty simple.  First, a
stateHook similar to lineHook and callHook that was called every time a
task was created, started, stopped, or finished; this made the tasked
version of our debugger possible.  I also added nexttask() with operation
similar to next(), for iterating over running tasks from within Lua (at the
C level I just iterated over my list of states).  nexttask()
iterated over them in the order that they appeared in the list, and I
provided a function to say "put task A in front of task B" to provide a
simple priority mechanism usable from within Lua as well as without.  Of
course this is useless without the additional taskentry() which returns the
function that started the task.

> 3) I don't quite see (it's my ignorance on the subject) how setjmp/longjmp
> could help in this matter. If anybody wanted to share their experience with
> me on the subject, I would be more than grateful.

I'm confused about how people want to use this as well... Can anyone explain?

> A heart-felt "thank you" to the developers at Teccgraf who are so nice and
> let us have the fruit of their work for free.

I feel the same way... And as I'm sick of the feeling that I'm not giving
something in return for the pleasure of having Lua to begin with, I've
started reimplementing my changes at home in 4.0.  Note the "at home" part;
I'm saying I don't have a time frame for their completion.  It all depends
on how distracted I get... Active discussion on the Lua list keeps me very
interested.  =)

I was so tired at the end of Grim that I thought I'd never want to go back
and figure all those changes out again, but the quality of the Lua code is
really quite good, and after just a few moments browsing through it, I
found myself in familiar territory, keenly aware of all the issues again in
a way I am sure I was not by the time I wrote my original mail to the list.
Having all of those details in mind, I feel up to doing it all again.

Here is a pseudo-sketch of the elimination of the recursion of luaD_call()
during "direct" calls.  Local variables in luaV_execute() such as the
program counter are restored on entry and saved on return using a struct
that gets passed in as an argument, much like L->top does now.  OP_CALL and
OP_TAILCALL now return rather than call luaD_call().  The base and nresults
that they would normally pass as parameters are given back to the enclosing
luaD_call, which pushes its own base/nresults on a stack, then calls
luaV_execute() as normal with the base/nresults that were just returned.
It's a little brain-twisting, but once it's done it's fairly easy to follow
because the new logic all stays in luaD_call().  The only wrinkle right now
is proper handling OP_TAILCALL, which has different semantics I need to get
used to; it didn't exist in Lua 3.1.

With Roberto, Luiz, and Waldemar's permission, I would very much like to
contribute this first part to the next 4.0 beta. This is no way changes Lua
semantics and should have a negligible effect on speed. All it does is make
the remaining cooperative-task work splice more naturally into the base
code so that the eventual patch is more intelligible.  I'm hoping to finish
this part this weekend.

Sorry to be so long-winded...

Bret


PS: The code really is great... The only change that makes me sad is seeing
the debug-only "LINE" opcode eliminated.  Though I think it's great that
this was done (and done so cleverly!), it makes me despair of ever being
able to do anything with the compiled Lua code from Grim... Oh well, such
is progress.  Thanks again for providing such great code, guys!

-- 
Bret Mogilefsky  ** mogul@playstation.sony.com **  Programmer, SCEA R&D