lib/sort: Split out choose_swap_func() local helper
Subsystems (3)
PATCH 1/3 lib/sort: Split out choose_swap_func() local helper
In some new code we may need the same functionality as provided by newly introduced choose_swap_func() helper.
--- lib/sort.c | 21 +++++++++++++-------- 1 file changed, 13 insertions(+), 8 deletions(-)
lib/sort.c +13 -8
@@ -151,6 +151,18 @@ static int do_cmp(const void *a, const void *b, cmp_r_func_t cmp, const void *prreturn cmp (a, b, priv); } +static swap_func_t choose_swap_func (swap_func_t swap_func,void *base,size_t size) +{ +if (swap_func) +return swap_func; + +if (is_aligned (base, size,8 )) +return SWAP_WORDS_64 ; +if (is_aligned (base, size,4 )) +return SWAP_WORDS_32 ; +return SWAP_BYTES ; +} +/** * parent - given the offset of the child, find the offset of the parent. * @i: the offset of the heap element whose parent is sought. Non-zero.
@@ -208,14 +220,7 @@ void sort_r(void *base, size_t num, size_t size,if (!a)/* num < 2 || size == 0 */ return ; -if (!swap_func) { -if (is_aligned (base, size,8 )) - swap_func =SWAP_WORDS_64 ; -else if (is_aligned (base, size,4 )) - swap_func =SWAP_WORDS_32 ; -else - swap_func =SWAP_BYTES ; - } + swap_func =choose_swap_func (swap_func, base, size);/* * Loop invariants:
Signature · 1 line
2.32.0
PATCH 2/3 lib/sort: Introduce rotate() to circular shift an array of elements
In some cases we want to circular shift an array of elements. Introduce rotate() helper for that.
--- include/linux/sort.h | 3 +++ lib/sort.c | 61 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 64 insertions(+)
include/linux/sort.h +3 -0
@@ -13,4 +13,7 @@ void sort(void *base, size_t num, size_t size,cmp_func_t cmp_func, swap_func_t swap_func); +void rotate (void *base,size_t num,size_t size,size_t by, +swap_func_t swap_func); +#endif
lib/sort.c +61 -0
70 lines not on this page · raw message
Signature · 1 line
2.32.0
Re: [PATCH v1 2/3] lib/sort: Introduce rotate() to circular shift an array of elements
Quoted 34 lines · Andy Shevchenko
In some cases we want to circular shift an array of elements. Introduce
rotate()helper for that.Signed-off-by Andy Shevchenko <[email protected]>--- include/linux/sort.h | 3 +++ lib/sort.c | 61 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 64 insertions(+)include/linux/sort.h +3
-0@@ -13,4 +13,7 @@ void sort(void *base, size_t num, size_t size,cmp_func_t cmp_func, swap_func_t swap_func); +void rotate (void *base,size_t num,size_t size,size_t by, +swap_func_t swap_func); +#endif lib/sort.c +1
-0@@ -14,6 +14,7 @@#include <linux/types.h> #include <linux/export.h> +#include <linux/minmax.h> #include <linux/sort.h> /**
lib/sort.c void sort(void *base, size_t num, size_t size, · line 282
Quoted 7 lines
lib/sort.c +4
-0@@ -275,3 +276,63 @@ void sort(void *base, size_t num, size_t size,return sort_r (base, num, size, _CMP_WRAPPER, swap_func, cmp_func); }EXPORT_SYMBOL (sort); + +/** +* rotate - rotate an array of elements by a number of elements +* @base: pointer to data to sort
sort?
lib/sort.c void sort(void *base, size_t num, size_t size, · line 285
Quoted 3 lines
lib/sort.c +3
-0+* @num: number of elements +* @size: size of each element +* @by: number of elements to rotate by
Perhaps add (0 <= @by < @num) or something like that, and/or start the implementation with "if (num <= 1) return; if (by >= num) by %= num;"
Quoted 4 lines
lib/sort.c +4
-0+* @swap_func: pointer to swap function or NULL +* +* Helper function to advance all the elements of a circular buffer by +* @by positions.
lib/sort.c void sort(void *base, size_t num, size_t size, · line 299
Quoted 10 lines
lib/sort.c +10
-0+*/ +void rotate (void *base,size_t num,size_t size,size_t by, +swap_func_t swap_func) +{ +struct { +size_t begin, end; + } arr[2 ] = { + { .begin =0 , .end = by -1 }, + { .begin = by, .end = num -1 }, + };
I see you just copied-and-adapted, but I think the code would be much easier to read without all those plus/minus ones all over.
Quoted 25 lines
lib/sort.c +25
-0+ swap_func =choose_swap_func (swap_func, base, size); + +#define CHUNK_SIZE (a) ((a)->end - (a)->begin + 1) + +/* Loop as long as we have out-of-place entries */ +while (CHUNK_SIZE (&arr[0 ]) &&CHUNK_SIZE (&arr[1 ])) { +size_t size0, i; + +/* +* Find the number of entries that can be arranged on this +* iteration. +*/ + size0 =min (CHUNK_SIZE (&arr[0 ]),CHUNK_SIZE (&arr[1 ])); + +/* Swap the entries in two parts of the array */ +for (i =0 ; i < size0; i++) { +void *a = base + size * (arr[0 ].begin + i); +void *b = base + size * (arr[1 ].begin + i); + +do_swap (a, b, size, swap_func); + } + +if (CHUNK_SIZE (&arr[0 ]) >CHUNK_SIZE (&arr[1 ])) { +/* The end of the first array remains unarranged */ + arr[0 ].begin += size0;
lib/sort.c void sort(void *base, size_t num, size_t size, · line 335
Quoted 10 lines
lib/sort.c +10
-0+ }else { +/* +* The first array is fully arranged so we proceed +* handling the next one. +*/ + arr[0 ].begin = arr[1 ].begin; + arr[0 ].end = arr[1 ].begin + size0 -1 ; + arr[1 ].begin += size0; + } + }
Perhaps add a small self-test, it's not at all obvious how this works (perhaps it's some standard CS101 algorithm for rotating in-place, I don't know, but even then an implementation can have off-by-ones and corner cases).
for (len = 1; len < 15; ++len) {
for (by = 0; by <= len; ++by) {
for (i = 0; i < len; ++i)
arr[i] = i;
rotate(arr, len, sizeof(int), by);
for (i = 0; i < len; ++i)
if (arr[i] != (i + by) % len)
error(); }
}
Rasmus
Re: [PATCH v1 2/3] lib/sort: Introduce rotate() to circular shift an array of elements
Hi Rasmus, Andy,
Quoted 45 lines · Rasmus Villemoes
Quoted 34 lines · Andy Shevchenko
In some cases we want to circular shift an array of elements. Introduce
rotate()helper for that.Signed-off-by Andy Shevchenko <[email protected]>--- include/linux/sort.h | 3 +++ lib/sort.c | 61 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 64 insertions(+)include/linux/sort.h +3
-0@@ -13,4 +13,7 @@ void sort(void *base, size_t num, size_t size,cmp_func_t cmp_func, swap_func_t swap_func); +void rotate (void *base,size_t num,size_t size,size_t by, +swap_func_t swap_func); +#endif lib/sort.c +1
-0@@ -14,6 +14,7 @@#include <linux/types.h> #include <linux/export.h> +#include <linux/minmax.h> #include <linux/sort.h> /** lib/sort.c void sort(void *base, size_t num, size_t size, · line 282
Quoted 7 lines
lib/sort.c +4
-0@@ -275,3 +276,63 @@ void sort(void *base, size_t num, size_t size,return sort_r (base, num, size, _CMP_WRAPPER, swap_func, cmp_func); }EXPORT_SYMBOL (sort); + +/** +* rotate - rotate an array of elements by a number of elements +* @base: pointer to data to sort sort?
Quoted 6 lines
lib/sort.c void sort(void *base, size_t num, size_t size, · line 285
Quoted 3 lines
lib/sort.c +3
-0+* @num: number of elements +* @size: size of each element +* @by: number of elements to rotate by Perhaps add (0 <= @by < @num) or something like that, and/or start the implementation with "if (num <= 1) return; if (by >= num) by %= num;"
The latter could be done unconditionally.
Quoted 10 lines
Quoted 10 lines
lib/sort.c +9
-0+* @swap_func: pointer to swap function or NULL +* +* Helper function to advance all the elements of a circular buffer by +* @by positions. +*/ +void rotate (void *base,size_t num,size_t size,size_t by, +swap_func_t swap_func) +{ +struct {
Quoted 8 lines
lib/sort.c void sort(void *base, size_t num, size_t size, · line 299
Quoted 5 lines
lib/sort.c +5
-0+size_t begin, end; + } arr[2] = { + { .begin = 0, .end = by - 1 }, + { .begin = by, .end = num - 1 }, + };I see you just copied-and-adapted, but I think the code would be much easier to read without all those plus/minus ones all over.
Now that I think about it, they can be just removed. In that case end refers to the element following end, rather than the last element.
Quoted 33 lines
Quoted 33 lines
lib/sort.c +32
-0+ swap_func =choose_swap_func (swap_func, base, size); + +#define CHUNK_SIZE (a) ((a)->end - (a)->begin + 1) + +/* Loop as long as we have out-of-place entries */ +while (CHUNK_SIZE (&arr[0 ]) &&CHUNK_SIZE (&arr[1 ])) { +size_t size0, i; + +/* +* Find the number of entries that can be arranged on this +* iteration. +*/ + size0 =min (CHUNK_SIZE (&arr[0 ]),CHUNK_SIZE (&arr[1 ])); + +/* Swap the entries in two parts of the array */ +for (i =0 ; i < size0; i++) { +void *a = base + size * (arr[0 ].begin + i); +void *b = base + size * (arr[1 ].begin + i); + +do_swap (a, b, size, swap_func); + } + +if (CHUNK_SIZE (&arr[0 ]) >CHUNK_SIZE (&arr[1 ])) { +/* The end of the first array remains unarranged */ + arr[0 ].begin += size0; + }else { +/* +* The first array is fully arranged so we proceed +* handling the next one. +*/ + arr[0 ].begin = arr[1 ].begin; + arr[0 ].end = arr[1 ].begin + size0 -1 ;
Quoted 8 lines
lib/sort.c void sort(void *base, size_t num, size_t size, · line 335
Quoted 3 lines
lib/sort.c +3
-0+ arr[1 ].begin += size0; + } + }Perhaps add a small self-test, it's not at all obvious how this works (perhaps it's some standard CS101 algorithm for rotating in-place, I don't know, but even then an implementation can have off-by-ones and corner cases).
I don't know, I wrote this to fix a bug in the ipu3-cio2 driver. ;-) The hardware, and so the arguments, were static. Nice to see it would be useful elsewhere almost as-is.
Quoted 11 lines
for (len = 1; len < 15; ++len) {
for (by = 0; by <= len; ++by) { for (i = 0; i < len; ++i) arr[i] = i; rotate(arr, len, sizeof(int), by); for (i = 0; i < len; ++i) if (arr[i] != (i + by) % len) error();}
}
Makes sense to add something like that.
After addressing the comments, for patches from 1 to 3:
Signature · 3 lines
Kind regards, Sakari Ailus
Re: [PATCH v1 2/3] lib/sort: Introduce rotate() to circular shift an array of elements
Quoted 11 lines · Sakari Ailus
Hi Rasmus, Andy,
Quoted 6 lines
Quoted 3 lines
+ * @num: number of elements
+ * @size: size of each element
+ * @by: number of elements to rotate byPerhaps add (0 <= @by < @num) or something like that, and/or start the implementation with "if (num <= 1) return; if (by >= num) by %= num;"
The latter could be done unconditionally.
Yes (provided num is tested at least for being non-zero first, but then it's mostly free to check <= 1 instead), but in the vast majority of cases the caller would pass a sane value of by, and an unconditional %= would thus waste 100+ clock cycles for nothing.
Quoted 10 lines
Quoted 9 lines
lib/sort.c void sort(void *base, size_t num, size_t size, · line 299
Quoted 6 lines
lib/sort.c +6
-0+struct { +size_t begin, end; + } arr[2 ] = { + { .begin =0 , .end = by -1 }, + { .begin = by, .end = num -1 }, + };I see you just copied-and-adapted, but I think the code would be much easier to read without all those plus/minus ones all over.
Quoted 2 lines
Now that I think about it, they can be just removed. In that case end refers to the element following end, rather than the last element.
Yes, as we almost always do array indexing in C... the math simply ends up coming out more naturally that way in the majority of cases.
Quoted 8 lines
Quoted 4 lines
Perhaps add a small self-test, it's not at all obvious how this works (perhaps it's some standard CS101 algorithm for rotating in-place, I don't know, but even then an implementation can have off-by-ones and corner cases).
I don't know, I wrote this to fix a bug in the ipu3-cio2 driver. ;-) The hardware, and so the arguments, were static. Nice to see it would be useful elsewhere almost as-is.
Well, Andy hasn't actually shown that it would be useful anywhere else. I think I'd like to see another user. 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.
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.
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().
Rasmus
Re: [PATCH v1 2/3] lib/sort: Introduce rotate() to circular shift an array of elements
Quoted 1 line · Rasmus Villemoes
On 25/08/2021 10.08, Sakari Ailus wrote:
...
Quoted 2 lines
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.
Quoted 4 lines
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.
Quoted 4 lines
Especially since it can affect code generation of the much more important (at least, has many more users)
sort()function - thedo_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?
Quoted 7 lines
There's another slightly simpler way to implement
rotate(), which might end up having more users (though I can't find any currently): Add areverse()helper, thenrotate()can be done asreverse(a, 0, n);reverse(a, 0, k);reverse(a, k, n-k);. If my math is right, the current suggestedrotate()ends up doing n-gcd(n,k) swaps, while the implementation in terms of areverse()would do n-1 if either n or k is odd, otherwise n, calls toswap().
Interesting idea. And this, btw, may have more users per se.
Signature · 2 lines
With Best Regards, Andy Shevchenko
PATCH 3/3 media: ipu3-cio2: Replace custom implementation of rotate()
In reply to Andy Shevchenkorotate() is more efficient than custom implementation. Replace the latter by the former.
---
This should be a copy'n'paste of the algorithm with a slight difference that it should copy by 4 or 8 bytes at a time. Nonetheless it has to be tested. Hence, RFT. (Obviously no hurry with this, we are close to release)
drivers/media/pci/intel/ipu3/ipu3-cio2-main.c | 59 ++----------------- 1 file changed, 5 insertions(+), 54 deletions(-)
drivers/media/pci/intel/ipu3/ipu3-cio2-main.c +5 -54
@@ -21,6 +21,7 @@#include <linux/pfn.h> #include <linux/pm_runtime.h> #include <linux/property.h> +#include <linux/sort.h> #include <linux/vmalloc.h> #include <media/v4l2-ctrls.h> #include <media/v4l2-device.h>
@@ -1877,56 +1878,6 @@ static int __maybe_unused cio2_runtime_resume(struct device *dev)return 0 ; } -/* -* Helper function to advance all the elements of a circular buffer by "start" -* positions -*/ -static void arrange (void *ptr,size_t elem_size,size_t elems,size_t start) -{ -struct { -size_t begin, end; - } arr[2 ] = { - {0 , start -1 }, - { start, elems -1 }, - }; - -#define CHUNK_SIZE (a) ((a)->end - (a)->begin + 1) - -/* Loop as long as we have out-of-place entries */ -while (CHUNK_SIZE (&arr[0 ]) &&CHUNK_SIZE (&arr[1 ])) { -size_t size0, i; - -/* -* Find the number of entries that can be arranged on this -* iteration. -*/ - size0 =min (CHUNK_SIZE (&arr[0 ]),CHUNK_SIZE (&arr[1 ])); - -/* Swap the entries in two parts of the array. */ -for (i =0 ; i < size0; i++) { -u8 *d = ptr + elem_size * (arr[1 ].begin + i); -u8 *s = ptr + elem_size * (arr[0 ].begin + i); -size_t j; - -for (j =0 ; j < elem_size; j++) -swap (d[j], s[j]); - } - -if (CHUNK_SIZE (&arr[0 ]) >CHUNK_SIZE (&arr[1 ])) { -/* The end of the first array remains unarranged. */ - arr[0 ].begin += size0; - }else { -/* -* The first array is fully arranged so we proceed -* handling the next one. -*/ - arr[0 ].begin = arr[1 ].begin; - arr[0 ].end = arr[1 ].begin + size0 -1 ; - arr[1 ].begin += size0; - } - } -} -static void cio2_fbpt_rearrange (struct cio2_device *cio2,struct cio2_queue *q) {unsigned int i, j;
@@ -1940,10 +1891,10 @@ static void cio2_fbpt_rearrange(struct cio2_device *cio2, struct cio2_queue *q)return ;if (j) { -arrange (q->fbpt,sizeof (struct cio2_fbpt_entry ) *CIO2_MAX_LOPS , -CIO2_MAX_BUFFERS , j); -arrange (q->bufs,sizeof (struct cio2_buffer *), -CIO2_MAX_BUFFERS , j); +rotate (q->fbpt,sizeof (struct cio2_fbpt_entry ) *CIO2_MAX_LOPS , +CIO2_MAX_BUFFERS , j,NULL ); +rotate (q->bufs,sizeof (struct cio2_buffer *), +CIO2_MAX_BUFFERS , j,NULL ); }/*
Signature · 1 line
2.32.0
Sakari Ailus
maintainerHi Andy,
Thanks for the set.
Quoted 13 lines · Andy Shevchenko
In some new code we may need the same functionality as provided by newly introduced
choose_swap_func()helper.Signed-off-by Andy Shevchenko <[email protected]>--- lib/sort.c | 21 +++++++++++++-------- 1 file changed, 13 insertions(+), 8 deletions(-)lib/sort.c +0
-0
lib/sort.c static int do_cmp(const void *a, const void *b, cmp_r_func_t cmp, const void *pr · line 154
Quoted 4 lines
lib/sort.c +1
-0@@ -151,6 +151,18 @@ static int do_cmp(const void *a, const void *b, cmp_r_func_t cmp, const void *prreturn cmp (a, b, priv); } +static swap_func_t choose_swap_func (swap_func_t swap_func,void *base,size_t size)
Over 80, please wrap.
lib/sort.c static int do_cmp(const void *a, const void *b, cmp_r_func_t cmp, const void *pr · line 162
Quoted 8 lines
lib/sort.c +8
-0+{ +if (swap_func) +return swap_func; + +if (is_aligned (base, size,8 )) +return SWAP_WORDS_64 ; +if (is_aligned (base, size,4 )) +return SWAP_WORDS_32 ;
A newline here would be nice.
Quoted 22 lines
lib/sort.c +4
-8+return SWAP_BYTES ; +} +/** * parent - given the offset of the child, find the offset of the parent. * @i: the offset of the heap element whose parent is sought. Non-zero. @@ -208,14 +220,7 @@ void sort_r(void *base, size_t num, size_t size,if (!a)/* num < 2 || size == 0 */ return ; -if (!swap_func) { -if (is_aligned (base, size,8 )) - swap_func =SWAP_WORDS_64 ; -else if (is_aligned (base, size,4 )) - swap_func =SWAP_WORDS_32 ; -else - swap_func =SWAP_BYTES ; - } + swap_func =choose_swap_func (swap_func, base, size);/* * Loop invariants:
Signature · 3 lines
Kind regards, Sakari Ailus