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

> > 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 <net/genetlink.h>
> > +#include <linux/bsearch.h>
> >  
> >  #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);
> >  }
> >  
> >  /**
> >