Thread-support in LUA

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Thread-support in LUA

Mike Fahl
I'm interested in the possibility of doing some multi-threaded work with
LUA. However, there seem to be many global variables that could make
this diffucult. I would like to have each "LUA-thread" start out from
scratch (ie, as LUA normally starts up), and then only execute within
its own domain. 

I guess I could probably do this as separate processes (ie,
"fork"-style), but I would prefer to do it with separate threads within
the same process.

I assume this means I'd have to collect all LUA globals into a
LUAGlobals structure. I would then have to allocate one such LUAGlobal
structure for each thread, basically acting as a control block for its
LUA thread.

Does this make any sense? Have anybody else attempted something like
this? Any ideas or suggestions would be most welcome.

Mike Fahl

Reply | Threaded
Open this post in threaded view
|

RE: Thread-support in LUA

Bret Mogilefsky
Yes, I've done it for my game, but due to legal constraints by my
company, I'm not allowed to fold the changes back into Lua.  I did
cooperative multitasking, meaning each thread has to yield in order for
other threads to run and data is shared among the tasks.  You're right
in that collecting the globals together per task is the main thing, but
there are some other concerns.  In particular, Lua uses recursion for
its call stack... This is fine without multitasking, but as soon as you
add multitasking to the mix things get complex.  What happens if, say,
you have functions calling back from C to Lua in one task, so your
frames look like this:

	Lua1
	C1
	Lua2
	C2
	C3
	Lua3

While in another task, it looks like this:

	Lua4
	Lua5

If you yield from that first task to the second task, you are nested way
too deeply for the second task to properly finish or even yield to other
tasks without causing the same problem.  The solution is of course to
flatten the Lua call stack, creating an actual stack data structure on
which to push frames without recursing in C.  This is actually a lot
more difficult if you do it second (as I discovered to my misery), so
try to get it out of the way before you collect up the global variables.

If you have any questions, send them on and I'll answer them the best I
can without sending out code.

Good luck!

Bret

> -----Original Message-----
> From:	[hidden email] [SMTP:[hidden email]]
> Sent:	Monday, September 08, 1997 4:07 PM
> To:	Bret Mogilefsky
> Subject:	Thread-support in LUA
> 
> I'm interested in the possibility of doing some multi-threaded work
> with
> LUA. However, there seem to be many global variables that could make
> this diffucult. I would like to have each "LUA-thread" start out from
> scratch (ie, as LUA normally starts up), and then only execute within
> its own domain. 
> 
> I guess I could probably do this as separate processes (ie,
> "fork"-style), but I would prefer to do it with separate threads
> within
> the same process.
> 
> I assume this means I'd have to collect all LUA globals into a
> LUAGlobals structure. I would then have to allocate one such LUAGlobal
> structure for each thread, basically acting as a control block for its
> LUA thread.
> 
> Does this make any sense? Have anybody else attempted something like
> this? Any ideas or suggestions would be most welcome.
> 
> Mike Fahl

Reply | Threaded
Open this post in threaded view
|

Re: Thread-support in LUA

David Jeske-2
In reply to this post by Mike Fahl
On Mon, Sep 08, 1997 at 08:08:24PM -0300, Mike Fahl wrote:
> I'm interested in the possibility of doing some multi-threaded work with
> LUA. However, there seem to be many global variables that could make
> this diffucult. I would like to have each "LUA-thread" start out from
> scratch (ie, as LUA normally starts up), and then only execute within
> its own domain. 

I have an interest in doing the same thing. 

> I guess I could probably do this as separate processes (ie,
> "fork"-style), but I would prefer to do it with separate threads within
> the same process.

Same..

> I assume this means I'd have to collect all LUA globals into a
> LUAGlobals structure. I would then have to allocate one such LUAGlobal
> structure for each thread, basically acting as a control block for its
> LUA thread.

