Use common library function rather than explicitly coding
some variant of it yourself.
Signed-off-by: Thomas Meyer <[email protected]>
---
net/tipc/name_table.c | 30 +++++++++++++++---------------
1 file changed, 15 insertions(+), 15 deletions(-)
diff --git a/net/tipc/name_table.c b/net/tipc/name_table.c
index bd0aac87b41a..345454106390 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)
+{
+ u32 instance = *(u32 *)key;
+ struct sub_seq *sseq = (struct sub_seq *)elt;
+
+ 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);
}
/**
--
2.11.0
From: Thomas Meyer <[email protected]>
Date: Sat, 9 Sep 2017 05:18:19 +0200
> @@ -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)
> +{
> + u32 instance = *(u32 *)key;
> + struct sub_seq *sseq = (struct sub_seq *)elt;
Please order local variables from longest to shortest (ie. reverse
christmas tree).
Thank you.
From: David Miller
> Sent: 11 September 2017 22:30
> From: Thomas Meyer <[email protected]>
> Date: Sat, 9 Sep 2017 05:18:19 +0200
>
> > @@ -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)
> > +{
> > + u32 instance = *(u32 *)key;
> > + struct sub_seq *sseq = (struct sub_seq *)elt;
>
> Please order local variables from longest to shortest (ie. reverse
> christmas tree).
You probably just need to remove the unnecessary cast of 'void *'.
Although adding the 'const' qualifier will make it wrong again.
You probably ought to make the 'key' a structure - even if it only
contains a single u32.
Casting pointers to numeric types is often wrong.
David
Use common library function rather than explicitly coding
some variant of it yourself.
Signed-off-by: Thomas Meyer <[email protected]>
---
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);
}
/**
--
2.11.0
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 <[email protected]>
Acked-by: Ying Xue <[email protected]>
> ---
> 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 <[email protected]>
>
> Acked-by: Ying Xue <[email protected]>
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 <[email protected]>
>>
>> Acked-by: Ying Xue <[email protected]>
>
> 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 <[email protected]>
> > >
> > > Acked-by: Ying Xue <[email protected]>
> >
> > 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 <[email protected]>
>>>>
>>>> Acked-by: Ying Xue <[email protected]>
>>>
>>> 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 <[email protected]>
> > > > >
> > > > > Acked-by: Ying Xue <[email protected]>
> > > >
> > > > 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: [email protected] [mailto:netdev-
> [email protected]] On Behalf Of Joe Perches
> Sent: Saturday, September 16, 2017 06:18
> To: Ying Xue <[email protected]>; Thomas Meyer
> <[email protected]>; Jon Maloy <[email protected]>;
> [email protected]; [email protected]; linux-
> [email protected]; [email protected]
> 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 <[email protected]>
> > > > > >
> > > > > > Acked-by: Ying Xue <[email protected]>
> > > > >
> > > > > 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 <[email protected]>.
>>
>> 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:[email protected]]
> Sent: Sunday, September 17, 2017 11:00
> To: Jon Maloy <[email protected]>
> Cc: Joe Perches <[email protected]>; Ying Xue <[email protected]>;
> [email protected]; [email protected]; linux-
> [email protected]; [email protected]
> Subject: Re: [PATCH V2] tipc: Use bsearch library function
>
>
> > Am 16.09.2017 um 15:20 schrieb Jon Maloy <[email protected]>.
> >>
> >> 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:[email protected]]
[]
> > 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: [email protected] [mailto:netdev-
> [email protected]] On Behalf Of Joe Perches
> Sent: Sunday, September 17, 2017 23:15
> To: Jon Maloy <[email protected]>; Thomas Meyer
> <[email protected]>
> Cc: Ying Xue <[email protected]>; [email protected]; tipc-
> [email protected]; [email protected];
> [email protected]
> 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:[email protected]]
> []
> > > 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