[PATCH] tipc: Use bsearch library function

[PATCH] tipc: Use bsearch library function

[Thomas Meyer]

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(-)

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

Re: [PATCH] tipc: Use bsearch library function

[David Miller]

From: Thomas Meyer <thomas@m3y3r.de>
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.

RE: [PATCH] tipc: Use bsearch library function

[David Laight]

From: David Miller
> Sent: 11 September 2017 22:30
> From: Thomas Meyer <thomas@m3y3r.de>
> 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

RE: [PATCH] tipc: Use bsearch library function

[David Laight]

From: David Miller
> Sent: 11 September 2017 22:30
> From: Thomas Meyer <thomas@m3y3r.de>
> 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

[PATCH V2] tipc: Use bsearch library function

[Thomas Meyer]

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

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

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

[Ying Xue]

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

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

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

[Ying Xue]

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

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

[Joe Perches]

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.

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

[Ying Xue]

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.

> 

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

[Joe Perches]

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.

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

[Jon Maloy]

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

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

[Jon Maloy]

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

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

[Thomas Meyer]

[-- Attachment #1: Type: text/plain, Size: 717 bytes --]


> 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

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 5334 bytes --]

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

[Thomas Meyer]

[-- Attachment #1: Type: text/plain, Size: 717 bytes --]


> 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

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 5334 bytes --]

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

[Jon Maloy]

[-- Attachment #1: Type: text/plain, Size: 1396 bytes --]



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

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 6242 bytes --]

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

[Jon Maloy]

[-- Attachment #1: Type: text/plain, Size: 1396 bytes --]



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

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 6242 bytes --]

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

[Joe Perches]

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.

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

[Joe Perches]

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.

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

[Jon Maloy]

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

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

[Jon Maloy]

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