Re: [PATCH v1 2/3] lib/sort: Introduce rotate() to circular shift an array of elements

[Andy Shevchenko <andriy.shevchenko@linux.intel.com>]

On Wed, Aug 25, 2021 at 11:29:12AM +0200, Rasmus Villemoes wrote:
> On 25/08/2021 10.08, Sakari Ailus wrote:

...

> Well, Andy hasn't actually shown that it would be useful anywhere else.
> I think I'd like to see another user.

I have found another potential user, but in their case (it's networking)
the simple for-loop with swap() in use seems efficient enough (the element size
is 8 bytes there).

I haven't check for really custom implementations of entire rotate (where no
swap() macro is in use), it might be another user lurking around.

> Just doing "move this helper to
> lib/ because we can reuse choose-a-proper-swap-func and thus implement
> this perhaps a tiny bit faster" without considering whether it's even
> performance-critical in the sole user is not a good idea IMO.

I agree with you.

> Especially since it can affect code generation of the much more
> important (at least, has many more users) sort() function - the
> do_swap() function grows another user, so could make the compiler end up
> choosing not to inline it anymore.

This can be fixed by always inlining?

> There's another slightly simpler way to implement rotate(), which might
> end up having more users (though I can't find any currently): Add a
> reverse() helper, then rotate() can be done as reverse(a, 0, n);
> reverse(a, 0, k); reverse(a, k, n-k);. If my math is right, the current
> suggested rotate() ends up doing n-gcd(n,k) swaps, while the
> implementation in terms of a reverse() would do n-1 if either n or k is
> odd, otherwise n, calls to swap().

Interesting idea. And this, btw, may have more users per se.

-- 
With Best Regards,
Andy Shevchenko