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

[Jon Maloy]

> -Original Message-
> From: netdev-ow...@vger.kernel.org [mailto:netdev-
> ow...@vger.kernel.org] On Behalf Of Joe Perches
> Sent: Sunday, September 17, 2017 23:15
> To: Jon Maloy <jon.ma...@ericsson.com>; Thomas Meyer
> <tho...@m3y3r.de>
> Cc: Ying Xue <ying@windriver.com>; netdev@vger.kernel.org; tipc-
> discuss...@lists.sourceforge.net; linux-ker...@vger.kernel.org;
> da...@davemloft.net
> Subject: Re: [PATCH V2] tipc: Use bsearch library function
> 
> On Sun, 2017-09-17 at 16:27 +, Jon Maloy wrote:
> > > -Original Message-
> > > From: Thomas Meyer [mailto:tho...@m3y3r.de]
> []
> > > What about the other binary search implementation in the same file?
> > > Should I try to convert it it will it get NAKed for performance reasons 
> > > too?
> >
> > The searches for inserting and removing publications is less time
> > critical, so that would be ok with me.
> > If you have any more general interest in improving the code in this
> > file (which is needed) it would also be appreciated.
> 
> Perhaps using an rbtree would be an improvement.

Not a bad idea. It would probably reduce the code amount, possibly at the 
expense of cache hit rate during the binary lookup.
It is worth looking into.

///jon

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

[Joe Perches]

On Sun, 2017-09-17 at 16:27 +, Jon Maloy wrote:
> > -Original Message-
> > From: Thomas Meyer [mailto:tho...@m3y3r.de]
[]
> > What about the other binary search implementation in the same file? Should
> > I try to convert it it will it get NAKed for performance reasons too?
> 
> The searches for inserting and removing publications is less time critical,
> so that would be ok with me.
> If you have any more general interest in improving the code in this file
> (which is needed) it would also be appreciated.

Perhaps using an rbtree would be an improvement.

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

[Jon Maloy]

> -Original Message-
> From: Thomas Meyer [mailto:tho...@m3y3r.de]
> Sent: Sunday, September 17, 2017 11:00
> To: Jon Maloy <jon.ma...@ericsson.com>
> Cc: Joe Perches <j...@perches.com>; Ying Xue <ying@windriver.com>;
> netdev@vger.kernel.org; tipc-discuss...@lists.sourceforge.net; linux-
> ker...@vger.kernel.org; da...@davemloft.net
> Subject: Re: [PATCH V2] tipc: Use bsearch library function
> 
> 
> > Am 16.09.2017 um 15:20 schrieb Jon Maloy <jon.ma...@ericsson.com>.
> >>
> >> 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.
> 
> Hi,
> 
> Okay, should I prepare some performance numbers or do we NAK this
> change?
> What about the other binary search implementation in the same file? Should
> I try to convert it it will it get NAKed for performance reasons too?

The searches for inserting and removing publications is less time critical,
so that would be ok with me.
If you have any more general interest in improving the code in this file
(which is needed) it would also be appreciated.

BR
///jon


> 
> With kind regards
> Thomas


smime.p7s
Description: S/MIME cryptographic signature

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

[Thomas Meyer]

> Am 16.09.2017 um 15:20 schrieb Jon Maloy .
>> 
>> 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.

Hi,

Okay, should I prepare some performance numbers or do we NAK this change?
What about the other binary search implementation in the same file? Should I 
try to convert it it will it get NAKed for performance reasons too?

With kind regards
Thomas

smime.p7s
Description: S/MIME cryptographic signature

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

[Jon Maloy]

> -Original Message-
> From: netdev-ow...@vger.kernel.org [mailto:netdev-
> ow...@vger.kernel.org] On Behalf Of Joe Perches
> Sent: Saturday, September 16, 2017 06:18
> To: Ying Xue <ying@windriver.com>; Thomas Meyer
> <tho...@m3y3r.de>; Jon Maloy <jon.ma...@ericsson.com>;
> netdev@vger.kernel.org; tipc-discuss...@lists.sourceforge.net; linux-
> ker...@vger.kernel.org; da...@davemloft.net
> 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 <tho...@m3y3r.de>
> > > > > >
> > > > > > Acked-by: Ying Xue <ying@windriver.com>
> > > > >
> > > > > 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

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

[Joe Perches]

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 
> > > > > 
> > > > > 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.
> > 
> > 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.

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

[Ying Xue]

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 

 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.
> 
> 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.

> 

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

[Joe Perches]

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 
> > > 
> > > 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.

Comparison via a function pointer in bsearch is slower
than direct code without the function call overhead.

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

[Ying Xue]

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 [mid];
>>> -   }
>>> -   return NULL;
>>> +   return bsearch(, nseq->sseqs, nseq->first_free,
>>> +  sizeof(struct sub_seq), nameseq_find_subseq_cmp);
>>>  }
>>>  
>>>  /**
>>>
> 

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

[Joe Perches]

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?

> > 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 [mid];
> > -   }
> > -   return NULL;
> > +   return bsearch(, nseq->sseqs, nseq->first_free,
> > +  sizeof(struct sub_seq), nameseq_find_subseq_cmp);
> >  }
> >  
> >  /**
> > 

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

[Ying Xue]

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 

> ---
>  net/tipc/name_table.c | 30 +++---
>  1 file changed, 15 insertions(+), 15 deletions(-)
> 
> V2: Coding style
> 
> 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 [mid];
> - }
> - return NULL;
> + return bsearch(, nseq->sseqs, nseq->first_free,
> +sizeof(struct sub_seq), nameseq_find_subseq_cmp);
>  }
>  
>  /**
>