[LITMUS^RT] Binary heaps for Litmus

[Glenn Elliott]

On Mar 29, 2012, at 5:00 PM, Andrea Bastoni wrote:

> On 03/29/2012 10:23 PM, Glenn Elliott wrote:
>> 
>> On Mar 29, 2012, at 4:13 PM, Andrea Bastoni wrote:
>> 
>>> On 03/29/2012 05:25 PM, Glenn Elliott wrote:
>>>> On Mar 29, 2012, at 10:32 AM, Björn Brandenburg wrote:
>>>> 
>>>>> On Mar 22, 2012, at 12:29 AM, Glenn Elliott wrote:
>>>>> 
>>>>>> I realized that binheap_delete() was more complicated than necessary.  Cleaned that up and then added binheap_decrease().  Sorry for the explosion of patches.
>>>>>> 
>>>>>> -Glenn
>>>>>> 
>>>>>> 
>>>>>> On Mar 21, 2012, at 5:02 PM, Glenn Elliott wrote:
>>>>>> 
>>>>>>> Hi All,
>>>>>>> 
>>>>>>> GSN-EDF and C-EDF use a binomial heap to prioritize CPUs.  This seems to be a little bit overkill since binomial heaps are best at heap merges.  This patch series does the following:
>>>>>>> 
>>>>>>> 1) Implements a binary heap in the style of Linux's linked lists.
>>>>>>> 2) Updates GSN-EDF to use the binary heap instead of the binomial heap to order CPUs.
>>>>>>> 3) Updates C-EDF to use the binary heap instead of the binomial heap to order CPUs.
>>>>>>> 
>>>>>>> I need to use this binary heap data structure for other work (priority queues that don't need binomial's fast merges), but I thought it could be applied to other domains.
>>>>>>> 
>>>>>>> I've attached the patches.
>>>>>>> 
>>>>>>> For those with access to CGIT on rtsrv.cs.unc.edu, here are links (easier to read):
>>>>>>> Binary Heap: http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=5b73afc4eb1b0303cb92eb29a2ecc59c1db69537
>>>>>>> GSN-EDF w/ Binary Heap: http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=bdce67bc2babc2e5b3b2440964e9cf819ac814dc
>>>>>>> C-EDF w/ Binary Heap: http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=ee525fe7ba4edf4da2d293629ffdff2caa9ad02b
>>>>>>> 
>>>>>>> All of this work is in wip-binary-heap on rtsrv.cs.unc.edu.
>>>>>>> 
>>>>>>> I've tested these patches out both in QEMU and Bonham.  Comments and suggestions are welcome.
>>>>> 
>>>>> Hi Glenn,
>>>>> 
>>>>> thanks for the patches! We were using binomial heaps at that point because that was already implemented… Just wondering, did you observe a noticeable impact on overheads by using binary heaps instead?
>>>>> 
>>>>> Thanks,
>>>>> Björn
>>>> 
>>>> I haven't made any efforts to compare the binheap performance against binomial heaps.  I would expect binheap to have only a small edge.  I actually suspect that a sorted linked list may outperform both heap-based solutions.  A linked list modification requires an update of at most 4 pointers.  For the binheap, one bubble-up operation updates 6 pointers (parent, child, left, right, reference pointer, reference double pointer).  There may be several bubble-up operations heap operation.
>>> 
>>> Mmm, a comparison of the two heap implementations with a sorted list (or a
>>> simple heap implemented on 1 array) may be interesting. Afterall, if we use it
>>> for CPUs we can bound the WC size of the array and we don't normally use more
>>> than 20/30 CPUs.
>>> 
>>> Different topic:
>>> Glenn, do we need to keep the "in_heap" field in the cpu_entry_t structure? Can
>>> we refactor it in "binheap_node" and update it after add/delete/init? I don't
>>> like too much having to remember to do this:
>>> 
>>> +	binheap_add(&entry->hn, &gsnedf_cpu_heap, cpu_entry_t, hn);
>>> +	entry->in_heap = 1;
>>> 
>>> Thanks,
>>> - Andrea
>> 
>> On node init() and delete(), we could poison the node's parent/left/right pointers.  We could add an "binheap_inheap()" function/macro that would return false if the pointer(s) are poisoned.  Or we could add a boolean to the node itself and add this tracking to the binheap routines.  I prefer the former.
> 
> I'd have preferred the latter. If I delete a node, I swap it with a
> "structure-safe deletion" location, I restore the ordering property, and I can
> safely delete the node and mark it as "!in_heap."
> When I init the node I can keep the mark !in_heap until I logically do a
> add(node, heap).
> 
> Am I missing something? (It's very likely, late and not enough coffee ;))
> 
> Thanks,
> - Andrea

The parent pointer of a valid heap-node will either be NULL (it's the root) or have a reasonable pointer value.  We can just set the parent pointer of an initialized/deleted node to 0xdeadbeef.

#define binheap_inheap(node) ( (node)->parent != 0xdeadbeef )

This would just repurpose the parent pointer as a boolean indicator when the node is not in a heap.

-Glenn