On Sun, Oct 26, 2008 at 1:59 AM, Jörg F. Wittenberger <[EMAIL PROTECTED]> wrote: > > 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.
Yes, the fd-list is currently rather simplisticly handled. > > 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. > Thanks for the patch, Jörg. I'm impressed how deeply you hack the scheduler. Using a smarter data-structure for the fd-list makes sense, even though I'd like to avoid adding yet another core library unit (there are already too many), but perhaps a scaled down version could be included, exclusively for the scheduler (and thus easier to tune). I have to review this change thoroughly, and apologize in advance that it'll take some time. cheers, felix _______________________________________________ Chicken-users mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/chicken-users
