Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Subject: Re: [PATCH 5/5] lib/list_sort: Optimize number of calls to comparison
 function
To:     George Spelvin <lkml@sdf.org>, linux-kernel@vger.kernel.org
Cc:     akpm@linux-foundation.org, andriy.shevchenko@linux.intel.com,
        daniel.wagner@siemens.com, dchinner@redhat.com,
        don.mullis@gmail.com, geert@linux-m68k.org, st5pub@yandex.ru
References: <cover.1552097842.git.lkml@sdf.org>
 <b36187f091acc1b3a8fc1fc3e9dbb6eca56231a9.1552097842.git.lkml@sdf.org>
 <dd8924c1-07a9-4317-bfa8-23271b138a62@rasmusvillemoes.dk>
 <201903140158.x2E1wgFQ018649@sdf.org>
From:   Rasmus Villemoes <linux@rasmusvillemoes.dk>
Message-ID: <ee4312b3-ed26-2a78-de26-1907c38a5e4b@rasmusvillemoes.dk>
Date:   Sat, 22 Jun 2019 01:12:01 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.7.0
MIME-Version: 1.0
In-Reply-To: <201903140158.x2E1wgFQ018649@sdf.org>
Content-Type: text/plain; charset=windows-1252
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

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