Subject: Re: Callouts
To: Charles M. Hannum <firstname.lastname@example.org>
From: Dennis Ferguson <email@example.com>
Date: 03/27/1999 09:36:54
> Now that's actually a good point.
> At least one way around that comes to mind right offhand. Rather than
> storing the index in the heap structure, you can store a pointer to
> where the driver records the index -- updating the driver's knowledge
> whenever the structure moves. However, this screws your TLB footprint
> and starts to eat into any memory savings.
Though if you are this far you might as well go the whole way. A heap
requires copying O(log n) entries on every operation. If the entries are
16 or 32 bytes long you've substantially increased the data movement
overhead compared to what you would have to do if heap entries were
4 or 8 byte pointers.
So rather than storing timer entries in the heap, and pointers outside,
it seems like it would be much better to store pointers in the heap and
timer entries outside, with an index in the timer entry tracking the
location of the pointer in the heap to allow removal. Same amount of
data structure, but less copying. Then handles could just point at
the timer entry.