coroutines for newLISP

[frontera000]

I was looking at a portable coroutine library and I found one that runs on MacOSX , linux and windows.

I played around with libCoroutine
http://www.dekorte.com/projects/opensou ... Coroutine/

I wrote a bit about it in my blog. http://sparebandwidth.blogspot.com/2006 ... tines.html

Anyway, I hacked newLISP source code (version 8.9.7) to add prmitives for coroutine stuff using the libCoroutine code.

It seems to work.

Basically, I create a context for each coroutine task using a code template commonly used by bunch of threads.

Code: Select all

;;; coroutine testing

(define (make-coroutine) 
    (let (temp (append (lambda)  (list (first (args 1))) (rest (args 1))))
        (def-new 'temp (sym (args 0) (args 0))))) 

(define   (coroutine-generic  myname me him)
  (begin
    (setq taskname myname)
    (while 1
	   (println (format  "%s bytes left on stack %d" taskname (coroutine-bytes-left-on-stack me) ))
	   (coroutine-switch me him)
	   (sleep 1000))))

(define (coroutine1)
  (setq task2-handle (coroutine-create))
  (make-coroutine 'task2 (0 coroutine-generic))
  (setq task3-handle (coroutine-create))
  (make-coroutine 'task3 (0 coroutine-generic))
  (setq task4-handle (coroutine-create))
  (make-coroutine 'task4 (0 coroutine-generic))

  (coroutine-start task1-handle task2-handle (task2:task2 "task2" task2-handle task1-handle))
  (coroutine-start task1-handle task3-handle (task3:task3 "task3" task3-handle task1-handle))
  (coroutine-start task1-handle task4-handle (task4:task4 "task4" task4-handle task1-handle))

  (setq task-list '(task2-handle task3-handle task4-handle))
  (setq num 0)
  (while (< num 20)
	 (println (format  "coroutine1: bytes left on stack %d" (coroutine-bytes-left-on-stack task1-handle) ))	 
	 (coroutine-switch task1-handle (task-list (int (first (random 0 3 1)))))
	 (setq num (+ 1 num))
	 (sleep 1000)))

(setq task-main-handle (coroutine-main))
(setq task1-handle (coroutine-create))
(coroutine-start task-main-handle task1-handle (coroutine1))

But to run this, newLISP must be modified with my hacks. If anyone is interested, I can make it available.

Would you be interested in something like this Lutz?

[frontera000]

I wrote more about this coroutine hack in my blog if you care to visit...

http://sparebandwidth.blogspot.com/2006 ... wlisp.html

[pjot]

Hi frontera000,

Very interesting idea!! We have asked for some kind of multithreading in newLisp many times before. The standard answer is that we can use (fork), but this is not available in Windows (which is not a problem for me).

Besides, coroutines are not completely the same as forked processes. But a forked process can be programmed in a way that it behaves like a coprocess, of course.

But I vote to have coroutines in newLisp :-)

Peter

[Lutz]

When doing a complete implementation of coroutines things are much more involved. newLISP's result stack and environment stack would have to be replicated and switched for each instance of a coroutine. For other data structures like system variables, regex patterns, caches, etc. the same thing would have to be done. Without this one can only run simple coroutines which leave resources at exactly the same state at each switch point (yield) in the coroutine.

If coroutines have several switch points with different states you have to implement the duplication and switching of much more data strcutures inside newLISP.

For that reason forked UNIX processes were chosen, which do all the work of replicating stacks and data at the OS level. Coroutines would still be lighter during runtime, but much heavier to implement for a usable version.

newLISP can model coroutines easily with forked process, which are pretty light in newLISP because it is so light itself. The following prodcons.lsp code from the source distribution models perfectly the producer/consumer example from http://en.wikipedia.org/wiki/Coroutine

Code: Select all

# prodcons.lsp -  Producer/consumer
#
# this program only runs on Linux/UNIX

(constant 'wait -1 'signal 1 'release 0)

(define (consumer n)
        (set 'i 0)
        (while (< i n)
                (semaphore cons-sem wait)
                (println (set 'i (share data)) " <-") 
                (semaphore prod-sem signal))  
        (exit))

(define (producer n)
        (for (i 1 n)
                (semaphore prod-sem wait)
                (println "-> " (share data i)) 
                (semaphore cons-sem signal))   
        (exit))


(define (run n)
        (set 'data (share))
        (share data 0)

        (set 'prod-sem (semaphore)) ; get semaphores
        (set 'cons-sem (semaphore))

        (set 'prod-pid (fork (producer n))) ; start threads
        (set 'cons-pid (fork (consumer n)))
        (semaphore prod-sem signal) ; get producer started

        (wait-pid prod-pid) ; wait for threads to finish
        (wait-pid cons-pid) ; 
        (semaphore cons-sem release) ; release semaphores
        (semaphore prod-sem release))


(run 10)

(exit)

On the Mac Mini OS X this code can do 100,000 producer/consumer switches in less in about 1.7 seconds.

One could do further work and write coroutine-switch/start/stop functions etc. to take care of configuring semaphores correctly, starting forks etc. This could be done in a similar way As Bob has done in his coroutine demo using 'def-new' and named coroutines.

Lutz

[frontera000]

Thanks for your explanation Lutz.

I guess I am not very clear about the way these various stacks are used inside newLISP. Envrionment stack, result stack, lambda stack, etc.

I could be wrong, but the implementation of Coroutine I am using is written in C and would preserve the stacks within coroutine upon multiple entries. It isn't so much different than calling a subroutine in C.

I guess I fail to see problems.

Can you show me some examples where the coroutine running might be in jeopardy due to improper handling of the newLISP environment, result, and lambda stacks and other things? What kind of newLISP code would be affected? I can't think of any.

Regads,
Bob

[pjot]

That is a very interesting link, Lutz. I really learned something here. :-)

Now let's see if I can implement co-routines in newLisp using (fork).

I'll be back.

Peter

[frontera000]

I think that fork based emulation of coroutines is useful. And I also agree it is quite efficient, or efficient enough, in terms of context switching.

What I am interested in doing requires thousands of instantiations. That is thousdands of processes! I don't think it will do well with fork. This is easily doable with coroutines. That is why I am mainly interested in this.

I am very interested in potential problems my approach might cause in newLISP environment. So far I can't figure it out yet.

Regards
Bob

[Lutz]

...doing requires thousands of instantiations.

yes, for that fork could be too heavy (about 250kbyte per instance).

I actually started implementing some kind of cooperative scheduling in newLISP about 3-4 years ago , but stopped because it was too much code and overhead, then just used fork() and have been pretty happy with it for the applications I am involved in.

I am not familiar with your application, but wonder if each of your instances could be a statemachine and you just have a loop running over your thousands of instances? Using 'case', 'cond' or the multiple condtion form of 'if' state machines are easily programmed in newLISP.

There is also 'catch' and 'throw', which could be used to exit quickly from these instances to yield to the next one in the queue. Then there is 'source' which could be used to save the current environment/state quickly for a selected sets of variables. But if you use named instances (in a newLISP context/namespace) as you did in your coroutine demo, then you have already a stateful function.

More and more I find myself not even using 'fork' but running multiple newLISP server nodes on one or more computers and distributing stuff on to it. I am currently working on enhancing 'net-eval', 'load', 'save', 'get-url' and 'put-url' to work with 'newlisp -c -d <port>' server nodes.

The idea is that server nodes would start up empty and are then configured and controlled remotely.

There will be a 'Distributed Computing with newLISP' document ready beginning of September together with development version 8.9.8.


Lutz

[Lutz]

... continuing from previous post.

I am very interested in potential problems my approach might cause in newLISP environment.

You would have to implement some kind of setjmp()/longjmp() mechanism for the various stacks used by the newLISP VM, basically implementing some kind of continuation mechanism. Doing the coroutine work, which is done for the C language processing stack and context switching, again for the VM stacks.

If you don't do this a coroutine would yield with an environment and stack situation not expected or usable by the next coroutine in the queue.

Lutz

[frontera000]

Thanks.

I was concerned about something like that too. But all the coroutines go through one wrapper C function which just does one thing.

void coroutine_wrapper(CELL *params)
{
evaluateExpression (params);
}

Basically all the code being run by the wrapper is newLISP code. Inside newLISP code calling other primitives or lambdas preserve all the internal newLISP stacks. There is no C code being run effectively during a coroutine. And a coroutine at a time runs only of course.

I have been doing as much as I can think of to try to break my coroutine testing, expecting stack related issues in the VM. I simply cannot break it.

Perhaps I should send you the whole thing and you can try to break it?

I don't think there is a problem due to this simple approach. By the way, it is using Fibers on Windows XP. It uses "portable" ucontext in others. The last resort is setjmp and longjm but they are not really used. I would be mre worried if the library was usng setjmp/longjmp more, because I noticed newLISP code uses them for various things.

Let me know more about your thoughts and whether you'd like to look into to this more, then I can send you a tar'ed file.

[pjot]

This very basic code could be used as a framework to setup coroutines within newLisp:

Code: Select all

#!/usr/bin/newlisp
#
# Very basic coroutine implementation
#
# Using (fork), for now only 1 coroutine allowed
#
#-------------------------------------------------------------

(context 'co)

(define (create func)
    (set 'them (semaphore))
    (set 'orig (semaphore))
    (fork ((eval func)))
)

(define (resume)
    (semaphore them 1)
    (semaphore orig -1)
)

(define (yield)
    (semaphore orig 1)
    (semaphore them -1)
)

#-------------------------------------------------------------

(context 'MAIN)

(define (the_coroutine)
    (co:yield)
    (println "Routine: first stop")
    (co:yield)
    (println "Routine: second stop")
    (co:yield)
    (println "Routine: third stop")
)

(co:create 'the_coroutine)

(co:resume)

(println "Press spacebar...")
(while (!= (read-key) 32))
(println "The routine has spoken.\n")

(co:resume)

(println "Press spacebar...")
(while (!= (read-key) 32))
(println "The routine spoke again.\n")

(co:resume)

(println "Press spacebar...")
(while (!= (read-key) 32))
(println "The routine spoke at last.\n")

(exit)

A final version would take care that the forked process does not start immediately. Also more calls could be implemented, like 'status' or 'running', like in Lua.

Peter

[Lutz]

Frontera000 =>

... simply cannot break it.

I guess the problem would start if coroutines yield on different levels of VM execution, I mean coroutine A yields 2 levels deep, coroutine B resumes 1 level deep and yields at subroutines level 3, and etc. each coroutine following a different scheme. But I will download the library and study it a little bit more.

Pjot =>

... could be used as a framework...

very nice,

Lutz

[newdep]

I dont get it actualy...whats new to all this..?

[newdep]

Actualy we had this issue befor ;-) I can remember I once mentioned
the protothreads for newlisp... "http://www.sics.se/~adam/pt/" comes
very close to the way of Coroutines...

[frontera000]

Actualy we had this issue befor ;-) I can remember I once mentioned
the protothreads for newlisp... "http://www.sics.se/~adam/pt/" comes
very close to the way of Coroutines...

Coroutines are nothing new, I agree. I just wanted to be able to label off a newLISP expression as a coroutine which can behave like an independent thread with its own context.

protothreads won't work here. It uses Duff's Device which exploits C's weird switch feature. There is no way to mix in the newLISP code properly into the Duff's Device to do what I wanted.

I am still waiting to see if what I am trying to do is just plain stupid. I sent Lutz the code I was hacking and hopefully he will tell me if he can break the implementation.

Otherwise, I think it adds a nice feature to newLISP with very small amount of code increase.

Regards,
Bob

[pjot]

For me, the magic word in coroutines is 'reentrant'... :-)

Threads and forked processes are not reentrant. That is why the semaphores are needed in my small piece of code. (With threads you can stop execution waiting for mutexes to unlock, but it is not exactly the same.)

Also I found Simon Tatham's dirty trick extremely enlightening:

http://www.chiark.greenend.org.uk/~sgtatham/coroutine.h


Peter

[_ex_]

I demand coroutines in Win!! :))
Cool stuff frontera000.