drivers/md/bcache/util.h | 23 +++++---- fs/bcachefs/util.c | 109 ++++++++++++++++++++++++++------------- fs/bcachefs/util.h | 23 +++++---- 3 files changed, 98 insertions(+), 57 deletions(-)
Hello, The existing implementations of heap/heapsort follow the conventional textbook approach, where each heapify operation requires approximately 2*log2(n) comparisons. In this series, I introduce a bottom-up variant that reduces the number of comparisons during heapify operations to approximately log2(n), while maintaining the same number of swap operations. Thanks, Kuan-Wei Kuan-Wei Chiu (5): bcachefs: Optimize eytzinger0_sort() using bottom-up heapsort bcachefs: Introduce parent function for sort_cmp_size() bcachefs: Optimize sort_cmp_size() using bottom-up heapsort bcachefs: Optimize number of comparisons in heap_sift_down bcache: Optimize number of comparisons in heap_sift drivers/md/bcache/util.h | 23 +++++---- fs/bcachefs/util.c | 109 ++++++++++++++++++++++++++------------- fs/bcachefs/util.h | 23 +++++---- 3 files changed, 98 insertions(+), 57 deletions(-) -- 2.25.1
On Sun, Jan 21, 2024 at 11:36:44PM +0800, Kuan-Wei Chiu wrote: > Hello, > > The existing implementations of heap/heapsort follow the conventional > textbook approach, where each heapify operation requires approximately > 2*log2(n) comparisons. In this series, I introduce a bottom-up variant > that reduces the number of comparisons during heapify operations to > approximately log2(n), while maintaining the same number of swap > operations. > > Thanks, > Kuan-Wei > > Kuan-Wei Chiu (5): > bcachefs: Optimize eytzinger0_sort() using bottom-up heapsort > bcachefs: Introduce parent function for sort_cmp_size() > bcachefs: Optimize sort_cmp_size() using bottom-up heapsort > bcachefs: Optimize number of comparisons in heap_sift_down > bcache: Optimize number of comparisons in heap_sift > > drivers/md/bcache/util.h | 23 +++++---- > fs/bcachefs/util.c | 109 ++++++++++++++++++++++++++------------- > fs/bcachefs/util.h | 23 +++++---- > 3 files changed, 98 insertions(+), 57 deletions(-) Good stuff While we're looking at this code, we should be doing some cleanup too - there's no reason for the heap code to be duplicated in bcache and bcachefs anymore, and it'd also be nice to get fs/bcachefs/eytzinger.h moved to include/linux and bcache converted to use it. I also would not be surprised if there's another heap implementation in include/linux; we'll want to check for that and if there is decide which is worth keeping. Would you or Coli be interested in taking that on as well?
On Sun, Jan 21, 2024 at 11:21:06AM -0500, Kent Overstreet wrote: > On Sun, Jan 21, 2024 at 11:36:44PM +0800, Kuan-Wei Chiu wrote: > > Hello, > > > > The existing implementations of heap/heapsort follow the conventional > > textbook approach, where each heapify operation requires approximately > > 2*log2(n) comparisons. In this series, I introduce a bottom-up variant > > that reduces the number of comparisons during heapify operations to > > approximately log2(n), while maintaining the same number of swap > > operations. > > > > Thanks, > > Kuan-Wei > > > > Kuan-Wei Chiu (5): > > bcachefs: Optimize eytzinger0_sort() using bottom-up heapsort > > bcachefs: Introduce parent function for sort_cmp_size() > > bcachefs: Optimize sort_cmp_size() using bottom-up heapsort > > bcachefs: Optimize number of comparisons in heap_sift_down > > bcache: Optimize number of comparisons in heap_sift > > > > drivers/md/bcache/util.h | 23 +++++---- > > fs/bcachefs/util.c | 109 ++++++++++++++++++++++++++------------- > > fs/bcachefs/util.h | 23 +++++---- > > 3 files changed, 98 insertions(+), 57 deletions(-) > > Good stuff > > While we're looking at this code, we should be doing some cleanup too - > there's no reason for the heap code to be duplicated in bcache and > bcachefs anymore, and it'd also be nice to get fs/bcachefs/eytzinger.h > moved to include/linux and bcache converted to use it. > > I also would not be surprised if there's another heap implementation in > include/linux; we'll want to check for that and if there is decide which > is worth keeping. > Yes, we have 'min_heap.h' in include/linux. > Would you or Coli be interested in taking that on as well?
On Mon, Jan 22, 2024 at 12:55:51AM +0800, Kuan-Wei Chiu wrote: > On Sun, Jan 21, 2024 at 11:21:06AM -0500, Kent Overstreet wrote: > > On Sun, Jan 21, 2024 at 11:36:44PM +0800, Kuan-Wei Chiu wrote: > > > Hello, > > > > > > The existing implementations of heap/heapsort follow the conventional > > > textbook approach, where each heapify operation requires approximately > > > 2*log2(n) comparisons. In this series, I introduce a bottom-up variant > > > that reduces the number of comparisons during heapify operations to > > > approximately log2(n), while maintaining the same number of swap > > > operations. > > > > > > Thanks, > > > Kuan-Wei > > > > > > Kuan-Wei Chiu (5): > > > bcachefs: Optimize eytzinger0_sort() using bottom-up heapsort > > > bcachefs: Introduce parent function for sort_cmp_size() > > > bcachefs: Optimize sort_cmp_size() using bottom-up heapsort > > > bcachefs: Optimize number of comparisons in heap_sift_down > > > bcache: Optimize number of comparisons in heap_sift > > > > > > drivers/md/bcache/util.h | 23 +++++---- > > > fs/bcachefs/util.c | 109 ++++++++++++++++++++++++++------------- > > > fs/bcachefs/util.h | 23 +++++---- > > > 3 files changed, 98 insertions(+), 57 deletions(-) > > > > Good stuff > > > > While we're looking at this code, we should be doing some cleanup too - > > there's no reason for the heap code to be duplicated in bcache and > > bcachefs anymore, and it'd also be nice to get fs/bcachefs/eytzinger.h > > moved to include/linux and bcache converted to use it. > > > > I also would not be surprised if there's another heap implementation in > > include/linux; we'll want to check for that and if there is decide which > > is worth keeping. > > > Yes, we have 'min_heap.h' in include/linux. So that has the advantage of more readable code - functions instead of macros - whereas my version has the type safe interface. We could combine the two approaches, and put a type-safe interface on top of the min_heap.h code with some small macro wrappers - see generic-radix-tree.h for an example of how that's done. min_heap.h has only one user though? I don't think I can quite believe that's the only other code in the kernel using a heap, there must be more open coded out there...
On Sun, Jan 21, 2024 at 12:41:55PM -0500, Kent Overstreet wrote: > On Mon, Jan 22, 2024 at 12:55:51AM +0800, Kuan-Wei Chiu wrote: > > On Sun, Jan 21, 2024 at 11:21:06AM -0500, Kent Overstreet wrote: > > > On Sun, Jan 21, 2024 at 11:36:44PM +0800, Kuan-Wei Chiu wrote: > > > > Hello, > > > > > > > > The existing implementations of heap/heapsort follow the conventional > > > > textbook approach, where each heapify operation requires approximately > > > > 2*log2(n) comparisons. In this series, I introduce a bottom-up variant > > > > that reduces the number of comparisons during heapify operations to > > > > approximately log2(n), while maintaining the same number of swap > > > > operations. > > > > > > > > Thanks, > > > > Kuan-Wei > > > > > > > > Kuan-Wei Chiu (5): > > > > bcachefs: Optimize eytzinger0_sort() using bottom-up heapsort > > > > bcachefs: Introduce parent function for sort_cmp_size() > > > > bcachefs: Optimize sort_cmp_size() using bottom-up heapsort > > > > bcachefs: Optimize number of comparisons in heap_sift_down > > > > bcache: Optimize number of comparisons in heap_sift > > > > > > > > drivers/md/bcache/util.h | 23 +++++---- > > > > fs/bcachefs/util.c | 109 ++++++++++++++++++++++++++------------- > > > > fs/bcachefs/util.h | 23 +++++---- > > > > 3 files changed, 98 insertions(+), 57 deletions(-) > > > > > > Good stuff > > > > > > While we're looking at this code, we should be doing some cleanup too - > > > there's no reason for the heap code to be duplicated in bcache and > > > bcachefs anymore, and it'd also be nice to get fs/bcachefs/eytzinger.h > > > moved to include/linux and bcache converted to use it. > > > > > > I also would not be surprised if there's another heap implementation in > > > include/linux; we'll want to check for that and if there is decide which > > > is worth keeping. > > > > > Yes, we have 'min_heap.h' in include/linux. > > So that has the advantage of more readable code - functions instead of > macros - whereas my version has the type safe interface. > > We could combine the two approaches, and put a type-safe interface on > top of the min_heap.h code with some small macro wrappers - see > generic-radix-tree.h for an example of how that's done. Without modifying the interface provided by min_heap.h, it seems challenging to implement the functionality of heap_add due to the relationship with heap_setbackpointer. Additionally, when looking into the code in generic-radix-tree.h, should we replace type[0] with type[]? This is because zero-length arrays are deprecated language features mentioned in document [1]. Link: https://www.kernel.org/doc/html/latest/process/deprecated.html#zero-length-and-one-element-arrays [1] > > min_heap.h has only one user though? I don't think I can quite believe > that's the only other code in the kernel using a heap, there must be > more open coded out there... I'm not sure why, but it seems that in the kernel, other places using the heap implement their own subsystem-specific solutions rather than utilizing a generic heap interface. For instance, kernel/sched/cpudeadline.c and net/sched/sch_cake.c both have their own implementations.
On Mon, Jan 22, 2024 at 11:06:54PM +0800, Kuan-Wei Chiu wrote: > On Sun, Jan 21, 2024 at 12:41:55PM -0500, Kent Overstreet wrote: > > On Mon, Jan 22, 2024 at 12:55:51AM +0800, Kuan-Wei Chiu wrote: > > > On Sun, Jan 21, 2024 at 11:21:06AM -0500, Kent Overstreet wrote: > > > > On Sun, Jan 21, 2024 at 11:36:44PM +0800, Kuan-Wei Chiu wrote: > > > > > Hello, > > > > > > > > > > The existing implementations of heap/heapsort follow the conventional > > > > > textbook approach, where each heapify operation requires approximately > > > > > 2*log2(n) comparisons. In this series, I introduce a bottom-up variant > > > > > that reduces the number of comparisons during heapify operations to > > > > > approximately log2(n), while maintaining the same number of swap > > > > > operations. > > > > > > > > > > Thanks, > > > > > Kuan-Wei > > > > > > > > > > Kuan-Wei Chiu (5): > > > > > bcachefs: Optimize eytzinger0_sort() using bottom-up heapsort > > > > > bcachefs: Introduce parent function for sort_cmp_size() > > > > > bcachefs: Optimize sort_cmp_size() using bottom-up heapsort > > > > > bcachefs: Optimize number of comparisons in heap_sift_down > > > > > bcache: Optimize number of comparisons in heap_sift > > > > > > > > > > drivers/md/bcache/util.h | 23 +++++---- > > > > > fs/bcachefs/util.c | 109 ++++++++++++++++++++++++++------------- > > > > > fs/bcachefs/util.h | 23 +++++---- > > > > > 3 files changed, 98 insertions(+), 57 deletions(-) > > > > > > > > Good stuff > > > > > > > > While we're looking at this code, we should be doing some cleanup too - > > > > there's no reason for the heap code to be duplicated in bcache and > > > > bcachefs anymore, and it'd also be nice to get fs/bcachefs/eytzinger.h > > > > moved to include/linux and bcache converted to use it. > > > > > > > > I also would not be surprised if there's another heap implementation in > > > > include/linux; we'll want to check for that and if there is decide which > > > > is worth keeping. > > > > > > > Yes, we have 'min_heap.h' in include/linux. > > > > So that has the advantage of more readable code - functions instead of > > macros - whereas my version has the type safe interface. > > > > We could combine the two approaches, and put a type-safe interface on > > top of the min_heap.h code with some small macro wrappers - see > > generic-radix-tree.h for an example of how that's done. > > Without modifying the interface provided by min_heap.h, it seems > challenging to implement the functionality of heap_add due to the > relationship with heap_setbackpointer. min_heap.h has the same functionality, different interface - updating the callers for an interface change is fine. > > Additionally, when looking into the code in generic-radix-tree.h, > should we replace type[0] with type[]? This is because zero-length > arrays are deprecated language features mentioned in document [1]. Zero length arrays are deprecated as VLAs, but this isn't a VLA - we're not storing anything there, the variable is just so that macros have access to the type. > Link: https://www.kernel.org/doc/html/latest/process/deprecated.html#zero-length-and-one-element-arrays [1] > > > > min_heap.h has only one user though? I don't think I can quite believe > > that's the only other code in the kernel using a heap, there must be > > more open coded out there... > > I'm not sure why, but it seems that in the kernel, other places using > the heap implement their own subsystem-specific solutions rather than > utilizing a generic heap interface. For instance, > kernel/sched/cpudeadline.c and net/sched/sch_cake.c both have their own > implementations. Sounds like a fun cleanup project :)
On Mon, Jan 22, 2024 at 11:06:39AM -0500, Kent Overstreet wrote: > On Mon, Jan 22, 2024 at 11:06:54PM +0800, Kuan-Wei Chiu wrote: > > On Sun, Jan 21, 2024 at 12:41:55PM -0500, Kent Overstreet wrote: > > > On Mon, Jan 22, 2024 at 12:55:51AM +0800, Kuan-Wei Chiu wrote: > > > > On Sun, Jan 21, 2024 at 11:21:06AM -0500, Kent Overstreet wrote: > > > > > On Sun, Jan 21, 2024 at 11:36:44PM +0800, Kuan-Wei Chiu wrote: > > > > > > Hello, > > > > > > > > > > > > The existing implementations of heap/heapsort follow the conventional > > > > > > textbook approach, where each heapify operation requires approximately > > > > > > 2*log2(n) comparisons. In this series, I introduce a bottom-up variant > > > > > > that reduces the number of comparisons during heapify operations to > > > > > > approximately log2(n), while maintaining the same number of swap > > > > > > operations. > > > > > > > > > > > > Thanks, > > > > > > Kuan-Wei > > > > > > > > > > > > Kuan-Wei Chiu (5): > > > > > > bcachefs: Optimize eytzinger0_sort() using bottom-up heapsort > > > > > > bcachefs: Introduce parent function for sort_cmp_size() > > > > > > bcachefs: Optimize sort_cmp_size() using bottom-up heapsort > > > > > > bcachefs: Optimize number of comparisons in heap_sift_down > > > > > > bcache: Optimize number of comparisons in heap_sift > > > > > > > > > > > > drivers/md/bcache/util.h | 23 +++++---- > > > > > > fs/bcachefs/util.c | 109 ++++++++++++++++++++++++++------------- > > > > > > fs/bcachefs/util.h | 23 +++++---- > > > > > > 3 files changed, 98 insertions(+), 57 deletions(-) > > > > > > > > > > Good stuff > > > > > > > > > > While we're looking at this code, we should be doing some cleanup too - > > > > > there's no reason for the heap code to be duplicated in bcache and > > > > > bcachefs anymore, and it'd also be nice to get fs/bcachefs/eytzinger.h > > > > > moved to include/linux and bcache converted to use it. > > > > > > > > > > I also would not be surprised if there's another heap implementation in > > > > > include/linux; we'll want to check for that and if there is decide which > > > > > is worth keeping. > > > > > > > > > Yes, we have 'min_heap.h' in include/linux. > > > > > > So that has the advantage of more readable code - functions instead of > > > macros - whereas my version has the type safe interface. > > > > > > We could combine the two approaches, and put a type-safe interface on > > > top of the min_heap.h code with some small macro wrappers - see > > > generic-radix-tree.h for an example of how that's done. > > > > Without modifying the interface provided by min_heap.h, it seems > > challenging to implement the functionality of heap_add due to the > > relationship with heap_setbackpointer. > > min_heap.h has the same functionality, different interface - updating > the callers for an interface change is fine. > OK, I'll take some time to do these cleanups. > > > > Additionally, when looking into the code in generic-radix-tree.h, > > should we replace type[0] with type[]? This is because zero-length > > arrays are deprecated language features mentioned in document [1]. > > Zero length arrays are deprecated as VLAs, but this isn't a VLA - we're > not storing anything there, the variable is just so that macros have > access to the type. > > > Link: https://www.kernel.org/doc/html/latest/process/deprecated.html#zero-length-and-one-element-arrays [1] > > > > > > min_heap.h has only one user though? I don't think I can quite believe > > > that's the only other code in the kernel using a heap, there must be > > > more open coded out there... > > > > I'm not sure why, but it seems that in the kernel, other places using > > the heap implement their own subsystem-specific solutions rather than > > utilizing a generic heap interface. For instance, > > kernel/sched/cpudeadline.c and net/sched/sch_cake.c both have their own > > implementations. > > Sounds like a fun cleanup project :)
© 2016 - 2025 Red Hat, Inc.