RE: [PATCH V2] tipc: Use bsearch library function

From: Jon Maloy
Date: Sat Sep 16 2017 - 09:35:41 EST




> -----Original Message-----
> From: netdev-owner@xxxxxxxxxxxxxxx [mailto:netdev-
> owner@xxxxxxxxxxxxxxx] On Behalf Of Joe Perches
> Sent: Saturday, September 16, 2017 06:18
> To: Ying Xue <ying.xue@xxxxxxxxxxxxx>; Thomas Meyer
> <thomas@xxxxxxxx>; Jon Maloy <jon.maloy@xxxxxxxxxxxx>;
> netdev@xxxxxxxxxxxxxxx; tipc-discussion@xxxxxxxxxxxxxxxxxxxxx; linux-
> kernel@xxxxxxxxxxxxxxx; davem@xxxxxxxxxxxxx
> Subject: Re: [PATCH V2] tipc: Use bsearch library function
>
> On Sat, 2017-09-16 at 18:10 +0800, Ying Xue wrote:
> > On 09/16/2017 05:58 PM, Joe Perches wrote:
> > > On Sat, 2017-09-16 at 17:36 +0800, Ying Xue wrote:
> > > > 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 <thomas@xxxxxxxx>
> > > > > >
> > > > > > Acked-by: Ying Xue <ying.xue@xxxxxxxxxxxxx>
> > > > >
> > > > > 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.
> > >
> > > Comparison via a function pointer in bsearch is slower than direct
> > > code without the function call overhead.
> > >
> >
> > Right, but probably we can tolerate the slight sacrifice here.
>
> What part of "very time critical" have you verified and benchmarked as
> inconsequential?
>
> Please post your results.

I agree with Joe here. This change does not simplify anything, it does not reduce the amount of code, plus that it introduce an unnecessary outline call in a place where we have every reason to let the compiler do its optimization job properly.

///jon