Coroutines in Lua

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

Coroutines in Lua

Stefano Lanzavecchia
==========================
print "setup"

function hot_potato_1 ()
	while (1) do
		print ("co1: n is ".. n)
		if (n <= 0) then
			return
		else
			n = n-1
			cororesume (co2)
		end
	end
end

function hot_potato_2 ()
	while (1) do
		print ("co2: n is ".. n)
		if (n <= 0) then
			return
		else
			n = n-1
			cororesume (co1)
		end
	end
end

print "create"
co1 = coronew ("hot_potato_1")
co2 = coronew ("hot_potato_2")

n =  100
print ("start: "..n)
cororesume (co1)

print("done!")
corokill(co1)
corokill(co2)
read()
==========================

This sample (borrowed and re-adapted, from an old thread in the Python-coro
maillist) works. I am using Win32 fibers (which really are coroutines, not
different at all from the ones provided by the library coro-1.x.x and I did
not have to change anything at all in the Lua source code.
I have simply registered three functions (coronew, cororesume, corokill)
whose semantic should appear clear enough from my sample.
I only have one lua_State but every coroutine has its own L->stack, created
on coronew and swapped on the fly in L on every resume. To make sure the
garbage collector does not collect stuff from suspended coroutines
(including the one implicitly associated with main!) I have to copy on
coronew the entire content of the stack into the new stack. This is a real
waste of space (and possibly also of time) but so far I haven't found
another way to do this. Would it be possible to lock all the objects on the
stack of the parent of the new coroutine?
I believe that I should now be able to implement something in the direction
of Python's micro-threads.
I still have to figure out how to make a coresume return a result,
understand what happens to the longjmp chain used by Lua to unwind the stack
when exceptions are thrown, implement the scheduling mechanism (half C, half
Lua) and a few more of these minor issues :-)
The good points of the implementation are:
1) it's not platform independent but I know it could work on Linux and
FreeBSD without too much trouble;
2) there are no memory leaks (thanks to corokill);
3) no changes to the source files of the distribution of Lua are required,
although the sources must be kept synchronised in case something fundamental
changes in lua_State or luaD_Init or lmem.c;

In case you wonder, the output of the sample looks like this:
setup
create
start: 100
co1: n is 100
co2: n is 99

[and so on, until...]

co2: n is 1
co1: n is 0
done!
--
WildHeart'2k - [hidden email]
Homepage: http://come.to/wildheart/


<<<... geeks smooching!?! ... ---
   WildHeart'98 productions>>>


Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Roberto Ierusalimschy
Coroutines is in our wish-list for Lua 4.1. Because there is no ANSI way to 
implement them, we will not put them inside Lua, but we want to make very 
easy to implement them outside Lua. We are planning to add built-in support 
for multiple Lua stacks, so you will not have to worry about the GC 
collecting things from suspended threads. 

