[Chicken-users] pet project continued

[F. Wittenberger]

Hi all,

the other day I posted some modifications to the scheduler.scm, which
speed it up dramatically it you use a lot of srfi-18 features.

Thanks to a hint from Alex Shinn I also tried skip-lists since.  (Their
downside: a huge amount of code and lot's of allocations too.)

Eventually I decided to give those left leaning red black trees a shot.

Find Attached

A sched.patch - a diff against svn rev. 12496
  - Modifies scheduler.scm and Makefile
  - uses cond-expand to either compile with Marc Feeley's rbtree.scm
    (in the form I posted last time - be wary of possible licensing
    issues)  [if compiled with -feature rbtree]
    or by default with the llrbtree
B llrbtree.scm
  - Expands either to an allocation free implementation (in the style
    of Marc's rbtree) or a side effect free implementation of left
    leaning red black trees.
C llrbtree-test.scm
  - Would be better named "llrbtree-example.scm".


State Of Development

So far I did these tests:

* manually (rudimentary test code optionally expanded)
* used for a priority queue under another Scheme (rscheme)
* visualised tree under execution (this actually revealed a mistake
  I made, resulting in almost exclusively left leaning trees, if
  the minimum node is frequently deleted).
* ran askemos for some minutes (i.e., about 150 active file descriptors,
  50 subprocesses and 3000 threads)

Than I updated my chicken to prepare the posting.  (See other message.)

Best Regards

/Jörg

sched.path
Description: Text Data

llrbtree.scm
Description: Text Data

llrbtree-test.scm
Description: Text Data