Right, it needs to go, we need to eliminate the "lumps" in time :)
> >
> > -Bret
>
> Wouldn't a heap be a good data structure for a list of timers? Insertion
> is log(n) and finding the one with the least time is O(1), ie pop off the
> front.... It can be implemented in an array which should help cache
> coherency and all those other things they talked about in school :)
>
I must be missing something here. You get log(n) from what? B-trees?
How would you manage them to get the needed balance? Stopping the world
to re-balance is worse than the cascade. I guess I need to read up on
this stuff. A good pointer would be much appreciated.
Meanwhile, I keep thinking of a simple doubly linked list in time
order. To speed it up keep an array of pointers to the first N whole
jiffie points and maybe pointers to coarser points beyond the first N.
Make N, say 512. Build the pointers as needed. This should give
something like O(n/N) insertion and O(1) removal.
George
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/