Re: [Chicken-users] faster threading

[Marc Feeley]

On 2-Nov-08, at 6:50 PM, Jörg F. Wittenberger wrote:

> > Yes, that seems to be the best course of action, unless Marc consents
> > to re-release his code under a BSD license for inclusion in Chicken.
> >
> > If we ask nicely, he might very well do!
>
> I hope so!  Marc, would you please do!
>
> In "exchange" I shall take my spare time to finish the llrbtree (I  
> admit
> I'm afraid I've got hooked to do so anyway) and release it under a
> license (set) compatible with gambit and chicken (and rscheme ;-).  In
> the hope that this might improve gabmit-c too.
>
> So please remove those legal road blocks.

Let me clarify the situation.  My implementation of red-black trees  
(rbtree.scm) was inspired by the MIT-Scheme file of the same name.   
The MIT-Scheme file is licensed under the MIT license.  The LGPL  
license I put on the Snow rbtree.scm was for consistency with the  
other Snow files.  I am willing to change my rbtree.scm to an MIT  
license.  Would that suit your purposes?  In any case, the copyright  
information must be maintained, simply to indicate who has  
intellectual property of the code (i.e. an acknowledgement of who  
designed and wrote the code).

Concerning the alternative priority queue implementations (wttree.scm,  
llrbtree.scm and skip lists), you have to be careful because those  
implementations allocate memory (in the case of llrbtree.scm it is  
stack space for non-tail recursive calls).  What this means is that  
the garbage collector might be called during a priority queue  
operation, possibly inside the thread scheduler.  This is not a good  
thing because it precludes the implementation of object finalization  
by the garbage collector (i.e. the garbage collector cannot call  
object finalizers, such as will executors, at the end of the GC  
because a finalizer might request an operation on the priority queue  
which is currently in an inconsistent state).  To put it another way,  
it is hard to make the priority queue operations appear atomic if they  
allocate memory.  My red-black tree implementation allocates no memory  
and requires a shallow call stack.

Marc