[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Chicken-users] pet project continued

From: F. Wittenberger
Subject: [Chicken-users] pet project continued
Date: Fri, 14 Nov 2008 16:21:45 +0100

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


Attachment: sched.path
Description: Text Data

Attachment: llrbtree.scm
Description: Text Data

Attachment: llrbtree-test.scm
Description: Text Data

reply via email to

[Prev in Thread] Current Thread [Next in Thread]