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

Groups > linux.kernel > #1730349 > unrolled thread

[PATCH] tipc: Use bsearch library function

Back to article view | Back to linux.kernel

Contents

  [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

#1730349 — [PATCH] tipc: Use bsearch library function

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

[toc] | [next] | [standalone]

#1730563

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.

[toc] | [prev] | [next] | [standalone]

#1730773

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

[toc] | [prev] | [next] | [standalone]

#1733223 — [PATCH V2] tipc: Use bsearch library function

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

[toc] | [prev] | [next] | [standalone]

#1733226 — Re: [PATCH V2] tipc: Use bsearch library function

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

[toc] | [prev] | [next] | [standalone]

#1733228 — Re: [PATCH V2] tipc: Use bsearch library function

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

[toc] | [prev] | [next] | [standalone]

#1733231 — Re: [PATCH V2] tipc: Use bsearch library function

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

[toc] | [prev] | [next] | [standalone]

#1733235 — Re: [PATCH V2] tipc: Use bsearch library function

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.

[toc] | [prev] | [next] | [standalone]

#1733237 — 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.

[toc] | [prev] | [next] | [standalone]

#1733473 — Re: [PATCH V2] tipc: Use bsearch library function

[Multipart message — attachments visible in raw view] — view raw

> 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

[toc] | [prev] | [next] | [standalone]

#1733537 — 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.

[toc] | [prev] | [next] | [standalone]

#1733239 — Re: [PATCH V2] tipc: Use bsearch library function

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.

> 

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web