Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751278AbdIPJi1 (ORCPT ); Sat, 16 Sep 2017 05:38:27 -0400 Received: from mail5.windriver.com ([192.103.53.11]:50160 "EHLO mail5.wrs.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751050AbdIPJi0 (ORCPT ); Sat, 16 Sep 2017 05:38:26 -0400 Subject: Re: [PATCH V2] tipc: Use bsearch library function To: Joe Perches , Thomas Meyer , , , , , References: <20170911.143025.555018840006192902.davem@davemloft.net> <20170916075036.28676-1-thomas@m3y3r.de> <16128f5e-66ff-b6ec-c0e1-74ea08c212b0@windriver.com> <1505553970.16316.1.camel@perches.com> From: Ying Xue Message-ID: <64ee51ce-eb7e-ac1c-56a9-9481f6f80b35@windriver.com> Date: Sat, 16 Sep 2017 17:36:33 +0800 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.2.1 MIME-Version: 1.0 In-Reply-To: <1505553970.16316.1.camel@perches.com> Content-Type: text/plain; charset="utf-8" Content-Language: en-US Content-Transfer-Encoding: 7bit X-Originating-IP: [128.224.155.110] Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2613 Lines: 87 On 09/16/2017 05:26 PM, Joe Perches wrote: > On Sat, 2017-09-16 at 17:02 +0800, Ying Xue wrote: >> On 09/16/2017 03:50 PM, Thomas Meyer wrote: >>> Use common library function rather than explicitly coding >>> some variant of it yourself. >>> >>> Signed-off-by: Thomas Meyer >> >> Acked-by: Ying Xue > > Are you sure you want to do this? > > Note the comment above nameseq_find_subseq > > * Very time-critical, so binary searches through sub-sequence array. > > What impact does this change have on performance? Sorry, I couldn't see any essential difference between this new implementation and the original one except that the former tries to use the library function - bsearch() to replace the original binary search algorithm implemented in TIPC itself. Therefore, I don't think the change will have a big impact on performance. If I miss something, please let me know. Thanks, Ying > >>> diff --git a/net/tipc/name_table.c b/net/tipc/name_table.c >>> index bd0aac87b41a..eeb4d7a13de2 100644 >>> --- a/net/tipc/name_table.c >>> +++ b/net/tipc/name_table.c >>> @@ -44,6 +44,7 @@ >>> #include "addr.h" >>> #include "node.h" >>> #include >>> +#include >>> >>> #define TIPC_NAMETBL_SIZE 1024 /* must be a power of 2 */ >>> >>> @@ -168,6 +169,18 @@ static struct name_seq *tipc_nameseq_create(u32 type, struct hlist_head *seq_hea >>> return nseq; >>> } >>> >>> +static int nameseq_find_subseq_cmp(const void *key, const void *elt) >>> +{ >>> + struct sub_seq *sseq = (struct sub_seq *)elt; >>> + u32 instance = *(u32 *)key; >>> + >>> + if (instance < sseq->lower) >>> + return -1; >>> + else if (instance > sseq->upper) >>> + return 1; >>> + return 0; >>> +} >>> + >>> /** >>> * nameseq_find_subseq - find sub-sequence (if any) matching a name instance >>> * >>> @@ -176,21 +189,8 @@ static struct name_seq *tipc_nameseq_create(u32 type, struct hlist_head *seq_hea >>> static struct sub_seq *nameseq_find_subseq(struct name_seq *nseq, >>> u32 instance) >>> { >>> - struct sub_seq *sseqs = nseq->sseqs; >>> - int low = 0; >>> - int high = nseq->first_free - 1; >>> - int mid; >>> - >>> - while (low <= high) { >>> - mid = (low + high) / 2; >>> - if (instance < sseqs[mid].lower) >>> - high = mid - 1; >>> - else if (instance > sseqs[mid].upper) >>> - low = mid + 1; >>> - else >>> - return &sseqs[mid]; >>> - } >>> - return NULL; >>> + return bsearch(&instance, nseq->sseqs, nseq->first_free, >>> + sizeof(struct sub_seq), nameseq_find_subseq_cmp); >>> } >>> >>> /** >>> >