Re: [Libevent-users] bug in min_heap
On Wed, Apr 15, 2009 at 08:00:39PM +0300, Marko Kreen wrote: [...] > Well, I attached a draft of it, but its totally untested and the > minheap code is not very parseable for me. So somebody with > has better understanding of the code should review it. (Maxim?) > > Basic idea - if you replace an element in the middle of heap with > last element, there is chance it needs to be pushed up not down. I've checked this in for now, but please see the comments on Sourceforge at https://sourceforge.net/tracker/index.php?func=detail&aid=2778433&group_id=50884&atid=461324 I think that this might not actually be a bug; I can't seem to write a test case that provokes it. Have I missed something? Do you have a test case? yrs, -- Nick ___ Libevent-users mailing list Libevent-users@monkey.org http://monkeymail.org/mailman/listinfo/libevent-users
Re: [Libevent-users] bug in min_heap
On 4/15/09, Nick Mathewson wrote: > On Wed, Apr 15, 2009 at 01:01:00PM +0300, Marko Kreen wrote: > > Given heap shape of: > > > > 1 > >/ \ > > / \ > > 10 3 > >/ \ / \ > > 11 12 5 6 > > > > And now deleting '11', it seems to fail to keep heap property. > > > > The bug is probably hard to notice in practice as the events > > will reach top anyway, only later than expected. > > Got a patch for this? Well, I attached a draft of it, but its totally untested and the minheap code is not very parseable for me. So somebody with has better understanding of the code should review it. (Maxim?) Basic idea - if you replace an element in the middle of heap with last element, there is chance it needs to be pushed up not down. I found it when writing heap code for my own small libevent-compatible event loop. I've used to writing against libevent API, but when the program will process only small number of connections, it seems unnecessary to create libevent dependency for it. Code can be seen here: http://github.com/markokr/libusual/blob/0812279371dcf07ea3961642ecf88403dceda2e6/usual/heap-impl.h > > Btw, I did not got feedback on my event struct size decreasing patch: > > > > http://monkeymail.org/archives/libevent-users/2008-July/001346.html > > > > 24 bytes on 64-bit platforms may not sound like a big memory saving, > > but if we want to process tens or even hundreds of thousands of events > > with maximum efficiency, then best use of CPU caches becomes important. > > And there the bytes can matter. > > > This looks pretty good. I'll apply it in 2.0; Thanks. > I'd prefer to leave the > struct layout alone for the 1.4 series so as not to break binary > compatibility more than necessary. Yeah, thats reasonable. -- marko Index: minheap-internal.h === --- minheap-internal.h (revision 1174) +++ minheap-internal.h (working copy) @@ -88,7 +88,12 @@ { if(((unsigned int)-1) != e->min_heap_idx) { -min_heap_shift_down_(s, e->min_heap_idx, s->p[--s->n]); + struct event *last = s->p[--s->n]; +unsigned parent = (e->min_heap_idx - 1) / 2; + if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last)) +min_heap_shift_up_(s, e->min_heap_idx, last); + else +min_heap_shift_down_(s, e->min_heap_idx, last); e->min_heap_idx = -1; return 0; } ___ Libevent-users mailing list Libevent-users@monkey.org http://monkeymail.org/mailman/listinfo/libevent-users
Re: [Libevent-users] bug in min_heap
On Wed, Apr 15, 2009 at 01:01:00PM +0300, Marko Kreen wrote: > Given heap shape of: > > 1 >/ \ > / \ > 10 3 >/ \ / \ > 11 12 5 6 > > And now deleting '11', it seems to fail to keep heap property. > > The bug is probably hard to notice in practice as the events > will reach top anyway, only later than expected. Got a patch for this? > Btw, I did not got feedback on my event struct size decreasing patch: > > http://monkeymail.org/archives/libevent-users/2008-July/001346.html > > 24 bytes on 64-bit platforms may not sound like a big memory saving, > but if we want to process tens or even hundreds of thousands of events > with maximum efficiency, then best use of CPU caches becomes important. > And there the bytes can matter. This looks pretty good. I'll apply it in 2.0; I'd prefer to leave the struct layout alone for the 1.4 series so as not to break binary compatibility more than necessary. BTW, if anybody else has any patches or code we seem to have totally dropped on the floor, could you upload them to the sourceforge tracker? Niels and I tend to do Libevent work in fits and starts, and between our productive periods, it's easy to lose track of what everybody else has done. -- Nick ___ Libevent-users mailing list Libevent-users@monkey.org http://monkeymail.org/mailman/listinfo/libevent-users
[Libevent-users] bug in min_heap
Given heap shape of: 1 / \ / \ 10 3 / \ / \ 11 12 5 6 And now deleting '11', it seems to fail to keep heap property. The bug is probably hard to notice in practice as the events will reach top anyway, only later than expected. Btw, I did not got feedback on my event struct size decreasing patch: http://monkeymail.org/archives/libevent-users/2008-July/001346.html 24 bytes on 64-bit platforms may not sound like a big memory saving, but if we want to process tens or even hundreds of thousands of events with maximum efficiency, then best use of CPU caches becomes important. And there the bytes can matter. -- marko ___ Libevent-users mailing list Libevent-users@monkey.org http://monkeymail.org/mailman/listinfo/libevent-users