It looks like I will be using this heap for my next project over the next three weeks. If there are bugs, I hope to find them. Once we're confident it is bug free, we could merge this.<br><br><div class="gmail_quote">On Thu, Mar 29, 2012 at 11:25 AM, Glenn Elliott <span dir="ltr"><<a href="mailto:gelliott@cs.unc.edu">gelliott@cs.unc.edu</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div></div><div class="h5">On Mar 29, 2012, at 10:32 AM, Björn Brandenburg wrote:<br>
<br>
> On Mar 22, 2012, at 12:29 AM, Glenn Elliott wrote:<br>
><br>
>> I realized that binheap_delete() was more complicated than necessary.  Cleaned that up and then added binheap_decrease().  Sorry for the explosion of patches.<br>
>><br>
>> -Glenn<br>
>><br>
>><br>
>> On Mar 21, 2012, at 5:02 PM, Glenn Elliott wrote:<br>
>><br>
>>> Hi All,<br>
>>><br>
>>> 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:<br>
>>><br>
>>> 1) Implements a binary heap in the style of Linux's linked lists.<br>
>>> 2) Updates GSN-EDF to use the binary heap instead of the binomial heap to order CPUs.<br>
>>> 3) Updates C-EDF to use the binary heap instead of the binomial heap to order CPUs.<br>
>>><br>
>>> 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.<br>
>>><br>
>>> I've attached the patches.<br>
>>><br>
>>> For those with access to CGIT on <a href="http://rtsrv.cs.unc.edu" target="_blank">rtsrv.cs.unc.edu</a>, here are links (easier to read):<br>
>>> Binary Heap: <a href="http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=5b73afc4eb1b0303cb92eb29a2ecc59c1db69537" target="_blank">http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=5b73afc4eb1b0303cb92eb29a2ecc59c1db69537</a><br>


>>> GSN-EDF w/ Binary Heap: <a href="http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=bdce67bc2babc2e5b3b2440964e9cf819ac814dc" target="_blank">http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=bdce67bc2babc2e5b3b2440964e9cf819ac814dc</a><br>


>>> C-EDF w/ Binary Heap: <a href="http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=ee525fe7ba4edf4da2d293629ffdff2caa9ad02b" target="_blank">http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=ee525fe7ba4edf4da2d293629ffdff2caa9ad02b</a><br>


>>><br>
>>> All of this work is in wip-binary-heap on <a href="http://rtsrv.cs.unc.edu" target="_blank">rtsrv.cs.unc.edu</a>.<br>
>>><br>
>>> I've tested these patches out both in QEMU and Bonham.  Comments and suggestions are welcome.<br>
><br>
> Hi Glenn,<br>
><br>
> 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?<br>
><br>
> Thanks,<br>
> Björn<br>
<br>
</div></div>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.<br>


<font color="#888888"><br>
-Glenn<br>
</font><div><div></div><div class="h5">_______________________________________________<br>
litmus-dev mailing list<br>
<a href="mailto:litmus-dev@lists.litmus-rt.org">litmus-dev@lists.litmus-rt.org</a><br>
<a href="https://lists.litmus-rt.org/listinfo/litmus-dev" target="_blank">https://lists.litmus-rt.org/listinfo/litmus-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br>Jonathan Herman<br>Department of Computer Science at UNC Chapel Hill<br>