Messages in this thread | | | Date | Wed, 25 Aug 2021 12:55:53 +0300 | From | Andy Shevchenko <> | Subject | Re: [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
| |