lib-sort-optimize-heapsort-with-double-pop-variation.patch removed from -mm tree
The quilt patch titled
Subject: lib/sort: optimize heapsort with double-pop variation
has been removed from the -mm tree. Its filename was
lib-sort-optimize-heapsort-with-double-pop-variation.patch
This patch was dropped because it was merged into the mm-hotfixes-stable branch of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
------------------------------------------------------
From: Kuan-Wei Chiu <[email protected]>
Subject: lib/sort: optimize heapsort with double-pop variation
Date: Sat, 13 Jan 2024 11:13:52 +0800
Instead of popping only the maximum element from the heap during each iteration, we now pop the two largest elements at once. Although this introduces an additional comparison to determine the second largest element, it enables a reduction in the height of the tree by one during the heapify operations starting from root's left/right child. This reduction in tree height by one leads to a decrease of one comparison and one swap.
This optimization results in saving approximately 0.5 * n swaps without increasing the number of comparisons. Additionally, the heap size during heapify is now one less than the original size, offering a chance for further reduction in comparisons and swaps.
The following experimental data is based on the array generated using get_random_u32().
| N | swaps (old) | swaps (new) | comparisons (old) | comparisons (new) | |-------|-------------|-------------|-------------------|-------------------| | 1000 | 9054 | 8569 | 10328 | 10320 | | 2000 | 20137 | 19182 | 22634 | 22587 | | 3000 | 32062 | 30623 | 35833 | 35752 | | 4000 | 44274 | 42282 | 49332 | 49306 | | 5000 | 57195 | 54676 | 63300 | 63294 | | 6000 | 70205 | 67202 | 77599 | 77557 | | 7000 | 83276 | 79831 | 92113 | 92032 | | 8000 | 96630 | 92678 | 106635 | 106617 | | 9000 | 110349 | 105883 | 121505 | 121404 | | 10000 | 124165 | 119202 | 136628 | 136617 |
---
lib/sort.c | 18 ++++++++++++++---- 1 file changed, 14 insertions(+), 4 deletions(-)
lib/sort.c renamed from lib/sort.c~lib-sort-optimize-heapsort-with-double-pop-variation +14 -4
@@ -215,6 +215,7 @@ void sort_r(void *base, size_t num, size/* pre-scale counters for performance */ size_t n = num * size, a = (num/2 ) * size;const unsigned int lsbit = size & -size;/* Used to find parent */ +size_t shift =0 ;if (!a)/* num < 2 || size == 0 */ return ;
@@ -242,12 +243,21 @@ void sort_r(void *base, size_t num, sizefor (;;) {size_t b, c, d; -if (a)/* Building heap: sift down --a */ - a -= size; -else if (n -= size)/* Sorting: Extract root to --n */ +if (a)/* Building heap: sift down a */ + a -= size << shift; +else if (n >3 * size) {/* Sorting: Extract two largest elements */ + n -= size;do_swap (base, base + n, size, swap_func, priv); -else /* Sort complete */ + shift =do_cmp (base + size, base +2 * size, cmp_func, priv) <=0 ; + a = size << shift; + n -= size; +do_swap (base + a, base + n, size, swap_func, priv); + }else if (n > size) {/* Sorting: Extract root */ + n -= size; +do_swap (base, base + n, size, swap_func, priv); + }else {/* Sort complete */ break ; + }/* * Sift element at "a" down into heap. This is the
_
Patches currently in -mm which might be from [email protected] are