[Chicken-users] pet project continued

[F. Wittenberger]

Hi all,

at Fri, 14 Nov 2008 16:21:45 +0100 I posted last time about some
modifications to the scheduler, which make it use O(log(n)) algorithms
instead of O(n) (actually O(log(n)) instead of O(n^2) while - in reality
- rarely n!=1).

Since then I improved the implementation of
left-leaning-read-black-trees, which I attached to the the last posting.

The version I posted contains a macro, which expands to a reasonable
implementation for the allocation free case (which I focused on to
improve chicken's scheduler).  Today I want to share with you a version,
which avoids most non-essential memory allocations for the case where it
expands to a pure implementation.  ((Hence it's not chicken/scheduler
specific but about llrbtree.scm in general.  ---  Only for Felix: on the
shallow tested version I sent you in private mail in between: it had a
bug in the impure version too, so please save your time and never try
anything but the attached version.))

For completeness I attach the scheduler.scm, which I am currently using.
(Not a diff, since the diff is just 11 lines shorter that the whole
file.)  You need to compile chicken's scheduler with -feature llrbtree
set using this one line patch:

$ svn diff rules.make 
Index: rules.make
===================================================================
--- rules.make  (Revision 12875)
+++ rules.make  (Arbeitskopie)
@@ -1249,7 +1249,7 @@
 regex.c: $(SRCDIR)regex.scm
        $(CHICKEN) $< $(CHICKEN_LIBRARY_OPTIONS)
$(CHICKEN_PCRE_LIBRARY_OPTIONS) -output-file $@ 
 scheduler.c: $(SRCDIR)scheduler.scm
-       $(CHICKEN) $< $(CHICKEN_LIBRARY_OPTIONS) -output-file $@ 
+       $(CHICKEN) $< $(CHICKEN_LIBRARY_OPTIONS) -extend llrbtree.scm
-output-file $@ 
 profiler.c: $(SRCDIR)profiler.scm
        $(CHICKEN) $< $(CHICKEN_LIBRARY_OPTIONS) -output-file $@ 
 stub.c: $(SRCDIR)stub.scm


Placing the attached files into the chicken source directory and
applying above patch to rules.make is supposed to be all you need to use
these modifications.

Best reagards

/Jörg

PS: Is this patch for you?

If you are less than a dozen of thread at once, you will hardly measure
a difference.  But if you run - like me - at 200-300 open file
descriptors at once and some more active threads (((I've been trying
httperf these days with Askemos [see www.askemos.org ], which sometimes
creates hundreds of threads being _ready_ to run[*]))) you'll see a
difference between "dire need to hit Ctrl-C" and "twice as fast as
rscheme" for exactly the same program.
(Regarding the Askemos implementation that is, I'm curious to read about
the effects for you, but please litter my private mailbox only, not the
list.  If I get enough responses I'll post a summary.)

Otherwise there is only one important difference to the original version
of chickens/scheduler.scm: Slot 4 of the "thread" structure now contains
an _entry_ of the ##sys#timeout-list instead of it's key.  Since that's
nowhere reference but in scheduler.scm it should be API-compatible.
(Which correlates with my personal experience.  Please sent me a note it
that's not the case for you!)



[*] Threads blocked anywhere do not increase the load on default chicken
but those being ready and those waiting for timeout do.

llrbtree.scm
Description: Text Data

scheduler.scm
Description: Text Data