Subject: Re: Preparing callout(9) for a HZ-less kernel
To: None <tech-kern@NetBSD.org>
From: David Laight <firstname.lastname@example.org>
Date: 10/25/2007 21:13:49
On Wed, Oct 24, 2007 at 10:39:19AM +0200, Joerg Sonnenberger wrote:
> On Tue, Oct 23, 2007 at 10:54:35AM -0400, der Mouse wrote:
> > >> A 'heap' [...]
> > > I'm so sure about the heap. We can't just use the classic binary
> > > heap as that needs a resizable array we don't have.
> > A heap is a particular subclass of binary tree. Storing it in an array
> > is just a way to optimize away the parent and child pointers, and make
> > it easy to find the insertion point for new nodes.
> Sure, but if you do that it is not that much cheaper then an red black
> tree anymore.
It should be, because you don't have to do any rebalancing, just a ripple
up/down on start/stop/expire. It would require 5 pointers/node, which
would end up pulling in a lot of cache lines during any operation.
David Laight: email@example.com