Your approach ("I did not have to change anything at all in the Lua source 
code. I have simply registered three functions [...]") is what we have in 
mind. But there is still a long way to define the best API to support 
different implementations and coroutine "styles" (and, of course, to easy 
the task of those implementing real multi-thread in the language). 

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Steve Dekorte-6
In reply to this post by Stefano Lanzavecchia
Roberto Ierusalimschy wrote:
> Coroutines is in our wish-list for Lua 4.1. 

This is great news. 
Lua will make a fine language for implementing servers once coroutines are supported.

Steve

Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Sebby
In reply to this post by Roberto Ierusalimschy
Hi.

--- In [hidden email], Roberto Ierusalimschy <roberto@i...> wrote:
> Coroutines is in our wish-list for Lua 4.1. Because there is no 
ANSI way to 
> implement them, we will not put them inside Lua, but we want to 
make very 
> easy to implement them outside Lua. We are planning to add built-in 
support 
> for multiple Lua stacks, so you will not have to worry about the GC 
> collecting things from suspended threads. 
>

Ok, this makes me wonder. If i create different lua_State for threads 
(only building the thread specific section of each) and attach them 
to a global state before executing them, is there an issue with the 
GC cleaning up stuff it shouldn't from the inactive threads?

If so, is there a way around that?

Sebastien St-Laurent
Software Engineer, Z-Axis ltd.
[hidden email]



Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Edgar Toernig
In reply to this post by Stefano Lanzavecchia
Stefano Lanzavecchia wrote:
> 
> function hot_potato_1 ()
>         while (1) do
>                 print ("co1: n is ".. n)
>                 if (n <= 0) then
>                         return
> ...

Huh.  A coroutine that returns?  To where?

> ... and I did
> not have to change anything at all in the Lua source code.

I still think, that's impossible.

> To make sure the
> garbage collector does not collect stuff from suspended coroutines
> (including the one implicitly associated with main!) I have to copy on
> coronew the entire content of the stack into the new stack.

The stack is dynamic.  It will surely change after coronew.  So the
snapshot copied will not be valid very long.  And, the stacks of _all_
coroutines have to be marked by the gc.  Not only that of the current
coroutine and a snapshot of it's creator's stack.

Ciao, ET.

Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Edgar Toernig
In reply to this post by Roberto Ierusalimschy
Roberto Ierusalimschy wrote:
> 
> But there is still a long way to define the best API to support
> different implementations and coroutine "styles" (and, of course, to easy
> the task of those implementing real multi-thread in the language).

My current plans: a new type TAG_COROUTINE (or how types will be named
in 4.0).  Data of this type will be the the thread specific data of
lua_state + a user field for the C coroutine handle.  The lua_state
only has a reference to the currently active coroutine instead of the
thread specific data.

The C API will be 3 functions:

  handle = cocreate(cfunc, stacksize),
  void *data = cocall(handle, void *data)
  codelete(handle)

The Lua API will be even simpler:
  a global: _COROUTINE_STACKSIZE  (C stack size)
  maybe globals: cocurrent, comain.  will see.
  coro = cocreate(func)

Calling coroutines is simply done by calling them:

  a,b,c = coro(x,y,z)  -- the vars are passed/received arguments.

Delete is done by the garbage collector.


But I guess, 4.1 will take a while.  So you'll see my implementation *g*

Ciao, ET.


PS: What do you mean with "real mutli-thread"?  Real concurrent pre-
emptive threads?  That would be hell...

Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Stefano Lanzavecchia
In reply to this post by Stefano Lanzavecchia
>From Roberto:

> Coroutines is in our wish-list for Lua 4.1. Because there is
> no ANSI way to
> implement them, we will not put them inside Lua, but we want
> to make very
> easy to implement them outside Lua. We are planning to add
> built-in support
> for multiple Lua stacks, so you will not have to worry about the GC
> collecting things from suspended threads.

Great! Thank you guys :-)

>From ET:

> > function hot_potato_1 ()
> >         while (1) do
> >                 print ("co1: n is ".. n)
> >                 if (n <= 0) then
> >                         return
> > ...
>
> Huh.  A coroutine that returns?  To where?

To the guy who did coronew() at his last cororesume(). That is, in my
sample, to main right after the first cororesume(co1). I am not saying this
is the right way to do it. I just thought it was convenient for the time
being.

> > To make sure the
> > garbage collector does not collect stuff from suspended coroutines
> > (including the one implicitly associated with main!) I have
> to copy on
> > coronew the entire content of the stack into the new stack.
>
> The stack is dynamic.  It will surely change after coronew.  So the
> snapshot copied will not be valid very long.  And, the stacks of _all_
> coroutines have to be marked by the gc.  Not only that of the current
> coroutine and a snapshot of it's creator's stack.

Oh man... I did not think of that. And of course you are right. This is
going to cause me a big headache. And changes in the Lua core, of course!

> But I guess, 4.1 will take a while.  So you'll see my
> implementation *g*

I'd love to :-)

> PS: What do you mean with "real mutli-thread"?  Real concurrent pre-
> emptive threads?  That would be hell...

What I have in mind is Python's microthreads. They are based on a small
addition to the core (a timeslice parameter) which returns control to the
registered coroutine handling the task switching (the coroutine is written
in Python, Lua in our case) once the timeslice is expired (more or less).
This is almost real pre-emptive...

> And here's your problem.  The Lua stack of inactive threads has
> references to objects.  But the gc has no knowledge of these
> inactive threads and will not mark the objects referenced by their
> stacks.  So the objects will be freed.  And when a thread later
> becomes active he has references to freed objects.  Boom.

I spent all the afternoon on this yesterday, because I could not see what
was going wrong. And apparently my solution only works because my sample was
to simplistic to catch more complex cases.
Here's an example:

========================
co1 = coronew("some_function")

newvariable = 42 -- a very important constant!

cororesume(co1) -- this causes GC to activate and eventually resume main

print (newvariable) -- this will print NIL since when the stack for
-- coroutine 1 was created, newvariable did not exist, therefore when GC
-- started in coroutine 1 newvariable wasn't linked from any useful place.
=========================


Otherwise, maybe, I should handle the global state explicitly. But that
would be a hell... It would mean that I cannot preload all my utility
functions but I would have to load them inside every coroutine. Otherwise I
would have to write the coroutines so that they access this explicit global
table. I know I could instrument the access to globals so that it could try
my table if a value was not found, but that would slow down things a bit...
how much? That remains to be seen...

Thanks everyone. I am learning a lot of things from these discussions.
--
WildHeart'2k - [hidden email]
Homepage: http://come.to/wildheart/

<<<In the beginning the Universe was created.  ---
   This has made a lot of people very angry and been widely regarded as a
bad move. >>>


Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Roberto Ierusalimschy
In reply to this post by Edgar Toernig
> PS: What do you mean with "real mutli-thread"?  Real concurrent pre-
> emptive threads?

Yes.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Sebby
In reply to this post by Stefano Lanzavecchia
> > > To make sure the
> > > garbage collector does not collect stuff from suspended 
coroutines
> > > (including the one implicitly associated with main!) I have
> > to copy on
> > > coronew the entire content of the stack into the new stack.
> >
> > The stack is dynamic.  It will surely change after coronew.  So 
the
> > snapshot copied will not be valid very long.  And, the stacks of 
_all_
> > coroutines have to be marked by the gc.  Not only that of the 
current
> > coroutine and a snapshot of it's creator's stack.
> 
> Oh man... I did not think of that. And of course you are right. 
This is
> going to cause me a big headache. And changes in the Lua core, of 
course!
> 

Yeah, i didn't think of that myself. Although, i took a look at Lua's 
GC code and it seems simple enough to support multiple threads. 
Basicaly, you'd need to split up the marking and the collecting 
parts. Then simply call mark for all threads and then collect. It 
will require some changes to lua but at least it seems constrained to 
1 function. In my case it's somewhat easier since i set the gc limit 
so it doesn't do automatic collection. Since i'd be using this for 
video games, i don't want to have stalls due to gc at random points 
in time, so i'll do the gc manually when i feel it will not cause any 
speed issues (changing levels, opening up a menu, ...)

Sebastien St-Laurent


Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Edgar Toernig
In reply to this post by Roberto Ierusalimschy
Roberto Ierusalimschy wrote:
> 
> > PS: What do you mean with "real mutli-thread"?  Real concurrent pre-
> > emptive threads?
> 
> Yes.

Good luck in spinlock/semaphore/mutex hell.

I guess an incremental gc would be more interesting for the
major user base (soft real time, games).

Ciao, ET.



Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Edgar Toernig
In reply to this post by Stefano Lanzavecchia
Stefano Lanzavecchia wrote:
> 
> What I have in mind is Python's microthreads. They are based on a small
> addition to the core (a timeslice parameter) which returns control to the
> registered coroutine handling the task switching (the coroutine is written
> in Python, Lua in our case) once the timeslice is expired (more or less).
> This is almost real pre-emptive...

... while within Lua.  Sounds reasonable.

> ========================
> co1 = coronew("some_function")
> 
> newvariable = 42 -- a very important constant!
> 
> cororesume(co1) -- this causes GC to activate and eventually resume main
> 
> print (newvariable) -- this will print NIL since when the stack for
> -- coroutine 1 was created, newvariable did not exist, therefore when GC
> -- started in coroutine 1 newvariable wasn't linked from any useful place.
> =========================

