| Message ID | 20170916075036.28676-1-thomas@m3y3r.de |
|---|---|
| State | Changes Requested, archived |
| Delegated to: | David Miller |
| Headers | show |
| Series | [V2] tipc: Use bsearch library function | expand |
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> > --- > 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 <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); > } > > /** >
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); > > } > > > > /** > >
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@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? 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 <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); >>> } >>> >>> /** >>> >
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@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? > > 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.
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@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? >> >> 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. >
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@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? > > > > > > 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.
> -----Original Message----- > From: netdev-owner@vger.kernel.org [mailto:netdev- > owner@vger.kernel.org] On Behalf Of Joe Perches > Sent: Saturday, September 16, 2017 06:18 > To: Ying Xue <ying.xue@windriver.com>; Thomas Meyer > <thomas@m3y3r.de>; Jon Maloy <jon.maloy@ericsson.com>; > netdev@vger.kernel.org; tipc-discussion@lists.sourceforge.net; linux- > kernel@vger.kernel.org; davem@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 <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? > > > > > > > > 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
> Am 16.09.2017 um 15:20 schrieb Jon Maloy <jon.maloy@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? With kind regards Thomas
> -----Original Message----- > From: Thomas Meyer [mailto:thomas@m3y3r.de] > Sent: Sunday, September 17, 2017 11:00 > To: Jon Maloy <jon.maloy@ericsson.com> > Cc: Joe Perches <joe@perches.com>; Ying Xue <ying.xue@windriver.com>; > netdev@vger.kernel.org; tipc-discussion@lists.sourceforge.net; linux- > kernel@vger.kernel.org; davem@davemloft.net > Subject: Re: [PATCH V2] tipc: Use bsearch library function > > > > Am 16.09.2017 um 15:20 schrieb Jon Maloy <jon.maloy@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
On Sun, 2017-09-17 at 16:27 +0000, Jon Maloy wrote: > > -----Original Message----- > > From: Thomas Meyer [mailto:thomas@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.
> -----Original Message----- > From: netdev-owner@vger.kernel.org [mailto:netdev- > owner@vger.kernel.org] On Behalf Of Joe Perches > Sent: Sunday, September 17, 2017 23:15 > To: Jon Maloy <jon.maloy@ericsson.com>; Thomas Meyer > <thomas@m3y3r.de> > Cc: Ying Xue <ying.xue@windriver.com>; netdev@vger.kernel.org; tipc- > discussion@lists.sourceforge.net; linux-kernel@vger.kernel.org; > davem@davemloft.net > Subject: Re: [PATCH V2] tipc: Use bsearch library function > > On Sun, 2017-09-17 at 16:27 +0000, Jon Maloy wrote: > > > -----Original Message----- > > > From: Thomas Meyer [mailto:thomas@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
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); } /**
Use common library function rather than explicitly coding some variant of it yourself. Signed-off-by: Thomas Meyer <thomas@m3y3r.de> --- net/tipc/name_table.c | 30 +++++++++++++++--------------- 1 file changed, 15 insertions(+), 15 deletions(-) V2: Coding style