• Darrick J. Wong's avatar
    xfs: convert xfarray insertion sort to heapsort using scratchpad memory · c390c645
    Darrick J. Wong authored
    In the previous patch, we created a very basic quicksort implementation
    for xfile arrays.  While the use of an alternate sorting algorithm to
    avoid quicksort recursion on very small subsets reduces the runtime
    modestly, we could do better than a load and store-heavy insertion sort,
    particularly since each load and store requires a page mapping lookup in
    the xfile.
    
    For a small increase in kernel memory requirements, we could instead
    bulk load the xfarray records into memory, use the kernel's existing
    heapsort implementation to sort the records, and bulk store the memory
    buffer back into the xfile.  On the author's computer, this reduces the
    runtime by about 5% on a 500,000 element array.
    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>
    c390c645
trace.h 36.7 KB