Prio_heap: heap_remove(), heap_maximum(), heap_replace() and heap_cherrypick()
RFC PATCH 1/1 Prio_heap: heap_remove(), heap_maximum(), heap_replace() and heap_cherrypick()
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.
--- include/linux/prio_heap.h | 44 ++++++++++++++++++++++ lib/prio_heap.c | 91 ++++++++++++++++++++++++++++++++++++---------- 2 files changed, 116 insertions(+), 19 deletions(-)
include/linux/prio_heap.h +44 -0
@@ -23,6 +23,18 @@ struct ptr_heap { };/** +* heap_maximum - return the largest element in the heap +* @heap: the heap to be operated on +* +* Returns the largest element in the heap, without performing any modification +* to the heap structure. Returns NULL if the heap is empty. +*/ +static inline void *heap_maximum (const struct ptr_heap *heap) +{ +return heap->size ? heap->ptrs[0 ] :NULL ; +} + +/** * heap_init - initialize an empty heap with a given memory size * @heap: the heap structure to be initialized * @size: amount of memory to use in bytes
@@ -53,6 +65,38 @@ void heap_free(struct ptr_heap *heap);*/ extern void *heap_insert (struct ptr_heap *heap,void *p); +/** +* heap_remove - remove the largest element from the heap +* @heap: the heap to be operated on +* +* Returns the largest element in the heap. It removes this element from the +* heap. Returns NULL if the heap is empty. +*/ +extern void *heap_remove (struct ptr_heap *heap); +/** +* 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); + +/** +* heap_replace_max - replace the the largest element from the heap +* @heap: the heap to be operated on +* @p: the pointer to be inserted as topmost element replacement +* +* Returns the largest element in the heap. It removes this element from the +* heap. The heap is rebalanced only once after the insertion. Returns NULL if +* the heap is empty. +* +* This is the equivalent of calling heap_remove() and then heap_insert(), but +* it only rebalances the heap once. +*/ +extern void *heap_replace_max (struct ptr_heap *heap,void *p);#endif /* _LINUX_PRIO_HEAP_H */
lib/prio_heap.c +72 -19
108 lines not on this page · raw message
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 18 lines · Mathieu Desnoyers
These added interfaces lets
prio_heapusers 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 <[email protected]>Cc Paul Menage <[email protected]>Cc David Rientjes <[email protected]>Cc Nick Piggin <[email protected]>Cc Balbir Singh <[email protected]>Cc Cedric Le Goater <[email protected]>Cc "Eric W. Biederman" <[email protected]>Cc Andrew Morton <[email protected]>Cc Linus Torvalds <[email protected]>
Quoted 1 line
---
The patchset looks good to me, one comment on cherry picking below
Quoted 40 lines
include/linux/prio_heap.h | 44 ++++++++++++++++++++++ lib/prio_heap.c | 91 ++++++++++++++++++++++++++++++++++++---------- 2 files changed, 116 insertions(+), 19 deletions(-)Index:
linux.trees.git/include/linux/prio_heap.h
===================================================================include/linux/prio_heap.h +20
-0@@ -23,6 +23,18 @@ struct ptr_heap { };/** +* heap_maximum - return the largest element in the heap +* @heap: the heap to be operated on +* +* Returns the largest element in the heap, without performing any modification +* to the heap structure. Returns NULL if the heap is empty. +*/ +static inline void *heap_maximum (const struct ptr_heap *heap) +{ +return heap->size ? heap->ptrs[0 ] :NULL ; +} + +/** * heap_init - initialize an empty heap with a given memory size * @heap: the heap structure to be initialized * @size: amount of memory to use in bytes @@ -53,6 +65,38 @@ void heap_free(struct ptr_heap *heap);*/ extern void *heap_insert (struct ptr_heap *heap,void *p); +/** +* heap_remove - remove the largest element from the heap +* @heap: the heap to be operated on +* +* Returns the largest element in the heap. It removes this element from the +* heap. Returns NULL if the heap is empty. +*/ +extern void *heap_remove (struct ptr_heap *heap);
include/linux/prio_heap.h void heap_free(struct ptr_heap *heap); · line 86
Quoted 10 lines
include/linux/prio_heap.h +10
-0+/** +* 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.
Signature · 2 lines
Three Cheers, Balbir
Quoted 22 lines · * Balbir Singh ([email protected]) wrote:
Quoted 18 lines · Mathieu Desnoyers
These added interfaces lets
prio_heapusers 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 <[email protected]>Cc Paul Menage <[email protected]>Cc David Rientjes <[email protected]>Cc Nick Piggin <[email protected]>Cc Balbir Singh <[email protected]>Cc Cedric Le Goater <[email protected]>Cc "Eric W. Biederman" <[email protected]>Cc Andrew Morton <[email protected]>Cc Linus Torvalds <[email protected]>Quoted 1 line
---
Quoted 3 lines
The patchset looks good to me, one comment on cherry picking below
Acked-by Balbir Singh <[email protected]>
Thanks!
[...]
Quoted 7 lines
Quoted 7 lines
+/**
+ *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
Quoted 8 lines
Quoted 3 lines
+ * O(log(n)) provided by the rest of this API.
+ */
+extern void *heap_cherrypick(structptr_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
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com