lkml.org 
[lkml]   [2021]   [Aug]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH v1 2/3] lib/sort: Introduce rotate() to circular shift an array of elements
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


\
 
 \ /
  Last update: 2021-08-25 11:56    [W:0.050 / U:0.212 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site