[Chicken-users] faster threading

[F. Wittenberger]

Hi all,

these days i asked myself if I could do something to speed up my app.

Doing the math: I have usually a minimum of 50 entries in ##sys#fd-list
and my stuff is rather critical wrt. i/o _latency_.  ##sys#fd-list is a
linear unordered list.  The network is wide area, hence we can assume a
random position of to-be-unblocked threads in the list.  => avg. 25
steps (and memory allocations) in the loop per fd becoming ready.  Under
load there are easily 150+ entries.  An O(lb n) - algorithm should need
6-8 steps even under high load (when the linear list would need 75).  So
even if a step was four times as expensive it should be a win in any
case.

I lifted the wt-tree code from slib (which I already extended to support
access to tree nodes via handles, so nodes need not to be in core - but
while that feature might be generally useful it is not used here ... and
needs documentation), wrote a module declaration around it and made
##sys#fd-list a balanced tree to find out how much I could gain.

Until now I did not find the time to create a special test case to
stress just the i/o.  My "off line" test case involves a fair amount of
computation and just a little i/o.  Still it's almost 50% faster now.
Let alone the live test, which depends on i/o latency.  Unfortunately
there is no easy way to get useful numbers from the live system, but it
does not cough as often anymore.

For me this is a worthy improvement already.  Find two files attached: a
diff adding the wttree.scm into the build (and fixing a few things in
the debian subdir) and wttree.scm itself.

There are still things left to be done.  I'll try save some select(2)
calls until the ready queue has been eaten up once.  This will require a
"still-ready" queue for those threads which had their go since the last
select call.  When no more threads are ready select shall be called and
the still-ready queue be appended to the newly unblocked threads.

Best regards

/Jörg

lb2fd.patch
Description: Text Data

wttree.scm
Description: Text Data