Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1733228

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

Show all headers | View raw

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@m3y3r.de>
> 
> Acked-by: Ying Xue <ying.xue@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?

> > 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);
> >  }
> >  
> >  /**
> > 

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH] tipc: Use bsearch library function Thomas Meyer <thomas@m3y3r.de> - 2017-09-11 15:20 +0200
  Re: [PATCH] tipc: Use bsearch library function David Miller <davem@davemloft.net> - 2017-09-11 23:40 +0200
    RE: [PATCH] tipc: Use bsearch library function David Laight <David.Laight@ACULAB.COM> - 2017-09-12 11:30 +0200
    [PATCH V2] tipc: Use bsearch library function Thomas Meyer <thomas@m3y3r.de> - 2017-09-16 10:00 +0200
      Re: [PATCH V2] tipc: Use bsearch library function Ying Xue <ying.xue@windriver.com> - 2017-09-16 11:10 +0200
        Re: [PATCH V2] tipc: Use bsearch library function Joe Perches <joe@perches.com> - 2017-09-16 11:30 +0200
          Re: [PATCH V2] tipc: Use bsearch library function Ying Xue <ying.xue@windriver.com> - 2017-09-16 11:40 +0200
            Re: [PATCH V2] tipc: Use bsearch library function Joe Perches <joe@perches.com> - 2017-09-16 12:00 +0200
              Re: [PATCH V2] tipc: Use bsearch library function Joe Perches <joe@perches.com> - 2017-09-16 12:20 +0200
                Re: [PATCH V2] tipc: Use bsearch library function Thomas Meyer <thomas@m3y3r.de> - 2017-09-17 17:10 +0200
                Re: [PATCH V2] tipc: Use bsearch library function Joe Perches <joe@perches.com> - 2017-09-17 23:20 +0200
              Re: [PATCH V2] tipc: Use bsearch library function Ying Xue <ying.xue@windriver.com> - 2017-09-16 12:20 +0200

csiph-web