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

From: Joe Perches
Date: Sat Sep 16 2017 - 05:26:35 EST


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