• Darrick J. Wong's avatar
    xfs: improve xfarray quicksort pivot · 764018ca
    Darrick J. Wong authored
    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: default avatarDarrick J. Wong <djwong@kernel.org>
    Reviewed-by: default avatarKent Overstreet <kent.overstreet@linux.dev>
    Reviewed-by: default avatarDave Chinner <dchinner@redhat.com>
    764018ca
xfarray.h 3.99 KB