Re: [Chicken-hackers] PATCH Re: slow polling

[Jörg F . Wittenberger]

Hi Megane,

thanks for looking at my submission.  Let me try to answer your questions.

On Nov 17 2018, megane wrote:

> Jörg F. Wittenberger <address@hidden> writes:
>
> > Am 19.02.2016 um 22:39 schrieb Jörg F. Wittenberger:
> > > ...
> > > > I opened ticket 1259 for this.
> > > >
> > > > To make the kind reviewers job easier, I'll post diffs in piecemeal 
> > > > here.
> >
> > This patch goes after killing a single - but important - comment line in
> > scheduler.scm:
> >
> >     ;; This should really use a balanced tree:
> >
> > Now it does.
> >
> > This patch replaces the timeout queue with a balanced tree.
> >
> >
> >    It does not matter so much, which kind of tree we use.  But a
> >    linear list is really a bad choice.
>
> Hi Jörg,
>
> What kind of performance benefits did you see with this patch?

Sorry, it's 10 years since I wrote this code
http://lists.nongnu.org/archive/html/chicken-users/2008-10/msg00103.html

I'm not sure that my observations from those days still hold.

> Do you think the performance gains are worth the added complexity to the
> scheduler?

At that time it definitely did.

> Did you consider binary heap as the priority queue implementation? It
> can be implemented with a vector and has nicer cache performance than
> search trees which your patch seems to use.

Still I would not go with the patch today anymore: since I learned that the 
pure version of the llrb tree is considerable faster under CHICKEN (at 
least since argvectors days; I did not bother to try older versions).

(The llrb-tree egg includes a - for that reason now disabled - mutating 
version of the llrb-tree, which you could try.)

Given that experience I'd at least pitch the pure version against 
alternative algorithms to implement the priority queue.

Yes I tried a heap for my initial implementation using poll(2) with 
chicken. That is at least for the fd-list. (I failed to locate the code 
right now; should be in this context: 
http://lists.nongnu.org/archive/html/chicken-hackers/2012-05/msg00008.html 
)

> I did play with some heaps for a toy coroutine scheduler and binary heap
> was faster than binomial heap and pairing heap in simple synthetic
> tests. Less garbage too. The latter two implementations use separate
> node structures which add garbage.

That's interesting as it contradicts my observation where mutation appears 
to be worse than garbage. Though the latter was found measuring the very 
same algorithm (llrb tree) in pure and mutating versions.

Best Regards

/Jörg