This was my plan when I decided I needed to do this. I have not had the
time to implement it though. A "psudo-overlapping" desire of mine is to
have first-class function definetions (like lambda functions, in that you
would do something like "boo = function(a,b) ... end". When I brought this
up before, it was said that the parser needs to be made reenterant for
this to work, so I was hoping to combine my efforts for these two things.

-- 
David Jeske (N9LCA) + [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: Thread-support in LUA

David Jeske-2
In reply to this post by Bret Mogilefsky
On Tue, Sep 09, 1997 at 12:00:25AM -0300, Bret Mogilefsky wrote:
> cooperative multitasking, meaning each thread has to yield in order for
> other threads to run and data is shared among the tasks.  You're right
> in that collecting the globals together per task is the main thing, but
> there are some other concerns.  In particular, Lua uses recursion for
> its call stack... This is fine without multitasking, but as soon as you
> add multitasking to the mix things get complex.  What happens if, say,
> you have functions calling back from C to Lua in one task, so your
> frames look like this:

However, what both of us were talking about won't run into this problem.
We were not going to share data and have a concept of "multiple-lua"
threads. We effectively just want to be able to instantiate multiple
copies of the "lua environment", each in it's own thread, but completely
separate. 

While it would be nice to include all of this functionality into Lua, I
don't have any immediate need for multiple threads within one global lua
space.

-- 
David Jeske (N9LCA) + [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: Thread-support in LUA

Luiz Henrique de Figueiredo-2
In reply to this post by Mike Fahl
>A "psudo-overlapping" desire of mine is to
>have first-class function definetions (like lambda functions, in that you
>would do something like "boo = function(a,b) ... end". When I brought this
>up before, it was said that the parser needs to be made reenterant for
>this to work, so I was hoping to combine my efforts for these two things.

We currently are working on exactly this extension for Lua 3.1.
Keep tuned. :-)
--lhf

PS: About the junk in lua-l lately:
    1. Spam is too hard to avoid. Any ideas, besides moderation?
    2. Unfortunately we have not managed to change the headers produced by
       listproc so as to avoid personal replies being sent to the list.
       listproc even puts the "wrong" "From" field, and misleads people
       into thinking that the reply will go to the sender instead of to the
       list. The "Reply-to" field is set to "lua-l", but is usually hidden
       from view.
       Does anyone know how to change this in listproc?
       In the meantime, please double check a reply before sending it.
       (This applies to me too!)

       As a whole, we are less than happy with listproc; we are thinking
       about switching to majordormo, as soon as our sysadm has some time.
       On the other hand, I'm pleased with the traffic in Lua: not too much,
       no junk at all (except for the last few days), only good questions
       and answers.

--lhf

Reply | Threaded
Open this post in threaded view
|

Re: Thread-support in LUA

Mark Ian Barlow
In reply to this post by Mike Fahl
In message <19970908210724.58827@...> David Jeske wrote:
 > On Tue, Sep 09, 1997 at 12:00:25AM -0300, Bret Mogilefsky wrote:
 > > cooperative multitasking, meaning each thread has to yield in order for
 > > other threads to run and data is shared among the tasks.  You're right
 > > in that collecting the globals together per task is the main thing, but
 > > there are some other concerns.  In particular, Lua uses recursion for
 > > its call stack... This is fine without multitasking, but as soon as you
 > > add multitasking to the mix things get complex.  What happens if, say,
 > > you have functions calling back from C to Lua in one task, so your
 > > frames look like this:
 > 
 > However, what both of us were talking about won't run into this problem.
 > We were not going to share data and have a concept of "multiple-lua"
 > threads. We effectively just want to be able to instantiate multiple
 > copies of the "lua environment", each in it's own thread, but completely
 > separate. 

There's a terminology confusion here, I think. Traditionally "threads" are
lightweight, and all share the same stack while "processes" are completely
independent as David describes. Threads do not *have* to share other data,
however, and current thinking amongst most formal methods folk is that they
shouldn't be *seen* to (from the user's point of view) even if they actually
*do* at the implementation level.

On this basis I'd say David is on the right track, but Bret has a point: You
couldn't preemtively multitask between your threads unless they each had a
protected stack space, because if you did a longjmp() to some point inside
a previously suspended thread it might subsequently walk all over the call
stack of the one you just suspended. The only way you could make this work
using a single stack would be if each thread's stack requirements were
statically determinable at compile time (with Lua? no chance!).

Pragmatically then, fork/join would be the best way to get things working
quickly, and pipes could be used for communication. David doesn't say (this
confuses me a bit) that he wants to multitask his Lua sessions and communicate
between them but I don't see what use they would be if you couldn't; If you
just want multiple independent sessions surely you just spawn them from a
shell script? I suppose this goes beyond ANSI C, however; such a "Parallel
Lua" would really need POSIX compliance as well. To go the other way would
need, as Bret says, the splitting off of Lua's call stack from C's and it's
incorporation into a "Lua_Thread" structure along with the globals.



A lot of the basic theory for multitasking derives from C.A.R. Hoare's work
at Oxford University here in the UK. IMHO, the designers of Java slipped up
badly when they used his earlier concept of monitors (ie: 'synchronised'
methods) rather than his later and much superior CSP ("Communicating-
Sequential-Processes") model as used (but not exclusively) in Ada. In the
former, a thread-safe application *can* be written, with due discipline;
in the pure form of the latter it is impossible to write an un-safe one.

Note that it is still possible under both schemes to write an application
that will deadlock, ie: halt because a closed loop of processes are all
waiting for their predecessors to perform some action before they can
continue. If you want to avoid this you must analyse your program using
higher-level concepts; Eg: restrict yourself to a client-server model and
ensure that if closed communication loops exist then the client => server
direction is always either "clockwise" or "anti".



I write embedded (sometimes quite safety-critical) multi-processor robotic
applications and I've been using an obscure parallel processing language
called 'occam' for years now. See http://www.hensa.ac.uk/parallel/occam/
if you're interested. It's based on CSP, with strict type-checking applied
to communications (and assignments too, of course). The confidence, and
hence productivity you gain from not being allowed to make mistakes is
well worth the frustration of seeing a few extra compiler errors, believe me!

I'm not suggesting Lua needs strict typing BTW, just that it *doesn't* need
<yuck> shared memory. I suppose what I *am* saying is that multi-threaded,
multi-tasking programming is only ever going to be much fun to do on a large
scale if you have a lot of compiler support, which goes against Lua's spirit
somewhat.  Java people struggle and thrash around trying to coordinate of the
order of 10 threads; Ada pushes that envelope a bit, and occam allows me to
cope easily with 100+ but only at the expense of great formality in the
language: The pre-compilation checking must be > 80% of the total
compiler code!

--  Mark Ian Barlow                Non-Linear Control Consultants Ltd.
    -----------------------------------------------------------------
    [hidden email]            Voice / Fax: +44 (0)1207 562 154

Reply | Threaded
Open this post in threaded view
|

RE: Thread-support in LUA

Tony Wetmore
Luiz,

> We currently are working on exactly this extension for Lua 3.1.

Do you have an idea when you might be releasing v3.1 of Lua?  Can
you describe what exactly you intend to implement in 3.1 to address
the "thread" issues discussed here?

Along with a co-worker, I am currently investigating various "embedded
languages" for use in our games, and need to decide which language
to integrate fairly soon.  The other languages we are currently considering
are Tcl and Python.

The single biggest problem that I see with Lua is the global environment,
where Lua seems to assume that you are only running one Lua program
at a time.

We would like to use an embedded programming language to control
many objects within our game, each having its own "brain".  Lua is one
of our top choices for such a language, obviously, but currently we
would add this multiple environment layer on top of Lua.  If you guys 
are already working on such an enhancement, however, that's better! :)

Thanks for all the great work!

+===========================================+=====================+
| Tony Wetmore (mailto: [hidden email]) | Senior Programmer   |
|-------------------------------------------| Kesmai Studios      |
| Opinions are mine, ALL mine!              | Charlottesville, VA |
+===========================================+=====================+

Reply | Threaded
Open this post in threaded view
|

Re: Thread-support in LUA

Roberto Ierusalimschy
> Do you have an idea when you might be releasing v3.1 of Lua?  Can
> you describe what exactly you intend to implement in 3.1 to address
> the "thread" issues discussed here?

I think there was a misundertanding here. What was told in the other message
was that Lua 3.1 was going to support "closures", that is, nested functions
with proper lexical scope; check below:

> >A "psudo-overlapping" desire of mine is to
> >have first-class function definetions (like lambda functions, in that you
> >would do something like "boo = function(a,b) ... end". When I brought this
> >up before, it was said that the parser needs to be made reenterant for
> >this to work, so I was hoping to combine my efforts for these two things.
> 
> We currently are working on exactly this extension for Lua 3.1.
> Keep tuned. :-)

  Lua 3.1 also is going through a lot of "reengineering", for better
modularity, clarity of source code, etc. But it is not our goal now to
support multiple environments and/or threads.

  Multiple environments can be simulated by a proper manipulation of the global
variables. From a Lua point of view (not from C), the only global state are
the global variables. You can save all global variables in a table and later
restore those variables. In this way, you have a rather good approximation of
multiple environments.

(for instance, to save an environment, you can use:

function save ()
  local env = {}
  local n, v = nextvar(nil)
  while n do
    env[n] = v
    n, v = nextvar(n)
  end
  return env
end
)

  Multiple threads is a complete different story, as already pointed out.
Even if you flatten Lua calls in the Lua stack, as Bret Mogilefsky has done,
you still do not have a general solution, since you can not mix in calls
to C that calls back Lua (like dostring, dofile, gsub, etc). Please don't get
me wrong: Bret's solution seems like an excelent piece of software. But
to be part of the language it should be a complete general and portable
solution. It seems to us that a general solution would need threads in C,
too (or at least co-rotines, that is, multiple stacks), and there is no
portable (in an ANSI universe, not only POSIX) way of doing that.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Thread-support in LUA

David Jeske-2
In reply to this post by Mark Ian Barlow
On Tue, Sep 09, 1997 at 09:56:55AM -0300, Mark Ian Barlow wrote:
> There's a terminology confusion here, I think. Traditionally "threads" are
> lightweight, and all share the same stack while "processes" are completely
> independent as David describes. Threads do not *have* to share other data,
> however, and current thinking amongst most formal methods folk is that they
> shouldn't be *seen* to (from the user's point of view) even if they actually
> *do* at the implementation level.

I'm talking purely about the mechanism of my implementation. I want to be
able to run multiple copies of the lua environment simultaneously, and in
the same address space. However, I don't want to share "lua data" between
the different lua environments. Essentially, from Lua, it'll just seem
like a normal lua environment, and from "C" it'll seem like you have
several threads (os supported threads) all running, and occasionally
calling into their own private lua environments.

> On this basis I'd say David is on the right track, but Bret has a point: You
> couldn't preemtively multitask between your threads unless they each had a
> protected stack space, because if you did a longjmp() to some point inside
> a previously suspended thread it might subsequently walk all over the call
> stack of the one you just suspended. The only way you could make this work
> using a single stack would be if each thread's stack requirements were
> statically determinable at compile time (with Lua? no chance!).

I'm going to let the OS take care of the threading issues. Yes, each
thread (we're talking real machine-C threads here) will have it's own
stack.

> Pragmatically then, fork/join would be the best way to get things working
> quickly, and pipes could be used for communication. David doesn't say (this
> confuses me a bit) that he wants to multitask his Lua sessions and communicate
> between them but I don't see what use they would be if you couldn't; If you
> just want multiple independent sessions surely you just spawn them from a
> shell script? I suppose this goes beyond ANSI C, however; such a "Parallel
> Lua" would really need POSIX compliance as well. To go the other way would
> need, as Bret says, the splitting off of Lua's call stack from C's and it's
> incorporation into a "Lua_Thread" structure along with the globals.

fork()/join() is not acceptable for what I'm doing. I have a large main
program with lots of data structures. I call into lua to handle "events".
I don't want to have events be purely "sequential", so I want to have
multiple threads, each with it's own independent lua environment. I'll
just call into the private lua environment when an event occurs, and it'll
call back into C to do things, and it'll all be private to this thread.
However, it has to operate on data-structures in my program, so
fork()/pipe() is not acceptable.

In fact what I'm talking about is not radical at all and requires no
specific support from lua. The ONLY thing I need to be able to do with Lua
which I can not currently do is to "create an instance" of the lua
environment. So I can create more instances whenever I want (one per
OS-thread).

> A lot of the basic theory for multitasking derives from C.A.R. Hoare's work
> at Oxford University here in the UK. IMHO, the designers of Java slipped up
> badly when they used his earlier concept of monitors (ie: 'synchronised'
> methods) rather than his later and much superior CSP ("Communicating-
> Sequential-Processes") model as used (but not exclusively) in Ada. In the
> former, a thread-safe application *can* be written, with due discipline;
> in the pure form of the latter it is impossible to write an un-safe one.

I'll handle the multithreadding issues in my parent C/C++ code..

> I'm not suggesting Lua needs strict typing BTW, just that it *doesn't* need
> <yuck> shared memory. I suppose what I *am* saying is that multi-threaded,
> multi-tasking programming is only ever going to be much fun to do on a large
> scale if you have a lot of compiler support, which goes against Lua's spirit
> somewhat.  Java people struggle and thrash around trying to coordinate of the
> order of 10 threads; Ada pushes that envelope a bit, and occam allows me to
> cope easily with 100+ but only at the expense of great formality in the
> language: The pre-compilation checking must be > 80% of the total
> compiler code!

I understand where you're coming frmo, and in principle I agree. However,
I merely want to use OS threads to allow the execution of several
independent "lua events" to run at the same time, so that I don't get a
"serialization" of events. 

The "protected model" for this would involve having a different address
space for each lua environment, which would have some RPC/pipe mechanism
to talk to my mail program. However, this is a game, and it dosn't need
that level of protection because the code involved is tiny, and needs to
be fast. I can't accept the overhead of fork(), and then run lua code, and
then use RPC with the main program just to do the equivilant of:

object[6]:ai_event(); -> (from C)

function ai_event(self)
    /* some computation */
    self:goto(self.newlocx,self.newlocy);
end

-- 
David Jeske (N9LCA) + [hidden email]