Messages in this thread | | | Subject | Re: [PATCH 5/5] lib/list_sort: Optimize number of calls to comparison function | From | Rasmus Villemoes <> | Date | Sat, 22 Jun 2019 01:12:01 +0200 |
| |
On 14/03/2019 02.58, George Spelvin wrote: > On Thu, 14 Mar 2019 at 00:28:16 +0100, Rasmus Villemoes wrote:
>> Similarly one could do a SORT_SIMPLE_CMP() for when sorting an array of >> structs according to a single numeric member. That sort is not stable, >> so the comparison functions would have to do a full -1,0,1 return, of >> course, but we'd still avoid indirect calls. > > Actually, while some sorts (notably fat-pivot quicksort) require > a 3-way return to avoid O(n^2) performance, heapsort is just fine > with a boolean return value.
Hi George
So I tried starting to implement this, and the timing results look promising. However, currently I'm doing
(*(u32*)ka > *(u32*)kb) - (*(u32*)ka < *(u32*)kb);
in my do_cmp. Both existing invocations of the comparison function in sort.c compare its return value >= 0, which is always true if I just return the boolean (*(u32*)ka > *(u32*)kb). So it seems the algorithm would have to be changed to allow the cmp function to return a bool. Perhaps it's as simple as changing the two >= to >, but can I get you to check that that would be ok? (Quick testing seems to suggest so, but it's possible there are some corner cases where it would break.)
Thanks, Rasmus
| |