Hmm...  Are you sure there's no other problem?  This should work!  The
global table is shared between all threads and shouldn't be affected.
And if you really have different L->gt the one of main should have been
freed.  But then even finding 'print' would be pretty difficult ;)

Btw, when working on such things a debug malloc that fills freed memory
may be handy to detect references to stale data.

Ciao, ET.



Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Edgar Toernig
In reply to this post by Sebby
Sebby wrote:
> 
> Basicaly, you'd need to split up the marking and the collecting
> parts.

It's already split.  Just add marking of all stacks in markall.

> In my case it's somewhat easier since i set the gc limit
> so it doesn't do automatic collection. Since i'd be using this for
> video games, i don't want to have stalls due to gc at random points
> in time, so i'll do the gc manually when i feel it will not cause any
> speed issues (changing levels, opening up a menu, ...)

I hope you know what you're doing.  Delaying gc multiple minutes may
generate a _huge_ heap if Lua is really used.  You have to program
really careful with such long gc-delays (basically you have to avoid
generating temporary objects).  It may be even better to call the gc
every frame to have a pretty short gc-run.

Ciao ET.


Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Sebby
--- In [hidden email], Edgar Toernig <froese@g...> wrote:
> Sebby wrote:
> > 
> > Basicaly, you'd need to split up the marking and the collecting
> > parts.
> 
> It's already split.  Just add marking of all stacks in markall.

Yeah, well that's kinda what i meant, for me i'd need to seperate the 
marking process from the collecting process so i can go through and 
mark all my threads. Should be trivial to do.

> > In my case it's somewhat easier since i set the gc limit
> > so it doesn't do automatic collection. Since i'd be using this for
> > video games, i don't want to have stalls due to gc at random 
points
> > in time, so i'll do the gc manually when i feel it will not cause 
any
> > speed issues (changing levels, opening up a menu, ...)
> 
> I hope you know what you're doing.  Delaying gc multiple minutes may
> generate a _huge_ heap if Lua is really used.  You have to program
> really careful with such long gc-delays (basically you have to avoid
> generating temporary objects).  It may be even better to call the gc
> every frame to have a pretty short gc-run.

Well, if i understand correctly the GC, everytime you run it (and the 
gc limit is reached), it goes through every used object to mark them 
then it goes through every object to collect thoes that haven't been 
marked. So, unless the actual cost of "freeing" an object is big, 
wouldn't the actual cost of GC be proprotional to the total number of 
objects not the number who would be collected?

But then i guess it's the kind of thing that is worth experimenting 
with. Worst case, i could put a fairly high limit (some maximum 
amount i'm willing to allocate for the heap) then regularly do GC and 
hopes that the actual collection doesn't happen too often. And i 
could also force a complete GC everytime the game does something non 
time critical.

Sebastien St-Laurent
Software Engineer, Z-Axis
[hidden email]


> 
> Ciao ET.


Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Dave Borgelt
In reply to this post by Edgar Toernig
I, too, think an incremental garbage collector to allow 'soft' real-time
performance would be a great help.

Not to say real multi-threading would be a bad thing.

Dave Borgelt

----- Original Message -----
From: "Edgar Toernig" <[hidden email]>
To: "Multiple recipients of list" <[hidden email]>
Sent: Wednesday, October 25, 2000 6:37 PM
Subject: Re: Coroutines in Lua


>
> Roberto Ierusalimschy wrote:
> >
> > > PS: What do you mean with "real mutli-thread"?  Real concurrent pre-
> > > emptive threads?
> >
> > Yes.
>
> Good luck in spinlock/semaphore/mutex hell.
>
> I guess an incremental gc would be more interesting for the
> major user base (soft real time, games).
>
> Ciao, ET.
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: Coroutines in Lua

Roberto Ierusalimschy
In reply to this post by Edgar Toernig
> Good luck in spinlock/semaphore/mutex hell.

I didn't say we would do real multi-thread; I said that our API for 
multiple Lua stacks should try to "easy the task of those implementing real 
multi-thread in the language". 

-- Roberto