kernel/linux.git/lib/sort.c, branch v6.12.80

lib/sort: optimize heapsort for handling final 2 or 3 elements

2024-06-25T05:25:03+00:00

After building the heap, the code continuously pops two elements from the heap until only 2 or 3 elements remain, at which point it switches back to a regular heapsort with one element popped at a time. However, to handle the final 2 or 3 elements, an additional else-if statement in the while loop was introduced, potentially increasing branch misses. Moreover, when there are only 2 or 3 elements left, continuing with regular heapify operations is unnecessary as these cases are simple enough to be handled with a single comparison and 1 or 2 swaps outside the while loop. Eliminating the additional else-if statement and directly managing cases involving 2 or 3 elements outside the loop reduces unnecessary conditional branches resulting from the numerous loops and conditionals in heapify. This optimization maintains consistent numbers of comparisons and swaps for arrays with even lengths while reducing swaps and comparisons for arrays with odd lengths from 2.5 swaps and 1 comparison to 1.5 swaps and 1 comparison. Link: https://lkml.kernel.org/r/20240527203011.1644280-4-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Cc: Ching-Chun (Jim) Huang Signed-off-by: Andrew Morton

lib/sort: fix outdated comment regarding glibc qsort()

2024-06-25T05:25:02+00:00

The existing comment in lib/sort refers to glibc qsort() using quicksort. However, glibc qsort() no longer uses quicksort; it now uses mergesort and falls back to heapsort if memory allocation for mergesort fails. This makes the comment outdated and incorrect. Update the comment to refer to quicksort in general rather than glibc's implementation to provide accurate information about the comparisons and trade-offs without implying an outdated implementation. Link: https://lkml.kernel.org/r/20240527203011.1644280-3-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Cc: Ching-Chun (Jim) Huang Signed-off-by: Andrew Morton

lib/sort: remove unused pr_fmt macro

2024-06-25T05:25:02+00:00

Patch series "lib/sort: Optimizations and cleanups". This patch series optimizes the handling of the last 2 or 3 elements in lib/sort and adds a testcase in lib/test_sort to maintain 100% code coverage reflecting this change. Additionally, it corrects outdated descriptions regarding glibc qsort() and removes the unused pr_fmt macro. This patch (of 4): The pr_fmt macro is defined but not used in lib/sort.c. Since there are no pr_* functions printing any messages, the pr_fmt macro is redundant and can be safely removed. Link: https://lkml.kernel.org/r/20240527203011.1644280-1-visitorckw@gmail.com Link: https://lkml.kernel.org/r/20240527203011.1644280-2-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Cc: Ching-Chun (Jim) Huang Signed-off-by: Andrew Morton

lib/sort: optimize heapsort with double-pop variation

2024-02-22T23:38:52+00:00

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 | Link: https://lkml.kernel.org/r/20240113031352.2395118-3-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Cc: Ching-Chun (Jim) Huang Cc: George Spelvin Signed-off-by: Andrew Morton

lib/sort: optimize heapsort for equal elements in sift-down path

2024-02-22T23:38:52+00:00

Patch series "lib/sort: Optimize the number of swaps and comparisons". This patch series aims to optimize the heapsort algorithm, specifically targeting a reduction in the number of swaps and comparisons required. This patch (of 2): Currently, when searching for the sift-down path and encountering equal elements, the algorithm chooses the left child. However, considering that the height of the right subtree may be one less than that of the left subtree, selecting the right child in such cases can potentially reduce the number of comparisons and swaps. For instance, when sorting an array of 10,000 identical elements, the current implementation requires 247,209 comparisons. With this patch, the number of comparisons can be reduced to 227,241. Link: https://lkml.kernel.org/r/20240113031352.2395118-1-visitorckw@gmail.com Link: https://lkml.kernel.org/r/20240113031352.2395118-2-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Signed-off-by: Andrew Morton

lib/sort: Add priv pointer to swap function

2022-03-18T03:17:18+00:00

Adding support to have priv pointer in swap callback function. Following the initial change on cmp callback functions [1] and adding SWAP_WRAPPER macro to identify sort call of sort_r. Signed-off-by: Jiri Olsa Signed-off-by: Alexei Starovoitov Reviewed-by: Masami Hiramatsu Link: https://lore.kernel.org/bpf/20220316122419.933957-2-jolsa@kernel.org [1] 4333fb96ca10 ("media: lib/sort.c: implement sort() variant taking context argument")

lib: fix spelling mistakes

2021-07-08T18:48:20+00:00

Fix some spelling mistakes in comments: permanentely ==> permanently wont ==> won't remaning ==> remaining succed ==> succeed shouldnt ==> shouldn't alpha-numeric ==> alphanumeric storeing ==> storing funtion ==> function documenation ==> documentation Determin ==> Determine intepreted ==> interpreted ammount ==> amount obious ==> obvious interupts ==> interrupts occured ==> occurred asssociated ==> associated taking into acount ==> taking into account squence ==> sequence stil ==> still contiguos ==> contiguous matchs ==> matches Link: https://lkml.kernel.org/r/20210607072555.12416-1-thunder.leizhen@huawei.com Signed-off-by: Zhen Lei Reviewed-by: Jacob Keller Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/sort: Move swap, cmp and cmp_r function types for wider use

2019-11-14T18:15:11+00:00

The function types for swap, cmp and cmp_r functions are already being in use by modules. Move them to types.h that everybody in kernel will be able to use generic types instead of custom ones. This adds more sense to the comment in bsearch() later on. Link: http://lkml.kernel.org/r/20191007135656.37734-1-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko Signed-off-by: Steven Rostedt (VMware)

media: lib/sort.c: implement sort() variant taking context argument

2019-08-19T16:14:53+00:00

Our list_sort() utility has always supported a context argument that is passed through to the comparison routine. Now there's a use case for the similar thing for sort(). This implements sort_r by simply extending the existing sort function in the obvious way. To avoid code duplication, we want to implement sort() in terms of sort_r(). The naive way to do that is static int cmp_wrapper(const void *a, const void *b, const void *ctx) { int (*real_cmp)(const void*, const void*) = ctx; return real_cmp(a, b); } sort(..., cmp) { sort_r(..., cmp_wrapper, cmp) } but this would do two indirect calls for each comparison. Instead, do as is done for the default swap functions - that only adds a cost of a single easily predicted branch to each comparison call. Aside from introducing support for the context argument, this also serves as preparation for patches that will eliminate the indirect comparison calls in common cases. Requested-by: Boris Brezillon Signed-off-by: Rasmus Villemoes Signed-off-by: Boris Brezillon Acked-by: Andrew Morton Tested-by: Philipp Zabel Signed-off-by: Hans Verkuil Signed-off-by: Mauro Carvalho Chehab

lib/sort.c: fix kernel-doc notation warnings

2019-06-01T22:51:31+00:00

Fix kernel-doc notation in lib/sort.c by using correct function parameter names. lib/sort.c:59: warning: Excess function parameter 'size' description in 'swap_words_32' lib/sort.c:83: warning: Excess function parameter 'size' description in 'swap_words_64' lib/sort.c:110: warning: Excess function parameter 'size' description in 'swap_bytes' Link: http://lkml.kernel.org/r/60e25d3d-68d1-bde2-3b39-e4baa0b14907@infradead.org Fixes: 37d0ec34d111a ("lib/sort: make swap functions more generic") Signed-off-by: Randy Dunlap Cc: George Spelvin Cc: Andrew Morton Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds