Jörg F. Wittenberger <joerg.wittenber...@softeyes.net> 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? Do you think the performance gains are worth the added complexity to the scheduler? 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. 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. Regards. _______________________________________________ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers