Messages in this thread | | | Date | Thu, 7 Oct 2010 02:24:14 -0400 | From | Mathieu Desnoyers <> | Subject | Re: [RFC PATCH] Prio_heap: heap_remove(), heap_maximum(), heap_replace() and heap_cherrypick() |
| |
* Balbir Singh (balbir@linux.vnet.ibm.com) wrote: > * Mathieu Desnoyers <mathieu.desnoyers@efficios.com> [2010-10-06 14:03:23]: > > > These added interfaces lets prio_heap users lookup the top of heap item without > > performing any insertion, perform removal of the topmost heap entry, and also > > replacement of topmost heap entry. This is useful if one need to use the result > > of the lookup to determine if the current maximum should simply be removed or if > > it should be replaced. > > > > This is used by the Generic Ring Buffer to perform timestamp-based fusion-merge > > of per-cpu buffer records into a single stream. > > > > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> > > Cc: Paul Menage <menage@google.com> > > Cc: David Rientjes <rientjes@google.com> > > Cc: Nick Piggin <nickpiggin@yahoo.com.au> > > Cc: Balbir Singh <balbir@in.ibm.com> > > Cc: Cedric Le Goater <clg@fr.ibm.com> > > Cc: "Eric W. Biederman" <ebiederm@xmission.com> > > Cc: Andrew Morton <akpm@linux-foundation.org> > > Cc: Linus Torvalds <torvalds@linux-foundation.org> > > --- > > The patchset looks good to me, one comment on cherry picking below > > Acked-by: Balbir Singh <balbir@linux.vnet.ibm.com>
Thanks!
[...] > > +/** > > + * heap_cherrypick - remove a given element from the heap > > + * @heap: the heap to be operated on > > + * @p: the element > > + * > > + * Remove the given element from the heap. Return the element if present, else > > + * return NULL. This algorithm has a complexity of O(n), which is higher than > > + * O(log(n)) provided by the rest of this API. > > + */ > > +extern void *heap_cherrypick(struct ptr_heap *heap, void *p); > > One way to reduce cherrypick'ing in O(n) if n is large, is to sort the > entire heap using heapify() and then doing a binary search. The cost > of sorting is high, so it depends on how often and in what phases we > cherry pick.
I need this to implement the ring buffer iterator "reset" primitive, which is very infrequently called. So for my use-case, I really prefer to keep very fast add/remove/get max (as implemented currently) without sorting the rest of the heap. What you propose looks more like a balanced binary tree, which we already have in the kernel, but clearly adds some overhead by requiring to keep the whole tree sorted.
Thanks,
Mathieu
-- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
| |