Searched hist:"764018 caa99f7629cefc92257a26b83289a674f3" (Results 1 – 2 of 2) sorted by relevance
| /openbmc/linux/fs/xfs/scrub/ |
| H A D | xfarray.h | diff 764018caa99f7629cefc92257a26b83289a674f3 Thu Aug 10 09:48:07 CDT 2023 Darrick J. Wong <djwong@kernel.org> xfs: improve xfarray quicksort pivot
Now that we have the means to do insertion sorts of small in-memory
subsets of an xfarray, use it to improve the quicksort pivot algorithm
by reading 7 records into memory and finding the median of that. This
should prevent bad partitioning when a[lo] and a[hi] end up next to each
other in the final sort, which can happen when sorting for cntbt repair
when the free space is extremely fragmented (e.g. generic/176).
This doesn't speed up the average quicksort run by much, but it will
(hopefully) avoid the quadratic time collapse for which quicksort is
famous.
Signed-off-by: Darrick J. Wong <djwong@kernel.org>
Reviewed-by: Kent Overstreet <kent.overstreet@linux.dev>
Reviewed-by: Dave Chinner <dchinner@redhat.com>
|
| H A D | xfarray.c | diff 764018caa99f7629cefc92257a26b83289a674f3 Thu Aug 10 09:48:07 CDT 2023 Darrick J. Wong <djwong@kernel.org> xfs: improve xfarray quicksort pivot
Now that we have the means to do insertion sorts of small in-memory
subsets of an xfarray, use it to improve the quicksort pivot algorithm
by reading 7 records into memory and finding the median of that. This
should prevent bad partitioning when a[lo] and a[hi] end up next to each
other in the final sort, which can happen when sorting for cntbt repair
when the free space is extremely fragmented (e.g. generic/176).
This doesn't speed up the average quicksort run by much, but it will
(hopefully) avoid the quadratic time collapse for which quicksort is
famous.
Signed-off-by: Darrick J. Wong <djwong@kernel.org>
Reviewed-by: Kent Overstreet <kent.overstreet@linux.dev>
Reviewed-by: Dave Chinner <dchinner@redhat.com>
|