Re: [Chicken-users] faster threading

[F. Wittenberger]

Am Montag, den 03.11.2008, 11:11 -0500 schrieb Marc Feeley:
> > So please remove those legal road blocks.
> 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).

DEFINATELY!

I'm afraid my citation of the original source in the posting, where I
attached that crappy, expanded rbtree.scm might have been not prominent
enough.  Sorry for that.  That's the kind of posting I make at three
o'clock in the night, astonished by the gain of the past hours (even
though those are easily explained by a change from an exponentiell
algorithm to a logarithmic one), confused by the copyright statements in
the code and about to post some code, which is stylistically bad[*].

(((Remark to casual readers: The file was for two reasons *a
intentionally [since that would surely raise questions - even by
myself..] and *b accidentally [since it could come into the compilers
way] just the minimum the compiler would need.  No documentation,
history or copyright.  All left to pointers in the surrounding mail.)))

> Would that suit your purposes?

Since - AFAIK - it's compatible with GPL and BSD - that's enough for me.

> Concerning the alternative priority queue implementations (wttree.scm,  
> llrbtree.scm and skip lists), you have to be careful because those  
> implementations allocate memory

!!!

One of the roadblocks I encountered yesterday.

Nevertheless, Marc, I've got the feeling that llrbtree might be an
interesting alternative.  By now I'm still learning about it.  But the
stomach tells me an implementation without allocation could be possible.

Furthermore I'm interested in an implementation, wich emphasises object
sharing.  Within the Askemos system, I'm faced with a huge difference
between read and write operations to the store.  (Read is what the
underlying Scheme implementation delivers [plus a constant overhead],
mutation is 150-600ms; hardly dependant on the merits of the
implementation in use.)

>  (in the case of llrbtree.scm it is  
> stack space for non-tail recursive calls).

Which, too, means that you can not just unqueue a node.  Removal of a
node is tight to a traversal operation of the tree.

> What this means is that  
> the garbage collector might be called during a priority queue  
> operation, possibly inside the thread scheduler.

Which is a bad thing to have.

  In fact, the "this takes for ever version" of my test case - to all
  reasonable probability - hang endlessly garbage collecting.

Nevertheless - and iff my reading of the code is correct - chicken
should withstand that (or die from it anyway).  At least the old
implementation used to allocate memory in queue removal operations and
ran reliably (though slow).

>   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.

Object finalisation in Chicken is yet another topic anyway.

I would call chickens finalisation support "cooperative".  That is: if
you are unsure your finalisation procedure may ever encounter an
exception, you better wrap it into an exception handler.  Otherwise be
prepared for surprise.  And if your finalisers take their time (let's
say block on i/o...) watch your eyebrows.

Best regards

/Jörg

Footnotes:

[*]: Bad style at least for chicken, which is currently euphoric about
hygiene.  (Not to call that a bad, it's just my impression.  And I
welcome it.)