Re: [RESEND PATCH v2 0/5] lib/sort & lib/list_sort: faster and smaller

[Andy Shevchenko]

On Tue, Mar 19, 2019 at 08:15:56AM +0000, George Spelvin wrote:
> (Resend because earlier send had GIT_AUTHOR_DATE in the e-mail
> headers and got filed with last month's archives.  And probably
> tripped a few spam filters.)

I got both.

> 
> v1->v2:	Various spelling, naming and code style cleanups.
> 	Generally positive and no negative responses to the
> 	goals and algorithms used.
> 
> 	I'm running these patches, with CONFIG_TEST_SORT and
> 	CONFIG_TEST_LIST_SORT, on the machine I'm sending this from.
> 	I have tweaked the comments further, but I have verified
> 	the compiled object code is identical to a snapshot I took
> 	when I rebooted.
> 
> 	As far as I'm concerned, this is ready to be merged.
> 	As there is no owner in MAINTAINERS, I was thinking of
> 	sending it via AKPM, like the recent lib/lzo changes.
> 	Andrew, is that okay with you?
> 

Thanks for this improvement. I like when academic work is used in real life!

FWIW,
Reviewed-by: Andy Shevchenko <andriy.shevchenko@xxxxxxxxxxxxxxx>

> Because CONFIG_RETPOLINE has made indirect calls much more expensive,
> I thought I'd try to reduce the number made by the library sort
> functions.
> 
> The first three patches apply to lib/sort.c.
> 
> Patch #1 is a simple optimization.  The built-in swap has special cases
> for aligned 4- and 8-byte objects.  But those are almost never used;
> most calls to sort() work on larger structures, which fall back to the
> byte-at-a-time loop.  This generalizes them to aligned *multiples* of 4
> and 8 bytes.  (If nothing else, it saves an awful lot of energy by not
> thrashing the store buffers as much.)
> 
> Patch #2 grabs a juicy piece of low-hanging fruit.  I agree that
> nice simple solid heapsort is preferable to more complex algorithms
> (sorry, Andrey), but it's possible to implement heapsort with far fewer
> comparisons (50% asymptotically, 25-40% reduction for realistic sizes)
> than the way it's been done up to now.  And with some care, the code
> ends up smaller, as well.  This is the "big win" patch.
> 
> Patch #3 adds the same sort of indirect call bypass that has been added
> to the net code of late.  The great majority of the callers use the
> builtin swap functions, so replace the indirect call to sort_func with a
> (highly preditable) series of if() statements.  Rather surprisingly,
> this decreased code size, as the swap functions were inlined and their
> prologue & epilogue code eliminated.
> 
> lib/list_sort.c is a bit trickier, as merge sort is already close to
> optimal, and we don't want to introduce triumphs of theory over
> practicality like the Ford-Johnson merge-insertion sort.
> 
> Patch #4, without changing the algorithm, chops 32% off the code size and
> removes the part[MAX_LIST_LENGTH+1] pointer array (and the corresponding
> upper limit on efficiently sortable input size).
> 
> Patch #5 improves the algorithm.  The previous code is already optimal
> for power-of-two (or slightly smaller) size inputs, but when the input
> size is just over a power of 2, there's a very unbalanced final merge.
> 
> There are, in the literature, several algorithms which solve this, but
> they all depend on the "breadth-first" merge order which was replaced
> by commit 835cc0c8477f with a more cache-friendly "depth-first" order.
> Some hard thinking came up with a depth-first algorithm which defers
> merges as little as possible while avoiding bad merges.  This saves
> 0.2*n compares, averaged over all sizes.
> 
> The code size increase is minimal (64 bytes on x86-64, reducing the net
> savings to 26%), but the comments expanded significantly to document
> the clever algorithm.
> 
> 
> TESTING NOTES: I have some ugly user-space benchmarking code
> which I used for testing before moving this code into the kernel.
> Shout if you want a copy.
> 
> I'm running this code right now, with CONFIG_TEST_SORT and
> CONFIG_TEST_LIST_SORT, but I confess I haven't rebooted since
> the last round of minor edits to quell checkpatch.  I figure there
> will be at least one round of comments and final testing.
> 
> George Spelvin (5):
>   lib/sort: Make swap functions more generic
>   lib/sort: Use more efficient bottom-up heapsort variant
>   lib/sort: Avoid indirect calls to built-in swap
>   lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS
>   lib/list_sort: Optimize number of calls to comparison function
> 
>  include/linux/list_sort.h |   1 +
>  lib/list_sort.c           | 244 +++++++++++++++++++++++++---------
>  lib/sort.c                | 266 +++++++++++++++++++++++++++++---------
>  3 files changed, 387 insertions(+), 124 deletions(-)
> 
> -- 
> 2.20.1
> 

-- 
With Best Regards,
Andy Shevchenko